ck_coredirtree.cxx

C++ 编写的EROS RTOS

/*
 * Copyright (C) 1998, 1999, Jonathan S. Shapiro.
 *
 * This file is part of the EROS Operating System.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2,
 * or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/* Note: This code adapted from my tree package.  Experience suggests
 * that trying to debug this code in the kernel is lunacy.  Debug the
 * tree package as an application and then re-convert by changing the
 * function names.  I have tried to minimize the name changes.
 */

#include <disk/DiskFrame.hxx>
#include <kerninc/kernel.hxx>
#include <kerninc/MsgLog.hxx>
#include <kerninc/Checkpoint.hxx>

#define dbg_insert  1u
#define dbg_remove  2u

#define dbg_flags   ( 0u )
#define dbg_find    ( 0u )

#define DBCOND(x) (dbg_##x & dbg_flags)
#define DEBUG(x) if DBCOND(x)

#define TREENODE CoreDirent
#define TREEKEY OID
#define TREE_NIL CkNIL
#define TREE_RED CoreDirent::red
#define TREE_BLACK CoreDirent::black
#define tree_succ(x) (x)->Successor()

/* Returns new root */
TREENODE *
CoreDirent::B_Insert(TREENODE *root, TREENODE *z)
{
#ifdef VERBOSE
  printf("Insert node 0x%08x into 0x%08x\n", z, root);
  fflush(stdout);
#endif
  
  int whichcase;
  
  z->parent = TREE_NIL;
  z->left = TREE_NIL;
  z->right = TREE_NIL;
  
  TREENODE *y = TREE_NIL;
  TREENODE *x = root;

  DEBUG(insert)
    assert( Tree_Validate(root, root) );
  
  while (x != TREE_NIL) {
    assert (x->left == TREE_NIL || x->left->parent == x);
    assert (x->right == TREE_NIL || x->right->parent == x);

    y = x;
    if ( Tree_Compare(z,x) < 0 ) {
      x = x->left;
    }
    else {
      x = x->right;
    }
  }

  z->parent = y;
  if (y == TREE_NIL) {
    whichcase = 1;
    root = z;
  }
  else {
    whichcase = 2;
    
    if ( Tree_Compare(z, y) < 0 )
      y->left = z;
    else
      y->right = z;

    assert (y->left == TREE_NIL || y->left->parent == y);
    assert (y->right == TREE_NIL || y->right->parent == y);
  }

  assert(root->parent == TREE_NIL);

  DEBUG(insert)
    assert ( Tree_Validate(root, root) ) ;

  return root;
}

TREENODE *
CoreDirent::RB_Insert(TREENODE * root, TREENODE *x)
{
  root = B_Insert(root, x);

  x->color = TREE_RED;

  while (x != root && x->parent->color == TREE_RED) {
    assert (x->parent->parent);
    
    if (x->parent == x->parent->parent->left) {
      TREENODE *y = x->parent->parent->right;
      if (y->color == TREE_RED) {
	x->parent->color = TREE_BLACK;
	y->color = TREE_BLACK;
	x->parent->parent->color = TREE_RED;
	x = x->parent->parent;
      }
      else {
	if (x == x->parent->right) {
	  x = x->parent;
	  root = RB_Tree_LeftRotate(root, x);
	}
	x->parent->color = TREE_BLACK;
	assert (x->parent->parent);
	x->parent->parent->color = TREE_RED;
	root = RB_Tree_RightRotate(root, x->parent->parent);
      }
    }
    else {
      TREENODE *y = x->parent->parent->left;
      if (y->color == TREE_RED) {
	x->parent->color = TREE_BLACK;
	y->color = TREE_BLACK;
	assert (x->parent->parent != TREE_NIL);
	x->parent->parent->color = TREE_RED;
	x = x->parent->parent;
      }
      else {
	if (x == x->parent->left) {
	  x = x->parent;
	  root = RB_Tree_RightRotate(root, x);
	}
	x->parent->color = TREE_BLACK;
	assert (x->parent->parent != TREE_NIL);
	x->parent->parent->color = TREE_RED;
	root = RB_Tree_LeftRotate(root, x->parent->parent);
      }
    }
  }

  root->color = TREE_BLACK;
  assert(root->parent == TREE_NIL);

  DEBUG(insert)
    assert ( Tree_Validate(root, root) );

  return root;
}

TREENODE *
CoreDirent::RB_Tree_Remove_Fixup(TREENODE * root, TREENODE *x)
{
  TREENODE *w = TREE_NIL;

  if (x->parent == TREE_NIL)	/* deleted last node in tree */
    return root;
  
#ifdef BROKEN
  assert (x != TREE_NIL);
#endif
  
  while ((x != root) && (x->color == TREE_BLACK)) {

    /* MacManis checks x == nilnode && x.parent.left == null OR */
    if (x == x->parent->left) {
      w = x->parent->right;

      if (w->color == TREE_RED) {
	w->color = TREE_BLACK;
	assert (x->parent != TREE_NIL);
	x->parent->color = TREE_RED;
	root = RB_Tree_LeftRotate(root, x->parent);
	w = x->parent->right;
      }

      if ((w->left->color == TREE_BLACK) && (w->right->color == TREE_BLACK)) {
	assert (w != TREE_NIL);
	w->color = TREE_RED;
	x = x->parent;		/* move up the tree */
      }
      else {
	if (w->right->color == TREE_BLACK) {
	  w->left->color = TREE_BLACK;
	  assert (w != TREE_NIL);
	  w->color = TREE_RED;
	  root = RB_Tree_RightRotate(root, w);
	  w = x->parent->right;
	}

	w->color = x->parent->color;
	x->parent->color = TREE_BLACK;
	w->right->color = TREE_BLACK;
	root = RB_Tree_LeftRotate(root, x->parent);
	x = root;
      }
    }
    else {
      w = x->parent->left;

      if (w->color == TREE_RED) {
	w->color = TREE_BLACK;
	assert (x->parent != TREE_NIL);
	x->parent->color = TREE_RED;
	root = RB_Tree_RightRotate(root, x->parent);
	w = x->parent->left;
      }

      if ((w->right->color == TREE_BLACK) && (w->left->color == TREE_BLACK)) {
	assert (w != TREE_NIL);
	w->color = TREE_RED;
	x = x->parent;
      }
      else {
	if (w->left->color == TREE_BLACK) {
	  w->right->color = TREE_BLACK;
	  assert (w != TREE_NIL);
	  w->color = TREE_RED;
	  root = RB_Tree_LeftRotate(root, w);
	  w = x->parent->left;
	}
	w->color = x->parent->color;
	x->parent->color = TREE_BLACK;
	w->left->color = TREE_BLACK;
	root = RB_Tree_RightRotate(root, x->parent);
	x = root;
      }
    }
  }
  
  x->color = TREE_BLACK;
  assert(root->parent == TREE_NIL);

  return root;
}

TREENODE *
CoreDirent::RB_Remove(TREENODE * root, TREENODE *z)
{
#ifdef VERBOSE
  printf("Remove node 0x%08x from 0x%08x\n", z, root);
  fflush(stdout);
#endif  

  TREENODE *y = TREE_NIL;
  TREENODE *x = TREE_NIL;
  
  DEBUG(remove)
    assert ( Tree_Validate(root, root) );

  int whichcase = 0;
  
  TREE_NIL->color = TREE_BLACK;
  
  assert (z != TREE_NIL);
  
  if (z->left == TREE_NIL || z->right == TREE_NIL) {
    whichcase |= 0x1;
    /* Node to delete has only one child or none; can just splice it
     * out.
     */
    y = z;
  }
  else {
    /* Node to delete has two children.  Find it's suceessor and
     * splice successor in in place of deleted node.
     */
    y = tree_succ(z);
  }

  assert(y != TREE_NIL);

  /* We now know that y has at most one child.  Make x point to that
   * child
   */

  x = (y->left != TREE_NIL) ? y->left : y->right;

  x->parent = y->parent;	/* OKAY if X is TREE_NIL per CLR p. 273 */

  /* If y was the root, have to update the tree. */
  if (y->parent == TREE_NIL) {
    whichcase |= 0x10;
    root = x;
  }
  else {
    whichcase |= 0x20;
    if (y == y->parent->left) {
      y->parent->left = x;
    }
    else {
      y->parent->right = x;
    }
  }

#ifndef NDEBUG
  DEBUG(remove) {
    if ( Tree_FindReference(root, y) ) {
      MsgLog::printf("x=0x%08x, y=0x%08x, z=0x%08x root=0x%08x\n", x,
		     y, z, root);
      MsgLog::fatal("Deleted node 0x%08x still referenced before fixup!\n",
		    y);
    }
  }
#endif

  /* Until I actually understand the fixup transformation, do this
   * just as the book would have us do and then fix the fact that the
   * wrong thing was deleted after the fact.
   */
  
  
  if (y != z) {
    z->oid = y->oid;
    z->lid = y->lid;
    z->count = y->count;
  }
  
  if ( y->color == TREE_BLACK )
    root = RB_Tree_Remove_Fixup(root, x);

#ifndef NDEBUG
  DEBUG(remove) {
    if ( Tree_FindReference(root, (y!=z) ? y : z) )
      MsgLog::printf("Deleted znode 0x%08x still referenced by after fixup!\n",
		     z);

    if ( Tree_Validate(root, root) == false )
      MsgLog::fatal("Bad post-remove validation, case 0x%08x\n",
		    whichcase);
  }
#endif

  if (y != z) {
#ifndef NDEBUG
    DEBUG(remove) {
      if ( Tree_FindReference(root, y) )
	MsgLog::printf("Deleted ynode (post fixup) 0x%08x still referenced by after fixup!\n",
		       z);
    }
#endif

    /* The tree is now correct, but for the slight detail that we have
     * deleted the wrong node.  It needed to be done that way for
     * rb_remove_fixup to work.  At this point, Y is unreferenced, and
     * Z (the node we intended to delete) is firmly wired into the
     * tree.  Put Y in in Z's place and restore the old value to Z:
     */

    y->parent = z->parent;
    y->left = z->left;
    y->right = z->right;
    y->oid = z->oid;
    y->lid = z->lid;
    y->count = z->count;
    y->color = z->color;

    if (y->parent != TREE_NIL) {
      if (y->parent->left == z)
	y->parent->left = y;
      else
	y->parent->right = y;
    }
    if (y->left != TREE_NIL)
      y->left->parent = y;
    if (y->right != TREE_NIL)
      y->right->parent = y;

    if (root == z)
      root = y;
  }      

#ifndef NDEBUG
  DEBUG(remove) {
    if ( Tree_FindReference(root, z) )
      MsgLog::printf("Deleted znode (post fixup) 0x%08x still referenced by after fixup!\n",
		     z);
    
    if ( Tree_Validate(root, root) == false ) {
      MsgLog::fatal("Bad post-remove validation, case 0x%08x\n",
		    whichcase);
    }
  }
#endif
  
  return root;
}

TREENODE *
CoreDirent::RB_Tree_RightRotate(TREENODE *root, TREENODE *y)
{
  TREENODE *x = y->left;

  y->left = x->right;
  if (x->right != TREE_NIL)
    x->right->parent = y;

  x->parent = y->parent;
  if (x->parent == TREE_NIL)
    root = x;
  else if (y == y->parent->left)
    y->parent->left = x;
  else
    y->parent->right = x;

  x->right = y;
  y->parent = x;

  assert(root->parent == TREE_NIL);
  return root;
}

TREENODE *
CoreDirent::RB_Tree_LeftRotate(TREENODE *root, TREENODE *x)
{
  TREENODE *y = x->right;

  x->right = y->left;
  if (y->left != TREE_NIL)
    y->left->parent = x;

  y->parent = x->parent;
  if (x->parent == TREE_NIL)
    root = y;
  else if (x == x->parent->left)
    x->parent->left = y;
  else
    x->parent->right = y;

  y->left = x;
  x->parent = y;

  assert(root->parent == TREE_NIL);
  return root;
}

#if 0
/* Preserved for reasons of ancient history until I decide that
 * unmerged trees are the way to go.
 */
bool
CoreDirent::IsLessThan(CklogDirent *n)
{
  if (oid < n->oid)
    return true;

  if (oid > n->oid)
    return false;

  /* The current version should always sort lower */
  if (generation < n->generation)
    return true;

  return false;
}
#endif

CoreDirent *
CoreDirent::Tree_Find(CoreDirent * root, OID oid)
{
  CoreDirent *n = root;
  
  while (n != CkNIL) {
    DEBUG(find)
      MsgLog::printf("tree_find: Considering n = 0x%08x\n", n);
    if (n->oid == oid) {
      DEBUG(find)
	MsgLog::printf("tree_find: return w/ n = 0x%08x\n", n);
      return n;
    }
    else if (n->oid > oid)
      n = n->left;
    else
      n = n->right;
  }

  DEBUG(find)
    MsgLog::printf("tree_find: return w/ n = 0x%08x\n", CkNIL);
  return CkNIL;
}

CoreDirent *
CoreDirent::Tree_Find_Frame(CoreDirent * root, OID oid)
{
  oid = oid - (oid % EROS_OBJECTS_PER_FRAME);
  
  CoreDirent *n = root;
  
  while (n != CkNIL) {
    DEBUG(find)
      MsgLog::printf("tree_find: Considering n = 0x%08x\n", n);
    OID noid = (n->oid - (n->oid % EROS_OBJECTS_PER_FRAME)); 
    if (noid == oid) {
      DEBUG(find)
	MsgLog::printf("tree_find: return w/ n = 0x%08x\n", n);
      return n;
    }
    else if (noid > oid)
      n = n->left;
    else
      n = n->right;
  }

  DEBUG(find)
    MsgLog::printf("tree_find: return w/ n = 0x%08x\n", CkNIL);
  return CkNIL;
}

#ifndef NDEBUG
bool
CoreDirent::Tree_Validate(CoreDirent *root, CoreDirent *node)
{
  if (node == CkNIL)
    return true;
  
  if (node == root && node->parent != CkNIL)
    return false;
  
  if (node != root && node->parent == CkNIL)
    return false;

  if (node->left != CkNIL && node->left->parent != node)
    return false;

  if (node->left != CkNIL && node->left->IsLessThan(node) == false)
    return false;
  
  if (node->right != CkNIL && node->right->parent != node)
    return false;

  if (node->right != CkNIL && node->IsLessThan(node->right) == false)
    return false;

  if (!Tree_Validate(root, node->left))
    return false;
  
  return Tree_Validate(root, node->right);
}

CoreDirent *
CoreDirent::Tree_FindReference(CoreDirent *tree, CoreDirent *node)
{
  if (tree == CkNIL) {
    return 0;
  }
  
  if (tree == node) {
    return tree;
  }

  assert (tree->left != tree);
  assert (tree->right != tree);
  
  CoreDirent *ref;
  
  ref = Tree_FindReference(tree->left, node);
  if (ref)
    return ref;
  
  ref = Tree_FindReference(tree->right, node);

  return ref;
}
#endif