Annotation of fam/include/BTree.h, Revision 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