arzmq-sys 0.6.3

/*********************************************************************
 *
 * 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 <string.h>
#ifndef _WIN32_WCE
#include <sys/types.h>  // for BYTE_ORDER (ENDIAN) macros for "ProtoTree::GetNativeEndian()
#else
#include <types.h>
#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 ITEM_TYPE>
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<ITEM_TYPE*>(ProtoTree::Find(key, keysize)));}
        
        ITEM_TYPE* FindString(const char* keyString) const
            {return (static_cast<ITEM_TYPE*>(ProtoTree::FindString(keyString)));}
        
        ITEM_TYPE* FindClosestMatch(const char* key, unsigned int keysize) const
            {return (static_cast<ITEM_TYPE*>(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<ITEM_TYPE*>(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<ITEM_TYPE*>(ProtoTree::Iterator::GetPrevItem());}
                ITEM_TYPE* PeekPrevItem()
                    {return static_cast<ITEM_TYPE*>(ProtoTree::Iterator::PeekPrevItem());}
                
                ITEM_TYPE* GetNextItem()
                    {return static_cast<ITEM_TYPE*>(ProtoTree::Iterator::GetNextItem());}
                ITEM_TYPE* PeekNextItem()
                    {return static_cast<ITEM_TYPE*>(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<ITEM_TYPE*>(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<ITEM_TYPE*>(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<ExampleItem> {}; 
*/
/**
 * @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*>(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<Item> {};   
    
    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<Item> {}; 
        
        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 ITEM_TYPE>
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<ITEM_TYPE*>(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<ITEM_TYPE*>(ProtoSortedTree::FindPrefix(key, keysize)));}
        
        ITEM_TYPE* GetHead() const
            {return (static_cast<ITEM_TYPE*>(ProtoSortedTree::GetHead()));}      
        ITEM_TYPE* GetTail() const
            {return (static_cast<ITEM_TYPE*>(ProtoSortedTree::GetTail()));}
        ITEM_TYPE* RemoveHead() 
            {return (static_cast<ITEM_TYPE*>(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<ITEM_TYPE*>(ProtoSortedTree::Iterator::GetPrevItem());}
                ITEM_TYPE* PeekPrevItem()
                    {return static_cast<ITEM_TYPE*>(ProtoSortedTree::Iterator::PeekPrevItem());}
                
                ITEM_TYPE* GetNextItem()
                    {return static_cast<ITEM_TYPE*>(ProtoSortedTree::Iterator::GetNextItem());}
                ITEM_TYPE* PeekNextItem()
                    {return static_cast<ITEM_TYPE*>(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<ITEM_TYPE*>(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);}
        // 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();}    
            
        double  item_key;
};  // end class ExampleItem

class ExampleTree : public ProtoSortedTreeTemplate<ExampleItem> {};

*/
        
#endif // PROTO_TREE