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
24{
25protected:
26 void ** objects;
27 unsigned int * keys;
28 unsigned int count, size;
29 unsigned int mask;
30
31public:
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
85private:
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