nucleus/library/structures/int_hash.h

   1 #ifndef INT_HASH_CLASS
   2 #define INT_HASH_CLASS
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : int_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
  21 #include <basis/outcome.h>
  22 #include <structures/set.h>
  23
  24 namespace structures {
  25
  26 //! A hash table for storing integers.
  27 /*!
  28   Implements a hash table indexed on integers that maintains a separate set of
  29   identifiers for listing the items that are presently in the hash table.  This
  30   slows down additions somewhat, but finds are not affected.  The advantage of
  31   the separate index is that the apply() method is much faster.
  32 */
  33
  34 template <class contents>
  35 class int_hash : public hash_table<int, contents>
  36 {
  37 public:
  38   int_hash(int max_bits);
  39   ~int_hash();
  40
  41   const int_set &ids() const;
  42   void ids(int_set &ids) const;
  43     //!< provides the current list of valid identifiers.
  44
  45   basis::outcome add(int key, contents *to_store);
  46     //!< overrides base add() and ensures that the id list stays up to date.
  47   contents *acquire(int key);
  48     //!< overrides base acquire() by ensuring that the ids stay up to date.
  49   bool zap(int key);
  50     //!< overrides base zap() method plus keeps id list updated.
  51   void reset();
  52     //!< overrides base reset() and ensures that the id list stays up to date.
  53
  54   typedef bool apply_function(const int &key, contents &current,
  55         void *data_link);
  56
  57   void apply(apply_function *to_apply, void *data_link);
  58     //!< operates on every item in the int_hash table.
  59
  60 private:
  61   int_set *_ids;
  62     //!< a separate list of the identifiers stored here.
  63     /*! this provides a fairly quick way to iterate rather than having to span
  64     the whole hash table.  it does slow down zap() a bit though. */
  65 };
  66
  67 //////////////
  68
  69 // implementations below...
  70
  71 template <class contents>
  72 int_hash<contents>::int_hash(int max_bits)
  73 : hash_table<int, contents>(rotating_byte_hasher(), max_bits),
  74   _ids(new int_set)
  75 {}
  76
  77 template <class contents>
  78 int_hash<contents>::~int_hash()
  79 { WHACK(_ids); }
  80
  81 template <class contents>
  82 const int_set &int_hash<contents>::ids() const { return *_ids; }
  83
  84 template <class contents>
  85 void int_hash<contents>::ids(int_set &ids) const { ids = *_ids; }
  86
  87 template <class contents>
  88 basis::outcome int_hash<contents>::add(int key, contents *to_store)
  89 {
  90   _ids->add(key);
  91   return hash_table<int, contents>::add(key, to_store);
  92 }
  93
  94 template <class contents>
  95 contents *int_hash<contents>::acquire(int key)
  96 {
  97   _ids->remove(key);
  98   return hash_table<int, contents>::acquire(key);
  99 }
 100
 101 template <class contents>
 102 bool int_hash<contents>::zap(int key)
 103 {
 104   _ids->remove(key);
 105   return hash_table<int, contents>::zap(key);
 106 }
 107
 108 template <class contents>
 109 void int_hash<contents>::reset()
 110 {
 111   _ids->clear();
 112   hash_table<int, contents>::reset();
 113 }
 114
 115 template <class contents>
 116 void int_hash<contents>::apply(apply_function *to_apply, void *data_link)
 117 {
 118   for (int i = 0; i < _ids->elements(); i++) {
 119     int current = (*_ids)[i];
 120     contents *found = hash_table<int, contents>::find(current);
 121     if (!found) {
 122       _ids->remove(current);
 123       continue;
 124     }
 125     to_apply(current, *found, data_link);
 126   }
 127 }
 128
 129 } //namespace.
 130
 131 #endif // outer guard.
 132