1 /*
2 * This is copied more or less verbatim from the pointer table implementation in sv.c
3 */
4
5 #include "ppport.h"
6
7 #define PTABLE_HASH(ptr) ((PTR2UV(ptr) >> 3) ^ (PTR2UV(ptr) >> (3 + 7)) ^ (PTR2UV(ptr) >> (3 + 17)))
8
9 struct PTABLE_entry {
10 struct PTABLE_entry *next;
11 void *key;
12 void *value;
13 };
14
15 struct PTABLE {
16 struct PTABLE_entry **tbl_ary;
17 UV tbl_max;
18 UV tbl_items;
19 };
20
21 typedef struct PTABLE_entry PTABLE_ENTRY_t;
22 typedef struct PTABLE PTABLE_t;
23
24 static PTABLE_t * PTABLE_new(void);
25 static PTABLE_ENTRY_t * PTABLE_find(PTABLE_t *tbl, const void *key);
26 static void * PTABLE_fetch(PTABLE_t *tbl, const void *key);
27 static void PTABLE_store(PTABLE_t *tbl, void *key, void *value);
28 static void PTABLE_grow(PTABLE_t *tbl);
29 static void PTABLE_clear(PTABLE_t *tbl);
30 static void PTABLE_free(PTABLE_t *tbl);
31
32 /* create a new pointer => pointer table */
33
34 static PTABLE_t *
PTABLE_new(void)35 PTABLE_new(void)
36 {
37 PTABLE_t *tbl;
38 Newxz(tbl, 1, PTABLE_t);
39 tbl->tbl_max = 511;
40 tbl->tbl_items = 0;
41 Newxz(tbl->tbl_ary, tbl->tbl_max + 1, PTABLE_ENTRY_t*);
42 return tbl;
43 }
44
45 /* map an existing pointer using a table */
46
47 static PTABLE_ENTRY_t *
PTABLE_find(PTABLE_t * tbl,const void * key)48 PTABLE_find(PTABLE_t *tbl, const void *key) {
49 PTABLE_ENTRY_t *tblent;
50 const UV hash = PTABLE_HASH(key);
51 tblent = tbl->tbl_ary[hash & tbl->tbl_max];
52 for (; tblent; tblent = tblent->next) {
53 if (tblent->key == key)
54 return tblent;
55 }
56 return NULL;
57 }
58
59 static void *
PTABLE_fetch(PTABLE_t * tbl,const void * key)60 PTABLE_fetch(PTABLE_t *tbl, const void *key)
61 {
62 PTABLE_ENTRY_t const *const tblent = PTABLE_find(tbl, key);
63 return tblent ? tblent->value : NULL;
64 }
65
66 /* add a new entry to a pointer => pointer table */
67
68 static void
PTABLE_store(PTABLE_t * tbl,void * key,void * value)69 PTABLE_store(PTABLE_t *tbl, void *key, void *value)
70 {
71 PTABLE_ENTRY_t *tblent = PTABLE_find(tbl, key);
72
73 if (tblent) {
74 tblent->value = value;
75 } else {
76 const UV entry = PTABLE_HASH(key) & tbl->tbl_max;
77 Newx(tblent, 1, PTABLE_ENTRY_t);
78
79 tblent->key = key;
80 tblent->value = value;
81 tblent->next = tbl->tbl_ary[entry];
82 tbl->tbl_ary[entry] = tblent;
83 tbl->tbl_items++;
84 if (tblent->next && (tbl->tbl_items > tbl->tbl_max))
85 PTABLE_grow(tbl);
86 }
87 }
88
89 /* double the hash bucket size of an existing ptr table */
90
91 static void
PTABLE_grow(PTABLE_t * tbl)92 PTABLE_grow(PTABLE_t *tbl)
93 {
94 PTABLE_ENTRY_t **ary = tbl->tbl_ary;
95 const UV oldsize = tbl->tbl_max + 1;
96 UV newsize = oldsize * 2;
97 UV i;
98
99 Renew(ary, newsize, PTABLE_ENTRY_t*);
100 Zero(&ary[oldsize], newsize - oldsize, PTABLE_ENTRY_t*);
101 tbl->tbl_max = --newsize;
102 tbl->tbl_ary = ary;
103
104 for (i = 0; i < oldsize; i++, ary++) {
105 PTABLE_ENTRY_t **curentp, **entp, *ent;
106 if (!*ary)
107 continue;
108 curentp = ary + oldsize;
109 for (entp = ary, ent = *ary; ent; ent = *entp) {
110 if ((newsize & PTABLE_HASH(ent->key)) != i) {
111 *entp = ent->next;
112 ent->next = *curentp;
113 *curentp = ent;
114 continue;
115 } else {
116 entp = &ent->next;
117 }
118 }
119 }
120 }
121
122 /* remove all the entries from a ptr table */
123
124 static void
PTABLE_clear(PTABLE_t * tbl)125 PTABLE_clear(PTABLE_t *tbl)
126 {
127 if (tbl && tbl->tbl_items) {
128 register PTABLE_ENTRY_t * * const array = tbl->tbl_ary;
129 UV riter = tbl->tbl_max;
130
131 do {
132 PTABLE_ENTRY_t *entry = array[riter];
133
134 while (entry) {
135 PTABLE_ENTRY_t * const oentry = entry;
136 entry = entry->next;
137 Safefree(oentry);
138 }
139
140 /* chocolateboy 2008-01-08
141 *
142 * make sure we clear the array entry, so that subsequent probes fail
143 */
144
145 array[riter] = NULL;
146 } while (riter--);
147
148 tbl->tbl_items = 0;
149 }
150 }
151
152 /* clear and free a ptr table */
153
154 static void
PTABLE_free(PTABLE_t * tbl)155 PTABLE_free(PTABLE_t *tbl)
156 {
157 if (!tbl) {
158 return;
159 }
160 PTABLE_clear(tbl);
161 Safefree(tbl->tbl_ary);
162 Safefree(tbl);
163 }
164