libStatGen Software  1
IntHash.h
1 /*
2  * Copyright (C) 2000-2007 Goncalo Abecasis
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 //////////////////////////////////////////////////////////////////////
19 // libsrc/IntHash.h
20 // (c) 2000-2007 Goncalo Abecasis
21 //
22 // This file is distributed as part of the MaCH source code package
23 // and may not be redistributed in any form, without prior written
24 // permission from the author. Permission is granted for you to
25 // modify this file for your own personal use, but modified versions
26 // must retain this copyright notice and must not be distributed.
27 //
28 // Permission is granted for you to use this file to compile MaCH.
29 //
30 // All computer programs have bugs. Use this file at your own risk.
31 //
32 // Monday October 29, 2007
33 //
34 
35 #ifndef __INTHASH_H__
36 #define __INTHASH_H__
37 
38 #include <stdlib.h>
39 
40 class IntHash
41 {
42 protected:
43  bool * objects;
44  unsigned int * keys;
45  unsigned int count, size;
46  unsigned int mask;
47 
48 public:
49  IntHash(int startsize = 32);
50  virtual ~IntHash();
51 
52  void Grow()
53  {
54  SetSize(size * 2);
55  }
56  void Shrink()
57  {
58  SetSize(size / 2);
59  }
60 
61  void SetSize(int newsize);
62 
63  void Clear();
64 
65  int Capacity() const
66  {
67  return size;
68  }
69  int Entries() const
70  {
71  return count;
72  }
73 
74  bool Object(int i) const
75  {
76  return objects[i];
77  }
78 
79  void SetObject(int i, bool object)
80  {
81  objects[i] = object;
82  }
83 
84  int Add(int key, bool object = true);
85  int Find(int key);
86  int Rehash(int key, int h);
87 
88  IntHash & operator = (const IntHash & rhs);
89 
90  bool operator [](int i) const
91  {
92  return objects[i];
93  }
94 
95  void Delete(unsigned int index);
96 
97  bool SlotInUse(int index)
98  {
99  return objects[index] != false;
100  }
101 
102 private:
103  unsigned int Iterate(unsigned int key) const
104  {
105  unsigned int h = key & mask;
106 
107  while (objects[h] != false && keys[h] != key)
108  h = (h + 1) & mask;
109 
110  return h;
111  }
112 
113  unsigned int ReIterate(unsigned int key, unsigned int h) const
114  {
115  h = (h + 1) & mask;
116 
117  while (objects[h] != false && keys[h] != key)
118  h = (h + 1) & mask;
119 
120  return h;
121  }
122 };
123 
124 #endif
125 
IntHash
Definition: IntHash.h:40