/********************************************************************* * * 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. ********************************************************************/ #ifndef _PROTO_TREE #define _PROTO_TREE #include "protoList.h" // for ProtoIterable base class #include #ifndef _WIN32_WCE #include // for BYTE_ORDER (ENDIAN) macros for "ProtoTree::GetNativeEndian() #else #include #endif /** * @class ProtoTree * * @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. * * The class ProtoTree provides a relatively * lightweight but good performance * data storage and retrieval mechanism which * might be useful in prototype protocol * implementations. Thus, its inclusion * in the NRL Protolib. * * Note: "Items" with different key sizes are * now freely mixed within a single tree structure. * The keys of Items within a ProtoTree must be * unique. However, ProtoSortedTree (see below) * allows multiple items with the same key to be * inserted into it. Arbitrary length strings * can be easily indexed. * * ProtoTree supports the notion of big * or little endian byte order of the Item * keys (Note however it is still a prefix * tree, regardless of the "endian"). This * is useful for "ProtoSortedTree::Item" * subclasses that may wish to have the ordering * based on a key that is a data type ordered * according to the machine endian (e.g., * integers, IEEE doubles, etc). * Big Endian is default. * */ class ProtoTree : public ProtoIterable { public: ProtoTree(); virtual ~ProtoTree(); bool IsEmpty() const {return (NULL == root);} // "Empty()" doesn't delete the items, just removes them all from the tree void Empty(); // "Destroy()" deletes any items in the tree void Destroy(); class Item; // Insert the "item" into the tree (will fail if item with equivalent key already in tree) bool Insert(Item& item); // Remove the "item" from the tree void Remove(Item& item); // This should be implemented as shown here. I commented it out // to detect if anything was using its old, incorrect implementation //bool Contains(const Item& item) const // {return (&item == Find(item.GetKey(), item.GetKeysize()));} // Find item with exact match to "key" and "keysize" (keysize is in bits) ProtoTree::Item* Find(const char* key, unsigned int keysize) const; ProtoTree::Item* FindString(const char* keyString) const {return Find(keyString, (unsigned int)(8*strlen(keyString)));} // Find shortest item to which 'key' is a prefix, or secondly the item that // is the largest prefix of 'key' (i.e. the closet prefix match) ProtoTree::Item* FindClosestMatch(const char* key, unsigned int keysize) const; // Find item which is largest prefix of the "key" (keysize is in bits) ProtoTree::Item* FindPrefix(const char* key, unsigned int keysize) const; ProtoTree::Item* GetRoot() const {return root;} ProtoTree::Item* GetFirstItem() const; ProtoTree::Item* GetLastItem() const; ProtoTree::Item* RemoveRoot(); class Iterator; class ItemPool; enum Endian {ENDIAN_BIG, ENDIAN_LITTLE}; // Helper static function to get "native" (hardware) endian static ProtoTree::Endian GetNativeEndian() { #if BYTE_ORDER == LITTLE_ENDIAN return ProtoTree::ENDIAN_LITTLE; #else return ProtoTree::ENDIAN_BIG; #endif // end if/else (BYTE_ORDER == LITTLE_ENDIAN) } // end ProtoTree::GetNativeEndian() /** * @class Item * * @brief ProtoTree::Item provides a base class * for items to be stored in the tree. */ class Item : public ProtoIterable::Item { friend class ProtoTree; friend class Iterator; friend class ItemPool; public: Item(); virtual ~Item(); // Required overrides virtual const char* GetKey() const = 0; virtual unsigned int GetKeysize() const = 0; // Optional overrides // TBD - make the GetEndian() member of ProtoTree instead // i.e., just like UseSignBit() and UseComplementTwo() #ifdef WIN32 // Some windows compilers don't like the other format virtual Endian GetEndian() const {return ENDIAN_BIG;} // default endian for ProtoTree #else virtual ProtoTree::Endian GetEndian() const {return ENDIAN_BIG;} // default endian for ProtoTree #endif // Returns how deep in its tree this Item lies unsigned int GetDepth() const; // Debug helper for keys that are strings const char* GetKeyText() const { static char text[256]; unsigned int tlen = GetKeysize() >> 3; if (tlen > 255) tlen = 255; #ifdef WIN32 strncpy_s(text, 256, GetKey(), tlen); #else strncpy(text, GetKey(), tlen); #endif // if/else WIN32 text[tlen] = '\0'; return text; } protected: Item* GetParent() const {return parent;} Item* GetLeft() const {return left;} Item* GetRight() const {return right;} unsigned int GetBit() {return bit;} // bitwise comparison of the two keys bool IsEqual(const char* theKey, unsigned int theKeysize) const; bool PrefixIsEqual(const char* prefix, unsigned int prefixSize) const; // Methods for item pooling (accessed by class ItemPool) void SetPoolNext(Item* poolNext) {right = poolNext;} Item* GetPoolNext() const {return right;} unsigned int bit; Item* parent; Item* left; Item* right; }; // end class ProtoTree::Item /** * @class ItemPool * * @brief This is useful for managing a reserved "pool" of Items (containers) * even though it is not used by the ProtoTree classes themselves. We use * in other classes in Protolib that use ProtoTree (e.g. ProtoGraph, ProtoQueue, etc) */ class ItemPool { public: ItemPool(); virtual ~ItemPool(); void Destroy(); bool IsEmpty() const {return (NULL == head);} Item* Get(); void Put(Item& item); private: Item* head; }; // end class ProtoTree::ItemPool /** * @class Iterator * * @brief This can be used to iterate over the entire data set (default) * or limited to certain prefix subtree (iterates in lexical order) * NOTE: The iteration here invokes the ProtoTree::Item virtual * methods (GetKey(), etc) */ class Iterator : public ProtoIterable::Iterator { public: Iterator(ProtoTree& tree, bool reverse = false, Item* cursor = NULL); virtual ~Iterator(); void Reset(bool reverse = false, const char* prefix = NULL, unsigned int prefixSize = 0); void SetCursor(Item& item); Item* GetPrevItem(); Item* PeekPrevItem(); Item* GetNextItem(); Item* PeekNextItem(); //private: // Required override for ProtoIterable to make sure any // iterators associated with a list are updated upon // Item addition or removal. void Update(ProtoIterable::Item* theItem, Action theAction); bool reversed; // true if currently iterating backwards unsigned int prefix_size; // if non-zero, iterating over items of certain prefix Item* prefix_item; // reference item with matching prefix for subtree iteration Item* prev; Item* next; Item* curr_hop; }; // end class ProtoTree::Iterator friend class Iterator; /** * @class SimpleIterator * * @brief This can be used to iterate over the entire data set. Note * it does _not_ iterate in lexical order, but also (beneficially) * does _not_ make any virtual function calls (e.g. GetKey(), etc) * on the ProtoTree::Item members and is thus safe to call most all * of the time (i.e., such as during destructor calls) */ class SimpleIterator : public ProtoIterable::Iterator { public: SimpleIterator(ProtoTree& theTree); virtual ~SimpleIterator(); void Reset(); Item* GetNextItem(); private: // Required override for ProtoIterable to make sure any // iterators associated with a list are updated upon // Item addition or removal. void Update(ProtoIterable::Item* theItem, Action theAction); Item* next; }; // end class ProtoTree::SimpleIterator static bool Bit(const char* key, unsigned int keysize, unsigned int index, Endian keyEndian); static bool ItemIsEqual(const Item& item, const char* key, unsigned int keysize); static bool ItemsAreEqual(const Item& item1, const Item& item2); protected: // This finds the closest matching item with backpointer to "item" ProtoTree::Item* FindPredecessor(ProtoTree::Item& item) const; // This finds the root of a subtree of Items matching the given prefix ProtoTree::Item* FindPrefixSubtree(const char* prefix, unsigned int prefixLen) const; static bool KeysAreEqual(const char* key1, const char* key2, unsigned int keysize, Endian keyEndian); static bool PrefixIsEqual(const char* key, unsigned int keysize, const char* prefix, unsigned int prefixSize, Endian keyEndian); // Member variables Item* root; }; // end class ProtoTree // The ITEM_TYPE here _must_ be something // subclassed from ProtoTree::Item template class ProtoTreeTemplate : public ProtoTree { public: ProtoTreeTemplate() {} virtual ~ProtoTreeTemplate() {} bool Insert(ITEM_TYPE& item) {return ProtoTree::Insert(item);} void Remove(ITEM_TYPE& item) {ProtoTree::Remove(item);} // Find item with exact match to "key" and "keysize" (keysize is in bits) ITEM_TYPE* Find(const char* key, unsigned int keysize) const {return (static_cast(ProtoTree::Find(key, keysize)));} ITEM_TYPE* FindString(const char* keyString) const {return (static_cast(ProtoTree::FindString(keyString)));} ITEM_TYPE* FindClosestMatch(const char* key, unsigned int keysize) const {return (static_cast(ProtoTree::FindClosestMatch(key, keysize)));} // Find item which is largest prefix of the "key" (keysize is in bits) ITEM_TYPE* FindPrefix(const char* key, unsigned int keysize) const {return (static_cast(ProtoTree::FindPrefix(key, keysize)));} void Destroy() {ProtoTree::Destroy();} class Iterator : public ProtoTree::Iterator { public: Iterator(ProtoTreeTemplate& theTree, bool reverse = false, Item* cursor = NULL) : ProtoTree::Iterator(theTree, reverse, cursor) {} virtual ~Iterator() {} ITEM_TYPE* GetPrevItem() {return static_cast(ProtoTree::Iterator::GetPrevItem());} ITEM_TYPE* PeekPrevItem() {return static_cast(ProtoTree::Iterator::PeekPrevItem());} ITEM_TYPE* GetNextItem() {return static_cast(ProtoTree::Iterator::GetNextItem());} ITEM_TYPE* PeekNextItem() {return static_cast(ProtoTree::Iterator::PeekNextItem());} }; // end class ProtoTreeTemplate::Iterator class SimpleIterator : public ProtoTree::SimpleIterator { public: SimpleIterator(ProtoTreeTemplate& theTree) : ProtoTree::SimpleIterator(theTree) {} virtual ~SimpleIterator() {} ITEM_TYPE* GetNextItem() {return static_cast(ProtoTree::SimpleIterator::GetNextItem());} }; // end class ProtoTreeTemplate::SimpleIterator class ItemPool : public ProtoTree::ItemPool { public: ItemPool() {} virtual ~ItemPool() {} void Put(ITEM_TYPE& item) {ProtoTree::ItemPool::Put(item);} ITEM_TYPE* Get() {return static_cast(ProtoTree::ItemPool::Get());} }; // end class ProtoTreeTemplate::ItemPool }; // end class ProtoTreeTemplate // Example: /*class ExampleItem : public ProtoTree::Item { public: ExampleItem(char* theKey, unsigned int theKeysize, void* theValue): key(theKey), keysize(theKeysize), value(theValue) {} ~ExampleItem() {} const char* GetKey() const {return key;} unsigned int GetKeysize() const {return keysize;} const void* GetValue() const {return value;} private: const char * key; unsigned int keysize; const void * value; }; class ExampleItemList : public ProtoTreeTemplate {}; */ /** * @class ProtoSortedTree * * @brief This class extends ProtoTree::Item to provide a "threaded" tree * for rapid (linked-list) iteration. Also note that entries with * duplicate key values are allowed. * * By default, items are sorted lexically by their key. Optionally the tree may be configured * to treat the first bit of the key as a "sign" bit and order the * sorted list properly with a mix of positive and negative values * using two's complement (e.g. "int") rules or just signed ordering * (e.g. "double"). Note that the key Endian must be set properly * according to what the key represents. */ class ProtoSortedTree { // TBD - this should be reimplemented using ProtoList for the // threaded aspect. public: ProtoSortedTree(bool uniqueItemsOnly = false); virtual ~ProtoSortedTree(); bool IsEmpty() const {return item_tree.IsEmpty();} class Iterator; class ItemPool; class Item : public ProtoTree::Item, public ProtoList::Item { friend class ProtoSortedTree; friend class Iterator; friend class ItemPool; public: Item(); virtual ~Item(); // Required overrides virtual const char* GetKey() const = 0; virtual unsigned int GetKeysize() const = 0; // TBD - move the Endian, UseComplement2, UseSignBit stuff // _out_ of the ProtoSortedTree::Item and make them // configurable properties of the tree class itself??? // Optional overrides (affect sorting) virtual ProtoTree::Endian GetEndian() const #ifdef WIN32 // some windows compilers are more restrictive {return ProtoTree::Item::GetEndian();} #else {return ProtoTree::Item::GetEndian();} #endif virtual bool UseSignBit() const {return false;} virtual bool UseComplement2() const {return true;} private: // Linked list (threading) helper bool IsInTree() const {return (NULL != left);} }; // end class ProtoSortedTree::Item bool Insert(Item& item); Item* GetHead() const {return item_list.GetHead();} Item* RemoveHead() { Item* item = GetHead(); if (NULL != item) Remove(*item); return item; } Item* GetTail() const {return item_list.GetTail();} Item* GetRoot() const {return static_cast(item_tree.GetRoot());} // Random access methods (uses ProtoTree) // Note that since a ProtoSortedTree can have multiple items // with the same key, you should generally use the // ProtoSortedTree::Iterator and set the keyMin/keysize // parameters to find _all_ items for a given "key" // (i.e., iterate until the next item key doesn't match) Item* Find(const char* key, unsigned int keysize) const {return item_tree.Find(key, keysize);} Item* FindString(const char* keyString) const {return Find(keyString, (unsigned int)(8*strlen(keyString)));} // Find item which _is_ largest prefix of the "key" (keysize is in bits) Item* FindPrefix(const char* key, unsigned int keysize) const {return item_tree.FindPrefix(key, keysize);} void Remove(Item& item); //bool Contains(const Item& item) const // {return item_tree.Contains(item);} void Empty(); // empties tree without deleting items contained void Destroy(); // _Unsorted_ Prepend()/Append() methods ("Find()" won't work if used) // Do _not_ mix use of "Insert()" method w/ Prepend()/Append() methods! void Prepend(Item& item); void Append(Item& item); protected: class List : public ProtoListTemplate {}; public: class Iterator { public: Iterator(ProtoSortedTree& tree, bool reverse = false, const char* keyMin = NULL, unsigned int keysize = 0); virtual ~Iterator(); bool HasEmptyTree() const {return tree.IsEmpty();} // These methods can be used to jog back and forth as desired // (i.e. reversals are automatically managed) Item* GetNextItem() {return list_iterator.GetNextItem();} Item* GetPrevItem() {return list_iterator.GetPrevItem();} Item* PeekNextItem() {return list_iterator.PeekNextItem();} Item* PeekPrevItem() {return list_iterator.PeekPrevItem();} /// Note if "reverse" is "true", then "keyMin" is really "keyMax" void Reset(bool reverse = false, const char* keyMin = NULL, unsigned int keysize = 0); void SetCursor(Item* item) {list_iterator.SetCursor(item);} Item* GetCursor() {return list_iterator.PeekNextItem();} // This flips the reversal state, moving // cursor forward or backward one item void Reverse() {list_iterator.Reverse();} bool IsReversed() const {return list_iterator.IsReversed();} private: /** * @class TempItem * * @brief This is a helper class for getting iterator started, etc */ class TempItem : public Item { public: TempItem(const char* theKey, unsigned int theKeysize, ProtoTree::Endian keyEndian); virtual ~TempItem(); const char* GetKey() const {return key;} unsigned int GetKeysize() const {return keysize;} ProtoTree::Endian GetEndian() const {return key_endian;} private: const char* key; unsigned int keysize; ProtoTree::Endian key_endian; }; // end class ProtoSortedTree::Iterator::TempItem ProtoSortedTree& tree; List::Iterator list_iterator; }; // end class ProtoSortedTree::Iterator friend class Iterator; /** * @class ItemPool * @brief This is useful for managing a reserved "pool" of Items (containers) */ class ItemPool : public List::ItemPool {}; void EmptyToPool(ItemPool& itemPool); protected: class Tree : public ProtoTreeTemplate {}; bool unique_items_only; // "false" by default (i.e., allow duplicate keys) Item* positive_min; // Pointer to minimum non-negative entry when useSignBit Tree item_tree; List item_list; }; // end class ProtoSortedTree // The ITEM_TYPE here _must_ be something // subclassed from ProtoSortedTree::Item template class ProtoSortedTreeTemplate : public ProtoSortedTree { public: ProtoSortedTreeTemplate() {} virtual ~ProtoSortedTreeTemplate() {} // Find item with exact match to "key" and "keysize" ITEM_TYPE* Find(const char* key, unsigned int keysize) const {return (static_cast(ProtoSortedTree::Find(key, keysize)));} // Find item which _is_ largest prefix of the "key" (keysize is in bits) ITEM_TYPE* FindPrefix(const char* key, unsigned int keysize) const {return (static_cast(ProtoSortedTree::FindPrefix(key, keysize)));} ITEM_TYPE* GetHead() const {return (static_cast(ProtoSortedTree::GetHead()));} ITEM_TYPE* GetTail() const {return (static_cast(ProtoSortedTree::GetTail()));} ITEM_TYPE* RemoveHead() {return (static_cast(ProtoSortedTree::RemoveHead()));} class Iterator : public ProtoSortedTree::Iterator { public: Iterator(ProtoSortedTreeTemplate& theTree, bool reverse = false, const char* keyMin = NULL, unsigned int keysize = 0) : ProtoSortedTree::Iterator(theTree, reverse, keyMin, keysize) {} virtual ~Iterator() {} ITEM_TYPE* GetPrevItem() {return static_cast(ProtoSortedTree::Iterator::GetPrevItem());} ITEM_TYPE* PeekPrevItem() {return static_cast(ProtoSortedTree::Iterator::PeekPrevItem());} ITEM_TYPE* GetNextItem() {return static_cast(ProtoSortedTree::Iterator::GetNextItem());} ITEM_TYPE* PeekNextItem() {return static_cast(ProtoSortedTree::Iterator::PeekNextItem());} }; // end class ProtoSortedTreeTemplate::Iterator class ItemPool : public ProtoSortedTree::ItemPool { public: ItemPool() {} virtual ~ItemPool() {} void Put(ITEM_TYPE& item) {ProtoSortedTree::ItemPool::Put(item);} ITEM_TYPE* Get() {return static_cast(ProtoSortedTree::ItemPool::Get());} }; // end class ProtoSortedTreeTemplate::ItemPool }; // end class ProtoSortedTreeTemplate // Here's an example use of ProtoSortedTree configured to keep a table of items indexed // by a "double" key. Note that multiple equal-valued items _can_ be included in a // ProtoSortedTree (the basic ProtoTree only allows a single item with a given key). /* class ExampleItem : public ProtoSortedTree::Item { public: ExampleItem(double key); private: const char* GetKey() const {return (char*)&item_key;} unsigned int GetKeysize() const {return (sizeof(double) << 3);} double item_key; }; // end class ExampleItem class ExampleTree : public ProtoSortedTreeTemplate { private: // These configure the key interpretation to properly sort "double" type key values virtual bool UseSignBit() const {return true;} virtual bool UseComplement2() const {return false;} virtual ProtoTree::Endian GetEndian() const {return ProtoTree::GetNativeEndian();} }; */ #endif // PROTO_TREE