ACE/apps/JAWS2/JAWS/Hash_Bucket_T.h

   1 /* -*- c++ -*- */
   2 // Hey Emacs!  This is a C++ file!
   3 #ifndef JAWS_HASH_BUCKET_T_H
   4 #define JAWS_HASH_BUCKET_T_H
   5
   6 #include "ace/Containers.h"
   7
   8 #define JAWS_HASH_BUCKET_ITEM JAWS_Hash_Bucket_Item<EXT_ID, INT_ID>
   9 #define JAWS_HASH_BUCKET_DLCSTACK JAWS_Hash_Bucket_DLCStack<EXT_ID, INT_ID>
  10 #define JAWS_HASH_BUCKET_DLCSTACK_ITERATOR \
  11         JAWS_Hash_Bucket_DLCStack_Iterator<EXT_ID, INT_ID>
  12
  13
  14 // Why Hash_Bucket?
  15 //
  16 // This is an attempt to simplify the creation of high-performance
  17 // hash tables with respect to concurrent access by multiple threads.
  18 // To this end, we attempt to raise the amount of concurrency through
  19 // the use or readers/writer locks rather than through mutual
  20 // exclusion.
  21
  22 template <class EXT_ID, class INT_ID>
  23 class JAWS_Hash_Bucket_Item
  24 {
  25 public:
  26   JAWS_Hash_Bucket_Item (const EXT_ID &ext_id, const INT_ID &int_id,
  27                          JAWS_Hash_Bucket_Item<EXT_ID, INT_ID> *next = 0,
  28                          JAWS_Hash_Bucket_Item<EXT_ID, INT_ID> *prev = 0);
  29   JAWS_Hash_Bucket_Item (JAWS_Hash_Bucket_Item<EXT_ID, INT_ID> *next = 0,
  30                          JAWS_Hash_Bucket_Item<EXT_ID, INT_ID> *prev = 0);
  31
  32   ~JAWS_Hash_Bucket_Item ();
  33   // Destructor.
  34
  35   EXT_ID ext_id_;
  36   // Key used to look up an entry.
  37
  38   INT_ID int_id_;
  39   // The contents of the entry itself.
  40
  41   JAWS_Hash_Bucket_Item<EXT_ID, INT_ID> *next_;
  42   // Pointer to the next item in the bucket of overflow nodes.
  43
  44   JAWS_Hash_Bucket_Item<EXT_ID, INT_ID> *prev_;
  45   // Pointer to the prev item in the bucket of overflow nodes.
  46 };
  47
  48
  49 template <class EXT_ID, class INT_ID> class JAWS_Hash_Bucket_DLCStack_Iterator;
  50
  51 template <class EXT_ID, class INT_ID, class EQ_FUNC>
  52 class JAWS_Hash_Bucket_Manager;
  53
  54 template <class EXT_ID, class INT_ID>
  55 class JAWS_Hash_Bucket_DLCStack
  56 // Create a doubly linked circular stack to be managed by the
  57 // Hash_Bucket_Manager
  58 {
  59   friend class JAWS_Hash_Bucket_DLCStack_Iterator<EXT_ID, INT_ID>;
  60
  61 public:
  62   JAWS_Hash_Bucket_DLCStack (ACE_Allocator *alloc = 0);
  63   ~JAWS_Hash_Bucket_DLCStack ();
  64
  65   int is_empty () const;
  66   // Returns 1 if the container is empty, otherwise returns 0.
  67
  68   JAWS_Hash_Bucket_Item<EXT_ID, INT_ID> *push (const EXT_ID &ext_id,
  69                                               const INT_ID &int_id);
  70   // Adds <new_item> to the head of the list.
  71   // Returns the new item that was inserted.
  72
  73   JAWS_Hash_Bucket_Item<EXT_ID, INT_ID> *pop ();
  74   // Removes and returns the first <item> in the list.  Returns
  75   // internal node's address on success, 0 if the queue was empty.
  76   // This method will *not* free the internal node.
  77
  78   void reset ();
  79   // Reset the <JAWS_Hash_Bucket_DLCStack> to be empty.
  80   // Notice that since no one is interested in the items within,
  81   // This operation will delete all items.
  82
  83   int remove (JAWS_Hash_Bucket_Item<EXT_ID, INT_ID> *item);
  84   // If item is still part of the CStack, it is removed.
  85   // In anycase, if there is no error, item is freed.
  86   // Returns 0 if ok, -1 on error.
  87
  88   ACE_Allocator *allocator_;
  89
  90 private:
  91   JAWS_Hash_Bucket_Item<EXT_ID, INT_ID> *head_;
  92   JAWS_Hash_Bucket_Item<EXT_ID, INT_ID> *tail_;
  93 };
  94
  95
  96 template <class EXT_ID, class INT_ID>
  97 class JAWS_Hash_Bucket_DLCStack_Iterator
  98 {
  99 public:
 100   JAWS_Hash_Bucket_DLCStack_Iterator (const JAWS_HASH_BUCKET_DLCSTACK &dlcstack);
 101
 102   int first ();
 103   // Moves to first element in the set, clears done flag.  Returns 0
 104   // if empty, 1 otherwise.
 105
 106   int last ();
 107   // Moves to last element in the set, clears done flag.  Returns 0 if
 108   // empty, 1 otherwise.
 109
 110   int advance ();
 111   // Move forward by one element of set.  Returns 0 if empty or we end
 112   // up being the first element in the set, 1 otherwise.  If advance
 113   // takes us to the first element, done is set to true.
 114
 115   int revert ();
 116   // Move backward by one element of set.  Returns 0 if empty or we
 117   // end up being the last element in the set, 1 otherwise.  If revert
 118   // takes us to the last element, done is set to true.
 119
 120   int next (JAWS_HASH_BUCKET_ITEM *&item);
 121   int next (JAWS_HASH_BUCKET_ITEM *&item) const;
 122   // Pass back the next item.  Returns 0 if done is true, 1 otherwise.
 123
 124   int prev (JAWS_HASH_BUCKET_ITEM *&item);
 125   int prev (JAWS_HASH_BUCKET_ITEM *&item) const;
 126   // Pass back the previous item.  Returns 0 if done is true, 1
 127   // otherwise.
 128
 129   int done () const;
 130   // Returns 1 if done_ flag is set, 0 otherwise.  done_ flag is set
 131   // if next takes us to first element or prev takes us to last
 132   // element.
 133
 134 private:
 135   const JAWS_HASH_BUCKET_DLCSTACK &dlcstack_;
 136   JAWS_HASH_BUCKET_ITEM *next_;
 137   JAWS_HASH_BUCKET_ITEM *prev_;
 138   int done_;
 139 };
 140
 141
 142 template <class EXT_ID, class INT_ID, class EQ_FUNC>
 143 class JAWS_Hash_Bucket_Manager
 144 {
 145 public:
 146   JAWS_Hash_Bucket_Manager (ACE_Allocator *alloc = 0);
 147   int open (ACE_Allocator *alloc = 0);
 148
 149   ~JAWS_Hash_Bucket_Manager ();
 150   int close ();
 151
 152   int find (const EXT_ID &ext_id) const;
 153   int find (const EXT_ID &ext_id, INT_ID &int_id) const;
 154   // Locate <ext_id> and pass out parameter via <int_id>.  If found,
 155   // return 0, returns -1 if not found.
 156
 157   int bind (const EXT_ID &ext_id, const INT_ID &int_id);
 158   int trybind (const EXT_ID &ext_id, INT_ID &int_id);
 159   // Associate <ext_id> with <int_id> if and only if <ext_id> is not
 160   // in the map.  If <ext_id> is already in the map then the <int_id>
 161   // parameter is assigned the existing value in the map.  Returns 0
 162   // if a new entry is bound successfully, returns 1 if an attempt is
 163   // made to bind an existing entry, and returns -1 if failures occur.
 164
 165   int rebind (const EXT_ID &ext_id, const INT_ID &int_id,
 166               EXT_ID &old_ext_id, INT_ID &old_int_id);
 167   // Associate <ext_id> with <int_id>.  If <ext_id> is not in the map
 168   // then behaves just like <bind>.  Otherwise, store the old values
 169   // of <ext_id> and <int_id> into the "out" parameters and rebind the
 170   // new parameters.  This is very useful if you need to have an
 171   // atomic way of updating <JAWS_Hash_Map_Entrys> and you also need full
 172   // control over memory allocation.  Returns 0 if a new entry is
 173   // bound successfully, returns 1 if an existing entry was rebound,
 174   // and returns -1 if failures occur.
 175
 176   int unbind (const EXT_ID &ext_id);
 177   int unbind (const EXT_ID &ext_id, INT_ID &int_id);
 178   // Break any association of <ext_id>.  Returns the value of <int_id>
 179   // in case the caller needs to deallocate memory.  Return value is 0
 180   // if unbind succeeds, -1 otherwise.
 181
 182 protected:
 183   JAWS_Hash_Bucket_Item<EXT_ID, INT_ID> *find_i (const EXT_ID &ext_id) const;
 184   // Returns the item associated with ext_id if found in list.
 185   // Returns NULL if not found.
 186
 187 private:
 188   JAWS_Hash_Bucket_DLCStack<EXT_ID, INT_ID> dlcstack_;
 189 };
 190
 191 #include "JAWS/Hash_Bucket_T.cpp"
 192
 193 #endif /* JAWS_HASH_BUCKET_T_H */