1 //metadoc PHash copyright Steve Dekorte 2002
2 //metadoc PHash license BSD revised
3 //metadoc PHash notes Suggestion to use cuckoo hash and original implementation by Marc Fauconneau
4
5 #define PHASH_C
6 #include "PHash.h"
7 #undef PHASH_C
8 #include "IoObject.h"
9 #include <stdlib.h>
10 #include <stdio.h>
11 #include <string.h>
12 #include <assert.h>
13
PHash_new(void)14 PHash *PHash_new(void)
15 {
16 PHash *self = (PHash *)io_calloc(1, sizeof(PHash));
17 PHash_setSize_(self, 8);
18 return self;
19 }
20
PHash_copy_(PHash * self,const PHash * other)21 void PHash_copy_(PHash *self, const PHash *other)
22 {
23 io_free(self->records);
24 memcpy(self, other, sizeof(PHash));
25 self->records = malloc(self->size * sizeof(PHashRecord));
26 memcpy(self->records, other->records, self->size * sizeof(PHashRecord));
27 }
28
PHash_clone(PHash * self)29 PHash *PHash_clone(PHash *self)
30 {
31 PHash *other = PHash_new();
32 PHash_copy_(other, self);
33 return other;
34 }
35
PHash_setSize_(PHash * self,size_t size)36 void PHash_setSize_(PHash *self, size_t size)
37 {
38 self->records = realloc(self->records, size * sizeof(PHashRecord));
39
40 if(size > self->size)
41 {
42 memset(self->records + self->size * sizeof(PHashRecord),
43 0x0, (size - self->size) * sizeof(PHashRecord));
44 }
45
46 self->size = size;
47
48 PHash_updateMask(self);
49 }
50
PHash_updateMask(PHash * self)51 void PHash_updateMask(PHash *self)
52 {
53 self->mask = (intptr_t)(self->size - 1);
54 }
55
PHash_show(PHash * self)56 void PHash_show(PHash *self)
57 {
58 int i;
59
60 printf("PHash records:\n");
61 for(i = 0; i < self->size; i++)
62 {
63 PHashRecord *r = Records_recordAt_(self->records, i);
64 printf(" %i: %p %p\n", (int)i, r->k, r->v);
65 }
66 }
67
PHash_free(PHash * self)68 void PHash_free(PHash *self)
69 {
70 io_free(self->records);
71 io_free(self);
72 }
73
PHash_insert_(PHash * self,PHashRecord * x)74 void PHash_insert_(PHash *self, PHashRecord *x)
75 {
76 int n;
77
78 for (n = 0; n < PHASH_MAXLOOP; n ++)
79 {
80 PHashRecord *r;
81
82 r = PHash_record1_(self, x->k);
83 PHashRecord_swapWith_(x, r);
84 if(x->k == 0x0) { self->keyCount ++; return; }
85
86 r = PHash_record2_(self, x->k);
87 PHashRecord_swapWith_(x, r);
88 if(x->k == 0x0) { self->keyCount ++; return; }
89 }
90
91 PHash_grow(self);
92 PHash_at_put_(self, x->k, x->v);
93 }
94
PHash_insertRecords(PHash * self,unsigned char * oldRecords,size_t oldSize)95 void PHash_insertRecords(PHash *self, unsigned char *oldRecords, size_t oldSize)
96 {
97 int i;
98
99 for (i = 0; i < oldSize; i ++)
100 {
101 PHashRecord *r = Records_recordAt_(oldRecords, i);
102
103 if (r->k)
104 {
105 PHash_at_put_(self, r->k, r->v);
106 }
107 }
108 }
109
PHash_resizeTo_(PHash * self,size_t newSize)110 void PHash_resizeTo_(PHash *self, size_t newSize)
111 {
112 unsigned char *oldRecords = self->records;
113 size_t oldSize = self->size;
114 self->size = newSize;
115 self->records = io_calloc(1, sizeof(PHashRecord) * self->size);
116 self->keyCount = 0;
117 PHash_updateMask(self);
118 PHash_insertRecords(self, oldRecords, oldSize);
119 io_free(oldRecords);
120 }
121
PHash_grow(PHash * self)122 void PHash_grow(PHash *self)
123 {
124 PHash_resizeTo_(self, self->size * 2);
125 }
126
PHash_shrink(PHash * self)127 void PHash_shrink(PHash *self)
128 {
129 PHash_resizeTo_(self, self->size / 2);
130 }
131
PHash_removeKey_(PHash * self,void * k)132 void PHash_removeKey_(PHash *self, void *k)
133 {
134 PHashRecord *r;
135
136 r = PHash_record1_(self, k);
137 if(r->k == k)
138 {
139 r->k = 0x0;
140 r->v = 0x0;
141 self->keyCount --;
142 PHash_shrinkIfNeeded(self);
143 return;
144 }
145
146 r = PHash_record2_(self, k);
147 if(r->k == k)
148 {
149 r->k = 0x0;
150 r->v = 0x0;
151 self->keyCount --;
152 PHash_shrinkIfNeeded(self);
153 return;
154 }
155 }
156
PHash_size(PHash * self)157 size_t PHash_size(PHash *self) // actually the keyCount
158 {
159 return self->keyCount;
160 }
161
162 // ----------------------------
163
PHash_memorySize(PHash * self)164 size_t PHash_memorySize(PHash *self)
165 {
166 return sizeof(PHash) + self->size * sizeof(PHashRecord);
167 }
168
PHash_compact(PHash * self)169 void PHash_compact(PHash *self)
170 {
171 }
172