added kdenlive
[feisty_meow.git] / 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