btree.h

好东东。linux下面的文件节点、文件状态的变化监听代码

    Node *p, *q;
    for (p = root; q = p->link[0]; p = q)
	continue;
    return p->key[0];
}

template <class Key, class Value>
Key
BTree<Key, Value>::next(const Key& pred) const
{
    if (!root)
	return 0;

    assert(root->n);

    Closure it = root->next(pred);
    switch (Status(it))
    {
    case OK:
	return it.key;

    case OVER:
	return 0;			// All done.

    default:
	assert(0);
	return 0;
    }
}

template <class Key, class Value>
BTree<Key, Value>::Closure
BTree<Key, Value>::Node::next(const Key& pred) const
{
    if (!this)
	return OVER;

    unsigned i = find(pred);
    assert(i <= n);
    if (i < n && key[i] == pred)
	i++;
    Closure it = link[i]->next(pred);
    if (Status(it) != OVER)
	return it;
    if (i == n)
	return OVER;
    else
	return Closure(OK, key[i]);
}

//  BTB::insert() -- insert a new key/value pair
//  into the tree.  Fails and returns false if key is already
//  in tree.
//
//  This code is the only place that makes the tree taller.


template <class Key, class Value>
bool
BTree<Key, Value>::insert(const Key& key, const Value& value)
{
    Closure it = insert(root, key, value);
    switch (Status(it))
    {
    case OK:
	npairs++;
	return true;

    case NO:
	return false;

    case OVER:
	root = new Node(root, it);
	npairs++;
	return true;

    default:
	assert(0);
	return false;
    }
}

//  BTB::insert(Node *, ...) -- helper function for
//  BTB::insert(Key&, ...)  Recurses to the appropriate leaf, splits
//  nodes as necessary on the way back.

template <class Key, class Value>
BTree<Key, Value>::Closure
BTree<Key, Value>::insert(Node *p, const Key& key, const Value& value)
{
    if (!p) return Closure(key, value, NULL);
    //  If you're running Purify on a client linking with libfam, and it says
    //  that line is causing a 3-byte UMR for BTree<int, bool>::insert() in
    //  FAMNextEvent() ("Reading 8 bytes from 0x... on the stack (3 bytes at
    //  0x... uninit)"), and sizeof(bool) == 1, it's actually OK.  Those 3
    //  bytes are the padding between the bool Value and the Node *link in
    //  BTree<int, bool>::Closure.

    int i = p->find(key);
    if (i < p->n && key == p->key[i])
	return NO;			// key already exists.

    Closure it = insert(p->link[i], key, value);

    if (Status(it) == OVER)
    {   if (p->insert(i, it))
	    return Closure(OK);
	else
	{   if (i > fanout / 2)
	    {   Node *np = new Node(p, fanout / 2 + 1);
		np->insert(i - fanout / 2 - 1, it);
		assert(p->n > fanout / 2);
		it = p->remove(fanout / 2);
		return Closure(it.key, it.value, np);
	    }
	    else if (i < fanout / 2)
	    {
		Node *np = new Node(p, fanout / 2);
		p->insert(i, it);
		assert(p->n > fanout / 2);
		it = p->remove(fanout / 2);
		return Closure(it.key, it.value, np);
	    }
	    else // (i == fanout / 2)
	    {
		Node *np = new Node(p, fanout / 2);
		np->link[0] = it.link;
		return Closure(it.key, it.value, np);
	    }
	}
    }
    
    return it;
}

//  BTB::remove() -- remove a key/value from the tree.
//  This function is the only one that makes the tree shorter.

template <class Key, class Value>
bool
BTree<Key, Value>::remove(const Key& key)
{
    Status s = remove(root, key);
    switch (s)
    {
    case OK:
	assert(npairs);
	--npairs;
	assert(!root || root->n);
	return true;

    case NO:
	assert(!root || root->n);
	return false;

    case UNDER:
	if (root->n == 0)
	{   Node *nr = root->link[0];
	    root->link[0] = NULL;	// don't delete subtree
	    delete root;
	    root = nr;
	}
	assert(npairs);
	--npairs;
	assert(!root || root->n);
	return true;

    default:
	assert(0);
	return false;
    }
}

//  BTB::underflow -- helper function to BTB::remove() When a node
//  has too few elements (less than fanout / 2), this function is
//  invoked.  It tries to join i'th child of node p with one of its
//  adjacent siblings, then tries to move entries from an adjacent
//  sibling to child node.
//
//  Returns UNDER if node p is too small afterward, OK otherwise.

template <class Key, class Value>
BTree<Key, Value>::Status
BTree<Key, Value>::underflow(Node *p, unsigned i)
{
    assert(p);
    assert(i <= p->n);
    Node *cp = p->link[i];
    assert(cp);
    
    Node *rp = i < p->n ? p->link[i + 1] : NULL;
    Node *lp = i > 0    ? p->link[i - 1] : NULL;
    assert(!rp || rp->n >= fanout / 2);
    assert(!lp || lp->n >= fanout / 2);

    if (rp && rp->n == fanout / 2)
    {
	// join cp w/ rp;
	cp->join(p->remove(i), rp);
	delete rp;
    }
    else if (lp && lp->n == fanout / 2)
    {
	// join lp w/ cp;
	lp->join(p->remove(i - 1), cp);
	delete cp;
    }
    else if (lp)
    {
	// shuffle from lp to cp;
	Closure li = lp->remove(lp->n - 1);
	cp->insert(0, Closure(p->key[i - 1], p->value[i - 1], cp->link[0]));
	cp->link[0] = li.link;
	p->key[i - 1] = li.key;
	p->value[i - 1] = li.value;
	return OK;
    }
    else if (rp)
    {
	// shuffle from rp to cp;
	Closure ri = rp->remove(0);
	cp->insert(cp->n, Closure(p->key[i], p->value[i], rp->link[0]));
	p->key[i] = ri.key;
	p->value[i] = ri.value;
	rp->link[0] = ri.link;
	return OK;
    }
    
    return p->n >= fanout / 2 ? OK : UNDER;
}

//  BTB::remove_rightmost() -- helper to BTB::remove().
//
//  Removes rightmost leaf key/value from subtree and returns them.
//  If Nodes become too small in the process, invokes Node::underflow()
//  to fix them up.  Return status is either OK or UNDER, indicating
//  root of subtree is too small.


template <class Key, class Value>
BTree<Key, Value>::Closure
BTree<Key, Value>::remove_rightmost(Node *p)
{
    int i = p->n;
    Node *cp = p->link[i];
    if (cp)
    {   Closure it = remove_rightmost(cp);
	if (Status(it) == UNDER)
	    return Closure(underflow(p, i), it);
	else
	    return it;
    }
    else
    {   Closure it = p->remove(p->n - 1);
	if (p->n >= fanout / 2)
	    return Closure(OK, it);
	else
	    return Closure(UNDER, it);
    }	    
}

//  BTB::remove(Node *, ...) -- helper to BTB::remove(const Key&).
//
//  Recurses into tree to find key/value to delete.  When it finds
//  them, it pulls the rightmost leaf key/value off the branch to
//  the left and replaces the removed k/v with them.  Watches for
//  Node underflows from BTB::remove_rightmost() and propagates them
//  back up.

template <class Key, class Value>
BTree<Key, Value>::Status
BTree<Key, Value>::remove(Node *p, const Key& key)
{
    if (!p)
	return NO;			// key not found
    int i = p->find(key);
    if (i < p->n && key == p->key[i])
    {
	// Delete this one.

	Closure it = p->remove(i);
	if (p->link[i])
	{   Closure rm = remove_rightmost(p->link[i]);
	    assert(!rm.link);
	    p->insert(i, Closure(rm.key, rm.value, it.link));
	    if (Status(rm) == UNDER)
		return underflow(p, i);
	}
	return p->n >= fanout / 2 ? OK : UNDER;
    }
    else
    {   Node *cp = p->link[i];
	Status s = remove(cp, key);
	if (s == UNDER)
	    return underflow(p, i);
	else
	    return s;
    }
}



//#ifndef NDEBUG
//
//template <class K, class V>
//BTree<K, V>::BTree()
//{
//    //assert(sizeof K <= sizeof BTB::Key);
//    //assert(sizeof V <= sizeof BTB::Value);
//}
//
//#endif /* !NDEBUG */


#endif /* !BTree_included */