alloctree.c

C++ 编写的EROS RTOS

  register uint32_t newMask;
  
  if (treeKey == tree->lastRemove->value)
    /*  note that if tree->lastRemove == TREE_NIL, lastInsert->value
     * will never match treeKey, so tree_find will be run..
     */
    theNode = tree->lastRemove;
  else
    theNode = tree_find(tree->root,treeKey);

  assert(theNode != NULL);
  
  /* See if the OID in question is in the tree: */
  if (theNode == TREE_NIL) {
    DEBUG(dealloc)
      kdprintf(KR_OSTREAM,
	       "allocTree_removeOID passed OID 0x"DW_HEX", "
	       "which does not have a treenode\n",
	       DW_HEX_ARG(oid));
    return 0; /* RETURN "object not within tree" */
  }

  tree->lastRemove = theNode; /* store it for next time */

  curMap = theNode->body.map[offset];
  
  if (curMap == 0) { /* empty */
    DEBUG(dealloc)
      kdprintf(KR_OSTREAM,
	       "allocTree_removeOID passed OID 0x"DW_HEX", "
	       "whose frame is not part of this tree\n",
	       DW_HEX_ARG(oid));
    return 0; /* RETURN "object not within tree" */
  }
#ifndef TREE_NO_TYPES
#ifndef NDEBUG
  if (theNode->body.type[offset] != type) {
    debug_print_node(theNode);
    kpanic(KR_OSTREAM,
	   "allocTree_removeOID passed OID 0x"DW_HEX", whose "
	   "type (%s)is not the same as the one passed in (%s)\n",
	   DW_HEX_ARG(oid),
	   theNode->body.type[offset],
	   type);
    return 0; /* RETURN "object has wrong type" */
  }
#endif
#endif

  newMask = (1 << objNum);
  
  if ( (curMap & newMask) != newMask) {
    DEBUG(dealloc)
      kdprintf(KR_OSTREAM,
	       "allocTree_removeOID passed OID 0x"DW_HEX", "
	       "who is not marked allocated in its map (0x%04x)\n",
	       DW_HEX_ARG(oid),
	       curMap);
    return 0; /* RETURN "object not allocated" */
  }

  DEBUG(dealloc)
    kprintf(KR_OSTREAM,
	    "Deallocating %s 0x"DW_HEX", whose frame has "
	     "map 0x%04x (before)\n",
	    type_name(type),
	    DW_HEX_ARG(oid),
	    curMap);

  curMap &= ~newMask;
  
  if (curMap == 0) {
    /* this part of the node is completele deallocated -- check if the
     * whole node is empty, too, and if so, delete it from the tree.
     */
    uint32_t x;

    DEBUG(dealloc)
      kprintf(KR_OSTREAM,
	      "Frame empty -- checking if everything is empty\n");

    /* invalidate the offset */
    theNode->body.map[offset] = 0u; 
#ifndef TREE_NO_TYPES
    theNode->body.type[offset] = SBOT_INVALID;
#endif

    /* check if we are empty */
    x = SB_FRAMES_PER_TREENODE;

    while (x > 0) {
      x--;
      if (theNode->body.map[x] != 0u) {
	x = SB_FRAMES_PER_TREENODE;
	break; /* BREAK "Nope, not empty yet!" */
      }
    }
    
    if (x == 0) {
      /* completely empty */

      DEBUG(dealloc)
	kprintf(KR_OSTREAM,
		"TREENODE empty -- deleting it\n");

      _allocTree_clearCachedInfo(tree); /* we are going to be deleting*/

      /* remove the node */
      tree->root = tree_remove(tree->root, theNode);

      /* since object pointed to by lastRemove is now ancient history,
	 nil that out: */
      tree->lastRemove = TREE_NIL;

      /* It may happen (has happened!) that this tree node we are
	 about to delete is also the most recently *inserted* node.
	 If so, we must nil that out too lest a deleted node get stuck
	 into the tree somehow. */
      if (tree->lastInsert == theNode)
	tree->lastInsert = TREE_NIL;
      
      /* and delete it */
      tree_deleteNode(theNode);
    }

    /* release the now empty frame */
    DEBUG(limit)
      kprintf(KR_OSTREAM,
	      "allocTree_removeOID unreserving frame for oid "
	      DW_HEX"\n",
	      DW_HEX_ARG(oid));
	      
    bank_UnreserveFrames(bank, 1);
    if (type == OT_Node)
      ob_ReleaseNodeFrame(bank, EROS_FRAME_FROM_OID(oid));
    else
      ob_ReleasePageFrame(bank, EROS_FRAME_FROM_OID(oid));
  } else {
    theNode->body.map[offset] = curMap; /*
					 * put in the new map
					 */
    DEBUG(dealloc)
      kprintf(KR_OSTREAM,
	      "Wrote new map 0x%04x\n",curMap);
  }

  return 1; /* RETURN "success" */
}

uint32_t
allocTree_IncrementalDestroy(TREE *toDie, OID *retFrame)
{
  if (toDie->root == TREE_NIL) {
    toDie->lastInsert = TREE_NIL;
    toDie->lastRemove = TREE_NIL;
    
    return 0; /* RETURN "there is no more left!" */
  } else {
    TREENODE *curNode = toDie->root;
    OID oid;
    uint32_t index;
    
    oid = curNode->value;
    for (index = 0; index < SB_FRAMES_PER_TREENODE; index++) {
      if (curNode->body.map[index] != 0u) {
	if (retFrame) *retFrame = oid + index * EROS_OBJECTS_PER_FRAME;
	oid++;
#ifndef TREE_NO_TYPES
	curNode->body.type[index] = SBOT_INVALID;
#endif
	curNode->body.map[index] = 0u;
	index++; /* increment past this one, as we know it is zero */
	break;
      }
    }

    /* skip past any empty ones after this one */
    while (index < SB_FRAMES_PER_TREENODE
	   && curNode->body.map[index] == 0u) {
      index++;
    }
    if (index == SB_FRAMES_PER_TREENODE) {
      /* this node is finished */
      /* we are going to be deleting */      
      _allocTree_clearCachedInfo(toDie); 
      toDie->root = tree_remove(toDie->root, curNode);

      /* SHAP: and delete it */
      tree_deleteNode(curNode);
    }
    return 1; /* RETURN "got some" */
  }  
}

uint32_t
allocTree_mergeTrees(TREE *dest, TREE *src)
{
  TREENODE *curNode = src->root;

  if (src == dest)
    kpanic(KR_OSTREAM,"AllocTree.c:%d: Merging identical trees!\n",__LINE__);

  _allocTree_clearCachedInfo(src); /* we are going to be deleting */
  
  while (curNode != TREE_NIL) {
    /*   loop through the tree, removing the root of /src/ and
     * inserting it's contents into /dest/
     */
    TREENODE *destNode;
    
    src->root = tree_remove(src->root,curNode);
    
    destNode = tree_find(dest->root,curNode->value);

    if (destNode == TREE_NIL) {
      /* not there - insert it */
      dest->root = tree_insert(dest->root,curNode);
    } else {
      /* there -- merge the old and new */
      uint32_t idx;

      for (idx = 0; idx < SB_FRAMES_PER_TREENODE; idx++) {
	if (curNode->body.map[idx] != 0) {
#ifdef PARANOID
	  if (destNode->body.map[idx] != 0) {
	    debug_print_node(curNode);
	    debug_print_node(destNode);
	    /* conflict */
	    kpanic(KR_OSTREAM,"Spacebank: treenode merge conflict\n");
	  }
#endif /*PARANOID*/	  
	  /* write in the data */
#ifndef TREE_NO_TYPES
	  destNode->body.type[idx] = curNode->body.type[idx];
#endif
	  destNode->body.map[idx] = curNode->body.map[idx];
	}
      }
      /* done merging, delete the node */
      tree_deleteNode(curNode);
    }

    curNode = src->root; /* reset curNode to the new root */
    
  } /* while (curNode != TREE_NIL) */

  /* the old tree is dead, long live the tree! */
  src->root = TREE_NIL;
  src->lastInsert = TREE_NIL;
  src->lastRemove = TREE_NIL;
      
  /* Having done the merge, our cached information about last
     insertion and removal may now be stale, but there is no point in
     chucking it.  Think of the spacebank clobber that just occurred
     as being "out of band" w.r.t. the normal sequence of allocations
     and deletions.  If we're right we win, and if we're wrong we cost
     ourselves a marginal compare, which is not a bad downside. */

  return 0;
}

void
debug_print_node(TREENODE *node)
{
  uint32_t i;
  kprintf(KR_OSTREAM,
	  "%sNode 0x%08x Parent 0x%08x Left 0x%08x Right %08x\n",
	  ((node->color == TREE_BLACK)?"Black  ":
	    (node->color == TREE_RED)?"Red    ": "BADCLR "),
	  node, node->parent, node->left, node->right);

  kprintf(KR_OSTREAM,
	  "Value: 0x%08x%08x\n",
	  DW_HEX_ARG(node->value));

#ifndef TREE_NO_TYPES
  kprintf(KR_OSTREAM,
	  "Type: ");

  for (i = 0; i < SB_FRAMES_PER_TREENODE; i++)
    kprintf(KR_OSTREAM, "   %02x", (uint32_t)node->body.type[i]);

  kprintf(KR_OSTREAM,"\n");
#endif	  

  kprintf(KR_OSTREAM,
	  "Map:  ");

  for (i = 0; i < SB_FRAMES_PER_TREENODE; i++)
    kprintf(KR_OSTREAM, " %04x", (uint32_t)node->body.map[i]);

  kprintf(KR_OSTREAM,"\n");
}

/* node comparision functions */
#ifdef NO_FAST_MACRO_COMPARE
static int
tree_compare(TREENODE *t0, TREENODE *t1)
{
  if (t0->value < t1->value)
    return -1;
  if (t0->value > t1->value)
    return 1;
  return 0;
}

static int
tree_compare_key(TREENODE *t0, TREEKEY key)
{
  /* NOTE: in order to be found correctly, /key/ *MUST* have
   *       zeros in the low bits.  The best way to do this is
   *       to AND it with ~(SB_OBJECTS_PER_TREENODE - 1) before
   *       passing it to any call that uses this routine.
   */
  if (t0->value < key)
    return -1;
  if (t0->value > key)
    return 1;
  return 0;
}
#else /* ! NO_FAST_MACRO_COMPARE */ 
/* use macro versions of the above for speed! */
#define tree_compare(t0,t1) (((t0)->value < (t1)->value)? -1 : \
                             (((t0)->value > (t1)->value)? 1 : 0))

#define tree_compare_key(t0,key) (((t0)->value < key)? -1 : \
                                  (((t0)->value > key)? 1 : 0))
#endif /* ! NO_FAST_MACRO_COMPARE */

#define ERROR_PRINTF(x) kdprintf x
#define ERR_FIL KR_OSTREAM

#define VERB_PRINTF(x) kprintf x
#define VERB_FIL KR_OSTREAM

#include <rbtree/tree_init.c>
#include <rbtree/tree_util.c>
#include <rbtree/tree_find.c>
#include <rbtree/tree_insert.c>
#include <rbtree/tree_validate.c>
#include <rbtree/tree_remove.c>
#include <rbtree/tree_contains.c>
#include <rbtree/tree_succ.c>
#include <rbtree/tree_pred.c>
#include <rbtree/tree_min.c>
#include <rbtree/tree_max.c>