libStatGen Software 1
IntHash Class Reference

Public Member Functions

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

Protected Attributes

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

Detailed Description

Definition at line 40 of file IntHash.h.

Constructor & Destructor Documentation

◆ IntHash()

IntHash::IntHash ( int  startsize = 32)

Definition at line 23 of file IntHash.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("IntHash: Hash table size must be a power of two.\n");
32
33 objects = new bool [size];
34 keys = new unsigned int [size];
35
36 for (unsigned int i = 0; i < size; i++)
37 {
38 objects[i] = false;
39 }
40};

◆ ~IntHash()

IntHash::~IntHash ( )
virtual

Definition at line 42 of file IntHash.cpp.

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

Member Function Documentation

◆ Add()

int IntHash::Add ( int  key,
bool  object = true 
)

Definition at line 96 of file IntHash.cpp.

97{
98 if (count * 2 > size)
99 Grow();
100
101 unsigned int h = Iterate(key);
102
103 while ((objects[h] != false) && (objects[h] != object))
104 h = ReIterate(key, h);
105
106 if (objects[h] == false)
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 IntHash::Capacity ( ) const
inline

Definition at line 65 of file IntHash.h.

66 {
67 return size;
68 }

◆ Clear()

void IntHash::Clear ( )

Definition at line 48 of file IntHash.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] = false;
59}

◆ Delete()

void IntHash::Delete ( unsigned int  index)

Definition at line 132 of file IntHash.cpp.

133{
134 if (index >= size || objects[index] == false)
135 return;
136
137 objects[index] = false;
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] != false)
148 {
149 if ((keys[index] & mask) != index)
150 {
151 unsigned int h = Iterate(keys[index]);
152
153 while ((objects[h] != false) && (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] = false;
161 }
162 }
163
164 index = (index + 1) & mask;
165 }
166 }
167}

◆ Entries()

int IntHash::Entries ( ) const
inline

Definition at line 69 of file IntHash.h.

70 {
71 return count;
72 }

◆ Find()

int IntHash::Find ( int  key)

Definition at line 118 of file IntHash.cpp.

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

◆ Grow()

void IntHash::Grow ( )
inline

Definition at line 52 of file IntHash.h.

53 {
54 SetSize(size * 2);
55 }

◆ Object()

bool IntHash::Object ( int  i) const
inline

Definition at line 74 of file IntHash.h.

75 {
76 return objects[i];
77 }

◆ operator[]()

bool IntHash::operator[] ( int  i) const
inline

Definition at line 90 of file IntHash.h.

91 {
92 return objects[i];
93 }

◆ Rehash()

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

Definition at line 125 of file IntHash.cpp.

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

◆ SetObject()

void IntHash::SetObject ( int  i,
bool  object 
)
inline

Definition at line 79 of file IntHash.h.

80 {
81 objects[i] = object;
82 }

◆ SetSize()

void IntHash::SetSize ( int  newsize)

Definition at line 61 of file IntHash.cpp.

62{
63 int newmask = newsize - 1;
64
65 bool * newobjects = new bool [newsize];
66 unsigned int * newkeys = new unsigned int [newsize];
67
68 for (int i = 0; i < newsize; i++)
69 {
70 newobjects[i] = false;
71 }
72
73 if (count)
74 for (unsigned int i = 0; i < size; i++)
75 if (objects[i] != false)
76 {
77 unsigned int key = keys[i];
78 unsigned int h = key & newmask;
79
80 while (newobjects[h] != false && 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 IntHash::Shrink ( )
inline

Definition at line 56 of file IntHash.h.

57 {
58 SetSize(size / 2);
59 }

◆ SlotInUse()

bool IntHash::SlotInUse ( int  index)
inline

Definition at line 97 of file IntHash.h.

98 {
99 return objects[index] != false;
100 }

Member Data Documentation

◆ count

unsigned int IntHash::count
protected

Definition at line 45 of file IntHash.h.

◆ keys

unsigned int* IntHash::keys
protected

Definition at line 44 of file IntHash.h.

◆ mask

unsigned int IntHash::mask
protected

Definition at line 46 of file IntHash.h.

◆ objects

bool* IntHash::objects
protected

Definition at line 43 of file IntHash.h.

◆ size

unsigned int IntHash::size
protected

Definition at line 45 of file IntHash.h.


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