/********************************************************************* * * AUTHORIZATION TO USE AND DISTRIBUTE * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that: * * (1) source code distributions retain this paragraph in its entirety, * * (2) distributions including binary code include this paragraph in * its entirety in the documentation or other materials provided * with the distribution, and * * (3) all advertising materials mentioning features or use of this * software display the following acknowledgment: * * "This product includes software written and developed * by Brian Adamson of the Naval Research Laboratory (NRL)." * * The name of NRL, the name(s) of NRL employee(s), or any entity * of the United States Government may not be used to endorse or * promote products derived from this software, nor does the * inclusion of the NRL written and developed software directly or * indirectly suggest NRL or United States Government endorsement * of this product. * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. ********************************************************************/ /** * @file protoTree.cpp * * @brief This is a general purpose prefix-based C++ Patricia tree. * The code also provides an ability to iterate over items with a * common prefix of arbitrary bit length */ #include "protoTree.h" #include "protoDebug.h" // for PLOG() #include #include // for labs() ProtoTree::Item::Item() : bit(0), parent((Item*)NULL), left((Item*)NULL), right((Item*)NULL) { } ProtoTree::Item::~Item() { } unsigned int ProtoTree::Item::GetDepth() const { unsigned int depth = 0; const Item* p = this; while (NULL != (p = p->parent)) depth++; return depth; } // end ProtoTree::Item::GetDepth() ProtoTree::ItemPool::ItemPool() : head(NULL) { } ProtoTree::ItemPool::~ItemPool() { Destroy(); } void ProtoTree::ItemPool::Destroy() { Item* item; while ((item = Get())) delete item; } // end ProtoTree::ItemPool::Destroy() ProtoTree::Item* ProtoTree::ItemPool::Get() { Item* item = head; if (NULL != item) head = item->GetPoolNext(); return item; } // end ProtoTree::ItemPool::Get() void ProtoTree::ItemPool::Put(Item& item) { item.SetPoolNext(head); head = &item; } // end ProtoTree::ItemPool::Put() ProtoTree::ProtoTree() : root((Item*)NULL) { } ProtoTree::~ProtoTree() { } void ProtoTree::Empty() { root = (ProtoTree::Item*)NULL; UpdateIterators(NULL, Iterator::EMPTY); } // end ProtoTree::Empty() void ProtoTree::Destroy() { while (NULL != root) { Item* item = root; Remove(*item); delete item; } } // end ProtoTree::Destroy() bool ProtoTree::PrefixIsEqual(const char* key, unsigned int keysize, const char* prefix, unsigned int prefixSize, Endian keyEndian) { if (prefixSize > keysize) return false; unsigned int fullByteCount = (prefixSize >> 3); unsigned int remBitCount = prefixSize & 0x07; if (ENDIAN_BIG == keyEndian) { // Compare any "remainder bits" of the "prefix" to the // corresponding bits of the "key" // (we do this first to possibly avoid call to "memcmp()" below) if (0 != remBitCount) { char remBitMask = (unsigned char)0xff << (8 - remBitCount); // "remainder bits" are in last byte of big endian "prefix" if ((key[fullByteCount] & remBitMask) != (prefix[fullByteCount] & remBitMask)) return false; } } else { // Adjust "key" ptr to point at its prefix portion key += (keysize >> 3); if (0 != (keysize &0x07)) key++; key -= fullByteCount; // Compare any "remainder bits" of the "prefix" to the // corresponding bits of the "key" // (we do this first to possibly avoid call to "memcmp()" below) if (0 != remBitCount) { char remBitMask = 0xff << (8 - remBitCount); // "remainder bits" are in first byte of little endian "prefix" if ((key[0] & remBitMask) != (prefix[0] & remBitMask)) return false; // Compare any full byte portion of the key / prefix if (0 != fullByteCount) return (0 == memcmp(key+1, prefix+1, fullByteCount)); else return true; } } // Compare any full byte portion of the "prefix" // to the corresponding "key" bytes if (0 != fullByteCount) return (0 == memcmp(key, prefix, fullByteCount)); else return true; } // end ProtoTree::PrefixIsEqual() bool ProtoTree::KeysAreEqual(const char* key1, const char* key2, unsigned int keysize, Endian keyEndian) { unsigned int fullByteCount = keysize >> 3; unsigned int remBitCount = keysize & 0x07; if (0 != remBitCount) { // Compare any "remainder bits" of the keys // (we do this first to possibly avoid call to "memcmp()" below) char remBitMask = 0xff << (8 - remBitCount); if (ENDIAN_BIG == keyEndian) { // "remainder bits" are in last byte of big endian keys if ((key1[fullByteCount] & remBitMask) != (key2[fullByteCount] & remBitMask)) return false; } else { // "remainder bits" are in first byte of little endian keys if ((key1[0] & remBitMask) != (key2[0] & remBitMask)) return false; // Compare any full byte portion of the keys if (0 != fullByteCount) return (0 == memcmp(key1+1, key2+1, fullByteCount)); else return true; } } // Compare any full bytes of the keys if (0 != fullByteCount) return (0 == memcmp(key1, key2, fullByteCount)); else return true; } // end ProtoTree::KeysAreEqual() bool ProtoTree::ItemsAreEqual(const Item& item1, const Item& item2) { unsigned int keysize = item1.GetKeysize(); if (item2.GetKeysize() != keysize) return false; Endian keyEndian = item1.GetEndian(); if (keyEndian != item2.GetEndian()) { PLOG(PL_WARN, "ProtoTree::ItemsAreEqual() mis-matched key endian?!\n"); ASSERT(0); return false; } return KeysAreEqual(item1.GetKey(), item2.GetKey(), keysize, keyEndian); } // end ProtoTree::ItemsAreEqual() bool ProtoTree::ItemIsEqual(const Item& item, const char* key, unsigned int keysize) { if (item.GetKeysize() != keysize) return false; return KeysAreEqual(item.GetKey(), key, keysize, item.GetEndian()); } // end ProtoTree::ItemIsEqual() bool ProtoTree::Bit(const char* key, unsigned int keysize, unsigned int index, Endian keyEndian) { if (index < keysize) { unsigned int byteIndex = index >> 3; byteIndex = (ENDIAN_BIG == keyEndian) ? byteIndex : ((keysize - 1) >> 3) - byteIndex; return (0 != (key[byteIndex] & (0x80 >> (index & 0x07)))); } else if (index < (keysize + (sizeof(keysize) << 3))) { index -= keysize; return (0 != (((char*)&keysize)[index >> 3] & (0x80 >> (index & 0x07)))); } else { return false; } } // end ProtoTree::Bit() ProtoTree::Item* ProtoTree::GetFirstItem() const { if (NULL != root) { if (root->left == root->right) { // 2-A) Only one node in this tree return root; } else { // 2-B) Return left most node in this tree Item* x = (root->left == root) ? root->right : root; while (x->left->parent == x) x = x->left; return (x->left); } } return NULL; } // end ProtoTree::GetFirstItem() ProtoTree::Item* ProtoTree::GetLastItem() const { if (NULL != root) { // 2) Follow root or left of root all the way to right to find // the last item (lexically) in the tree Item* x = (root->right == root) ? root->left : root; Item* p; do { p = x; x = x->right; } while (p == x->parent); return x; } return NULL; } // end ProtoTree::GetLastItem() bool ProtoTree::Insert(ProtoTree::Item& item) { if (NULL != root) { // 1) Find closest match to "item" const char* key = item.GetKey(); unsigned int keysize = item.GetKeysize(); Endian keyEndian = item.GetEndian(); Item* x = root; Item* p; do { p = x; x = Bit(key, keysize, x->bit, keyEndian) ? x->right : x->left; } while (p == x->parent); // 2) Then, find index of first differing bit ("dBit") // (also look out for exact match!) unsigned int dBit = 0; // A) Do byte-wise comparison to extent possible unsigned int keysizeMin, indexMax; if (keysize < x->GetKeysize()) { keysizeMin = keysize; indexMax = x->GetKeysize() + (sizeof(unsigned int) << 3); } else { keysizeMin = x->GetKeysize(); indexMax = keysize + (sizeof(unsigned int) << 3); } const char* ptr1 = key; const char* ptr2 = x->GetKey(); ASSERT(x->GetEndian() == keyEndian); if (ENDIAN_LITTLE == keyEndian) { ptr1 += ((keysize - 1) >> 3); ptr2 += ((x->GetKeysize() - 1) >> 3); } unsigned int fullByteBits = keysizeMin & ~0x07; while (dBit < fullByteBits) { if (*ptr1 != *ptr2) { // B) Do bit-wise comparison on differing byte unsigned char delta = *ptr1 ^ *ptr2; ASSERT(0 != delta); while (delta < 0x80) { delta <<= 1; dBit++; } break; } if (ENDIAN_BIG == keyEndian) { ptr1++; ptr2++; } else { ptr1--; ptr2--; } dBit += 8; } ASSERT(dBit <= fullByteBits); if (dBit == fullByteBits) { // C) Compare any remainder bit-by-bit for (; dBit < indexMax; dBit++) { if (Bit(key, keysize, dBit, keyEndian) != Bit(x->GetKey(), x->GetKeysize(), dBit, keyEndian)) break; } if (dBit == indexMax) { PLOG(PL_WARN, "ProtoTree::Insert() Equivalent item already in tree!\n"); //ASSERT(0); return false; } } item.bit = dBit; // 3) Find "item" insertion point x = root; do { p = x; x = Bit(key, keysize, x->bit, keyEndian) ? x->right : x->left; } while ((x->bit < dBit) && (p == x->parent)); // 4) Insert "item" into tree if (Bit(key, keysize, dBit, keyEndian)) { ASSERT(NULL != x); item.left = x; item.right = &item; } else { item.left = &item; item.right = x; } item.parent = p; if (Bit(key, keysize, p->bit, keyEndian)) p->right = &item; else p->left = &item; if (p == x->parent) x->parent = &item; } else { // tree is empty, so make "item" the tree root root = &item; item.parent = (Item*)NULL; item.left = item.right = &item; item.bit = 0; } // Note for ProtoTree, we call UpdateIterators() _after_ // insertion/removal since we just reset the iterators UpdateIterators(&item, Iterator::INSERT); return true; } // end ProtoTree::Insert() // Find node with backpointer to "item" ProtoTree::Item* ProtoTree::FindPredecessor(ProtoTree::Item& item) const { // Find terminal "q" with backpointer to "item" Item* x = &item; Item* q; const char* key = item.GetKey(); unsigned int keysize = item.GetKeysize(); Endian keyEndian = item.GetEndian(); do { q = x; if (Bit(key, keysize, x->bit, keyEndian)) x = x->right; else x = x->left; } while (x != &item); return q; } // end ProtoTree::FindPredecessor() void ProtoTree::Remove(ProtoTree::Item& item) { ASSERT(0 != item.GetKeysize()); if (((&item == item.left) || (&item == item.right)) && (NULL != item.parent)) { // non-root "item" that has at least one self-pointer // (a.k.a an "external entry"?) Item* orphan = (&item == item.left) ? item.right : item.left; if (item.parent->left == &item) item.parent->left = orphan; else item.parent->right = orphan; if (orphan->bit > item.parent->bit) orphan->parent = item.parent; } else { // Root or "item" with no self-pointers // (a.k.a an "internal entry"?) // 1) Find terminal "q" with backpointer to "item" const char* key = item.GetKey(); unsigned int keysize = item.GetKeysize(); Endian keyEndian = item.GetEndian(); Item* x = &item; Item* q; do { q = x; if (Bit(key, keysize, x->bit, keyEndian)) x = x->right; else x = x->left; } while (x != &item); if (NULL != q->parent) { // Non-root "q", so "q" is moved into the place of "item" Item* s = NULL; if (NULL == item.parent) { // There are always two nodes backpointing to "root" // (unless root is the only node in the tree) // "s" is the other of these besides "q" // (We need to find "s" before we mess with the tree) x = Bit(key, keysize, item.bit, keyEndian) ? item.left : item.right; do { s = x; if (Bit(key, keysize, x->bit, keyEndian)) x = x->right; else x = x->left; } while (x != &item); } // A) Set bit index of "q" to that of "item" q->bit = item.bit; // B) Fix the parent, left, and right node pointers to "q" // (removes "q" from its current place in the tree) Item* parent = q->parent; Item* child = (q->left == &item) ? q->right : q->left; ASSERT(NULL != child); if (parent->left == q) parent->left = child; else parent->right = child; if (child->bit > parent->bit) child->parent = parent; // C) Fix the item's left->parent and right->parent node pointers to "item" // (places "q" into the current place of the "item" in the tree) ASSERT(q != NULL); if (item.left->parent == &item) item.left->parent = q; if (item.right->parent == &item) item.right->parent = q; if (NULL != item.parent) { if (item.parent->left == &item) item.parent->left = q; else item.parent->right = q; } else { // "item" was root node, so update the "s" node // backpointer to "q" instead of "item" ASSERT(s != NULL); ASSERT(s != &item); if (s->left == &item) s->left = q; else s->right = q; root = q; } // E) Finally, "q" gets the pointers of the "item" being removed // (which now _may_ include a pointer to itself) if (NULL != item.parent) ASSERT((&item != item.left) && (&item != item.right)); q->parent = item.parent; q->left = (item.left == &item) ? q : item.left; q->right = (item.right == &item) ? q : item.right; } else { // "root" is removed with none or one item left ASSERT(q == &item); Item* orphan = (q == q->left) ? q->right : q->left; if (q == orphan) { root = (Item*)NULL; } else { root = orphan; orphan->parent = NULL; if (orphan->left == q) orphan->left = orphan; else orphan->right = orphan; orphan->bit = 0; } } } item.parent = item.left = item.right = (Item*)NULL; UpdateIterators(&item, Iterator::REMOVE); } // end ProtoTree::Remove() ProtoTree::Item* ProtoTree::RemoveRoot() { Item* item = root; if (NULL != item) Remove(*item); return item; } // end ProtoTree::RemoveRoot() /** * Find item with exact match to key and keysize */ ProtoTree::Item* ProtoTree::Find(const char* key, unsigned int keysize) const { Item* x = root; if (NULL != x) { Endian keyEndian = x->GetEndian(); Item* p; do { p = x; x = Bit(key, keysize, x->bit, keyEndian) ? x->right : x->left; } while (x->parent == p); return (ItemIsEqual(*x, key, keysize) ? x : NULL); } else { return (Item*)NULL; } } // end ProtoTree::Find() /** * Find item with "closest" match to key and keysize (biggest prefix match?) */ ProtoTree::Item* ProtoTree::FindClosestMatch(const char* key, unsigned int keysize) const { Item* x = root; if (NULL != x) { Endian keyEndian = x->GetEndian(); Item* p; do { p = x; x = Bit(key, keysize, x->bit, keyEndian) ? x->right : x->left; } while ((x->parent == p) && (x->bit < keysize)); return x; } else { return (Item*)NULL; } } // end ProtoTree::FindClosestMatch() /** * Finds longest matching entry that is a prefix to "key" */ ProtoTree::Item* ProtoTree::FindPrefix(const char* key, unsigned int keysize) const { // (TBD) Retest this code with new "size-agnostic" ProtoTree implementation Item* x = root; if (NULL != x) { Endian keyEndian = x->GetEndian(); Item* p; do { p = x; x = Bit(key, keysize, x->bit, keyEndian) ? x->right : x->left; } while ((x->parent == p) && (x->bit < keysize)); if (PrefixIsEqual(key, keysize, x->GetKey(), x->GetKeysize(), keyEndian)) return x; } return NULL; } // end ProtoTree::FindPrefix() /** * This finds prefix subtree root, (TBD) add find prefix * subtree min, and find prefix subtree max methods * (e.g. for "min", first find subtree root, and roll left ???) */ ProtoTree::Item* ProtoTree::FindPrefixSubtree(const char* prefix, unsigned int prefixSize) const { // (TBD) Retest this code more with new "size-agnostic" ProtoTree implementation Item* x = root; if (NULL != x) { Endian keyEndian = x->GetEndian(); Item* p; do { p = x; x = Bit(prefix, prefixSize, x->bit, keyEndian) ? x->right : x->left; } while ((x->parent == p) && (x->bit < prefixSize)); if (PrefixIsEqual(x->GetKey(), x->GetKeysize(), prefix, prefixSize, keyEndian)) return x; } return (Item*)NULL; } // end ProtoTree::FindPrefixSubtree() ProtoTree::Iterator::Iterator(ProtoTree& theTree, bool reverse, ProtoTree::Item* cursor) : ProtoIterable::Iterator(theTree), prefix_size(0), prefix_item(NULL) { if (NULL != cursor) { reversed = reverse; SetCursor(*cursor); } else { Reset(reverse); // Reset() sets all to defaults } } ProtoTree::Iterator::~Iterator() { } void ProtoTree::Iterator::Reset(bool reverse, const char* prefix, unsigned int prefixSize) { ProtoTree* tree = static_cast(iterable); prefix_size = 0; prefix_item = prev = next = curr_hop = (Item*)NULL; if ((NULL == tree) || (NULL == tree->root)) return; if (0 != prefixSize) { if (NULL == prefix) return; // Find root of subtree with matching prefix // (TBD - there's a better way to find the min/max prefix matches via prefix00000 or prefix11111 ProtoTree::Item* prefixItem = tree->FindPrefixSubtree(prefix, prefixSize); if (NULL == prefixItem) return; // Temporarily "Reset()" the iterator and "SetCursor()" to find reversed = reverse ? false : true; SetCursor(*prefixItem); Endian keyEndian = prefixItem->GetEndian(); if (reverse) { // Find the maximum value with matching prefix. ProtoTree::Item* lastItem; while (NULL != (lastItem = GetNextItem())) { if (!tree->PrefixIsEqual(lastItem->GetKey(), lastItem->GetKeysize(), prefix, prefixSize, keyEndian)) break; // The "cursor" is set to after the last matching item } if (NULL == lastItem) Reset(reverse); } else { // Find the minimum value with matching prefix. ProtoTree::Item* firstItem; while (NULL != (firstItem = GetPrevItem())) { if (!tree->PrefixIsEqual(firstItem->GetKey(), firstItem->GetKeysize(), prefix, prefixSize, keyEndian)) break; // The "cursor" is set to before the first matching item } if (NULL == firstItem) Reset(reverse); } prefix_size = prefixSize; prefix_item = prefixItem; return; } if (reverse) { // This code is basically the same as ProtoTree::GetLastItem() if (NULL != tree->root) { // Follow left of root all the way to right to find // the very last item (lexically) in the tree Item* x = (tree->root->right == tree->root) ? tree->root->left : tree->root; Item* p; do { p = x; x = x->right; } while (p == x->parent); prev = x; } reversed = true; } else { // This code is basically the same as ProtoTree::GetFirstItem() // (although the code to find the "curr_hop" for iteration is different) if (NULL != tree->root) { if (tree->root->left == tree->root->right) { // Only one entry in the tree next = tree->root; curr_hop = NULL; } else { // If root has a left side, go as far left as possible // to find the very first item (lexically) in the tree Item* x = (tree->root->left == tree->root) ? tree->root->right : tree->root; while (x->left->parent == x) x = x->left; next = x->left; if (x->right->parent == x) { // Branch right and go as far left as possible x = x->right; while (x->left->parent == x) x = x->left; } curr_hop = x; } } reversed = false; } } // end ProtoTree::Iterator::Reset() void ProtoTree::Iterator::SetCursor(ProtoTree::Item& item) { ProtoTree* tree = static_cast(iterable); // Save prefix subtree info unsigned int prefixSize = prefix_size; ProtoTree::Item* prefixItem = prefix_item; prefix_size = 0; prefix_item = NULL; if ((NULL== tree) || (NULL == tree->root)) { prev = next = curr_hop = NULL; } else if (tree->root->left == tree->root->right) { ASSERT(&item == tree->root); curr_hop = NULL; if (reversed) { prev = NULL; next = tree->root; } else { prev = tree->root; next = NULL; } } else if (reversed) { // Setting "cursor" for "reversed" iteration is easy. curr_hop = NULL; prev = &item; GetPrevItem(); // note this sets "next" } else { // Setting "cursor" for forward iteration is a little more complicated. // Given an "item", we can find the "curr_hop" for the tree // entry that lexically precedes the "item" // (We do a reverse iteration to find that preceding entry) reversed = true; prev = &item; GetPrevItem(); // note "GetPrevItem()" also sets "next" as needed if (NULL == GetPrevItem()) { Reset(false); // Move forward one place so "cursor" is correct position GetNextItem(); } else { // This finds the proper "curr_hop" that goes with // the entry previous of "item" ... if ((&item != tree->root) || (item.right != &item)) { // Find the node's "predecessor" // (has backpointer to "item" curr_hop = tree->FindPredecessor(item); } else { // Instead, use the other node with backpointer to root "item" ASSERT(&item == tree->root); const char* key = item.GetKey(); unsigned int keysize = item.GetKeysize(); Endian keyEndian = item.GetEndian(); Item* s; Item* x = tree->Bit(key, keysize, item.bit, keyEndian) ? item.left : item.right; ASSERT((x == item.left) || (x == item.right)); do { s = x; if (tree->Bit(key, keysize, x->bit, keyEndian)) x = x->right; else x = x->left; } while (x != &item); curr_hop = s; } // Move forward two places so "cursor" is correct position reversed = false; GetNextItem(); GetNextItem(); } } // Restore prefix subtree info if (0 != prefixSize) { prefix_item = prefixItem; prefix_size = prefixSize; } } // end ProtoTree::Iterator::SetCursor() ProtoTree::Item* ProtoTree::Iterator::GetPrevItem() { if (NULL != prev) { ProtoTree* tree = static_cast(iterable); if (!reversed) { // This iterator has been moving forward // so we need to turn it around. reversed = true; // temporarily suspend prefix matching (if applicable) to allow turn-around unsigned savePrefixSize = prefix_size; prefix_size = 0; GetPrevItem(); prefix_size = savePrefixSize; if (NULL == prev) return NULL; } Item* item = prev; Endian keyEndian = item->GetEndian(); if (0 != prefix_size) { // Test "item" against our reference "prefix_item" if ((NULL == prefix_item) || !tree->PrefixIsEqual(item->GetKey(), item->GetKeysize(), prefix_item->GetKey(), prefix_size, keyEndian)) { prev = NULL; return NULL; } } Item* x; // Find node "q" with backpointer to "item" if ((NULL == item->parent) && (item->right == item)) x = item->left; else x = item; Item* q; do { q = x; if (tree->Bit(item->GetKey(), item->GetKeysize(), x->bit, keyEndian)) x = x->right; else x = x->left; } while (x != prev); if (q->right != item) { // Go up the tree do { x = q; q = q->parent; } while ((NULL != q) && (x == q->left)); if ((NULL == q) || (NULL == q->parent)) { if ((NULL == q) || (q->left == q)) { // We've bubbled completely up or // root has no left side, so we're done prev = NULL; } else { // We've iterated to root from the right side // and root has a left side we should check out // So, find the left-side predecessor to root "q" Item* r = q; x = q->left; do { q = x; if (tree->Bit(r->GetKey(), r->GetKeysize(), x->bit, keyEndian)) x = x->right; else x = x->left; } while (x != r); if (q->left != q) { // Go as far right of "q->left" as possible q = q->left; do { x = q; q = q->right; } while (x == q->parent); } prev = q; } next = item; return item; } } // end if (q->right != prev) if (q->left->parent != q) { if ((NULL == q->left->parent) && (q->left->left != q->left) && tree->Bit(q->GetKey(), q->GetKeysize(), 0, keyEndian)) { // We've come from the right and there is a left of root // So, go as far right of the left of root "q->left" as possible x = q->left->left; do { q = x; x = x->right; } while (q == x->parent); prev = x; } else { // Otherwise, this is the appropriate iterate prev = q->left; } } else { // Go as far right of "q->left" as possible x = q->left; do { q = x; x = x->right; } while (q == x->parent); prev = x; } next = item; return item; } else { return NULL; } } // end ProtoTree::Iterator::GetPrevItem() ProtoTree::Item* ProtoTree::Iterator::PeekPrevItem() { if (reversed) { return prev; } else { Item* prevItem = GetPrevItem(); GetNextItem(); // puts mode/cursor back to right place return prevItem; } } // end ProtoTree::PeekPrevItem() ProtoTree::Item* ProtoTree::Iterator::GetNextItem() { if (NULL != next) { ProtoTree* tree = static_cast(iterable); if (reversed) { // This iterator has been going backwards // so we need to turn it around reversed = false; SetCursor(*next); if (NULL == next) return NULL; } Item* item = next; Endian keyEndian = next->GetEndian(); if (NULL == curr_hop) { next = NULL; } else { Item* x = curr_hop; if (((x->left != next) && (x->left->parent != x)) || (x->right->parent == x)) { next = x->left; // Now, update "curr_hop" if applicable // First, check for root node visit if ((NULL == next->parent) && (tree->Bit(next->GetKey(), next->GetKeysize(), 0, keyEndian) != tree->Bit(x->GetKey(), x->GetKeysize(), 0, keyEndian))) { if (x->right == x) { next = x; curr_hop = NULL; } else { // Branch right and go as far left as possible x = x->right; while (x->left->parent == x) x = x->left; next = x->left; if (x->right->parent == x) { // Branch right and go as far left as possible x = x->right; while (x->left->parent == x) x = x->left; } curr_hop = x; } } else if (x->right->parent == x) { // Branch right and go as far left as possible x = x->right; while (x->left->parent == x) x = x->left; curr_hop = x; } // Otherwise, there was no change to "curr_hop" for now } else // if (curr_hop->right->parent != curr_hop) { // Right item is next in iteration next = x->right; // Now, update "curr_hop" if applicable // First, check for root node visit if ((NULL == next->parent) && (next->right != next) && (tree->Bit(x->GetKey(), x->GetKeysize(), 0, keyEndian) != tree->Bit(next->GetKey(), next->GetKeysize(), 0, keyEndian))) { // Branch right and go as far left as possible x = next->right; while (x->left->parent == x) x = x->left; next = x->left; if (x->right->parent == x) { // Again, branch right and go as far left as possible x = x->right; while (x->left->parent == x) x = x->left; } curr_hop = x; } else { // Go back up the tree Item* p = x->parent; while ((p != NULL) && (p->right == x)) { x = p; p = x->parent; } if (NULL != p) { if ((NULL == p->parent) && (p->right == p)) { p = NULL; } else if (p->right->parent == p) { // Branch right and go as far left as possible Item* x = p->right; while (x->left->parent == x) x = x->left; p = x; } } curr_hop = p; } } } // end if/else (NULL == curr_hop) if (0 != prefix_size) { // Test "item" against prefix of item last returned if ((NULL == prefix_item) || !tree->PrefixIsEqual(item->GetKey(), item->GetKeysize(), prefix_item->GetKey(), prefix_size, keyEndian)) return NULL; } prev = item; return item; } else { return NULL; } // end if/else(NULL != next) } // end ProtoTree::Item* ProtoTree::Iterator::GetNextItem() ProtoTree::Item* ProtoTree::Iterator::PeekNextItem() { if (reversed) { Item* nextItem = GetNextItem(); GetPrevItem(); // puts mode/cursor back to right place return nextItem; } else { return next; } } // end ProtoTree::PeekNextItem() void ProtoTree::Iterator::Update(ProtoIterable::Item* theItem, Action theAction) { switch (theAction) { case INSERT: { // Save our current iterator state Item* oldPrev = prev; Item* oldNext = next; Item* oldPrefixItem = prefix_item; // First, find new prefix subtree if applicable/needed if (NULL != prefix_item) { Reset(reversed, prefix_item->GetKey(), prefix_size); ASSERT(NULL != prefix_item); // should have found old one at least } // Restore iterator cursor state if (reversed) { if (NULL != oldNext) SetCursor(*oldNext); else if (NULL == prefix_item) Reset(true); } else { if (NULL != oldPrev) SetCursor(*oldPrev); else if (NULL == oldPrefixItem) Reset(false); } break; } case REMOVE: { // NOTE - This doesn't work quite right for prefix iterators // (mid-iteration removal of items can break comprehensive prefix iteration) // Save our current iterator state Item* oldPrev = prev; Item* oldNext = next; // First, find new prefix subtree if applicable/needed if (static_cast(theItem) == prefix_item) { Reset(reversed, prefix_item->GetKey(), prefix_size); if (NULL == prefix_item) break; // no matching prefix subtree remains } // Restore cursor state with trick if cursor was item removed if (reversed) { // "next" is the cursor for reverse mode if (static_cast(theItem) != oldNext) { if (NULL == oldNext) { // tree is now empty? //ASSERT(NULL == prefix_item); if (NULL == prefix_item) prev = next = NULL; else Reset(reversed, prefix_item->GetKey(), prefix_size); } else { SetCursor(*oldNext); } } else { // This puts the iteration to a ambiguous // state that allows subsequent calls to // either GetPrevItem() or GetNextItem() to // work properly even though the "cursor" is // wrong. (Note PeekNextItem() won't be correct) if (NULL == oldPrev) { // tree is now empty? //ASSERT(NULL == prefix_item); if (NULL == prefix_item) prev = next = NULL; else Reset(reversed, prefix_item->GetKey(), prefix_size); } else { if (NULL == prefix_item) { SetCursor(*oldPrev); prev = oldPrev; } else { Reset(reversed, prefix_item->GetKey(), prefix_size); } } } } else { // "prev" is the cursor for normal mode if (static_cast(theItem) != oldPrev) { if (NULL == oldPrev) { // tree is now empty? //ASSERT(NULL == prefix_item); if (NULL == prefix_item) prev = next = NULL; else Reset(reversed, prefix_item->GetKey(), prefix_size); } else { SetCursor(*oldPrev); } } else { if (NULL == oldNext) { // tree is now empty? //ASSERT(NULL == prefix_item); if (NULL == prefix_item) prev = next = NULL; else Reset(reversed, prefix_item->GetKey(), prefix_size); } else { if (NULL == prefix_item) { SetCursor(*oldNext); next = oldNext; } else { Reset(reversed, prefix_item->GetKey(), prefix_size); } } } } break; } case EMPTY: prev = next = prefix_item = NULL; prefix_size = 0; break; case APPEND: case PREPEND: ASSERT(0); break; } } // end ProtoTree::Iterator::Update() ProtoTree::SimpleIterator::SimpleIterator(ProtoTree& theTree) : ProtoIterable::Iterator(theTree) { Reset(); } ProtoTree::SimpleIterator::~SimpleIterator() { } void ProtoTree::SimpleIterator::Reset() { ProtoTree* tree = static_cast(iterable); if (NULL != tree) { Item* x = tree->root; if (NULL != x) { // Go left as far as possible while (x->left->parent == x) x = x->left; } next = x; } else { next = NULL; } } // end ProtoTree::SimpleIterator::Reset() ProtoTree::Item* ProtoTree::SimpleIterator::GetNextItem() { Item* i = next; if (NULL != i) { if (i->right->parent == i) { // Go right one, then left as far as possible Item* y = i->right; while (y->left->parent == y) y = y->left; if (y != i) { next = y; return i; } } Item* x = i; Item* y = i->parent; while ((NULL != y) && (y->right == x)) { x = y; y = y->parent; } next = y; } return i; } // end ProtoTree::SimpleIterator::GetNextItem() void ProtoTree::SimpleIterator::Update(ProtoIterable::Item* /*theItem*/, Action /*theAction*/) { // For ProtoTree::SimpleIterator, really the only "sane" thing to do when the associated // tree is modified is to "Reset()" the iterator since the logical tree structure // is potentially heavily affected by any change. This is heavy-handed so it's // actually more efficient to do a "GetRoot(), Remove()" loop until GetRoot() returns NULL // (see ProtoTree::Destroy()) instead of using this SimpleIterator. Where it _is_ // useful is in the ProtoIndexedQueue::Empty() method where it empties the tree without invoking // any of the Item virtual methods (i.e. GetKey(), etc). The SimpleIterator is also useful // as a little lighter weight (than the regular ProtoTree::Iterator) where the order of // iteration doesn't matter and mid-iteration Item insertion/removal isn't done. Reset(); } // end ProtoTree::SimpleIterator::Update() ProtoSortedTree::ProtoSortedTree(bool uniqueItemsOnly) : unique_items_only(uniqueItemsOnly), positive_min(NULL) { } ProtoSortedTree::~ProtoSortedTree() { } bool ProtoSortedTree::Insert(Item& item) { ASSERT(0 != item.GetKeysize()); // Is an item with this key already in tree? const char* key = item.GetKey(); unsigned int keysize = item.GetKeysize(); ProtoTree::Endian keyEndian = item.GetEndian(); Item* match = Find(key, keysize); if (NULL == match) { // Insert the item into our "item_tree" item_tree.Insert(item); // Now find the place to thread this new item into our linked list ProtoTree::Iterator iterator(item_tree, true, &item); match = static_cast(iterator.PeekPrevItem()); if (NULL == match) { if (item_list.IsEmpty()) { // nothing in the list yet item_list.Append(item); if (item.UseSignBit()) { bool itemSign = item_tree.Bit(key, keysize, 0, keyEndian); if (!itemSign) positive_min = &item; } } else { // this item lexically precedes the anything in the tree bool useSignBit = item.UseSignBit(); ASSERT(useSignBit == GetHead()->UseSignBit()); if (useSignBit) { bool itemSign = item_tree.Bit(key, keysize, 0, keyEndian); if (itemSign) { bool useComplement2 = item.UseComplement2(); ASSERT(useComplement2 == GetHead()->UseComplement2()); // A signed "item" with no lexical predecessor if (useComplement2) { // is smallest negative number in a tree that // has no positive numbers yet. // So this goes to the "head" automatically! item_list.Prepend(item); } else { // is biggest negative number in a tree that // has no positive numbers yet. // So this goes to the "tail" automatically! item_list.Append(item); } // Note: (itemSign && !headSign) is impossible here } else { Item* head = GetHead(); bool headSign = item_tree.Bit(head->GetKey(), head->GetKeysize(), 0, keyEndian); if (headSign) { // (!itemSign && headSign) // An unsigned (positive value) "item" with no lexical predecessor // is the smallest _positive_ number in the tree // so insert this before our prior "positive_min" or at tail if (NULL != positive_min) { item_list.Insert(item, *positive_min); } else { // first positive value, put at tail item_list.Append(item); } positive_min = &item; } else { // (!itemSign && !headSign) // Both positive, and "item" < "head" // (no negative numbers in the tree?) // So, insert "item" before "head" item_list.Prepend(item); positive_min = &item; } } } else { // this item lexically precedes the "head" item_list.Prepend(item); } // end if/else (useSignBit) } // end if/else item_list.IsEmpty() } else { // this "item" lexically succeeds the "match" bool useSignBit = item.UseSignBit(); ASSERT(useSignBit == match->UseSignBit()); if (useSignBit) { bool itemSign = item_tree.Bit(key, keysize, 0, keyEndian); if (!itemSign) { // (!itemSign && !matchSign) // Both positive, match < item // Insert "item" just after "match" Item* next = static_cast(item_list.GetNextItem(*match)); if (NULL != next) item_list.Insert(item, *next); else item_list.Append(item); ASSERT(!item_tree.Bit(match->GetKey(), match->GetKeysize(), 0, keyEndian)); // Note (!itemSign && matchSign) can't happen // here since signed "match" (negative value) // _must_ lexically succeed unsigned "item" } else { bool useComplement2 = item.UseComplement2(); ASSERT(useComplement2 == match->UseComplement2()); bool matchSign = item_tree.Bit(match->GetKey(), match->GetKeysize(), 0, keyEndian); if (matchSign) { // (itemSign && matchSign) if (useComplement2) { // Both negative, "match" < "item" // Insert "item" just after "match" Item* next = static_cast(item_list.GetNextItem(*match)); if (NULL != next) item_list.Insert(item, *next); else item_list.Append(item); } else { // Both negative, "item" < "match" // Insert "item" before first equivalent "match" // note "prev" here lexically _succeeds_ this // "item" that was inserted into tree above, so: ProtoTree::Iterator iterator(item_tree, false, &item); Item* prev = static_cast(iterator.PeekNextItem()); /* (Old "while()" loop approach to find prev, in-tree item) Item* prev = match->GetPrev(); while ((NULL != prev) && !prev->IsInTree()) { match = prev; prev = prev->GetPrev(); } */ if (NULL != prev) { Item* next = static_cast(item_list.GetNextItem(*prev)); ASSERT(NULL != next); item_list.Insert(item, *next); } else { item_list.Prepend(item); } } } else { // (itemSign && !matchSign) if (useComplement2) { // Smallest negative number, put at list head item_list.Prepend(item); } else { // Greatest negative number, put before "positive_min" ASSERT(NULL != positive_min); item_list.Insert(item, *positive_min); } } } } else { // Insert the item just after the close "match" from "item_tree" Item* next = static_cast(item_list.GetNextItem(*match)); if (NULL != next) item_list.Insert(item, *next); else item_list.Append(item); } // end if/else (useSignBit) } } else if (match != &item) { if (unique_items_only) return false; // Insert the item just before the exact "match" from "item_tree" item_list.Insert(item, *match); item.left = NULL; // denotes item is _not_ in tree (in linked list only) bool useSignBit = item.UseSignBit(); ASSERT(useSignBit == match->UseSignBit()); if (useSignBit && (match == positive_min)) positive_min = &item; } else { PLOG(PL_ERROR, "ProtoSortedTree::Insert() warning: item already in tree!\n"); } return true; } // end ProtoSortedTree::Insert() void ProtoSortedTree::Prepend(Item& item) { item_list.Prepend(item); } // end ProtoSortedTree::Prepend() void ProtoSortedTree::Append(Item& item) { item_list.Append(item); } // end ProtoSortedTree::Append() void ProtoSortedTree::Remove(Item& item) { // 1) Save some state and remove from linked list Item* prev = static_cast(item_list.GetPrevItem(item)); if (&item == positive_min) positive_min = static_cast(item_list.GetNextItem(item)); item_list.Remove(item); // 2) Remove from ProtoTree, if applicable if (item.IsInTree()) { // Remove "item" from the tree and mark as removed (item.left = NULL) item_tree.Remove(item); item.left = NULL; // Does "prev" needs to take the place of "item" in the ProtoTree? if ((NULL != prev) && !prev->IsInTree()) item_tree.Insert(*prev); } } // end ProtoSortedTree::Remove() void ProtoSortedTree::Empty() { if (!IsEmpty()) { item_tree.Empty(); item_list.Empty(); positive_min = NULL; } } // end ProtoSortedTree::Empty() void ProtoSortedTree::EmptyToPool(ItemPool& itemPool) { if (!IsEmpty()) { item_tree.Empty(); item_list.EmptyToPool(itemPool); positive_min = NULL; } } // end ProtoSortedTree::EmptyToPool() void ProtoSortedTree::Destroy() { if (!IsEmpty()) { item_tree.Empty(); item_list.Destroy(); positive_min = NULL; } } // end ProtoSortedTree::Destroy() ProtoSortedTree::Item::Item() { } ProtoSortedTree::Item::~Item() { } ProtoSortedTree::Iterator::Iterator(ProtoSortedTree& theTree, bool reverse, const char* keyMin, unsigned int keysize) : tree(theTree), list_iterator(theTree.item_list, reverse) { Reset(reverse, keyMin, keysize); } ProtoSortedTree::Iterator::~Iterator() { } void ProtoSortedTree::Iterator::Reset(bool reverse, const char* keyMin, unsigned int keysize) { list_iterator.Reset(reverse); // put the iterator in the right direction if ((NULL != keyMin) && list_iterator.IsValid() && !tree.IsEmpty()) { // refine if a "keyMin" start point was provided // (note for "reverse" == true, "keyMin" is really a "keyMax" Item* match = tree.Find(keyMin, keysize); if (NULL == match) { // There was no exact match to "keyMin", so look for next item (or prev if reverse == true) TempItem tmpItem(keyMin, keysize, tree.GetHead()->GetEndian()); tree.item_tree.Insert(tmpItem); ProtoTree::Iterator iterator(tree.item_tree, reverse, &tmpItem); match = reverse ? static_cast(iterator.PeekPrevItem()) : static_cast(iterator.PeekNextItem()); tree.item_tree.Remove(tmpItem); // it's done its job, so bye-bye } if ((NULL != match) && !reverse) { // Make sure we are positioned on _first_ item of equal valued items ProtoTree::Iterator iterator(tree.item_tree, true, match); Item* prev = static_cast(iterator.PeekPrevItem()); if (NULL == prev) match = tree.item_list.GetHead(); else match = static_cast(tree.item_list.GetNextItem(*prev)); } list_iterator.SetCursor(match); } } // end ProtoSortedTree::Iterator::Reset() ProtoSortedTree::Iterator::TempItem::TempItem(const char* theKey, unsigned int theKeysize, ProtoTree::Endian keyEndian) : key(theKey), keysize(theKeysize), key_endian(keyEndian) { } ProtoSortedTree::Iterator::TempItem::~TempItem() { }