nucleus/library/structures/pointer_hash.h

   1 #ifndef POINTER_HASH_CLASS
   2 #define POINTER_HASH_CLASS
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : pointer_hash                                                      *
   7 *  Author : Chris Koeritz                                                     *
   8 *                                                                             *
   9 *******************************************************************************
  10 * Copyright (c) 2001-$now By Author.  This program is free software; you can  *
  11 * redistribute it and/or modify it under the terms of the GNU General Public  *
  12 * License as published by the Free Software Foundation; either version 2 of   *
  13 * the License or (at your option) any later version.  This is online at:      *
  14 *     http://www.fsf.org/copyleft/gpl.html                                    *
  15 * Please send any updates to: fred@gruntose.com                               *
  16 \*****************************************************************************/
  17
  18 #include "byte_hasher.h"
  19 #include "hash_table.h"
  20 #include "pointer_hash.h"
  21 #include "set.h"
  22
  23 // forward.
  24 class pointer_set;
  25
  26 namespace structures {
  27
  28 //! A hash table for storing pointers.
  29 /*!
  30   Implements a hash table indexed on pointer values that maintains a separate
  31   set to list the items that are presently in the hash table.  This slows down
  32   additions somewhat, but finds are not affected.  The advantage of the
  33   separate index is that the apply() method is much faster.
  34 */
  35
  36 template <class contents>
  37 class pointer_hash : public hash_table<void *, contents>
  38 {
  39 public:
  40   pointer_hash(int estimated_elements);
  41   ~pointer_hash();
  42
  43   const pointer_set &ids() const;
  44   void ids(pointer_set &ids) const;
  45     //!< provides the current list of valid identifiers.
  46
  47   basis::outcome add(void *key, contents *to_store);
  48     //!< overrides base add() and ensures that the id list stays up to date.
  49   contents *acquire(void *key);
  50     //!< overrides base acquire() by ensuring that the ids stay up to date.
  51   bool zap(void *key);
  52     //!< overrides base zap() method plus keeps id list updated.
  53   void reset();
  54     //!< overrides base reset() and ensures that the id list stays up to date.
  55
  56   typedef bool apply_function(const void * &key, contents &current,
  57         void *data_link);
  58
  59   void apply(apply_function *to_apply, void *data_link);
  60     //!< operates on every item in the pointer_hash table.
  61
  62 private:
  63   pointer_set *_ids;
  64     //!< a separate list of the identifiers stored here.
  65     /*! this provides a fairly quick way to iterate rather than having to span
  66     the whole hash table.  it does slow down zap() a bit though. */
  67 };
  68
  69 //////////////
  70
  71 // implementations for larger methods below...
  72
  73 template <class contents>
  74 pointer_hash<contents>::pointer_hash(int estimated_elements)
  75 : hash_table<void *, contents>(rotating_byte_hasher(), estimated_elements),
  76   _ids(new pointer_set)
  77 {}
  78
  79 template <class contents>
  80 pointer_hash<contents>::~pointer_hash()
  81 { WHACK(_ids); }
  82
  83 template <class contents>
  84 const pointer_set &pointer_hash<contents>::ids() const { return *_ids; }
  85
  86 template <class contents>
  87 void pointer_hash<contents>::ids(pointer_set &ids) const { ids = *_ids; }
  88
  89 template <class contents>
  90 basis::outcome pointer_hash<contents>::add(void *key, contents *to_store)
  91 {
  92   _ids->add(key);
  93   return hash_table<void *, contents>::add(key, to_store);
  94 }
  95
  96 template <class contents>
  97 contents *pointer_hash<contents>::acquire(void *key)
  98 {
  99   _ids->remove(key);
 100   return hash_table<void *, contents>::acquire(key);
 101 }
 102
 103 template <class contents>
 104 bool pointer_hash<contents>::zap(void *key)
 105 {
 106   _ids->remove(key);
 107   return hash_table<void *, contents>::zap(key);
 108 }
 109
 110 template <class contents>
 111 void pointer_hash<contents>::reset()
 112 {
 113   _ids->clear();
 114   hash_table<void *, contents>::reset();
 115 }
 116
 117 template <class contents>
 118 void pointer_hash<contents>::apply(apply_function *to_apply, void *data_link)
 119 {
 120   for (int i = 0; i < _ids->elements(); i++) {
 121     void *current = (*_ids)[i];
 122     contents *found = hash_table<void *, contents>::find(current);
 123     if (!found) {
 124       _ids->remove(current);
 125       continue;
 126     }
 127     to_apply(current, *found, data_link);
 128   }
 129 }
 130
 131 } //namespace.
 132
 133 #endif // outer guard.
 134