btree.h

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

//  Copyright (C) 1999 Silicon Graphics, Inc.  All Rights Reserved.
//  
//  This program is free software; you can redistribute it and/or modify it
//  under the terms of version 2.1 of the GNU Lesser General Public License
//  as published by the Free Software Foundation.
//
//  This program is distributed in the hope that it would be useful, but
//  WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  Further, any
//  license provided herein, whether implied or otherwise, is limited to
//  this program in accordance with the express provisions of the GNU Lesser
//  General Public License.  Patent licenses, if any, provided herein do not
//  apply to combinations of this program with other product or programs, or
//  any other product whatsoever. This program is distributed without any
//  warranty that the program is delivered free of the rightful claim of any
//  third person by way of infringement or the like.  See the GNU Lesser
//  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 the Free Software Foundation, Inc., 59
//  Temple Place - Suite 330, Boston MA 02111-1307, USA.

#ifndef BTree_included
#define BTree_included

#include "Boolean.h"

//  This is an in-core B-Tree implementation.
//
//  The public interface is fairly sparse: find, insert and remove
//  are the provided functions.  insert() and remove() return true
//  on success, false on failure.  find() returns 0 on failure.
//
//  size() returns the number of key/value pairs in the tree.
//
//  sizeofnode() returns the size of a BTree node, in bytes.
//
//  BTree is instantiated by
//
//      libfam/Client.h:
//          BTree<int, void *> *userData;
//          BTree<int, bool>   *endExist;
//      fam/Listener.c++:
//          BTree<int, NegotiatingClient *> negotiating_clients;
//      fam/RequestMap.h:
//          typedef BTree<Request, ClientInterest *> RequestMap;
//      fam/Set.h:
//          template <class T> class Set : public BTree<T, bool>
//          typedef BTree<T, bool> inherited;
//
//  Set (derived from BTree) is instantiated by
//
//      fam/TCP_Client.h:
//          Set<Interest *> to_be_scanned;
//      fam/Pollster.h:
//          static Set<Interest *> polled_interests;
//          static Set<ServerHost *> polled_hosts;
//      fam/FileSystem.h:
//          typedef Set<ClientInterest *> Interests;
//
template <class Key, class Value> class BTree {

public:

    BTree();
    virtual ~BTree();

    Value find(const Key& k) const;
    bool insert(const Key& k, const Value& v);
    bool remove(const Key& k);

    Key first() const;
    Key next(const Key& k) const;

    unsigned size() const		{ return npairs; }

    static unsigned sizeofnode()	{ return sizeof (Node); }

private:

    enum { fanout = 32 };
    enum Status { OK, NO, OVER, UNDER };

    struct Node;
    struct Closure {

	Closure(Status s)		    : status(s), key(0),
                                              value(0), link(0) { }
	Closure(Key k, Value v, Node *l)    : status(OVER), key(k), value(v),
					      link(l) { }
	Closure(Status s, const Closure& i) : status(s), key(i.key),
					      value(i.value), link(i.link) { }
	Closure(Status s, const Key& k)	    : status(s), key(k),
                                              value(0), link(0) { }
	operator Status ()		    { return status; }

	Status status;
	Key    key;
	Value  value;
	Node  *link;

    };

    struct Node {

	Node(Node *, const Closure&);
	Node(Node *, unsigned index);
	~Node();

	unsigned find(const Key&) const;
	Closure next(const Key&) const;
	bool insert(unsigned, const Closure&);
	Closure remove(unsigned);
	void join(const Closure&, Node *);

	unsigned n;
	Key   key  [fanout];
	Node *link [fanout + 1];
	Value value[fanout];

    private:

	Node(const Node&);		// Do not copy
	Node& operator = (const Node&);	// or assign.

    };

    // Instance Variables

    Node *root;
    unsigned npairs;

    Closure insert(Node *, const Key&, const Value&);
    Status remove(Node *, const Key&);
    Status underflow(Node *, unsigned);
    Closure remove_rightmost(Node *);

    BTree(const BTree&);		// Do not copy
    BTree& operator = (const BTree&);	//  or assign.

};

//  Construct a Node from a Node and a Closure.  New node
//  has a single key-value pair, its left child
//  is the other node, and its right child is the link
//  field of the closure.

template <class K, class V>
BTree<K, V>::Node::Node(Node *p, const Closure& closure)
{
    n = 1;
    link[0] = p;
    key[0] = closure.key;
    value[0] = closure.value;
    link[1] = closure.link;
}

//  Construct a Node from a Node and an index.  Steals
//  the elements index..n of other Node for itself.
//  When this constructor is done, both this->link[0] and
//  that->link[that->n] point to the same place.  The caller
//  must resolve that.

template <class K, class V>
BTree<K, V>::Node::Node(Node *that, unsigned index)
{
    n = that->n - index;
    for (int i = 0; i < n; i++)
    {   key[i] = that->key[index + i];
	value[i] = that->value[index + i];
	link[i] = that->link[index + i];
    }
    link[n] = that->link[index + n];
    that->n = index;
}

//  Node destructor.  Recursively deletes subnodes.

template <class K, class V>
BTree<K, V>::Node::~Node()
{
    for (int i = 0; i <= n; i++)
	delete link[i];
}

//  Node::find() uses binary search to find the nearest key.
//  return index of key that matches or of next key to left.
//
//  E.g., if find() returns 3 then either key[3] matches or
//  key passed in is between key[3] and key[4].

template <class Key, class Value>
unsigned
BTree<Key, Value>::Node::find(const Key& k) const
{
    unsigned l = 0, r = n;
    while (l < r)
    {   int m = (l + r) / 2;
	if (k == key[m])
	    return m;
	else if (k < key[m])
	    r = m;
	else // (k > key[m])
	    l = m + 1;
    }
    assert(l == n || k < key[l]);
    return l;
}

//  Node::insert() inserts key/value into j'th position in node.
//  Inserts closure's link to the right.  Returns true if successful,
//  false if node is already full.

template <class K, class V>
bool
BTree<K, V>::Node::insert(unsigned j, const Closure& closure)
{
    if (n < fanout)
    {   for (int i = n; i > j; --i)
	{   key[i] = key[i - 1];
	    value[i] = value[i - 1];
	    link[i + 1] = link[i];
	}
	key[j] = closure.key; value[j] = closure.value;
	link[j + 1] = closure.link;
	n++;
	assert(j == 0     || key[j - 1] < key[j]);
	assert(j == n - 1 || key[j] < key[j + 1]);
	return true;
    }
    else
	return false;
}

//  Node::remove extracts the j'th key/value and the link
//  to the right and returns them.

template <class Key, class Value>
BTree<Key, Value>::Closure
BTree<Key, Value>::Node::remove(unsigned j)
{
    Key k = key[j];
    Value v = value[j];
    Node *l = link[j + 1];
    for (unsigned i = j + 1; i < n; i++)
    {   key[i - 1] = key[i];
	value[i - 1] = value[i];
	link[i] = link[i + 1];
    }
    --n;
    return Closure(k, v, l);
}

// Node::join() copies key/value from closure and moves all
// key/value/links from other Node into this node.
// Other Node is modified to contain no keys, no values, no links.

template <class K, class V>
void
BTree<K, V>::Node::join(const Closure& it, Node *that)
{
    assert(that);
    assert(n + that->n <= fanout - 1);
    key[n] = it.key;
    value[n] = it.value;
    for (int i = 0, j = n + 1; i < that->n; i++, j++)
    {   key[j] = that->key[i];
	value[j] = that->value[i];
	link[j] = that->link[i];
    }
    n += that->n + 1;
    link[n] = that->link[that->n];
    that->n = 0;
    that->link[0] = NULL;
}

///////////////////////////////////////////////////////////////////////////////

//  BTB constructor -- check that fanout is even.

template <class K, class V>
BTree<K, V>::BTree()
    : root(NULL), npairs(0)
{
    assert(!(fanout % 2));
}

//  BTB destructor -- delete all Nodes.

template <class K, class V>
BTree<K, V>::~BTree()
{
    delete root;
}

//  BTB::find() -- search BTB for Key, return matching value.

template <class Key, class Value>
Value
BTree<Key, Value>::find(const Key& key) const
{
    for (Node *p = root; p; )
    {   int i = p->find(key);
	if (i < p->n && key == p->key[i])
	    return p->value[i];
	else
	    p = p->link[i];
    }
    return Value(0);
}

template <class Key, class Value>
Key
BTree<Key, Value>::first() const
{
    if (!root)
	return 0;
    assert(root->n);