Leaked source code of windows server 2003
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

794 lines
29 KiB

  1. /*
  2. * rhizome.c
  3. *
  4. * author: John R. Douceur
  5. * date: 28 April 1997
  6. *
  7. * This source file provides functions that implement insertion, removal, and
  8. * search operations on the rhizome database. The code is object-oriented C,
  9. * transliterated from a C++ implementation.
  10. *
  11. * The rhizome is a database that stores patterns containing wildcards.
  12. * Each pattern defines a set of keys that it matches; if a pattern contains
  13. * N wildcards, then it matches 2^N keys. Since each pattern can match
  14. * multiple keys, it is possible for a given key to match multiple patterns
  15. * in the database. The rhizome requires that all patterns stored therein
  16. * have a strict hierarchical interrelationship. Two patterns may match no
  17. * common keys (in which case the patterns are said to be independent), or
  18. * one pattern may match all the keys matched by a second pattern as well as
  19. * additonal keys (in which case the second pattern is said to be more general
  20. * than the first, and the first more specific than the second). The database
  21. * will not accept two patterns which match some keys in common but each of
  22. * which also matches additional keys that the other does not.
  23. *
  24. * The database can be searched for patterns that match a given search key.
  25. * When the database is searched for a given key, the most specifically
  26. * matching pattern is found. If no patterns in the database match the key,
  27. * an appropriate indication is returned.
  28. *
  29. * None of the code or comments in this file needs to be understood by writers
  30. * of client code; all explanatory information for clients is found in the
  31. * associated header file, rhizome.h.
  32. *
  33. */
  34. #include "precomp.h"
  35. #pragma hdrstop
  36. // The fields of the RhizomeNode structure are accessed through the following
  37. // macros. The first three are obvious; the subsequent three rely on an agreed
  38. // usage of the cdata array in the RhizomeNode. The first keybytes locations
  39. // of the cdata array are used to store the value field of the node; the second
  40. // keybytes locations store the mask field; and the third keybytes locations
  41. // store the imask field.
  42. //
  43. #define CHILDREN udata.branch.children
  44. #define REFERENCE udata.leaf.reference
  45. #define GODPARENT udata.leaf.godparent
  46. #define VALUE(pointer) (pointer->cdata)
  47. #define MASK(pointer) (pointer->cdata + rhizome->keybytes)
  48. #define IMASK(pointer) (pointer->cdata + 2 * rhizome->keybytes)
  49. // This macro allocates a new rhizome node structure. The size of the structure
  50. // is a function of the value of keybytes, since three bytes of information
  51. // need to be stored in the structure for each byte of pattern length. The
  52. // cdata array, which is the last field in the structure, is declared as a
  53. // having a single element, but this array will actually extend beyond the
  54. // defined end of the structure into additional space that is allocated for it
  55. // by the following macro.
  56. //
  57. #define NEW_RhizomeNode(_pa) \
  58. GpcAllocMem((_pa),\
  59. sizeof(RhizomeNode) + 3 * rhizome->keybytes - 1,\
  60. NAT_TAG_RHIZOME)/*;\
  61. TRACE(RHIZOME, *_pa, sizeof(RhizomeNode) + 3 * rhizome->keybytes - 1, "NEW_RhizomeNode")*/
  62. // This macro gets the indexed bit of the value, where the most-significant bit
  63. // is defined as bit 0.
  64. //
  65. #define BIT_OF(value, index) \
  66. (((value)[(index) >> 3] >> (7 - ((index) & 0x7))) & 0x1)
  67. // Following are prototypes for static functions that are used internally by
  68. // the implementation of the rhizome routines.
  69. static int
  70. node_insert(
  71. Rhizome *rhizome,
  72. RhizomeNode *new_leaf,
  73. RhizomeNode **ppoint,
  74. int prev_bit);
  75. static void
  76. node_remove(
  77. Rhizome *rhizome,
  78. RhizomeNode *leaf,
  79. RhizomeNode **ppoint);
  80. static RhizomeNode *
  81. replicate(
  82. Rhizome *rhizome,
  83. RhizomeNode *source,
  84. int pivot_bit);
  85. static void
  86. eliminate(
  87. Rhizome *rhizome,
  88. RhizomeNode *point);
  89. static void
  90. coalesce(
  91. Rhizome *rhizome,
  92. RhizomeNode **leaf_list,
  93. RhizomeNode *point);
  94. // Since this is not C++, the Rhizome structure is not self-constructing;
  95. // therefore, the following constructor code must be called on the Rhizome
  96. // structure after it is allocated. The argument keybits specifies the size
  97. // (in bits) of each pattern that will be stored in the database.
  98. //
  99. void
  100. constructRhizome(
  101. Rhizome *rhizome,
  102. int keybits)
  103. {
  104. rhizome->keybits = keybits;
  105. rhizome->keybytes = (keybits - 1) / 8 + 1;
  106. rhizome->root = 0;
  107. }
  108. // Since this is not C++, the Rhizome structure is not self-destructing;
  109. // therefore, the following destructor code must be called on the Rhizome
  110. // structure before it is deallocated.
  111. //
  112. // If the structure is non-empty, call coalesce() to eliminate
  113. // all branch nodes and to string leaf nodes into a list; then delete list.
  114. //
  115. void
  116. destructRhizome(
  117. Rhizome *rhizome)
  118. {
  119. RhizomeNode *leaf_list, *next;
  120. if (rhizome->root != 0)
  121. {
  122. leaf_list = 0;
  123. coalesce(rhizome, &leaf_list, rhizome->root);
  124. while (leaf_list != 0)
  125. {
  126. next = leaf_list->GODPARENT;
  127. GpcFreeMem(leaf_list, NAT_TAG_RHIZOME);
  128. leaf_list = next;
  129. }
  130. }
  131. }
  132. // This function searches the database for the pattern that most specifically
  133. // matches the given key. The key is passed as an array of bytes. When the
  134. // most specific match is found, the PatternHandle of that matching pattern is
  135. // returned. From the PatternHandle can be gotten the reference value via the
  136. // macro GetReferenceFromPatternHandle. If no pattern in the database is found
  137. // to match the key, then a value of 0 is returned as the PatternHandle.
  138. //
  139. PatternHandle
  140. searchRhizome(
  141. Rhizome *rhizome,
  142. char *key)
  143. {
  144. int index;
  145. RhizomeNode *point;
  146. // If tree is empty, search fails.
  147. if (rhizome->root == 0)
  148. {
  149. return 0;
  150. }
  151. // Otherwise, start at rhizome->root and navigate tree until reaching a leaf.
  152. point = rhizome->root;
  153. while (point->pivot_bit < rhizome->keybits)
  154. {
  155. point = point->CHILDREN[BIT_OF(key, point->pivot_bit)];
  156. }
  157. // Check value for match, one byte at a time. If any byte fails to match,
  158. // continue checking godparent with same byte; since previous bytes matched
  159. // godchild, they are guaranteed to match godparent also.
  160. index = 0;
  161. while (index < rhizome->keybytes)
  162. {
  163. if ((((key)[index]) & MASK(point)[index]) != VALUE(point)[index])
  164. {
  165. if (point->GODPARENT != 0)
  166. {
  167. point = point->GODPARENT;
  168. }
  169. else
  170. {
  171. return 0;
  172. }
  173. }
  174. else
  175. {
  176. index++;
  177. }
  178. }
  179. return point;
  180. }
  181. // This function inserts a new pattern into the database. The pattern is
  182. // specified by a value and a mask. Each bit of the mask determines whether
  183. // the bit position is specified or is a wildcard: A 1 in a mask bit indicates
  184. // that the value of that bit is specified by the pattern; a 0 indicates that
  185. // the value of that bit is a wildcard. If a mask bit is 1, then the
  186. // corresponding bit in the value field indicates the specified value of that
  187. // bit. Value and mask fields are passed as arrays of bytes.
  188. //
  189. // The client specifies a void pointer reference value to associate with the
  190. // pattern. When the pattern is installed, the insertRhizome function returns
  191. // a pointer to a PatternHandle.
  192. //
  193. // If the new pattern conflicts with a pattern already installed in the
  194. // database, meaning that the two patterns match some keys in common but each
  195. // also matches additional keys that the other does not, then the new pattern
  196. // is not inserted, and a value of 0 is returned as the PatternHandle.
  197. //
  198. PatternHandle
  199. insertRhizome(
  200. Rhizome *rhizome,
  201. char *value,
  202. char *mask,
  203. void *reference,
  204. ulong *status)
  205. {
  206. RhizomeNode *new_leaf;
  207. int index0, insert_status;
  208. *status = GPC_STATUS_SUCCESS;
  209. // Create new leaf and copy data into it; restrict set bits of value to
  210. // those set in mask, since later code assumes this is the case. Add new
  211. // leaf to reference table.
  212. NEW_RhizomeNode(&new_leaf);
  213. if (new_leaf == 0)
  214. {
  215. // Memory could not be allocated for this new node. Therefore, we
  216. // return an indication of failure to the client.
  217. *status = GPC_STATUS_RESOURCES;
  218. return 0;
  219. }
  220. for (index0 = 0; index0 < rhizome->keybytes; index0++)
  221. {
  222. VALUE(new_leaf)[index0] = value[index0] & mask[index0];
  223. MASK(new_leaf)[index0] = mask[index0];
  224. IMASK(new_leaf)[index0] = mask[index0];
  225. }
  226. new_leaf->REFERENCE = reference;
  227. new_leaf->pivot_bit = rhizome->keybits;
  228. new_leaf->GODPARENT = 0;
  229. // If tree is empty, leaf becomes first node; otherwise, attempt to insert
  230. // using recursive node_insert() routine. If new leaf conflicts with
  231. // existing leaf, node_insert() throws exception; then remove new leaf and
  232. // return failure code.
  233. if (rhizome->root == 0)
  234. {
  235. rhizome->root = new_leaf;
  236. }
  237. else
  238. {
  239. insert_status = node_insert(rhizome, new_leaf, &rhizome->root, -1);
  240. if (insert_status != GPC_STATUS_SUCCESS)
  241. {
  242. removeRhizome(rhizome, new_leaf);
  243. *status = GPC_STATUS_CONFLICT;
  244. return 0; // return null pointer
  245. };
  246. }
  247. return new_leaf;
  248. }
  249. // This function removes a pattern from the rhizome. The pattern is specified
  250. // by the PatternHandle that was returned by the insertRhizome function. No
  251. // checks are performed to insure that this is a valid handle.
  252. //
  253. void
  254. removeRhizome(
  255. Rhizome *rhizome,
  256. PatternHandle phandle)
  257. {
  258. // Call recursive node_remove() routine to remove all references to leaf;
  259. // then delete leaf.
  260. node_remove(rhizome, phandle, &rhizome->root);
  261. //TRACE(RHIZOME, rhizome, phandle, "removeRhizome")
  262. GpcFreeMem(phandle, NAT_TAG_RHIZOME);
  263. }
  264. // Insert new_leaf into subtree pointed to by *ppoint. Update *ppoint to point
  265. // to newly created nodes if necessary. Index of most recently examined bit
  266. // is given by prev_bit. The return value is a status code: Normally, it
  267. // returns GPC_STATUS_SUCCESS; if there is a conflict, then it returns NDIS_STATUS_CONFLICT;
  268. // if there is insufficient memory available to perform the insertion, then it
  269. // returns GPC_STATUS_RESOURCES.
  270. //
  271. static int
  272. node_insert(
  273. Rhizome *rhizome,
  274. RhizomeNode *new_leaf,
  275. RhizomeNode **ppoint,
  276. int prev_bit)
  277. {
  278. int index, index0, bit_value, insert_status;
  279. char sub, super;
  280. RhizomeNode *point, *child, *new_branch;
  281. // This routine has a recursive structure, but unnecessary recursions have
  282. // been replaced by iteration, in order to improve performance. This
  283. // recursion removal has introduced a forever loop which encloses the
  284. // entirety of the routine; looping back to the beginning of this loop is
  285. // thus the equivalent of recursing.
  286. while (1)
  287. {
  288. point = *ppoint;
  289. // Examine each bit index beginnig with that following last bit index
  290. // examined previously. Continue examining bits until pivot bit of
  291. // current node is reached (unless loop is terminated prematurely).
  292. for (index = prev_bit + 1; index < point->pivot_bit; index++)
  293. {
  294. // If some leaf in the current subtree cares about the value of the
  295. // current bit, and if the new leaf cares about the value of the
  296. // current bit, and these two leaves disagree about the value of
  297. // this bit, then a new branch node should be inserted here.
  298. if (BIT_OF(MASK(new_leaf), index) == 1 &&
  299. BIT_OF(MASK(point), index) == 1 &&
  300. BIT_OF(VALUE(new_leaf), index) != BIT_OF(VALUE(point), index))
  301. {
  302. // Create new branch node; insert into tree; and set fields.
  303. bit_value = BIT_OF(VALUE(new_leaf), index);
  304. NEW_RhizomeNode(&new_branch);
  305. if (new_branch == 0)
  306. {
  307. // Memory could not be allocated for this new node.
  308. // Therefore, we pass an indication of failure up the stack.
  309. return GPC_STATUS_RESOURCES;
  310. }
  311. *ppoint = new_branch;
  312. for (index0 = 0; index0 < rhizome->keybytes; index0++)
  313. {
  314. VALUE(new_branch)[index0] =
  315. VALUE(point)[index0] | VALUE(new_leaf)[index0];
  316. MASK(new_branch)[index0] =
  317. MASK(point)[index0] | MASK(new_leaf)[index0];
  318. IMASK(new_branch)[index0] =
  319. IMASK(point)[index0] & IMASK(new_leaf)[index0];
  320. }
  321. // Pivot bit of new branch node is the bit that inspired the
  322. // creation of this branch.
  323. new_branch->pivot_bit = index;
  324. // The earlier subtree becomes the child whose bit disagreed
  325. // with that of the new leaf.
  326. new_branch->CHILDREN[1 - bit_value] = point;
  327. // If every leaf in the subtree cares about the value of this
  328. // bit, then we can insert the new leaf as the other child of
  329. // this branch.
  330. if (BIT_OF(IMASK(point), index) == 1)
  331. {
  332. // Insert new leaf here and return.
  333. new_branch->CHILDREN[bit_value] = new_leaf;
  334. return GPC_STATUS_SUCCESS;
  335. }
  336. // Otherwise, at least one leaf in the earlier subtree does not
  337. // care about the value of this bit. Copy all such leaves
  338. // (and necessary branches) to the other child of the new
  339. // branch node.
  340. child = replicate(rhizome, point, index);
  341. if (child == 0)
  342. {
  343. // Memory could not be allocated for the replica.
  344. // Therefore, we remove the new node from the structure,
  345. // delete the new node, and pass an indication of failure
  346. // up the stack.
  347. *ppoint = point;
  348. GpcFreeMem(new_branch, NAT_TAG_RHIZOME);
  349. return GPC_STATUS_RESOURCES;
  350. }
  351. new_branch->CHILDREN[bit_value] = child;
  352. // Continue search on newly copied subtree.
  353. ppoint = &new_branch->CHILDREN[bit_value];
  354. point = *ppoint;
  355. }
  356. }
  357. // All bits have been examined up to the pivot bit of the current node.
  358. // If this node is a leaf, then we have found a leaf with which the new
  359. // leaf has no disagreements over bit values.
  360. if (point->pivot_bit >= rhizome->keybits)
  361. {
  362. // Loop up the chain of godparents until one of the four cases
  363. // below causes an exit from the subroutine.
  364. while (1)
  365. {
  366. // Case 1: We have reached the end of the godparent chain.
  367. if (point == 0)
  368. {
  369. // Insert new leaf at this point and return.
  370. *ppoint = new_leaf;
  371. return GPC_STATUS_SUCCESS;
  372. }
  373. // Case 2: We discover that we have already inserted this leaf
  374. // at the appropriate location. This can happen because two
  375. // leaves in separate parts of the tree may have a common god-
  376. // ancestor, and a leaf which is a further god-ancestor of that
  377. // leaf will be reached more than once. Since the first
  378. // occasion inserted the leaf, the second one can return without
  379. // performing any action.
  380. if (point == new_leaf)
  381. {
  382. return GPC_STATUS_SUCCESS;
  383. }
  384. // Compare mask bits of the new leaf to the current leaf.
  385. sub = 0;
  386. super = 0;
  387. for (index = 0; index < rhizome->keybytes; index++)
  388. {
  389. sub |= MASK(new_leaf)[index] & ~MASK(point)[index];
  390. super |= ~MASK(new_leaf)[index] & MASK(point)[index];
  391. }
  392. // Case 3: The new leaf cares about at least one bit that the
  393. // current leaf does not; and the current leaf does not care
  394. // about any bits that the new leaf does not; thus, the new leaf
  395. // should be a godchild of the current leaf.
  396. if (sub != 0 && super == 0)
  397. {
  398. // Update imask field of new leaf; insert into chain;
  399. // and return.
  400. for (index0 = 0; index0 < rhizome->keybytes; index0++)
  401. {
  402. IMASK(new_leaf)[index0] &= IMASK(point)[index0];
  403. }
  404. new_leaf->GODPARENT = point;
  405. *ppoint = new_leaf;
  406. return GPC_STATUS_SUCCESS;
  407. }
  408. // Case 4: Either the new leaf has the same value and mask as
  409. // the current leaf, or there is a hierarchy conflict between
  410. // the two leaves. In either case, terminate the insertion
  411. // process and clean up (in insert() routine) anything done
  412. // already.
  413. if (sub != 0 || super == 0)
  414. {
  415. return GPC_STATUS_CONFLICT;
  416. }
  417. // None of the above cases occurred; thus, the new leaf should
  418. // be a god-ancestor of the current leaf. Update the imask
  419. // field of the current leaf, and continue with godparent of
  420. // current leaf.
  421. for (index0 = 0; index0 < rhizome->keybytes; index0++)
  422. {
  423. IMASK(point)[index0] &= IMASK(new_leaf)[index0];
  424. }
  425. ppoint = &point->GODPARENT;
  426. point = *ppoint;
  427. }
  428. }
  429. // The current node is not a leaf node. Thus, we recurse on one or both
  430. // of the child nodes of the current node. First, update the fields of
  431. // the current node to reflect the insertion of the new leaf into the
  432. // subtree.
  433. for (index0 = 0; index0 < rhizome->keybytes; index0++)
  434. {
  435. VALUE(point)[index0] |= VALUE(new_leaf)[index0];
  436. MASK(point)[index0] |= MASK(new_leaf)[index0];
  437. IMASK(point)[index0] &= IMASK(new_leaf)[index0];
  438. }
  439. // If the new leaf doesn't care about the value of the pivot bit of the
  440. // current leaf, then we must recurse on both children. We can only
  441. // replace a single recursive call with iteration, so we perform a true
  442. // recursion in this case, and we recurse on child 1.
  443. if (BIT_OF(MASK(new_leaf), point->pivot_bit) == 0)
  444. {
  445. insert_status =
  446. node_insert(rhizome, new_leaf, &point->CHILDREN[1],
  447. point->pivot_bit);
  448. if (insert_status != GPC_STATUS_SUCCESS)
  449. {
  450. return insert_status;
  451. }
  452. }
  453. // Update the values of prev_bit and ppoint to reflect the same
  454. // conditions that would hold in a recursive call. The pseudo-recursion
  455. // is performed on the bit indicated by the value of the pivot bit of
  456. // the new leaf. If the new leaf does not care about this bit, then
  457. // this value will be a 0, and we recursed on child 1 above. If the new
  458. // leaf does care about the value of this bit, then we continue down the
  459. // appropriate path.
  460. prev_bit = point->pivot_bit;
  461. ppoint = &point->CHILDREN[BIT_OF(VALUE(new_leaf), point->pivot_bit)];
  462. }
  463. }
  464. // Remove references to leaf from subtree pointed to by *ppoint. Update *ppoint
  465. // if necessary due to removal of branch nodes.
  466. //
  467. static void
  468. node_remove(
  469. Rhizome *rhizome,
  470. RhizomeNode *leaf,
  471. RhizomeNode **ppoint)
  472. {
  473. int pivot_bit, bit_value, index0;
  474. RhizomeNode *point, *child, *child0, *child1;
  475. point = *ppoint;
  476. pivot_bit = point->pivot_bit;
  477. if (pivot_bit < rhizome->keybits)
  478. {
  479. // The current node is a branch node.
  480. if (BIT_OF(MASK(leaf), pivot_bit) == 1)
  481. {
  482. // The leaf to be removed cares about this node's pivot bit;
  483. // therefore, we need only recurse on one of the current node's
  484. // children.
  485. bit_value = BIT_OF(VALUE(leaf), pivot_bit);
  486. node_remove(rhizome, leaf, &point->CHILDREN[bit_value]);
  487. child = point->CHILDREN[bit_value];
  488. if (child != 0 && BIT_OF(MASK(child), pivot_bit) == 1)
  489. {
  490. // Some leaf in the same subtree as the removed leaf cares about
  491. // the value of this node's pivot bit; therefore, this node
  492. // still has reason to exist. Update its fields to reflect the
  493. // change in one of its subtrees.
  494. child0 = point->CHILDREN[0];
  495. child1 = point->CHILDREN[1];
  496. for (index0 = 0; index0 < rhizome->keybytes; index0++)
  497. {
  498. VALUE(point)[index0] =
  499. VALUE(child0)[index0] | VALUE(child1)[index0];
  500. MASK(point)[index0] =
  501. MASK(child0)[index0] | MASK(child1)[index0];
  502. IMASK(point)[index0] =
  503. IMASK(child0)[index0] & IMASK(child1)[index0];
  504. }
  505. }
  506. else
  507. {
  508. // No leaf in the same subtree as the removed leaf cares about
  509. // the value of this node's pivot bit; therefore, there is no
  510. // longer any reason for this node to exist. Have the other
  511. // subtree take the current node's place in the tree; call
  512. // remove() to remove the unneeded subtree; and delete the
  513. // current node.
  514. *ppoint = point->CHILDREN[1 - bit_value];
  515. if (child != 0)
  516. {
  517. eliminate(rhizome, child);
  518. }
  519. GpcFreeMem(point, NAT_TAG_RHIZOME);
  520. }
  521. }
  522. else
  523. {
  524. // The leaf to be removed does not care about this node's pivot bit;
  525. // therefore, we must recurse on both of the current node's
  526. // children. This node must still be necessary, since we have not
  527. // removed any leaf which cares about this node's value. So we
  528. // update its fields to reflect the change in its two subtrees.
  529. node_remove(rhizome, leaf, &point->CHILDREN[0]);
  530. node_remove(rhizome, leaf, &point->CHILDREN[1]);
  531. child0 = point->CHILDREN[0];
  532. child1 = point->CHILDREN[1];
  533. for (index0 = 0; index0 < rhizome->keybytes; index0++)
  534. {
  535. VALUE(point)[index0] =
  536. VALUE(child0)[index0] | VALUE(child1)[index0];
  537. MASK(point)[index0] =
  538. MASK(child0)[index0] | MASK(child1)[index0];
  539. IMASK(point)[index0] =
  540. IMASK(child0)[index0] & IMASK(child1)[index0];
  541. }
  542. }
  543. }
  544. else
  545. {
  546. // The current node is a leaf node.
  547. if (point == leaf)
  548. {
  549. // The current node is the leaf to be removed; therefore, remove it
  550. // from chain of godparents.
  551. *ppoint = leaf->GODPARENT;
  552. }
  553. else
  554. {
  555. // The current node is not leaf to be removed. Therefore, if this
  556. // node has a godparent, then recurse on that godparent. If this
  557. // node does not have a godparent, then the to-be-removed leaf
  558. // either already was removed by a different path, or it was never
  559. // inserted to begin with. The latter might be the case if remove()
  560. // was called from the catch clause of insert().
  561. if (point->GODPARENT != 0)
  562. {
  563. node_remove(rhizome, leaf, &point->GODPARENT);
  564. }
  565. // We are now popping back up the recursion stack. If this node
  566. // does not have a godparent, or if it did but it does not anymore,
  567. // then initialize imask to mask; otherwise, copy the godparent's
  568. // value of imask. Since the godparent chain follows a strict
  569. // hierarchy, and since imask is formed by successive conjunction,
  570. // all leaves in any given godparent chain will have the same value
  571. // of imask, namely the mask value of the highest god-ancestor.
  572. if (point->GODPARENT == 0)
  573. {
  574. for (index0 = 0; index0 < rhizome->keybytes; index0++)
  575. {
  576. IMASK(point)[index0] = MASK(point)[index0];
  577. }
  578. }
  579. else
  580. {
  581. for (index0 = 0; index0 < rhizome->keybytes; index0++)
  582. {
  583. IMASK(point)[index0] = IMASK(point->GODPARENT)[index0];
  584. }
  585. }
  586. }
  587. }
  588. }
  589. // Replicate all nodes in a subtree which do not care about the value of
  590. // pivot_bit.
  591. //
  592. static RhizomeNode *
  593. replicate(
  594. Rhizome *rhizome,
  595. RhizomeNode *source,
  596. int pivot_bit)
  597. {
  598. int index0, current_bit;
  599. RhizomeNode *new_node, *child0, *child1;
  600. // If this routine were fully recursive, the following while statement
  601. // would be an if statement. However, recursion has been replaced by
  602. // iteration where possible, so the following code loops until bottoming
  603. // out when a leaf node is reached.
  604. while (source->pivot_bit < rhizome->keybits)
  605. {
  606. if (BIT_OF(IMASK(source->CHILDREN[0]), pivot_bit) == 0)
  607. {
  608. if (BIT_OF(IMASK(source->CHILDREN[1]), pivot_bit) == 0)
  609. {
  610. // Both subtrees contain leaves which do not care about the
  611. // pivot bit; therefore, we may need to make a copy of the
  612. // current node. It is not guaranteed that we need to make
  613. // a copy, since it may be a common leaf in both subtrees
  614. // that does not care about the pivot bit. This may happen
  615. // for a leaf which is a godparent of two leaves, one in each
  616. // subtree. Recurse on each child and examine results.
  617. child0 = replicate(rhizome, source->CHILDREN[0], pivot_bit);
  618. if (child0 == 0)
  619. {
  620. // Memory could not be allocated for the child replica.
  621. // Therefore, we abort the replication process and pass an
  622. // indication of failure op the stack.
  623. return 0;
  624. }
  625. child1 = replicate(rhizome, source->CHILDREN[1], pivot_bit);
  626. if (child1 == 0)
  627. {
  628. // Memory could not be allocated for the child replica.
  629. // Therefore, we abort the replication process, eliminate
  630. // the other child replica, and pass an indication of
  631. // failure op the stack.
  632. eliminate(rhizome, child0);
  633. return 0; // return null pointer
  634. }
  635. current_bit = source->pivot_bit;
  636. if (BIT_OF(MASK(child0), current_bit) == 1)
  637. {
  638. if (BIT_OF(MASK(child1), current_bit) == 1)
  639. {
  640. // Both replicated child subtrees contain leaves which
  641. // care about the current node's bit. Since any node
  642. // which is a godparent of nodes in both subtrees could
  643. // not possibly care about the current node's bit, we
  644. // know that we need to make a copy of the current node.
  645. NEW_RhizomeNode(&new_node);
  646. if (new_node == 0)
  647. {
  648. // Memory could not be allocated for this new node.
  649. // Therefore, we have to eliminate both children
  650. // and pass an indication of failure up the stack.
  651. eliminate(rhizome, child0);
  652. eliminate(rhizome, child1);
  653. return 0; // return null pointer
  654. }
  655. for (index0 = 0; index0 < rhizome->keybytes; index0++)
  656. {
  657. VALUE(new_node)[index0] =
  658. VALUE(child0)[index0] | VALUE(child1)[index0];
  659. MASK(new_node)[index0] =
  660. MASK(child0)[index0] | MASK(child1)[index0];
  661. IMASK(new_node)[index0] =
  662. IMASK(child0)[index0] & IMASK(child1)[index0];
  663. }
  664. new_node->pivot_bit = current_bit;
  665. new_node->CHILDREN[0] = child0;
  666. new_node->CHILDREN[1] = child1;
  667. return new_node;
  668. }
  669. // Child 0's subtree contains a leaf that cares about the
  670. // current bit; however, child 1's subtree does not. Thus,
  671. // all leaves which are in child 1's subtree are also in
  672. // child 0's subtree, so we only need to keep the latter.
  673. // We therefore eliminate child 1's subtree, and we return
  674. // child 0 as the new subtree at this location, since we
  675. // do not need to create a new branch node here.
  676. eliminate(rhizome, child1);
  677. return child0;
  678. }
  679. // Child 0's subtree does not contain a leaf that cares about
  680. // the current node's bit. Thus, all leaves which are in child
  681. // 0's subtree are also in child 1's subtree, so we only need to
  682. // keep the latter. We therefore eliminate child 0's subtree,
  683. // and we return child 1 as the new subtree at this location,
  684. // since we do not need to create a new branch node here.
  685. eliminate(rhizome, child0);
  686. return child1;
  687. }
  688. // Child 0's subtree contains a leaf which does not care about the
  689. // pivot bit; however, child 1's subtree does not. Therefore, we
  690. // recurse on child 0. Rather than truly recursing, we update the
  691. // value of source and iterate once through the while loop.
  692. source = source->CHILDREN[0];
  693. }
  694. else
  695. {
  696. // Child 0's subtree does not contain a leaf which does not care
  697. // about the pivot bit. Child 1's subtree must contain such a leaf,
  698. // since the current node's subtree contains such a leaf. Thus, we
  699. // recurse on child 1. Rather than truly recursing, we update the
  700. // value of source and iterate once through the while loop.
  701. source = source->CHILDREN[1];
  702. }
  703. }
  704. // A leaf node has been reached. We now iterate through the godparents of
  705. // the leaf until we find one which does not care about the pivot bit.
  706. // Once we find it, we know that all godparents of that leaf also do not
  707. // care about the pivot bit, since the godparents are arranged in a strict
  708. // hierarchy. We thus return the first leaf found which does not care about
  709. // the value of the pivot bit.
  710. while (BIT_OF(MASK(source), pivot_bit) == 1)
  711. {
  712. source = source->GODPARENT;
  713. }
  714. return source;
  715. }
  716. // Eliminate an entire subtree.
  717. //
  718. static void
  719. eliminate(
  720. Rhizome *rhizome,
  721. RhizomeNode *point)
  722. {
  723. RhizomeNode *child;
  724. // Partial recursion removal. The while loop takes the place of one of the
  725. // recursive calls to eliminate(). We eliminate each node and recursively
  726. // eleminate each subtree under the node. We do not eliminate leaves, since
  727. // there is only one copy of each leaf stored in the entire structure.
  728. while (point->pivot_bit < rhizome->keybits)
  729. {
  730. eliminate(rhizome, point->CHILDREN[0]);
  731. child = point->CHILDREN[1];
  732. GpcFreeMem(point, NAT_TAG_RHIZOME);
  733. point = child;
  734. }
  735. }
  736. // Coalesce leaves of subtree into a linked list and eliminate subtree. This
  737. // routine is called by the destructor so that it can deallocate the leaf nodes
  738. // after the branch nodes are eliminated.
  739. //
  740. static void
  741. coalesce(
  742. Rhizome *rhizome,
  743. RhizomeNode **leaf_list,
  744. RhizomeNode *point)
  745. {
  746. RhizomeNode *child, *godparent;
  747. // Partial recursion removal. This while loop takes the place of one of
  748. // the recursive calls to coalesce(). This performs an inorder traversal.
  749. // We delete each branch node after we have visited it, just as in the
  750. // eliminate() routine.
  751. while (point->pivot_bit < rhizome->keybits && point->pivot_bit >= 0)
  752. {
  753. coalesce(rhizome, leaf_list, point->CHILDREN[0]);
  754. child = point->CHILDREN[1];
  755. GpcFreeMem(point, NAT_TAG_RHIZOME);
  756. point = child;
  757. }
  758. // Once we have found a leaf, we search through the chain of godparents,
  759. // adding to the list each leaf node that is not already in the list.
  760. // A pivot_bit of -1 indicates that the leaf is already in the list.
  761. // If a leaf is in the list, then so are all of its godparents.
  762. while (point != 0 && point->pivot_bit >= 0)
  763. {
  764. godparent = point->GODPARENT;
  765. point->pivot_bit = -1;
  766. point->GODPARENT = *leaf_list;
  767. *leaf_list = point;
  768. point = godparent;
  769. }
  770. }