Debian Codegraph @

protolib/src/common/protoTree.cpp

raw
1
2 /*********************************************************************
3 *
4 * AUTHORIZATION TO USE AND DISTRIBUTE
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that:
8 *
9 * (1) source code distributions retain this paragraph in its entirety,
10 *
11 * (2) distributions including binary code include this paragraph in
12 * its entirety in the documentation or other materials provided
13 * with the distribution, and
14 *
15 * (3) all advertising materials mentioning features or use of this
16 * software display the following acknowledgment:
17 *
18 * "This product includes software written and developed
19 * by Brian Adamson of the Naval Research Laboratory (NRL)."
20 *
21 * The name of NRL, the name(s) of NRL employee(s), or any entity
22 * of the United States Government may not be used to endorse or
23 * promote products derived from this software, nor does the
24 * inclusion of the NRL written and developed software directly or
25 * indirectly suggest NRL or United States Government endorsement
26 * of this product.
27 *
28 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
29 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
30 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
31 ********************************************************************/
32 /**
33 * @file protoTree.cpp
34 *
35 * @brief This is a general purpose prefix-based C++ Patricia tree.
36 * The code also provides an ability to iterate over items with a
37 * common prefix of arbitrary bit length
38 */
39 #include "protoTree.h"
40 #include "protoDebug.h" // for PLOG()
41
42 #include <string.h>
43 #include <stdlib.h> // for labs()
44
45 ProtoTree::Item::Item()
46 : bit(0), parent((Item*)NULL), left((Item*)NULL), right((Item*)NULL)
47 {
48 }
49
50 ProtoTree::Item::~Item()
51 {
52 }
53
54 unsigned int ProtoTree::Item::GetDepth() const
55 {
56 unsigned int depth = 0;
57 const Item* p = this;
58 while (NULL != (p = p->parent)) depth++;
59 return depth;
60 } // end ProtoTree::Item::GetDepth()
61
62 ProtoTree::ItemPool::ItemPool()
63 : head(NULL)
64 {
65 }
66
67 ProtoTree::ItemPool::~ItemPool()
68 {
69 Destroy();
70 }
71
72 void ProtoTree::ItemPool::Destroy()
73 {
74 Item* item;
75 while ((item = Get())) delete item;
76 } // end ProtoTree::ItemPool::Destroy()
77
78 ProtoTree::Item* ProtoTree::ItemPool::Get()
79 {
80 Item* item = head;
81 if (NULL != item) head = item->GetPoolNext();
82 return item;
83 } // end ProtoTree::ItemPool::Get()
84
85 void ProtoTree::ItemPool::Put(Item& item)
86 {
87 item.SetPoolNext(head);
88 head = &item;
89 } // end ProtoTree::ItemPool::Put()
90
91 ProtoTree::ProtoTree()
92 : root((Item*)NULL)
93 {
94 }
95
96 ProtoTree::~ProtoTree()
97 {
98 }
99
100 void ProtoTree::Empty()
101 {
102 root = (ProtoTree::Item*)NULL;
103 UpdateIterators(NULL, Iterator::EMPTY);
104 } // end ProtoTree::Empty()
105
106 void ProtoTree::Destroy()
107 {
108 while (NULL != root)
109 {
110 Item* item = root;
111 Remove(*item);
112 delete item;
113 }
114 } // end ProtoTree::Destroy()
115
116 bool ProtoTree::PrefixIsEqual(const char* key,
117 unsigned int keysize,
118 const char* prefix,
119 unsigned int prefixSize,
120 Endian keyEndian)
121 {
122 if (prefixSize > keysize) return false;
123 unsigned int fullByteCount = (prefixSize >> 3);
124 unsigned int remBitCount = prefixSize & 0x07;
125 if (ENDIAN_BIG == keyEndian)
126
127 {
128 // Compare any "remainder bits" of the "prefix" to the
129 // corresponding bits of the "key"
130 // (we do this first to possibly avoid call to "memcmp()" below)
131 if (0 != remBitCount)
132 {
133 char remBitMask = (unsigned char)0xff << (8 - remBitCount);
134 // "remainder bits" are in last byte of big endian "prefix"
135 if ((key[fullByteCount] & remBitMask) != (prefix[fullByteCount] & remBitMask))
136 return false;
137 }
138 }
139 else
140 {
141 // Adjust "key" ptr to point at its prefix portion
142 key += (keysize >> 3);
143 if (0 != (keysize &0x07)) key++;
144 key -= fullByteCount;
145 // Compare any "remainder bits" of the "prefix" to the
146 // corresponding bits of the "key"
147 // (we do this first to possibly avoid call to "memcmp()" below)
148 if (0 != remBitCount)
149 {
150 char remBitMask = 0xff << (8 - remBitCount);
151 // "remainder bits" are in first byte of little endian "prefix"
152 if ((key[0] & remBitMask) != (prefix[0] & remBitMask))
153 return false;
154
155 // Compare any full byte portion of the key / prefix
156 if (0 != fullByteCount)
157 return (0 == memcmp(key+1, prefix+1, fullByteCount));
158 else
159 return true;
160 }
161 }
162 // Compare any full byte portion of the "prefix"
163 // to the corresponding "key" bytes
164 if (0 != fullByteCount)
165 return (0 == memcmp(key, prefix, fullByteCount));
166 else
167 return true;
168 } // end ProtoTree::PrefixIsEqual()
169
170 bool ProtoTree::KeysAreEqual(const char* key1,
171 const char* key2,
172 unsigned int keysize,
173 Endian keyEndian)
174 {
175 unsigned int fullByteCount = keysize >> 3;
176 unsigned int remBitCount = keysize & 0x07;
177 if (0 != remBitCount)
178 {
179 // Compare any "remainder bits" of the keys
180 // (we do this first to possibly avoid call to "memcmp()" below)
181 char remBitMask = 0xff << (8 - remBitCount);
182 if (ENDIAN_BIG == keyEndian)
183 {
184 // "remainder bits" are in last byte of big endian keys
185 if ((key1[fullByteCount] & remBitMask) != (key2[fullByteCount] & remBitMask))
186 return false;
187 }
188 else
189 {
190 // "remainder bits" are in first byte of little endian keys
191 if ((key1[0] & remBitMask) != (key2[0] & remBitMask))
192 return false;
193 // Compare any full byte portion of the keys
194 if (0 != fullByteCount)
195 return (0 == memcmp(key1+1, key2+1, fullByteCount));
196 else
197 return true;
198 }
199 }
200 // Compare any full bytes of the keys
201 if (0 != fullByteCount)
202 return (0 == memcmp(key1, key2, fullByteCount));
203 else
204 return true;
205 } // end ProtoTree::KeysAreEqual()
206
207 bool ProtoTree::ItemsAreEqual(const Item& item1, const Item& item2)
208 {
209 unsigned int keysize = item1.GetKeysize();
210 if (item2.GetKeysize() != keysize) return false;
211 Endian keyEndian = item1.GetEndian();
212 if (keyEndian != item2.GetEndian())
213 {
214 PLOG(PL_WARN, "ProtoTree::ItemsAreEqual() mis-matched key endian?!\n");
215 ASSERT(0);
216 return false;
217 }
218 return KeysAreEqual(item1.GetKey(), item2.GetKey(), keysize, keyEndian);
219 } // end ProtoTree::ItemsAreEqual()
220
221 bool ProtoTree::ItemIsEqual(const Item& item, const char* key, unsigned int keysize)
222 {
223 if (item.GetKeysize() != keysize) return false;
224 return KeysAreEqual(item.GetKey(), key, keysize, item.GetEndian());
225 } // end ProtoTree::ItemIsEqual()
226
227 bool ProtoTree::Bit(const char* key, unsigned int keysize, unsigned int index, Endian keyEndian)
228 {
229 if (index < keysize)
230 {
231 unsigned int byteIndex = index >> 3;
232 byteIndex = (ENDIAN_BIG == keyEndian) ? byteIndex : ((keysize - 1) >> 3) - byteIndex;
233 return (0 != (key[byteIndex] & (0x80 >> (index & 0x07))));
234 }
235 else if (index < (keysize + (sizeof(keysize) << 3)))
236 {
237 index -= keysize;
238 return (0 != (((char*)&keysize)[index >> 3] & (0x80 >> (index & 0x07))));
239 }
240 else
241 {
242 return false;
243 }
244 } // end ProtoTree::Bit()
245
246 ProtoTree::Item* ProtoTree::GetFirstItem() const
247 {
248 if (NULL != root)
249 {
250 if (root->left == root->right)
251 {
252 // 2-A) Only one node in this tree
253 return root;
254 }
255 else
256 {
257 // 2-B) Return left most node in this tree
258 Item* x = (root->left == root) ? root->right : root;
259 while (x->left->parent == x) x = x->left;
260 return (x->left);
261 }
262 }
263 return NULL;
264 } // end ProtoTree::GetFirstItem()
265
266 ProtoTree::Item* ProtoTree::GetLastItem() const
267 {
268 if (NULL != root)
269 {
270 // 2) Follow root or left of root all the way to right to find
271 // the last item (lexically) in the tree
272 Item* x = (root->right == root) ? root->left : root;
273 Item* p;
274 do
275 {
276 p = x;
277 x = x->right;
278 } while (p == x->parent);
279 return x;
280 }
281 return NULL;
282 } // end ProtoTree::GetLastItem()
283
284 bool ProtoTree::Insert(ProtoTree::Item& item)
285 {
286 if (NULL != root)
287 {
288 // 1) Find closest match to "item"
289 const char* key = item.GetKey();
290 unsigned int keysize = item.GetKeysize();
291 Endian keyEndian = item.GetEndian();
292 Item* x = root;
293 Item* p;
294 do
295 {
296 p = x;
297 x = Bit(key, keysize, x->bit, keyEndian) ? x->right : x->left;
298 } while (p == x->parent);
299
300 // 2) Then, find index of first differing bit ("dBit")
301 // (also look out for exact match!)
302 unsigned int dBit = 0;
303 // A) Do byte-wise comparison to extent possible
304 unsigned int keysizeMin, indexMax;
305 if (keysize < x->GetKeysize())
306 {
307 keysizeMin = keysize;
308 indexMax = x->GetKeysize() + (sizeof(unsigned int) << 3);
309 }
310 else
311 {
312 keysizeMin = x->GetKeysize();
313 indexMax = keysize + (sizeof(unsigned int) << 3);
314 }
315 const char* ptr1 = key;
316 const char* ptr2 = x->GetKey();
317 ASSERT(x->GetEndian() == keyEndian);
318 if (ENDIAN_LITTLE == keyEndian)
319 {
320 ptr1 += ((keysize - 1) >> 3);
321 ptr2 += ((x->GetKeysize() - 1) >> 3);
322 }
323 unsigned int fullByteBits = keysizeMin & ~0x07;
324 while (dBit < fullByteBits)
325 {
326 if (*ptr1 != *ptr2)
327 {
328 // B) Do bit-wise comparison on differing byte
329 unsigned char delta = *ptr1 ^ *ptr2;
330 ASSERT(0 != delta);
331 while (delta < 0x80)
332 {
333 delta <<= 1;
334 dBit++;
335 }
336 break;
337 }
338 if (ENDIAN_BIG == keyEndian)
339 {
340 ptr1++;
341 ptr2++;
342 }
343 else
344 {
345 ptr1--;
346 ptr2--;
347 }
348 dBit += 8;
349 }
350 ASSERT(dBit <= fullByteBits);
351 if (dBit == fullByteBits)
352 {
353 // C) Compare any remainder bit-by-bit
354 for (; dBit < indexMax; dBit++)
355 {
356 if (Bit(key, keysize, dBit, keyEndian) != Bit(x->GetKey(), x->GetKeysize(), dBit, keyEndian))
357 break;
358 }
359 if (dBit == indexMax)
360 {
361 PLOG(PL_WARN, "ProtoTree::Insert() Equivalent item already in tree!\n");
362 //ASSERT(0);
363 return false;
364 }
365 }
366 item.bit = dBit;
367
368 // 3) Find "item" insertion point
369 x = root;
370 do
371 {
372 p = x;
373 x = Bit(key, keysize, x->bit, keyEndian) ? x->right : x->left;
374 } while ((x->bit < dBit) && (p == x->parent));
375
376
377 // 4) Insert "item" into tree
378 if (Bit(key, keysize, dBit, keyEndian))
379 {
380 ASSERT(NULL != x);
381 item.left = x;
382 item.right = &item;
383 }
384 else
385 {
386 item.left = &item;
387 item.right = x;
388 }
389 item.parent = p;
390 if (Bit(key, keysize, p->bit, keyEndian))
391 p->right = &item;
392 else
393 p->left = &item;
394 if (p == x->parent)
395 x->parent = &item;
396 }
397 else
398 {
399 // tree is empty, so make "item" the tree root
400 root = &item;
401 item.parent = (Item*)NULL;
402 item.left = item.right = &item;
403 item.bit = 0;
404 }
405 // Note for ProtoTree, we call UpdateIterators() _after_
406 // insertion/removal since we just reset the iterators
407 UpdateIterators(&item, Iterator::INSERT);
408 return true;
409 } // end ProtoTree::Insert()
410
411 // Find node with backpointer to "item"
412 ProtoTree::Item* ProtoTree::FindPredecessor(ProtoTree::Item& item) const
413 {
414 // Find terminal "q" with backpointer to "item"
415 Item* x = &item;
416 Item* q;
417 const char* key = item.GetKey();
418 unsigned int keysize = item.GetKeysize();
419 Endian keyEndian = item.GetEndian();
420 do
421 {
422 q = x;
423 if (Bit(key, keysize, x->bit, keyEndian))
424 x = x->right;
425 else
426 x = x->left;
427 } while (x != &item);
428 return q;
429 } // end ProtoTree::FindPredecessor()
430
431 void ProtoTree::Remove(ProtoTree::Item& item)
432 {
433 ASSERT(0 != item.GetKeysize());
434 if (((&item == item.left) || (&item == item.right)) && (NULL != item.parent))
435 {
436 // non-root "item" that has at least one self-pointer
437 // (a.k.a an "external entry"?)
438 Item* orphan = (&item == item.left) ? item.right : item.left;
439 if (item.parent->left == &item)
440 item.parent->left = orphan;
441 else
442 item.parent->right = orphan;
443 if (orphan->bit > item.parent->bit)
444 orphan->parent = item.parent;
445 }
446 else
447 {
448 // Root or "item" with no self-pointers
449 // (a.k.a an "internal entry"?)
450 // 1) Find terminal "q" with backpointer to "item"
451 const char* key = item.GetKey();
452 unsigned int keysize = item.GetKeysize();
453 Endian keyEndian = item.GetEndian();
454 Item* x = &item;
455 Item* q;
456 do
457 {
458 q = x;
459 if (Bit(key, keysize, x->bit, keyEndian))
460 x = x->right;
461 else
462 x = x->left;
463 } while (x != &item);
464
465 if (NULL != q->parent)
466 {
467 // Non-root "q", so "q" is moved into the place of "item"
468 Item* s = NULL;
469 if (NULL == item.parent)
470 {
471 // There are always two nodes backpointing to "root"
472 // (unless root is the only node in the tree)
473 // "s" is the other of these besides "q"
474 // (We need to find "s" before we mess with the tree)
475 x = Bit(key, keysize, item.bit, keyEndian) ? item.left : item.right;
476 do
477 {
478 s = x;
479 if (Bit(key, keysize, x->bit, keyEndian))
480 x = x->right;
481 else
482 x = x->left;
483 } while (x != &item);
484 }
485
486 // A) Set bit index of "q" to that of "item"
487 q->bit = item.bit;
488
489 // B) Fix the parent, left, and right node pointers to "q"
490 // (removes "q" from its current place in the tree)
491 Item* parent = q->parent;
492 Item* child = (q->left == &item) ? q->right : q->left;
493 ASSERT(NULL != child);
494 if (parent->left == q)
495 parent->left = child;
496 else
497 parent->right = child;
498 if (child->bit > parent->bit)
499 child->parent = parent;
500
501 // C) Fix the item's left->parent and right->parent node pointers to "item"
502 // (places "q" into the current place of the "item" in the tree)
503 ASSERT(q != NULL);
504 if (item.left->parent == &item)
505 item.left->parent = q;
506 if (item.right->parent == &item)
507 item.right->parent = q;
508 if (NULL != item.parent)
509 {
510 if (item.parent->left == &item)
511 item.parent->left = q;
512 else
513 item.parent->right = q;
514 }
515 else
516 {
517 // "item" was root node, so update the "s" node
518 // backpointer to "q" instead of "item"
519 ASSERT(s != NULL);
520 ASSERT(s != &item);
521 if (s->left == &item)
522 s->left = q;
523 else
524 s->right = q;
525 root = q;
526 }
527
528 // E) Finally, "q" gets the pointers of the "item" being removed
529 // (which now _may_ include a pointer to itself)
530 if (NULL != item.parent)
531 ASSERT((&item != item.left) && (&item != item.right));
532 q->parent = item.parent;
533 q->left = (item.left == &item) ? q : item.left;
534 q->right = (item.right == &item) ? q : item.right;
535 }
536 else
537 {
538 // "root" is removed with none or one item left
539 ASSERT(q == &item);
540 Item* orphan = (q == q->left) ? q->right : q->left;
541 if (q == orphan)
542 {
543 root = (Item*)NULL;
544 }
545 else
546 {
547 root = orphan;
548 orphan->parent = NULL;
549 if (orphan->left == q)
550 orphan->left = orphan;
551 else
552 orphan->right = orphan;
553 orphan->bit = 0;
554 }
555 }
556 }
557 item.parent = item.left = item.right = (Item*)NULL;
558 UpdateIterators(&item, Iterator::REMOVE);
559 } // end ProtoTree::Remove()
560
561 ProtoTree::Item* ProtoTree::RemoveRoot()
562 {
563 Item* item = root;
564 if (NULL != item) Remove(*item);
565 return item;
566 } // end ProtoTree::RemoveRoot()
567
568
569 /**
570 * Find item with exact match to key and keysize
571 */
572 ProtoTree::Item* ProtoTree::Find(const char* key,
573 unsigned int keysize) const
574 {
575 Item* x = root;
576 if (NULL != x)
577 {
578 Endian keyEndian = x->GetEndian();
579 Item* p;
580 do
581 {
582 p = x;
583 x = Bit(key, keysize, x->bit, keyEndian) ? x->right : x->left;
584 } while (x->parent == p);
585 return (ItemIsEqual(*x, key, keysize) ? x : NULL);
586 }
587 else
588 {
589 return (Item*)NULL;
590 }
591 } // end ProtoTree::Find()
592
593 /**
594 * Find item with "closest" match to key and keysize (biggest prefix match?)
595 */
596 ProtoTree::Item* ProtoTree::FindClosestMatch(const char* key,
597 unsigned int keysize) const
598 {
599 Item* x = root;
600 if (NULL != x)
601 {
602 Endian keyEndian = x->GetEndian();
603 Item* p;
604 do
605 {
606 p = x;
607 x = Bit(key, keysize, x->bit, keyEndian) ? x->right : x->left;
608 } while ((x->parent == p) && (x->bit < keysize));
609 return x;
610 }
611 else
612 {
613 return (Item*)NULL;
614 }
615 } // end ProtoTree::FindClosestMatch()
616
617 /**
618 * Finds longest matching entry that is a prefix to "key"
619 */
620 ProtoTree::Item* ProtoTree::FindPrefix(const char* key,
621 unsigned int keysize) const
622 {
623 // (TBD) Retest this code with new "size-agnostic" ProtoTree implementation
624 Item* x = root;
625 if (NULL != x)
626 {
627 Endian keyEndian = x->GetEndian();
628 Item* p;
629 do
630 {
631 p = x;
632 x = Bit(key, keysize, x->bit, keyEndian) ? x->right : x->left;
633 } while ((x->parent == p) && (x->bit < keysize));
634 if (PrefixIsEqual(key, keysize, x->GetKey(), x->GetKeysize(), keyEndian))
635 return x;
636 }
637 return NULL;
638 } // end ProtoTree::FindPrefix()
639
640
641 /**
642 * This finds prefix subtree root, (TBD) add find prefix
643 * subtree min, and find prefix subtree max methods
644 * (e.g. for "min", first find subtree root, and roll left ???)
645 */
646 ProtoTree::Item* ProtoTree::FindPrefixSubtree(const char* prefix,
647 unsigned int prefixSize) const
648 {
649 // (TBD) Retest this code more with new "size-agnostic" ProtoTree implementation
650 Item* x = root;
651 if (NULL != x)
652 {
653 Endian keyEndian = x->GetEndian();
654 Item* p;
655 do
656 {
657 p = x;
658 x = Bit(prefix, prefixSize, x->bit, keyEndian) ? x->right : x->left;
659 } while ((x->parent == p) && (x->bit < prefixSize));
660 if (PrefixIsEqual(x->GetKey(), x->GetKeysize(), prefix, prefixSize, keyEndian))
661 return x;
662 }
663 return (Item*)NULL;
664 } // end ProtoTree::FindPrefixSubtree()
665
666
667 ProtoTree::Iterator::Iterator(ProtoTree& theTree, bool reverse, ProtoTree::Item* cursor)
668 : ProtoIterable::Iterator(theTree), prefix_size(0), prefix_item(NULL)
669 {
670 if (NULL != cursor)
671 {
672 reversed = reverse;
673 SetCursor(*cursor);
674 }
675 else
676 {
677 Reset(reverse); // Reset() sets all to defaults
678 }
679 }
680
681 ProtoTree::Iterator::~Iterator()
682 {
683 }
684
685 void ProtoTree::Iterator::Reset(bool reverse,
686 const char* prefix,
687 unsigned int prefixSize)
688 {
689 ProtoTree* tree = static_cast<ProtoTree*>(iterable);
690
691 prefix_size = 0;
692 prefix_item = prev = next = curr_hop = (Item*)NULL;
693 if ((NULL == tree) || (NULL == tree->root)) return;
694
695 if (0 != prefixSize)
696 {
697 if (NULL == prefix) return;
698 // Find root of subtree with matching prefix
699 // (TBD - there's a better way to find the min/max prefix matches via prefix00000 or prefix11111
700 ProtoTree::Item* prefixItem = tree->FindPrefixSubtree(prefix, prefixSize);
701 if (NULL == prefixItem) return;
702 // Temporarily "Reset()" the iterator and "SetCursor()" to find
703 reversed = reverse ? false : true;
704 SetCursor(*prefixItem);
705 Endian keyEndian = prefixItem->GetEndian();
706 if (reverse)
707 {
708 // Find the maximum value with matching prefix.
709 ProtoTree::Item* lastItem;
710 while (NULL != (lastItem = GetNextItem()))
711 {
712 if (!tree->PrefixIsEqual(lastItem->GetKey(), lastItem->GetKeysize(), prefix, prefixSize, keyEndian))
713 break; // The "cursor" is set to after the last matching item
714 }
715 if (NULL == lastItem) Reset(reverse);
716 }
717 else
718 {
719 // Find the minimum value with matching prefix.
720 ProtoTree::Item* firstItem;
721 while (NULL != (firstItem = GetPrevItem()))
722 {
723 if (!tree->PrefixIsEqual(firstItem->GetKey(), firstItem->GetKeysize(), prefix, prefixSize, keyEndian))
724 break; // The "cursor" is set to before the first matching item
725 }
726 if (NULL == firstItem) Reset(reverse);
727 }
728 prefix_size = prefixSize;
729 prefix_item = prefixItem;
730 return;
731 }
732
733 if (reverse)
734 {
735 // This code is basically the same as ProtoTree::GetLastItem()
736 if (NULL != tree->root)
737 {
738 // Follow left of root all the way to right to find
739 // the very last item (lexically) in the tree
740 Item* x = (tree->root->right == tree->root) ? tree->root->left : tree->root;
741 Item* p;
742 do
743 {
744 p = x;
745 x = x->right;
746 } while (p == x->parent);
747 prev = x;
748 }
749 reversed = true;
750 }
751 else
752 {
753 // This code is basically the same as ProtoTree::GetFirstItem()
754 // (although the code to find the "curr_hop" for iteration is different)
755 if (NULL != tree->root)
756 {
757 if (tree->root->left == tree->root->right)
758 {
759 // Only one entry in the tree
760 next = tree->root;
761 curr_hop = NULL;
762 }
763 else
764 {
765 // If root has a left side, go as far left as possible
766 // to find the very first item (lexically) in the tree
767 Item* x = (tree->root->left == tree->root) ? tree->root->right : tree->root;
768 while (x->left->parent == x) x = x->left;
769 next = x->left;
770 if (x->right->parent == x)
771 {
772 // Branch right and go as far left as possible
773 x = x->right;
774 while (x->left->parent == x) x = x->left;
775 }
776 curr_hop = x;
777 }
778 }
779 reversed = false;
780 }
781 } // end ProtoTree::Iterator::Reset()
782
783 void ProtoTree::Iterator::SetCursor(ProtoTree::Item& item)
784 {
785 ProtoTree* tree = static_cast<ProtoTree*>(iterable);
786 // Save prefix subtree info
787 unsigned int prefixSize = prefix_size;
788 ProtoTree::Item* prefixItem = prefix_item;
789 prefix_size = 0;
790 prefix_item = NULL;
791
792 if ((NULL== tree) || (NULL == tree->root))
793 {
794 prev = next = curr_hop = NULL;
795 }
796 else if (tree->root->left == tree->root->right)
797 {
798 ASSERT(&item == tree->root);
799 curr_hop = NULL;
800 if (reversed)
801 {
802 prev = NULL;
803 next = tree->root;
804 }
805 else
806 {
807 prev = tree->root;
808 next = NULL;
809 }
810 }
811 else if (reversed)
812 {
813 // Setting "cursor" for "reversed" iteration is easy.
814 curr_hop = NULL;
815 prev = &item;
816 GetPrevItem(); // note this sets "next"
817 }
818 else
819 {
820 // Setting "cursor" for forward iteration is a little more complicated.
821 // Given an "item", we can find the "curr_hop" for the tree
822 // entry that lexically precedes the "item"
823 // (We do a reverse iteration to find that preceding entry)
824 reversed = true;
825 prev = &item;
826 GetPrevItem(); // note "GetPrevItem()" also sets "next" as needed
827 if (NULL == GetPrevItem())
828 {
829 Reset(false);
830 // Move forward one place so "cursor" is correct position
831 GetNextItem();
832 }
833 else
834 {
835 // This finds the proper "curr_hop" that goes with
836 // the entry previous of "item" ...
837 if ((&item != tree->root) || (item.right != &item))
838 {
839 // Find the node's "predecessor"
840 // (has backpointer to "item"
841 curr_hop = tree->FindPredecessor(item);
842 }
843 else
844 {
845 // Instead, use the other node with backpointer to root "item"
846 ASSERT(&item == tree->root);
847 const char* key = item.GetKey();
848 unsigned int keysize = item.GetKeysize();
849 Endian keyEndian = item.GetEndian();
850 Item* s;
851 Item* x = tree->Bit(key, keysize, item.bit, keyEndian) ? item.left : item.right;
852 ASSERT((x == item.left) || (x == item.right));
853 do
854 {
855 s = x;
856 if (tree->Bit(key, keysize, x->bit, keyEndian))
857 x = x->right;
858 else
859 x = x->left;
860 } while (x != &item);
861 curr_hop = s;
862 }
863 // Move forward two places so "cursor" is correct position
864 reversed = false;
865 GetNextItem();
866 GetNextItem();
867 }
868 }
869 // Restore prefix subtree info
870 if (0 != prefixSize)
871 {
872 prefix_item = prefixItem;
873 prefix_size = prefixSize;
874 }
875 } // end ProtoTree::Iterator::SetCursor()
876
877 ProtoTree::Item* ProtoTree::Iterator::GetPrevItem()
878 {
879 if (NULL != prev)
880 {
881 ProtoTree* tree = static_cast<ProtoTree*>(iterable);
882 if (!reversed)
883 {
884 // This iterator has been moving forward
885 // so we need to turn it around.
886 reversed = true;
887 // temporarily suspend prefix matching (if applicable) to allow turn-around
888 unsigned savePrefixSize = prefix_size;
889 prefix_size = 0;
890 GetPrevItem();
891 prefix_size = savePrefixSize;
892 if (NULL == prev) return NULL;
893 }
894 Item* item = prev;
895 Endian keyEndian = item->GetEndian();
896 if (0 != prefix_size)
897 {
898 // Test "item" against our reference "prefix_item"
899 if ((NULL == prefix_item) ||
900 !tree->PrefixIsEqual(item->GetKey(), item->GetKeysize(), prefix_item->GetKey(), prefix_size, keyEndian))
901 {
902 prev = NULL;
903 return NULL;
904 }
905 }
906
907 Item* x;
908 // Find node "q" with backpointer to "item"
909 if ((NULL == item->parent) && (item->right == item))
910 x = item->left;
911 else
912 x = item;
913 Item* q;
914 do
915 {
916 q = x;
917 if (tree->Bit(item->GetKey(), item->GetKeysize(), x->bit, keyEndian))
918 x = x->right;
919 else
920 x = x->left;
921 } while (x != prev);
922
923 if (q->right != item)
924 {
925 // Go up the tree
926 do
927 {
928 x = q;
929 q = q->parent;
930 } while ((NULL != q) && (x == q->left));
931
932 if ((NULL == q) || (NULL == q->parent))
933 {
934 if ((NULL == q) || (q->left == q))
935 {
936 // We've bubbled completely up or
937 // root has no left side, so we're done
938 prev = NULL;
939 }
940 else
941 {
942 // We've iterated to root from the right side
943 // and root has a left side we should check out
944 // So, find the left-side predecessor to root "q"
945 Item* r = q;
946 x = q->left;
947 do
948 {
949 q = x;
950 if (tree->Bit(r->GetKey(), r->GetKeysize(), x->bit, keyEndian))
951 x = x->right;
952 else
953 x = x->left;
954 } while (x != r);
955 if (q->left != q)
956 {
957 // Go as far right of "q->left" as possible
958 q = q->left;
959 do
960 {
961 x = q;
962 q = q->right;
963 } while (x == q->parent);
964 }
965 prev = q;
966 }
967 next = item;
968 return item;
969 }
970 } // end if (q->right != prev)
971
972 if (q->left->parent != q)
973 {
974 if ((NULL == q->left->parent) &&
975 (q->left->left != q->left) &&
976 tree->Bit(q->GetKey(), q->GetKeysize(), 0, keyEndian))
977 {
978 // We've come from the right and there is a left of root
979 // So, go as far right of the left of root "q->left" as possible
980 x = q->left->left;
981 do
982 {
983 q = x;
984 x = x->right;
985 } while (q == x->parent);
986 prev = x;
987 }
988 else
989 {
990 // Otherwise, this is the appropriate iterate
991 prev = q->left;
992 }
993 }
994 else
995 {
996 // Go as far right of "q->left" as possible
997 x = q->left;
998 do
999 {
1000 q = x;
1001 x = x->right;
1002 } while (q == x->parent);
1003 prev = x;
1004 }
1005 next = item;
1006 return item;
1007 }
1008 else
1009 {
1010 return NULL;
1011 }
1012 } // end ProtoTree::Iterator::GetPrevItem()
1013
1014
1015 ProtoTree::Item* ProtoTree::Iterator::PeekPrevItem()
1016 {
1017 if (reversed)
1018 {
1019 return prev;
1020 }
1021 else
1022 {
1023 Item* prevItem = GetPrevItem();
1024 GetNextItem(); // puts mode/cursor back to right place
1025 return prevItem;
1026 }
1027 } // end ProtoTree::PeekPrevItem()
1028
1029 ProtoTree::Item* ProtoTree::Iterator::GetNextItem()
1030 {
1031 if (NULL != next)
1032 {
1033 ProtoTree* tree = static_cast<ProtoTree*>(iterable);
1034 if (reversed)
1035 {
1036 // This iterator has been going backwards
1037 // so we need to turn it around
1038 reversed = false;
1039 SetCursor(*next);
1040 if (NULL == next) return NULL;
1041 }
1042 Item* item = next;
1043 Endian keyEndian = next->GetEndian();
1044 if (NULL == curr_hop)
1045 {
1046 next = NULL;
1047 }
1048 else
1049 {
1050 Item* x = curr_hop;
1051 if (((x->left != next) && (x->left->parent != x)) ||
1052 (x->right->parent == x))
1053 {
1054 next = x->left;
1055 // Now, update "curr_hop" if applicable
1056 // First, check for root node visit
1057 if ((NULL == next->parent) &&
1058 (tree->Bit(next->GetKey(), next->GetKeysize(), 0, keyEndian) != tree->Bit(x->GetKey(), x->GetKeysize(), 0, keyEndian)))
1059 {
1060 if (x->right == x)
1061 {
1062 next = x;
1063 curr_hop = NULL;
1064 }
1065 else
1066 {
1067 // Branch right and go as far left as possible
1068 x = x->right;
1069 while (x->left->parent == x) x = x->left;
1070 next = x->left;
1071 if (x->right->parent == x)
1072 {
1073 // Branch right and go as far left as possible
1074 x = x->right;
1075 while (x->left->parent == x) x = x->left;
1076 }
1077 curr_hop = x;
1078 }
1079 }
1080 else if (x->right->parent == x)
1081 {
1082 // Branch right and go as far left as possible
1083 x = x->right;
1084 while (x->left->parent == x) x = x->left;
1085 curr_hop = x;
1086 }
1087 // Otherwise, there was no change to "curr_hop" for now
1088 }
1089 else // if (curr_hop->right->parent != curr_hop)
1090 {
1091 // Right item is next in iteration
1092 next = x->right;
1093 // Now, update "curr_hop" if applicable
1094 // First, check for root node visit
1095 if ((NULL == next->parent) &&
1096 (next->right != next) &&
1097 (tree->Bit(x->GetKey(), x->GetKeysize(), 0, keyEndian) != tree->Bit(next->GetKey(), next->GetKeysize(), 0, keyEndian)))
1098 {
1099 // Branch right and go as far left as possible
1100 x = next->right;
1101 while (x->left->parent == x) x = x->left;
1102 next = x->left;
1103 if (x->right->parent == x)
1104 {
1105 // Again, branch right and go as far left as possible
1106 x = x->right;
1107 while (x->left->parent == x) x = x->left;
1108 }
1109 curr_hop = x;
1110 }
1111 else
1112 {
1113 // Go back up the tree
1114 Item* p = x->parent;
1115 while ((p != NULL) && (p->right == x))
1116 {
1117 x = p;
1118 p = x->parent;
1119 }
1120 if (NULL != p)
1121 {
1122 if ((NULL == p->parent) && (p->right == p))
1123 {
1124 p = NULL;
1125 }
1126 else if (p->right->parent == p)
1127 {
1128 // Branch right and go as far left as possible
1129 Item* x = p->right;
1130 while (x->left->parent == x) x = x->left;
1131 p = x;
1132 }
1133 }
1134 curr_hop = p;
1135 }
1136 }
1137 } // end if/else (NULL == curr_hop)
1138 if (0 != prefix_size)
1139 {
1140 // Test "item" against prefix of item last returned
1141 if ((NULL == prefix_item) ||
1142 !tree->PrefixIsEqual(item->GetKey(), item->GetKeysize(), prefix_item->GetKey(), prefix_size, keyEndian))
1143 return NULL;
1144 }
1145 prev = item;
1146 return item;
1147 }
1148 else
1149 {
1150 return NULL;
1151 } // end if/else(NULL != next)
1152 } // end ProtoTree::Item* ProtoTree::Iterator::GetNextItem()
1153
1154 ProtoTree::Item* ProtoTree::Iterator::PeekNextItem()
1155 {
1156 if (reversed)
1157 {
1158 Item* nextItem = GetNextItem();
1159 GetPrevItem(); // puts mode/cursor back to right place
1160 return nextItem;
1161 }
1162 else
1163 {
1164 return next;
1165 }
1166 } // end ProtoTree::PeekNextItem()
1167
1168 void ProtoTree::Iterator::Update(ProtoIterable::Item* theItem, Action theAction)
1169 {
1170 switch (theAction)
1171 {
1172 case INSERT:
1173 {
1174 // Save our current iterator state
1175 Item* oldPrev = prev;
1176 Item* oldNext = next;
1177 Item* oldPrefixItem = prefix_item;
1178 // First, find new prefix subtree if applicable/needed
1179 if (NULL != prefix_item)
1180 {
1181 Reset(reversed, prefix_item->GetKey(), prefix_size);
1182 ASSERT(NULL != prefix_item); // should have found old one at least
1183 }
1184 // Restore iterator cursor state
1185 if (reversed)
1186 {
1187 if (NULL != oldNext)
1188 SetCursor(*oldNext);
1189 else if (NULL == prefix_item)
1190 Reset(true);
1191 }
1192 else
1193 {
1194 if (NULL != oldPrev)
1195 SetCursor(*oldPrev);
1196 else if (NULL == oldPrefixItem)
1197 Reset(false);
1198 }
1199 break;
1200 }
1201 case REMOVE:
1202 {
1203 // NOTE - This doesn't work quite right for prefix iterators
1204 // (mid-iteration removal of items can break comprehensive prefix iteration)
1205 // Save our current iterator state
1206 Item* oldPrev = prev;
1207 Item* oldNext = next;
1208 // First, find new prefix subtree if applicable/needed
1209 if (static_cast<Item*>(theItem) == prefix_item)
1210 {
1211 Reset(reversed, prefix_item->GetKey(), prefix_size);
1212 if (NULL == prefix_item)
1213 break; // no matching prefix subtree remains
1214 }
1215 // Restore cursor state with trick if cursor was item removed
1216 if (reversed)
1217 {
1218 // "next" is the cursor for reverse mode
1219 if (static_cast<Item*>(theItem) != oldNext)
1220 {
1221 if (NULL == oldNext)
1222 {
1223 // tree is now empty?
1224 //ASSERT(NULL == prefix_item);
1225 if (NULL == prefix_item)
1226 prev = next = NULL;
1227 else
1228 Reset(reversed, prefix_item->GetKey(), prefix_size);
1229 }
1230 else
1231 {
1232 SetCursor(*oldNext);
1233 }
1234 }
1235 else
1236 {
1237 // This puts the iteration to a ambiguous
1238 // state that allows subsequent calls to
1239 // either GetPrevItem() or GetNextItem() to
1240 // work properly even though the "cursor" is
1241 // wrong. (Note PeekNextItem() won't be correct)
1242 if (NULL == oldPrev)
1243 {
1244 // tree is now empty?
1245 //ASSERT(NULL == prefix_item);
1246 if (NULL == prefix_item)
1247 prev = next = NULL;
1248 else
1249 Reset(reversed, prefix_item->GetKey(), prefix_size);
1250 }
1251 else
1252 {
1253 if (NULL == prefix_item)
1254 {
1255 SetCursor(*oldPrev);
1256 prev = oldPrev;
1257 }
1258 else
1259 {
1260 Reset(reversed, prefix_item->GetKey(), prefix_size);
1261 }
1262 }
1263 }
1264 }
1265 else
1266 {
1267 // "prev" is the cursor for normal mode
1268 if (static_cast<Item*>(theItem) != oldPrev)
1269 {
1270 if (NULL == oldPrev)
1271 {
1272 // tree is now empty?
1273 //ASSERT(NULL == prefix_item);
1274 if (NULL == prefix_item)
1275 prev = next = NULL;
1276 else
1277 Reset(reversed, prefix_item->GetKey(), prefix_size);
1278 }
1279 else
1280 {
1281 SetCursor(*oldPrev);
1282 }
1283 }
1284 else
1285 {
1286 if (NULL == oldNext)
1287 {
1288 // tree is now empty?
1289 //ASSERT(NULL == prefix_item);
1290 if (NULL == prefix_item)
1291 prev = next = NULL;
1292 else
1293 Reset(reversed, prefix_item->GetKey(), prefix_size);
1294 }
1295 else
1296 {
1297 if (NULL == prefix_item)
1298 {
1299 SetCursor(*oldNext);
1300 next = oldNext;
1301 }
1302 else
1303 {
1304 Reset(reversed, prefix_item->GetKey(), prefix_size);
1305 }
1306 }
1307 }
1308 }
1309 break;
1310 }
1311 case EMPTY:
1312 prev = next = prefix_item = NULL;
1313 prefix_size = 0;
1314 break;
1315 case APPEND:
1316 case PREPEND:
1317 ASSERT(0);
1318 break;
1319 }
1320 } // end ProtoTree::Iterator::Update()
1321
1322 ProtoTree::SimpleIterator::SimpleIterator(ProtoTree& theTree)
1323 : ProtoIterable::Iterator(theTree)
1324 {
1325 Reset();
1326 }
1327
1328 ProtoTree::SimpleIterator::~SimpleIterator()
1329 {
1330 }
1331
1332 void ProtoTree::SimpleIterator::Reset()
1333 {
1334 ProtoTree* tree = static_cast<ProtoTree*>(iterable);
1335 if (NULL != tree)
1336 {
1337 Item* x = tree->root;
1338 if (NULL != x)
1339 {
1340 // Go left as far as possible
1341 while (x->left->parent == x)
1342 x = x->left;
1343 }
1344 next = x;
1345 }
1346 else
1347 {
1348 next = NULL;
1349 }
1350 } // end ProtoTree::SimpleIterator::Reset()
1351
1352 ProtoTree::Item* ProtoTree::SimpleIterator::GetNextItem()
1353 {
1354 Item* i = next;
1355 if (NULL != i)
1356 {
1357 if (i->right->parent == i)
1358 {
1359 // Go right one, then left as far as possible
1360 Item* y = i->right;
1361 while (y->left->parent == y) y = y->left;
1362 if (y != i)
1363 {
1364 next = y;
1365 return i;
1366 }
1367 }
1368 Item* x = i;
1369 Item* y = i->parent;
1370 while ((NULL != y) && (y->right == x))
1371 {
1372 x = y;
1373 y = y->parent;
1374 }
1375 next = y;
1376 }
1377 return i;
1378 } // end ProtoTree::SimpleIterator::GetNextItem()
1379
1380 void ProtoTree::SimpleIterator::Update(ProtoIterable::Item* /*theItem*/, Action /*theAction*/)
1381 {
1382 // For ProtoTree::SimpleIterator, really the only "sane" thing to do when the associated
1383 // tree is modified is to "Reset()" the iterator since the logical tree structure
1384 // is potentially heavily affected by any change. This is heavy-handed so it's
1385 // actually more efficient to do a "GetRoot(), Remove()" loop until GetRoot() returns NULL
1386 // (see ProtoTree::Destroy()) instead of using this SimpleIterator. Where it _is_
1387 // useful is in the ProtoIndexedQueue::Empty() method where it empties the tree without invoking
1388 // any of the Item virtual methods (i.e. GetKey(), etc). The SimpleIterator is also useful
1389 // as a little lighter weight (than the regular ProtoTree::Iterator) where the order of
1390 // iteration doesn't matter and mid-iteration Item insertion/removal isn't done.
1391 Reset();
1392 } // end ProtoTree::SimpleIterator::Update()
1393
1394
1395 ProtoSortedTree::ProtoSortedTree(bool uniqueItemsOnly)
1396 : unique_items_only(uniqueItemsOnly), positive_min(NULL)
1397 {
1398 }
1399
1400 ProtoSortedTree::~ProtoSortedTree()
1401 {
1402 }
1403
1404 bool ProtoSortedTree::Insert(Item& item)
1405 {
1406 ASSERT(0 != item.GetKeysize());
1407 // Is an item with this key already in tree?
1408 const char* key = item.GetKey();
1409 unsigned int keysize = item.GetKeysize();
1410 ProtoTree::Endian keyEndian = item.GetEndian();
1411 Item* match = Find(key, keysize);
1412
1413 if (NULL == match)
1414 {
1415 // Insert the item into our "item_tree"
1416 item_tree.Insert(item);
1417 // Now find the place to thread this new item into our linked list
1418 ProtoTree::Iterator iterator(item_tree, true, &item);
1419 match = static_cast<Item*>(iterator.PeekPrevItem());
1420 if (NULL == match)
1421 {
1422 if (item_list.IsEmpty())
1423 {
1424 // nothing in the list yet
1425 item_list.Append(item);
1426 if (item.UseSignBit())
1427 {
1428 bool itemSign = item_tree.Bit(key, keysize, 0, keyEndian);
1429 if (!itemSign) positive_min = &item;
1430 }
1431 }
1432 else
1433 {
1434 // this item lexically precedes the anything in the tree
1435 bool useSignBit = item.UseSignBit();
1436 ASSERT(useSignBit == GetHead()->UseSignBit());
1437 if (useSignBit)
1438 {
1439 bool itemSign = item_tree.Bit(key, keysize, 0, keyEndian);
1440 if (itemSign)
1441 {
1442 bool useComplement2 = item.UseComplement2();
1443 ASSERT(useComplement2 == GetHead()->UseComplement2());
1444 // A signed "item" with no lexical predecessor
1445 if (useComplement2)
1446 {
1447 // is smallest negative number in a tree that
1448 // has no positive numbers yet.
1449 // So this goes to the "head" automatically!
1450 item_list.Prepend(item);
1451 }
1452 else
1453 {
1454 // is biggest negative number in a tree that
1455 // has no positive numbers yet.
1456 // So this goes to the "tail" automatically!
1457 item_list.Append(item);
1458 }
1459 // Note: (itemSign && !headSign) is impossible here
1460 }
1461 else
1462 {
1463 Item* head = GetHead();
1464 bool headSign = item_tree.Bit(head->GetKey(), head->GetKeysize(), 0, keyEndian);
1465 if (headSign)
1466 {
1467 // (!itemSign && headSign)
1468 // An unsigned (positive value) "item" with no lexical predecessor
1469 // is the smallest _positive_ number in the tree
1470 // so insert this before our prior "positive_min" or at tail
1471 if (NULL != positive_min)
1472 {
1473 item_list.Insert(item, *positive_min);
1474 }
1475 else
1476 {
1477 // first positive value, put at tail
1478 item_list.Append(item);
1479 }
1480 positive_min = &item;
1481 }
1482 else
1483 {
1484 // (!itemSign && !headSign)
1485 // Both positive, and "item" < "head"
1486 // (no negative numbers in the tree?)
1487 // So, insert "item" before "head"
1488 item_list.Prepend(item);
1489 positive_min = &item;
1490 }
1491 }
1492 }
1493 else
1494 {
1495 // this item lexically precedes the "head"
1496 item_list.Prepend(item);
1497 } // end if/else (useSignBit)
1498 } // end if/else item_list.IsEmpty()
1499 }
1500 else
1501 {
1502 // this "item" lexically succeeds the "match"
1503 bool useSignBit = item.UseSignBit();
1504 ASSERT(useSignBit == match->UseSignBit());
1505 if (useSignBit)
1506 {
1507 bool itemSign = item_tree.Bit(key, keysize, 0, keyEndian);
1508 if (!itemSign)
1509 {
1510 // (!itemSign && !matchSign)
1511 // Both positive, match < item
1512 // Insert "item" just after "match"
1513 Item* next = static_cast<Item*>(item_list.GetNextItem(*match));
1514 if (NULL != next)
1515 item_list.Insert(item, *next);
1516 else
1517 item_list.Append(item);
1518 ASSERT(!item_tree.Bit(match->GetKey(), match->GetKeysize(), 0, keyEndian));
1519 // Note (!itemSign && matchSign) can't happen
1520 // here since signed "match" (negative value)
1521 // _must_ lexically succeed unsigned "item"
1522 }
1523 else
1524 {
1525 bool useComplement2 = item.UseComplement2();
1526 ASSERT(useComplement2 == match->UseComplement2());
1527 bool matchSign = item_tree.Bit(match->GetKey(), match->GetKeysize(), 0, keyEndian);
1528 if (matchSign)
1529 {
1530 // (itemSign && matchSign)
1531 if (useComplement2)
1532 {
1533 // Both negative, "match" < "item"
1534 // Insert "item" just after "match"
1535 Item* next = static_cast<Item*>(item_list.GetNextItem(*match));
1536 if (NULL != next)
1537 item_list.Insert(item, *next);
1538 else
1539 item_list.Append(item);
1540 }
1541 else
1542 {
1543 // Both negative, "item" < "match"
1544 // Insert "item" before first equivalent "match"
1545 // note "prev" here lexically _succeeds_ this
1546 // "item" that was inserted into tree above, so:
1547
1548 ProtoTree::Iterator iterator(item_tree, false, &item);
1549 Item* prev = static_cast<Item*>(iterator.PeekNextItem());
1550
1551 /* (Old "while()" loop approach to find prev, in-tree item)
1552 Item* prev = match->GetPrev();
1553 while ((NULL != prev) && !prev->IsInTree())
1554 {
1555 match = prev;
1556 prev = prev->GetPrev();
1557 }
1558 */
1559 if (NULL != prev)
1560 {
1561 Item* next = static_cast<Item*>(item_list.GetNextItem(*prev));
1562 ASSERT(NULL != next);
1563 item_list.Insert(item, *next);
1564 }
1565 else
1566 {
1567 item_list.Prepend(item);
1568 }
1569 }
1570 }
1571 else
1572 {
1573 // (itemSign && !matchSign)
1574 if (useComplement2)
1575 {
1576 // Smallest negative number, put at list head
1577 item_list.Prepend(item);
1578 }
1579 else
1580 {
1581 // Greatest negative number, put before "positive_min"
1582 ASSERT(NULL != positive_min);
1583 item_list.Insert(item, *positive_min);
1584 }
1585 }
1586 }
1587 }
1588 else
1589 {
1590 // Insert the item just after the close "match" from "item_tree"
1591 Item* next = static_cast<Item*>(item_list.GetNextItem(*match));
1592 if (NULL != next)
1593 item_list.Insert(item, *next);
1594 else
1595 item_list.Append(item);
1596 } // end if/else (useSignBit)
1597 }
1598 }
1599 else if (match != &item)
1600 {
1601 if (unique_items_only) return false;
1602 // Insert the item just before the exact "match" from "item_tree"
1603 item_list.Insert(item, *match);
1604 item.left = NULL; // denotes item is _not_ in tree (in linked list only)
1605 bool useSignBit = item.UseSignBit();
1606 ASSERT(useSignBit == match->UseSignBit());
1607 if (useSignBit && (match == positive_min))
1608 positive_min = &item;
1609 }
1610 else
1611 {
1612 PLOG(PL_ERROR, "ProtoSortedTree::Insert() warning: item already in tree!\n");
1613 }
1614 return true;
1615 } // end ProtoSortedTree::Insert()
1616
1617 void ProtoSortedTree::Prepend(Item& item)
1618 {
1619 item_list.Prepend(item);
1620 } // end ProtoSortedTree::Prepend()
1621
1622 void ProtoSortedTree::Append(Item& item)
1623 {
1624 item_list.Append(item);
1625 } // end ProtoSortedTree::Append()
1626
1627 void ProtoSortedTree::Remove(Item& item)
1628 {
1629 // 1) Save some state and remove from linked list
1630 Item* prev = static_cast<Item*>(item_list.GetPrevItem(item));
1631 if (&item == positive_min)
1632 positive_min = static_cast<Item*>(item_list.GetNextItem(item));
1633 item_list.Remove(item);
1634
1635 // 2) Remove from ProtoTree, if applicable
1636 if (item.IsInTree())
1637 {
1638 // Remove "item" from the tree and mark as removed (item.left = NULL)
1639 item_tree.Remove(item);
1640 item.left = NULL;
1641 // Does "prev" needs to take the place of "item" in the ProtoTree?
1642 if ((NULL != prev) && !prev->IsInTree())
1643 item_tree.Insert(*prev);
1644 }
1645 } // end ProtoSortedTree::Remove()
1646
1647 void ProtoSortedTree::Empty()
1648 {
1649 if (!IsEmpty())
1650 {
1651 item_tree.Empty();
1652 item_list.Empty();
1653 positive_min = NULL;
1654 }
1655 } // end ProtoSortedTree::Empty()
1656
1657 void ProtoSortedTree::EmptyToPool(ItemPool& itemPool)
1658 {
1659 if (!IsEmpty())
1660 {
1661 item_tree.Empty();
1662 item_list.EmptyToPool(itemPool);
1663 positive_min = NULL;
1664 }
1665 } // end ProtoSortedTree::EmptyToPool()
1666
1667 void ProtoSortedTree::Destroy()
1668 {
1669 if (!IsEmpty())
1670 {
1671 item_tree.Empty();
1672 item_list.Destroy();
1673 positive_min = NULL;
1674 }
1675 } // end ProtoSortedTree::Destroy()
1676
1677 ProtoSortedTree::Item::Item()
1678 {
1679 }
1680
1681 ProtoSortedTree::Item::~Item()
1682 {
1683 }
1684
1685 ProtoSortedTree::Iterator::Iterator(ProtoSortedTree& theTree,
1686 bool reverse,
1687 const char* keyMin,
1688 unsigned int keysize)
1689 : tree(theTree), list_iterator(theTree.item_list, reverse)
1690 {
1691 Reset(reverse, keyMin, keysize);
1692 }
1693
1694 ProtoSortedTree::Iterator::~Iterator()
1695 {
1696 }
1697
1698 void ProtoSortedTree::Iterator::Reset(bool reverse, const char* keyMin, unsigned int keysize)
1699 {
1700 list_iterator.Reset(reverse); // put the iterator in the right direction
1701 if ((NULL != keyMin) && list_iterator.IsValid() && !tree.IsEmpty())
1702 {
1703 // refine if a "keyMin" start point was provided
1704 // (note for "reverse" == true, "keyMin" is really a "keyMax"
1705 Item* match = tree.Find(keyMin, keysize);
1706 if (NULL == match)
1707 {
1708 // There was no exact match to "keyMin", so look for next item (or prev if reverse == true)
1709 TempItem tmpItem(keyMin, keysize, tree.GetHead()->GetEndian());
1710 tree.item_tree.Insert(tmpItem);
1711 ProtoTree::Iterator iterator(tree.item_tree, reverse, &tmpItem);
1712 match = reverse ? static_cast<Item*>(iterator.PeekPrevItem()) :
1713 static_cast<Item*>(iterator.PeekNextItem());
1714 tree.item_tree.Remove(tmpItem); // it's done its job, so bye-bye
1715 }
1716 if ((NULL != match) && !reverse)
1717 {
1718 // Make sure we are positioned on _first_ item of equal valued items
1719 ProtoTree::Iterator iterator(tree.item_tree, true, match);
1720 Item* prev = static_cast<Item*>(iterator.PeekPrevItem());
1721 if (NULL == prev)
1722 match = tree.item_list.GetHead();
1723 else
1724 match = static_cast<Item*>(tree.item_list.GetNextItem(*prev));
1725 }
1726 list_iterator.SetCursor(match);
1727 }
1728 } // end ProtoSortedTree::Iterator::Reset()
1729
1730
1731 ProtoSortedTree::Iterator::TempItem::TempItem(const char* theKey, unsigned int theKeysize, ProtoTree::Endian keyEndian)
1732 : key(theKey), keysize(theKeysize), key_endian(keyEndian)
1733 {
1734 }
1735
1736 ProtoSortedTree::Iterator::TempItem::~TempItem()
1737 {
1738 }