libStatGen Software 1
BasicHash Class Reference

Public Member Functions

 BasicHash (int startsize=32)
 
void Grow ()
 
void Shrink ()
 
void SetSize (int newsize)
 
void Clear ()
 
int Capacity () const
 
int Entries () const
 
void * Object (int i) const
 
void SetObject (int i, void *object)
 
int Add (int key, void *object=NULL)
 
int Find (int key)
 
int Rehash (int key, int h)
 
BasicHashoperator= (const BasicHash &rhs)
 
void * operator[] (int i) const
 
void Delete (unsigned int index)
 
bool SlotInUse (int index)
 

Protected Attributes

void ** objects
 
unsigned int * keys
 
unsigned int count
 
unsigned int size
 
unsigned int mask
 

Detailed Description

Definition at line 23 of file BasicHash.h.

Constructor & Destructor Documentation

◆ BasicHash()

BasicHash::BasicHash ( int  startsize = 32)

Definition at line 23 of file BasicHash.cpp.

24{
25 count = 0;
26 size = startsize;
27 mask = startsize - 1;
28
29 // In this implementation, the size of hash tables must be a power of two
30 if (startsize & mask)
31 error("BasicHash: Hash table size must be a power of two.\n");
32
33 objects = new void * [size];
34 keys = new unsigned int [size];
35
36 for (unsigned int i = 0; i < size; i++)
37 {
38 objects[i] = NULL;
39 }
40};

◆ ~BasicHash()

BasicHash::~BasicHash ( )
virtual

Definition at line 42 of file BasicHash.cpp.

43{
44 delete [] objects;
45 delete [] keys;
46}

Member Function Documentation

◆ Add()

int BasicHash::Add ( int  key,
void *  object = NULL 
)

Definition at line 96 of file BasicHash.cpp.

97{
98 if (count * 2 > size)
99 Grow();
100
101 unsigned int h = Iterate(key);
102
103 while ((objects[h] != NULL) && (objects[h] != object))
104 h = ReIterate(key, h);
105
106 if (objects[h] == NULL)
107 {
108// printf("At position %d, inserted %x\n", h, key);
109 keys[h] = key;
110 count++;
111 }
112
113 objects[h] = object;
114
115 return h;
116}

◆ Capacity()

int BasicHash::Capacity ( ) const
inline

Definition at line 48 of file BasicHash.h.

49 {
50 return size;
51 }

◆ Clear()

void BasicHash::Clear ( )

Definition at line 48 of file BasicHash.cpp.

49{
50// printf("Clearing...\n");
51
52 count = 0;
53
54 if (size > 16)
55 SetSize(16);
56
57 for (unsigned int i = 0; i < size; i++)
58 objects[i] = NULL;
59}

◆ Delete()

void BasicHash::Delete ( unsigned int  index)

Definition at line 132 of file BasicHash.cpp.

133{
134 if (index >= size || objects[index] == NULL)
135 return;
136
137 objects[index] = NULL;
138 count--;
139
140 if (count * 8 < size && size > 32)
141 Shrink();
142 else
143 {
144 // rehash the next entries until we find empty slot
145 index = (index + 1) & mask;
146
147 while (objects[index] != NULL)
148 {
149 if ((keys[index] & mask) != index)
150 {
151 unsigned int h = Iterate(keys[index]);
152
153 while ((objects[h] != NULL) && (objects[h] != objects[index]))
154 h = ReIterate(keys[index], h);
155
156 if (h != (unsigned int) index)
157 {
158 keys[h] = keys[index];
159 objects[h] = objects[index];
160 objects[index] = NULL;
161 }
162 }
163
164 index = (index + 1) & mask;
165 }
166 }
167}

◆ Entries()

int BasicHash::Entries ( ) const
inline

Definition at line 52 of file BasicHash.h.

53 {
54 return count;
55 }

◆ Find()

int BasicHash::Find ( int  key)

Definition at line 118 of file BasicHash.cpp.

119{
120 int h = Iterate(key);
121
122 return objects[h] == NULL ? -1 : h;
123}

◆ Grow()

void BasicHash::Grow ( )
inline

Definition at line 35 of file BasicHash.h.

36 {
37 SetSize(size * 2);
38 }

◆ Object()

void * BasicHash::Object ( int  i) const
inline

Definition at line 57 of file BasicHash.h.

58 {
59 return objects[i];
60 }

◆ operator[]()

void * BasicHash::operator[] ( int  i) const
inline

Definition at line 73 of file BasicHash.h.

74 {
75 return objects[i];
76 }

◆ Rehash()

int BasicHash::Rehash ( int  key,
int  h 
)

Definition at line 125 of file BasicHash.cpp.

126{
127 h = ReIterate(key, h);
128
129 return objects[h] == NULL ? -1 : h;
130}

◆ SetObject()

void BasicHash::SetObject ( int  i,
void *  object 
)
inline

Definition at line 62 of file BasicHash.h.

63 {
64 objects[i] = object;
65 }

◆ SetSize()

void BasicHash::SetSize ( int  newsize)

Definition at line 61 of file BasicHash.cpp.

62{
63 int newmask = newsize - 1;
64
65 void ** newobjects = new void * [newsize];
66 unsigned int * newkeys = new unsigned int [newsize];
67
68 for (int i = 0; i < newsize; i++)
69 {
70 newobjects[i] = NULL;
71 }
72
73 if (count)
74 for (unsigned int i = 0; i < size; i++)
75 if (objects[i] != NULL)
76 {
77 unsigned int key = keys[i];
78 unsigned int h = key & newmask;
79
80 while (newobjects[h] != NULL && newkeys[h] != h)
81 h = (h + 1) & newmask;
82
83 newkeys[h] = key;
84 newobjects[h] = objects[i];
85 }
86
87 delete [] objects;
88 delete [] keys;
89
90 objects = newobjects;
91 keys = newkeys;
92 size = newsize;
93 mask = newmask;
94}

◆ Shrink()

void BasicHash::Shrink ( )
inline

Definition at line 39 of file BasicHash.h.

40 {
41 SetSize(size / 2);
42 }

◆ SlotInUse()

bool BasicHash::SlotInUse ( int  index)
inline

Definition at line 80 of file BasicHash.h.

81 {
82 return objects[index] != NULL;
83 }

Member Data Documentation

◆ count

unsigned int BasicHash::count
protected

Definition at line 28 of file BasicHash.h.

◆ keys

unsigned int* BasicHash::keys
protected

Definition at line 27 of file BasicHash.h.

◆ mask

unsigned int BasicHash::mask
protected

Definition at line 29 of file BasicHash.h.

◆ objects

void** BasicHash::objects
protected

Definition at line 26 of file BasicHash.h.

◆ size

unsigned int BasicHash::size
protected

Definition at line 28 of file BasicHash.h.


The documentation for this class was generated from the following files: