Annotation of fam/include/BTree.h, Revision 1.1.1.1
1.1 trev 1: // Copyright (C) 1999 Silicon Graphics, Inc. All Rights Reserved.
2: //
3: // This program is free software; you can redistribute it and/or modify it
4: // under the terms of version 2.1 of the GNU Lesser General Public License
5: // as published by the Free Software Foundation.
6: //
7: // This program is distributed in the hope that it would be useful, but
8: // WITHOUT ANY WARRANTY; without even the implied warranty of
9: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Further, any
10: // license provided herein, whether implied or otherwise, is limited to
11: // this program in accordance with the express provisions of the GNU Lesser
12: // General Public License. Patent licenses, if any, provided herein do not
13: // apply to combinations of this program with other product or programs, or
14: // any other product whatsoever. This program is distributed without any
15: // warranty that the program is delivered free of the rightful claim of any
16: // third person by way of infringement or the like. See the GNU Lesser
17: // General Public License for more details.
18: //
19: // You should have received a copy of the GNU General Public License along
20: // with this program; if not, write the Free Software Foundation, Inc., 59
21: // Temple Place - Suite 330, Boston MA 02111-1307, USA.
22:
23: #ifndef BTree_included
24: #define BTree_included
25:
26: #include "Boolean.h"
27:
28: // This is an in-core B-Tree implementation.
29: //
30: // The public interface is fairly sparse: find, insert and remove
31: // are the provided functions. insert() and remove() return true
32: // on success, false on failure. find() returns 0 on failure.
33: //
34: // size() returns the number of key/value pairs in the tree.
35: //
36: // sizeofnode() returns the size of a BTree node, in bytes.
37: //
38: // BTree is instantiated by
39: //
40: // libfam/Client.h:
41: // BTree<int, void *> *userData;
42: // BTree<int, bool> *endExist;
43: // fam/Listener.c++:
44: // BTree<int, NegotiatingClient *> negotiating_clients;
45: // fam/RequestMap.h:
46: // typedef BTree<Request, ClientInterest *> RequestMap;
47: // fam/Set.h:
48: // template <class T> class Set : public BTree<T, bool>
49: // typedef BTree<T, bool> inherited;
50: //
51: // Set (derived from BTree) is instantiated by
52: //
53: // fam/TCP_Client.h:
54: // Set<Interest *> to_be_scanned;
55: // fam/Pollster.h:
56: // static Set<Interest *> polled_interests;
57: // static Set<ServerHost *> polled_hosts;
58: // fam/FileSystem.h:
59: // typedef Set<ClientInterest *> Interests;
60: //
61: template <class Key, class Value> class BTree {
62:
63: public:
64:
65: BTree();
66: virtual ~BTree();
67:
68: Value find(const Key& k) const;
69: bool insert(const Key& k, const Value& v);
70: bool remove(const Key& k);
71:
72: Key first() const;
73: Key next(const Key& k) const;
74:
75: unsigned size() const { return npairs; }
76:
77: static unsigned sizeofnode() { return sizeof (Node); }
78:
79: private:
80:
81: enum { fanout = 32 };
82: enum Status { OK, NO, OVER, UNDER };
83:
84: struct Node;
85: struct Closure {
86:
87: Closure(Status s) : status(s), key(0),
88: value(0), link(0) { }
89: Closure(Key k, Value v, Node *l) : status(OVER), key(k), value(v),
90: link(l) { }
91: Closure(Status s, const Closure& i) : status(s), key(i.key),
92: value(i.value), link(i.link) { }
93: Closure(Status s, const Key& k) : status(s), key(k),
94: value(0), link(0) { }
95: operator Status () { return status; }
96:
97: Status status;
98: Key key;
99: Value value;
100: Node *link;
101:
102: };
103:
104: struct Node {
105:
106: Node(Node *, const Closure&);
107: Node(Node *, unsigned index);
108: ~Node();
109:
110: unsigned find(const Key&) const;
111: Closure next(const Key&) const;
112: bool insert(unsigned, const Closure&);
113: Closure remove(unsigned);
114: void join(const Closure&, Node *);
115:
116: unsigned n;
117: Key key [fanout];
118: Node *link [fanout + 1];
119: Value value[fanout];
120:
121: private:
122:
123: Node(const Node&); // Do not copy
124: Node& operator = (const Node&); // or assign.
125:
126: };
127:
128: // Instance Variables
129:
130: Node *root;
131: unsigned npairs;
132:
133: Closure insert(Node *, const Key&, const Value&);
134: Status remove(Node *, const Key&);
135: Status underflow(Node *, unsigned);
136: Closure remove_rightmost(Node *);
137:
138: BTree(const BTree&); // Do not copy
139: BTree& operator = (const BTree&); // or assign.
140:
141: };
142:
143: // Construct a Node from a Node and a Closure. New node
144: // has a single key-value pair, its left child
145: // is the other node, and its right child is the link
146: // field of the closure.
147:
148: template <class K, class V>
149: BTree<K, V>::Node::Node(Node *p, const Closure& closure)
150: {
151: n = 1;
152: link[0] = p;
153: key[0] = closure.key;
154: value[0] = closure.value;
155: link[1] = closure.link;
156: }
157:
158: // Construct a Node from a Node and an index. Steals
159: // the elements index..n of other Node for itself.
160: // When this constructor is done, both this->link[0] and
161: // that->link[that->n] point to the same place. The caller
162: // must resolve that.
163:
164: template <class K, class V>
165: BTree<K, V>::Node::Node(Node *that, unsigned index)
166: {
167: n = that->n - index;
168: for (int i = 0; i < n; i++)
169: { key[i] = that->key[index + i];
170: value[i] = that->value[index + i];
171: link[i] = that->link[index + i];
172: }
173: link[n] = that->link[index + n];
174: that->n = index;
175: }
176:
177: // Node destructor. Recursively deletes subnodes.
178:
179: template <class K, class V>
180: BTree<K, V>::Node::~Node()
181: {
182: for (int i = 0; i <= n; i++)
183: delete link[i];
184: }
185:
186: // Node::find() uses binary search to find the nearest key.
187: // return index of key that matches or of next key to left.
188: //
189: // E.g., if find() returns 3 then either key[3] matches or
190: // key passed in is between key[3] and key[4].
191:
192: template <class Key, class Value>
193: unsigned
194: BTree<Key, Value>::Node::find(const Key& k) const
195: {
196: unsigned l = 0, r = n;
197: while (l < r)
198: { int m = (l + r) / 2;
199: if (k == key[m])
200: return m;
201: else if (k < key[m])
202: r = m;
203: else // (k > key[m])
204: l = m + 1;
205: }
206: assert(l == n || k < key[l]);
207: return l;
208: }
209:
210: // Node::insert() inserts key/value into j'th position in node.
211: // Inserts closure's link to the right. Returns true if successful,
212: // false if node is already full.
213:
214: template <class K, class V>
215: bool
216: BTree<K, V>::Node::insert(unsigned j, const Closure& closure)
217: {
218: if (n < fanout)
219: { for (int i = n; i > j; --i)
220: { key[i] = key[i - 1];
221: value[i] = value[i - 1];
222: link[i + 1] = link[i];
223: }
224: key[j] = closure.key; value[j] = closure.value;
225: link[j + 1] = closure.link;
226: n++;
227: assert(j == 0 || key[j - 1] < key[j]);
228: assert(j == n - 1 || key[j] < key[j + 1]);
229: return true;
230: }
231: else
232: return false;
233: }
234:
235: // Node::remove extracts the j'th key/value and the link
236: // to the right and returns them.
237:
238: template <class Key, class Value>
239: BTree<Key, Value>::Closure
240: BTree<Key, Value>::Node::remove(unsigned j)
241: {
242: Key k = key[j];
243: Value v = value[j];
244: Node *l = link[j + 1];
245: for (unsigned i = j + 1; i < n; i++)
246: { key[i - 1] = key[i];
247: value[i - 1] = value[i];
248: link[i] = link[i + 1];
249: }
250: --n;
251: return Closure(k, v, l);
252: }
253:
254: // Node::join() copies key/value from closure and moves all
255: // key/value/links from other Node into this node.
256: // Other Node is modified to contain no keys, no values, no links.
257:
258: template <class K, class V>
259: void
260: BTree<K, V>::Node::join(const Closure& it, Node *that)
261: {
262: assert(that);
263: assert(n + that->n <= fanout - 1);
264: key[n] = it.key;
265: value[n] = it.value;
266: for (int i = 0, j = n + 1; i < that->n; i++, j++)
267: { key[j] = that->key[i];
268: value[j] = that->value[i];
269: link[j] = that->link[i];
270: }
271: n += that->n + 1;
272: link[n] = that->link[that->n];
273: that->n = 0;
274: that->link[0] = NULL;
275: }
276:
277: ///////////////////////////////////////////////////////////////////////////////
278:
279: // BTB constructor -- check that fanout is even.
280:
281: template <class K, class V>
282: BTree<K, V>::BTree()
283: : root(NULL), npairs(0)
284: {
285: assert(!(fanout % 2));
286: }
287:
288: // BTB destructor -- delete all Nodes.
289:
290: template <class K, class V>
291: BTree<K, V>::~BTree()
292: {
293: delete root;
294: }
295:
296: // BTB::find() -- search BTB for Key, return matching value.
297:
298: template <class Key, class Value>
299: Value
300: BTree<Key, Value>::find(const Key& key) const
301: {
302: for (Node *p = root; p; )
303: { int i = p->find(key);
304: if (i < p->n && key == p->key[i])
305: return p->value[i];
306: else
307: p = p->link[i];
308: }
309: return Value(0);
310: }
311:
312: template <class Key, class Value>
313: Key
314: BTree<Key, Value>::first() const
315: {
316: if (!root)
317: return 0;
318: assert(root->n);
319:
320: Node *p, *q;
321: for (p = root; q = p->link[0]; p = q)
322: continue;
323: return p->key[0];
324: }
325:
326: template <class Key, class Value>
327: Key
328: BTree<Key, Value>::next(const Key& pred) const
329: {
330: if (!root)
331: return 0;
332:
333: assert(root->n);
334:
335: Closure it = root->next(pred);
336: switch (Status(it))
337: {
338: case OK:
339: return it.key;
340:
341: case OVER:
342: return 0; // All done.
343:
344: default:
345: assert(0);
346: return 0;
347: }
348: }
349:
350: template <class Key, class Value>
351: BTree<Key, Value>::Closure
352: BTree<Key, Value>::Node::next(const Key& pred) const
353: {
354: if (!this)
355: return OVER;
356:
357: unsigned i = find(pred);
358: assert(i <= n);
359: if (i < n && key[i] == pred)
360: i++;
361: Closure it = link[i]->next(pred);
362: if (Status(it) != OVER)
363: return it;
364: if (i == n)
365: return OVER;
366: else
367: return Closure(OK, key[i]);
368: }
369:
370: // BTB::insert() -- insert a new key/value pair
371: // into the tree. Fails and returns false if key is already
372: // in tree.
373: //
374: // This code is the only place that makes the tree taller.
375:
376:
377: template <class Key, class Value>
378: bool
379: BTree<Key, Value>::insert(const Key& key, const Value& value)
380: {
381: Closure it = insert(root, key, value);
382: switch (Status(it))
383: {
384: case OK:
385: npairs++;
386: return true;
387:
388: case NO:
389: return false;
390:
391: case OVER:
392: root = new Node(root, it);
393: npairs++;
394: return true;
395:
396: default:
397: assert(0);
398: return false;
399: }
400: }
401:
402: // BTB::insert(Node *, ...) -- helper function for
403: // BTB::insert(Key&, ...) Recurses to the appropriate leaf, splits
404: // nodes as necessary on the way back.
405:
406: template <class Key, class Value>
407: BTree<Key, Value>::Closure
408: BTree<Key, Value>::insert(Node *p, const Key& key, const Value& value)
409: {
410: if (!p) return Closure(key, value, NULL);
411: // If you're running Purify on a client linking with libfam, and it says
412: // that line is causing a 3-byte UMR for BTree<int, bool>::insert() in
413: // FAMNextEvent() ("Reading 8 bytes from 0x... on the stack (3 bytes at
414: // 0x... uninit)"), and sizeof(bool) == 1, it's actually OK. Those 3
415: // bytes are the padding between the bool Value and the Node *link in
416: // BTree<int, bool>::Closure.
417:
418: int i = p->find(key);
419: if (i < p->n && key == p->key[i])
420: return NO; // key already exists.
421:
422: Closure it = insert(p->link[i], key, value);
423:
424: if (Status(it) == OVER)
425: { if (p->insert(i, it))
426: return Closure(OK);
427: else
428: { if (i > fanout / 2)
429: { Node *np = new Node(p, fanout / 2 + 1);
430: np->insert(i - fanout / 2 - 1, it);
431: assert(p->n > fanout / 2);
432: it = p->remove(fanout / 2);
433: return Closure(it.key, it.value, np);
434: }
435: else if (i < fanout / 2)
436: {
437: Node *np = new Node(p, fanout / 2);
438: p->insert(i, it);
439: assert(p->n > fanout / 2);
440: it = p->remove(fanout / 2);
441: return Closure(it.key, it.value, np);
442: }
443: else // (i == fanout / 2)
444: {
445: Node *np = new Node(p, fanout / 2);
446: np->link[0] = it.link;
447: return Closure(it.key, it.value, np);
448: }
449: }
450: }
451:
452: return it;
453: }
454:
455: // BTB::remove() -- remove a key/value from the tree.
456: // This function is the only one that makes the tree shorter.
457:
458: template <class Key, class Value>
459: bool
460: BTree<Key, Value>::remove(const Key& key)
461: {
462: Status s = remove(root, key);
463: switch (s)
464: {
465: case OK:
466: assert(npairs);
467: --npairs;
468: assert(!root || root->n);
469: return true;
470:
471: case NO:
472: assert(!root || root->n);
473: return false;
474:
475: case UNDER:
476: if (root->n == 0)
477: { Node *nr = root->link[0];
478: root->link[0] = NULL; // don't delete subtree
479: delete root;
480: root = nr;
481: }
482: assert(npairs);
483: --npairs;
484: assert(!root || root->n);
485: return true;
486:
487: default:
488: assert(0);
489: return false;
490: }
491: }
492:
493: // BTB::underflow -- helper function to BTB::remove() When a node
494: // has too few elements (less than fanout / 2), this function is
495: // invoked. It tries to join i'th child of node p with one of its
496: // adjacent siblings, then tries to move entries from an adjacent
497: // sibling to child node.
498: //
499: // Returns UNDER if node p is too small afterward, OK otherwise.
500:
501: template <class Key, class Value>
502: BTree<Key, Value>::Status
503: BTree<Key, Value>::underflow(Node *p, unsigned i)
504: {
505: assert(p);
506: assert(i <= p->n);
507: Node *cp = p->link[i];
508: assert(cp);
509:
510: Node *rp = i < p->n ? p->link[i + 1] : NULL;
511: Node *lp = i > 0 ? p->link[i - 1] : NULL;
512: assert(!rp || rp->n >= fanout / 2);
513: assert(!lp || lp->n >= fanout / 2);
514:
515: if (rp && rp->n == fanout / 2)
516: {
517: // join cp w/ rp;
518: cp->join(p->remove(i), rp);
519: delete rp;
520: }
521: else if (lp && lp->n == fanout / 2)
522: {
523: // join lp w/ cp;
524: lp->join(p->remove(i - 1), cp);
525: delete cp;
526: }
527: else if (lp)
528: {
529: // shuffle from lp to cp;
530: Closure li = lp->remove(lp->n - 1);
531: cp->insert(0, Closure(p->key[i - 1], p->value[i - 1], cp->link[0]));
532: cp->link[0] = li.link;
533: p->key[i - 1] = li.key;
534: p->value[i - 1] = li.value;
535: return OK;
536: }
537: else if (rp)
538: {
539: // shuffle from rp to cp;
540: Closure ri = rp->remove(0);
541: cp->insert(cp->n, Closure(p->key[i], p->value[i], rp->link[0]));
542: p->key[i] = ri.key;
543: p->value[i] = ri.value;
544: rp->link[0] = ri.link;
545: return OK;
546: }
547:
548: return p->n >= fanout / 2 ? OK : UNDER;
549: }
550:
551: // BTB::remove_rightmost() -- helper to BTB::remove().
552: //
553: // Removes rightmost leaf key/value from subtree and returns them.
554: // If Nodes become too small in the process, invokes Node::underflow()
555: // to fix them up. Return status is either OK or UNDER, indicating
556: // root of subtree is too small.
557:
558:
559: template <class Key, class Value>
560: BTree<Key, Value>::Closure
561: BTree<Key, Value>::remove_rightmost(Node *p)
562: {
563: int i = p->n;
564: Node *cp = p->link[i];
565: if (cp)
566: { Closure it = remove_rightmost(cp);
567: if (Status(it) == UNDER)
568: return Closure(underflow(p, i), it);
569: else
570: return it;
571: }
572: else
573: { Closure it = p->remove(p->n - 1);
574: if (p->n >= fanout / 2)
575: return Closure(OK, it);
576: else
577: return Closure(UNDER, it);
578: }
579: }
580:
581: // BTB::remove(Node *, ...) -- helper to BTB::remove(const Key&).
582: //
583: // Recurses into tree to find key/value to delete. When it finds
584: // them, it pulls the rightmost leaf key/value off the branch to
585: // the left and replaces the removed k/v with them. Watches for
586: // Node underflows from BTB::remove_rightmost() and propagates them
587: // back up.
588:
589: template <class Key, class Value>
590: BTree<Key, Value>::Status
591: BTree<Key, Value>::remove(Node *p, const Key& key)
592: {
593: if (!p)
594: return NO; // key not found
595: int i = p->find(key);
596: if (i < p->n && key == p->key[i])
597: {
598: // Delete this one.
599:
600: Closure it = p->remove(i);
601: if (p->link[i])
602: { Closure rm = remove_rightmost(p->link[i]);
603: assert(!rm.link);
604: p->insert(i, Closure(rm.key, rm.value, it.link));
605: if (Status(rm) == UNDER)
606: return underflow(p, i);
607: }
608: return p->n >= fanout / 2 ? OK : UNDER;
609: }
610: else
611: { Node *cp = p->link[i];
612: Status s = remove(cp, key);
613: if (s == UNDER)
614: return underflow(p, i);
615: else
616: return s;
617: }
618: }
619:
620:
621:
622: //#ifndef NDEBUG
623: //
624: //template <class K, class V>
625: //BTree<K, V>::BTree()
626: //{
627: // //assert(sizeof K <= sizeof BTB::Key);
628: // //assert(sizeof V <= sizeof BTB::Value);
629: //}
630: //
631: //#endif /* !NDEBUG */
632:
633:
634: #endif /* !BTree_included */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/back.gif){kind=icon}
Return to BTree.h CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [Development] / fam / include