Commit | Line | Data |
---|---|---|
b82b06b8 FC |
1 | /* This is a pointer table implementation essentially copied from the ptr_table |
2 | * implementation in perl's sv.c, except that it has been modified to use memory | |
3 | * shared across threads. */ | |
4 | ||
5 | /* This header is designed to be included several times with different | |
6 | * definitions for PTABLE_NAME and PTABLE_VAL_FREE(). */ | |
7 | ||
8 | #undef pPTBLMS | |
9 | #undef pPTBLMS_ | |
10 | #undef aPTBLMS | |
11 | #undef aPTBLMS_ | |
12 | ||
13 | /* Context for PerlMemShared_* functions */ | |
14 | ||
15 | #ifdef PERL_IMPLICIT_SYS | |
16 | # define pPTBLMS pTHX | |
17 | # define pPTBLMS_ pTHX_ | |
18 | # define aPTBLMS aTHX | |
19 | # define aPTBLMS_ aTHX_ | |
20 | #else | |
21 | # define pPTBLMS | |
22 | # define pPTBLMS_ | |
23 | # define aPTBLMS | |
24 | # define aPTBLMS_ | |
25 | #endif | |
26 | ||
27 | #ifndef pPTBL | |
28 | # define pPTBL pPTBLMS | |
29 | #endif | |
30 | #ifndef pPTBL_ | |
31 | # define pPTBL_ pPTBLMS_ | |
32 | #endif | |
33 | #ifndef aPTBL | |
34 | # define aPTBL aPTBLMS | |
35 | #endif | |
36 | #ifndef aPTBL_ | |
37 | # define aPTBL_ aPTBLMS_ | |
38 | #endif | |
39 | ||
40 | #ifndef PTABLE_NAME | |
41 | # define PTABLE_NAME ptable | |
42 | #endif | |
43 | ||
44 | #ifndef PTABLE_VAL_FREE | |
45 | # define PTABLE_VAL_FREE(V) | |
46 | #endif | |
47 | ||
48 | #ifndef PTABLE_JOIN | |
49 | # define PTABLE_PASTE(A, B) A ## B | |
50 | # define PTABLE_JOIN(A, B) PTABLE_PASTE(A, B) | |
51 | #endif | |
52 | ||
53 | #ifndef PTABLE_PREFIX | |
54 | # define PTABLE_PREFIX(X) PTABLE_JOIN(PTABLE_NAME, X) | |
55 | #endif | |
56 | ||
57 | #ifndef ptable_ent | |
58 | typedef struct ptable_ent { | |
59 | struct ptable_ent *next; | |
60 | const void * key; | |
61 | void * val; | |
62 | } ptable_ent; | |
63 | #define ptable_ent ptable_ent | |
64 | #endif /* !ptable_ent */ | |
65 | ||
66 | #ifndef ptable | |
67 | typedef struct ptable { | |
68 | ptable_ent **ary; | |
69 | UV max; | |
70 | UV items; | |
71 | } ptable; | |
72 | #define ptable ptable | |
73 | #endif /* !ptable */ | |
74 | ||
75 | #ifndef ptable_new | |
76 | STATIC ptable *ptable_new(pPTBLMS) { | |
77 | #define ptable_new() ptable_new(aPTBLMS) | |
78 | ptable *t = PerlMemShared_malloc(sizeof *t); | |
79 | t->max = 63; | |
80 | t->items = 0; | |
81 | t->ary = PerlMemShared_calloc(t->max + 1, sizeof *t->ary); | |
82 | return t; | |
83 | } | |
84 | #endif /* !ptable_new */ | |
85 | ||
86 | #ifndef PTABLE_HASH | |
87 | # define PTABLE_HASH(ptr) \ | |
88 | ((PTR2UV(ptr) >> 3) ^ (PTR2UV(ptr) >> (3 + 7)) ^ (PTR2UV(ptr) >> (3 + 17))) | |
89 | #endif | |
90 | ||
91 | #ifndef ptable_find | |
92 | STATIC ptable_ent *ptable_find(const ptable * const t, const void * const key) { | |
93 | #define ptable_find ptable_find | |
94 | ptable_ent *ent; | |
95 | const UV hash = PTABLE_HASH(key); | |
96 | ||
97 | ent = t->ary[hash & t->max]; | |
98 | for (; ent; ent = ent->next) { | |
99 | if (ent->key == key) | |
100 | return ent; | |
101 | } | |
102 | ||
103 | return NULL; | |
104 | } | |
105 | #endif /* !ptable_find */ | |
106 | ||
107 | #ifndef ptable_fetch | |
108 | STATIC void *ptable_fetch(const ptable * const t, const void * const key) { | |
109 | #define ptable_fetch ptable_fetch | |
110 | const ptable_ent *const ent = ptable_find(t, key); | |
111 | ||
112 | return ent ? ent->val : NULL; | |
113 | } | |
114 | #endif /* !ptable_fetch */ | |
115 | ||
116 | #ifndef ptable_split | |
117 | STATIC void ptable_split(pPTBLMS_ ptable * const t) { | |
118 | #define ptable_split(T) ptable_split(aPTBLMS_ (T)) | |
119 | ptable_ent **ary = t->ary; | |
120 | const UV oldsize = t->max + 1; | |
121 | UV newsize = oldsize * 2; | |
122 | UV i; | |
123 | ||
124 | ary = PerlMemShared_realloc(ary, newsize * sizeof(*ary)); | |
125 | Zero(&ary[oldsize], newsize - oldsize, sizeof(*ary)); | |
126 | t->max = --newsize; | |
127 | t->ary = ary; | |
128 | ||
129 | for (i = 0; i < oldsize; i++, ary++) { | |
130 | ptable_ent **curentp, **entp, *ent; | |
131 | if (!*ary) | |
132 | continue; | |
133 | curentp = ary + oldsize; | |
134 | for (entp = ary, ent = *ary; ent; ent = *entp) { | |
135 | if ((newsize & PTABLE_HASH(ent->key)) != i) { | |
136 | *entp = ent->next; | |
137 | ent->next = *curentp; | |
138 | *curentp = ent; | |
139 | continue; | |
140 | } else | |
141 | entp = &ent->next; | |
142 | } | |
143 | } | |
144 | } | |
145 | #endif /* !ptable_split */ | |
146 | ||
147 | STATIC void PTABLE_PREFIX(_store)(pPTBL_ ptable * const t, const void * const key, void * const val) { | |
148 | ptable_ent *ent = ptable_find(t, key); | |
149 | ||
150 | if (ent) { | |
151 | void *oldval = ent->val; | |
152 | PTABLE_VAL_FREE(oldval); | |
153 | ent->val = val; | |
154 | } else if (val) { | |
155 | const UV i = PTABLE_HASH(key) & t->max; | |
156 | ent = PerlMemShared_malloc(sizeof *ent); | |
157 | ent->key = key; | |
158 | ent->val = val; | |
159 | ent->next = t->ary[i]; | |
160 | t->ary[i] = ent; | |
161 | t->items++; | |
162 | if (ent->next && t->items > t->max) | |
163 | ptable_split(t); | |
164 | } | |
165 | } | |
166 | ||
167 | #ifndef ptable_walk | |
168 | STATIC void ptable_walk(pTHX_ ptable * const t, void (*cb)(pTHX_ ptable_ent *ent, void *userdata), void *userdata) { | |
169 | #define ptable_walk(T, CB, UD) ptable_walk(aTHX_ (T), (CB), (UD)) | |
170 | if (t && t->items) { | |
171 | register ptable_ent ** const array = t->ary; | |
172 | UV i = t->max; | |
173 | do { | |
174 | ptable_ent *entry; | |
175 | for (entry = array[i]; entry; entry = entry->next) | |
176 | cb(aTHX_ entry, userdata); | |
177 | } while (i--); | |
178 | } | |
179 | } | |
180 | #endif /* !ptable_walk */ | |
181 | ||
182 | STATIC void PTABLE_PREFIX(_clear)(pPTBL_ ptable * const t) { | |
183 | if (t && t->items) { | |
184 | register ptable_ent ** const array = t->ary; | |
185 | UV i = t->max; | |
186 | ||
187 | do { | |
188 | ptable_ent *entry = array[i]; | |
189 | while (entry) { | |
190 | ptable_ent * const oentry = entry; | |
191 | void *val = oentry->val; | |
192 | entry = entry->next; | |
193 | PTABLE_VAL_FREE(val); | |
194 | PerlMemShared_free(oentry); | |
195 | } | |
196 | array[i] = NULL; | |
197 | } while (i--); | |
198 | ||
199 | t->items = 0; | |
200 | } | |
201 | } | |
202 | ||
203 | STATIC void PTABLE_PREFIX(_free)(pPTBL_ ptable * const t) { | |
204 | if (!t) | |
205 | return; | |
206 | PTABLE_PREFIX(_clear)(aPTBL_ t); | |
207 | PerlMemShared_free(t->ary); | |
208 | PerlMemShared_free(t); | |
209 | } | |
210 | ||
211 | #undef pPTBL | |
212 | #undef pPTBL_ | |
213 | #undef aPTBL | |
214 | #undef aPTBL_ | |
215 | ||
216 | #undef PTABLE_NAME | |
217 | #undef PTABLE_VAL_FREE |