refactored plugin api; refactored callback library; added signals library
[xonotic/netradiant.git] / libs / container / hashtable.h
1 /*
2 Copyright (C) 2001-2006, William Joseph.
3 All Rights Reserved.
4
5 This file is part of GtkRadiant.
6
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
20 */
21
22 #if !defined(INCLUDED_CONTAINER_HASHTABLE_H)
23 #define INCLUDED_CONTAINER_HASHTABLE_H
24
25 #include <cstddef>
26 #include <algorithm>
27 #include <functional>
28 #include "debugging/debugging.h"
29
30
31 namespace HashTableDetail
32 {
33   inline std::size_t next_power_of_two(std::size_t size)
34   {
35     std::size_t result = 1;
36     while(result < size)
37     {
38       result <<= 1;
39     }
40     return result;
41   }
42
43   struct BucketNodeBase
44   {
45     BucketNodeBase* next;
46     BucketNodeBase* prev;
47   };
48
49   inline void list_initialise(BucketNodeBase& self)
50   {
51     self.next = self.prev = &self;
52   }
53
54   inline void list_swap(BucketNodeBase& self, BucketNodeBase& other)
55   {
56     BucketNodeBase tmp(self);
57     if(other.next == &other)
58     {
59       list_initialise(self);
60     }
61     else
62     {
63       self = other;
64       self.next->prev = self.prev->next = &self;
65     }
66     if(tmp.next == &self)
67     {
68       list_initialise(other);
69     }
70     else
71     {
72       other = tmp;
73       other.next->prev = other.prev->next = &other;
74     }
75   }
76
77   inline void node_link(BucketNodeBase* node, BucketNodeBase* next)
78   {
79     node->next = next;
80     node->prev = next->prev;
81     next->prev = node;
82     node->prev->next = node;
83   }
84   inline void node_unlink(BucketNodeBase* node)
85   {
86     node->prev->next = node->next;
87     node->next->prev = node->prev;
88   }
89
90   template<typename Key, typename Value>
91   struct KeyValue
92   {
93     const Key key;
94     Value value;
95
96     KeyValue(const Key& key_, const Value& value_)
97       : key(key_), value(value_)
98     {
99     }
100   };
101
102   template<typename Key, typename Value, typename Hash>
103   struct BucketNode : public BucketNodeBase
104   {
105     Hash m_hash;
106     KeyValue<Key, Value> m_value;
107
108     BucketNode(Hash hash, const Key& key, const Value& value) 
109      : m_hash(hash), m_value(key, value)
110     {
111     }
112     BucketNode* getNext() const
113     {
114       return static_cast<BucketNode*>(next);
115     }
116     BucketNode* getPrev() const
117     {
118       return static_cast<BucketNode*>(prev);
119     }
120   };
121
122   template<typename Key, typename Value, typename Hash>
123   class BucketIterator
124   {
125     typedef BucketNode<Key, Value, Hash> Node;
126     Node* m_node;
127
128     void increment()
129     {
130       m_node = m_node->getNext();
131     }
132
133   public:
134     typedef std::forward_iterator_tag iterator_category;
135     typedef std::ptrdiff_t difference_type;
136     typedef difference_type distance_type;
137     typedef KeyValue<Key, Value> value_type;
138     typedef value_type* pointer;
139     typedef value_type& reference;
140
141     BucketIterator(Node* node) : m_node(node)
142     {
143     }
144
145     Node* node()
146     {
147       return m_node;
148     }
149
150     bool operator==(const BucketIterator& other) const
151     {
152       return m_node == other.m_node;
153     }
154     bool operator!=(const BucketIterator& other) const
155     {
156       return !operator==(other);
157     }
158     BucketIterator& operator++()
159     {
160       increment();
161       return *this;
162     }
163     BucketIterator operator++(int)
164     {
165       BucketIterator tmp = *this;
166       increment();
167       return tmp;
168     }
169     value_type& operator*() const
170     {
171       return m_node->m_value;
172     }
173     value_type* operator->() const
174     {
175       return &(operator*());
176     }
177   };
178 }
179
180
181 /// A hash-table container which maps keys to values.
182 ///
183 /// - Inserting or removing elements does not invalidate iterators.
184 /// - Inserting or retrieving an element for a given key takes O(1) time on average.
185 /// - Elements are stored in no particular order.
186 ///
187 /// \param Key Uniquely identifies a value. Must provide a copy-constructor.
188 /// \param Value The value to be stored . Must provide a default-constructor and a copy-constructor.
189 /// \param Hasher Must provide 'std::size_t operator()(const Key&) const' which always returns the same result if the same argument is given.
190 /// \param KeyEqual Must provide 'bool operator==(const Key&, const Key&) const' which returns true only if both arguments are equal.
191 ///
192 /// \dontinclude container/hashtable.cpp
193 /// \skipline HashTable example
194 /// \until end example
195 template<typename Key, typename Value, typename Hasher, typename KeyEqual = std::equal_to<Key> >
196 class HashTable : private KeyEqual, private Hasher
197 {
198   typedef typename Hasher::hash_type hash_type;
199   typedef HashTableDetail::KeyValue<Key, Value> KeyValue;
200   typedef HashTableDetail::BucketNode<Key, Value, hash_type> BucketNode;
201
202   inline BucketNode* node_create(hash_type hash, const Key& key, const Value& value)
203   {
204     return new BucketNode(hash, key, value);
205   }
206   inline void node_destroy(BucketNode* node)
207   {
208     delete node;
209   }
210
211   typedef BucketNode* Bucket;
212
213   static Bucket* buckets_new(std::size_t count)
214   {
215     Bucket* buckets = new Bucket[count];
216     std::uninitialized_fill(buckets, buckets + count, Bucket(0));
217     return buckets;
218   }
219   static void buckets_delete(Bucket* buckets)
220   {
221     delete[] buckets;
222   }
223
224   std::size_t m_bucketCount;
225   Bucket* m_buckets;
226   std::size_t m_size;
227   HashTableDetail::BucketNodeBase m_list;
228
229   BucketNode* getFirst()
230   {
231     return static_cast<BucketNode*>(m_list.next);
232   }
233   BucketNode* getLast()
234   {
235     return static_cast<BucketNode*>(&m_list);
236   }
237
238 public:
239
240   typedef KeyValue value_type;
241   typedef HashTableDetail::BucketIterator<Key, Value, hash_type> iterator;
242
243 private:
244
245   void initialise()
246   {
247     list_initialise(m_list);
248   }
249   hash_type hashKey(const Key& key)
250   {
251     return Hasher::operator()(key);
252   }
253
254   std::size_t getBucketId(hash_type hash) const
255   {
256     return hash & (m_bucketCount - 1);
257   }
258   Bucket& getBucket(hash_type hash)
259   {
260     return m_buckets[getBucketId(hash)];
261   }
262   BucketNode* bucket_find(Bucket bucket, hash_type hash, const Key& key)
263   {
264     std::size_t bucketId = getBucketId(hash);
265     for(iterator i(bucket); i != end(); ++i)
266     {
267       hash_type nodeHash = i.node()->m_hash;
268
269       if(getBucketId(nodeHash) != bucketId)
270       {
271         return 0;
272       }
273
274       if(nodeHash == hash && KeyEqual::operator()((*i).key, key))
275       {
276         return i.node();
277       }
278     }
279     return 0;
280   }
281   BucketNode* bucket_insert(Bucket& bucket, BucketNode* node)
282   {
283     // link node into list
284     node_link(node, bucket_next(bucket));
285     bucket = node;
286     return node;
287   }
288   BucketNode* bucket_next(Bucket& bucket)
289   {
290     Bucket* end = m_buckets + m_bucketCount;
291     for(Bucket* i = &bucket; i != end; ++i)
292     {
293       if(*i != 0)
294       {
295         return *i;
296       }
297     }
298     return getLast();
299   }
300
301   void buckets_resize(std::size_t count)
302   {
303     BucketNode* first = getFirst();
304     BucketNode* last = getLast();
305
306     buckets_delete(m_buckets);
307
308     m_bucketCount = count;
309
310     m_buckets = buckets_new(m_bucketCount);
311     initialise();
312
313     for(BucketNode* i = first; i != last;)
314     {
315       BucketNode* node = i;
316       i = i->getNext();
317       bucket_insert(getBucket((*node).m_hash), node);
318     }
319   }
320   void size_increment()
321   {
322     if(m_size == m_bucketCount)
323     {
324       buckets_resize(m_bucketCount == 0 ? 8 : m_bucketCount << 1);
325     }
326     ++m_size;
327   }
328   void size_decrement()
329   {
330     --m_size;
331   }
332
333   HashTable(const HashTable& other);
334   HashTable& operator=(const HashTable& other);
335 public:
336   HashTable() : m_bucketCount(0), m_buckets(0), m_size(0)
337   {
338     initialise();
339   }
340   HashTable(std::size_t bucketCount) : m_bucketCount(HashTableDetail::next_power_of_two(bucketCount)), m_buckets(buckets_new(m_bucketCount)), m_size(0)
341   {
342     initialise();
343   }
344   ~HashTable()
345   {
346     for(BucketNode* i = getFirst(); i != getLast();)
347     {
348       BucketNode* node = i;
349       i = i->getNext();
350       node_destroy(node);
351     }
352     buckets_delete(m_buckets);
353   }
354
355   iterator begin()
356   {
357     return iterator(getFirst());
358   }
359   iterator end()
360   {
361     return iterator(getLast());
362   }
363
364   bool empty() const
365   {
366     return m_size == 0;
367   }
368   std::size_t size() const
369   {
370     return m_size;
371   }
372
373   /// \brief Returns an iterator pointing to the value associated with \p key if it is contained by the hash-table, else \c end().
374   iterator find(const Key& key)
375   {
376     hash_type hash = hashKey(key);
377     if(m_bucketCount != 0)
378     {
379       Bucket bucket = getBucket(hash);
380       if(bucket != 0)
381       {
382         BucketNode* node = bucket_find(bucket, hash, key);
383         if(node != 0)
384         {
385           return iterator(node);
386         }
387       }
388     }
389     
390     return end();
391   }
392   /// \brief Adds \p value to the hash-table associated with \p key if it does not exist.
393   iterator insert(const Key& key, const Value& value)
394   {
395     hash_type hash = hashKey(key);
396     if(m_bucketCount != 0)
397     {
398       Bucket& bucket = getBucket(hash);
399       if(bucket != 0)
400       {
401         BucketNode* node = bucket_find(bucket, hash, key);
402         if(node != 0)
403         {
404           return iterator(node);
405         }
406       }
407     }
408
409     size_increment();
410     return iterator(bucket_insert(getBucket(hash), node_create(hash, key, value)));
411   }
412
413   /// \brief Removes the value pointed to by \p i from the hash-table.
414   ///
415   /// \p i must be a deferenceable iterator into the hash-table.
416   void erase(iterator i)
417   {
418     Bucket& bucket = getBucket(i.node()->m_hash);
419     BucketNode* node = i.node();
420
421     // if this was the last node in the bucket
422     if(bucket == node)
423     {
424       bucket = (node->getNext() == getLast() || &getBucket(node->getNext()->m_hash) != &bucket) ? 0 : node->getNext();
425     }
426
427     node_unlink(node);
428     ASSERT_MESSAGE(node != 0, "tried to erase a non-existent key/value");
429     node_destroy(node);
430
431     size_decrement();
432   }
433
434   /// \brief Returns the value identified by \p key if it is contained by the hash-table, else inserts and returns a new default-constructed value associated with \p key.
435   Value& operator[](const Key& key)
436   {
437     hash_type hash = hashKey(key);
438     if(m_bucketCount != 0)
439     {
440       Bucket& bucket = getBucket(hash);
441       if(bucket != 0)
442       {
443         BucketNode* node = bucket_find(bucket, hash, key);
444         if(node != 0)
445         {
446           return node->m_value.value;
447         }
448       }
449     }
450     size_increment();
451     return bucket_insert(getBucket(hash), node_create(hash, key, Value()))->m_value.value;
452   }
453   /// \brief Removes the value associated with \p key from the hash-table.
454   void erase(const Key& key)
455   {
456     erase(find(key));
457   }
458   /// \brief Swaps the contents of the hash-table with \p other.
459   void swap(HashTable& other)
460   {
461     std::swap(m_buckets, other.m_buckets);
462     std::swap(m_bucketCount, other.m_bucketCount);
463     std::swap(m_size, other.m_size);
464     HashTableDetail::list_swap(m_list, other.m_list);
465   }
466   /// \brief Removes all values from the hash-table.
467   void clear()
468   {
469     HashTable tmp;
470     tmp.swap(*this);
471   }
472 };
473
474 #endif