libStatGen Software  1
BasicHash.h
1 /*
2  * Copyright (C) 2010 Regents of the University of Michigan
3  *
4  * This program is free software: you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation, either version 3 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program. If not, see <http://www.gnu.org/licenses/>.
16  */
17 
18 #ifndef __BASICHASH_H__
19 #define __BASICHASH_H__
20 
21 #include <stdlib.h>
22 
23 class BasicHash
24 {
25 protected:
26  void ** objects;
27  unsigned int * keys;
28  unsigned int count, size;
29  unsigned int mask;
30 
31 public:
32  BasicHash(int startsize = 32);
33  virtual ~BasicHash();
34 
35  void Grow()
36  {
37  SetSize(size * 2);
38  }
39  void Shrink()
40  {
41  SetSize(size / 2);
42  }
43 
44  void SetSize(int newsize);
45 
46  void Clear();
47 
48  int Capacity() const
49  {
50  return size;
51  }
52  int Entries() const
53  {
54  return count;
55  }
56 
57  void * Object(int i) const
58  {
59  return objects[i];
60  }
61 
62  void SetObject(int i, void * object)
63  {
64  objects[i] = object;
65  }
66 
67  int Add(int key, void * object = NULL);
68  int Find(int key);
69  int Rehash(int key, int h);
70 
71  BasicHash & operator = (const BasicHash & rhs);
72 
73  void * operator [](int i) const
74  {
75  return objects[i];
76  }
77 
78  void Delete(unsigned int index);
79 
80  bool SlotInUse(int index)
81  {
82  return objects[index] != NULL;
83  }
84 
85 private:
86  unsigned int Iterate(unsigned int key) const
87  {
88  unsigned int h = key & mask;
89 
90  while (objects[h] != NULL && keys[h] != key)
91  h = (h + 1) & mask;
92 
93  return h;
94  }
95 
96  unsigned int ReIterate(unsigned int key, unsigned int h) const
97  {
98  h = (h + 1) & mask;
99 
100  while (objects[h] != NULL && keys[h] != key)
101  h = (h + 1) & mask;
102 
103  return h;
104  }
105 };
106 
107 #endif