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) | |
f39efbfa | 78 | ptable *t = (ptable *)PerlMemShared_malloc(sizeof *t); |
b82b06b8 FC |
79 | t->max = 63; |
80 | t->items = 0; | |
f39efbfa | 81 | t->ary = (ptable_ent **)PerlMemShared_calloc(t->max + 1, sizeof *t->ary); |
b82b06b8 FC |
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 | ||
f39efbfa | 124 | ary = (ptable_ent **)PerlMemShared_realloc(ary, newsize * sizeof(*ary)); |
b82b06b8 FC |
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++) { | |
92dfa259 | 130 | ptable_ent **currentp, **entp, *ent; |
b82b06b8 FC |
131 | if (!*ary) |
132 | continue; | |
92dfa259 | 133 | currentp = ary + oldsize; |
b82b06b8 FC |
134 | for (entp = ary, ent = *ary; ent; ent = *entp) { |
135 | if ((newsize & PTABLE_HASH(ent->key)) != i) { | |
136 | *entp = ent->next; | |
92dfa259 LV |
137 | ent->next = *currentp; |
138 | *currentp = ent; | |
b82b06b8 FC |
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; | |
f39efbfa | 156 | ent = (ptable_ent *)PerlMemShared_malloc(sizeof *ent); |
b82b06b8 FC |
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 | ||
3b32020f DM |
167 | /* this function appears to be unused */ |
168 | #if 0 | |
b82b06b8 FC |
169 | #ifndef ptable_walk |
170 | STATIC void ptable_walk(pTHX_ ptable * const t, void (*cb)(pTHX_ ptable_ent *ent, void *userdata), void *userdata) { | |
171 | #define ptable_walk(T, CB, UD) ptable_walk(aTHX_ (T), (CB), (UD)) | |
172 | if (t && t->items) { | |
5aaab254 | 173 | ptable_ent ** const array = t->ary; |
b82b06b8 FC |
174 | UV i = t->max; |
175 | do { | |
176 | ptable_ent *entry; | |
177 | for (entry = array[i]; entry; entry = entry->next) | |
178 | cb(aTHX_ entry, userdata); | |
179 | } while (i--); | |
180 | } | |
181 | } | |
182 | #endif /* !ptable_walk */ | |
3b32020f | 183 | #endif |
b82b06b8 | 184 | |
3b32020f DM |
185 | /* this function appears to be unused */ |
186 | #if 0 | |
b82b06b8 FC |
187 | STATIC void PTABLE_PREFIX(_clear)(pPTBL_ ptable * const t) { |
188 | if (t && t->items) { | |
5aaab254 | 189 | ptable_ent ** const array = t->ary; |
b82b06b8 FC |
190 | UV i = t->max; |
191 | ||
192 | do { | |
193 | ptable_ent *entry = array[i]; | |
194 | while (entry) { | |
195 | ptable_ent * const oentry = entry; | |
196 | void *val = oentry->val; | |
197 | entry = entry->next; | |
198 | PTABLE_VAL_FREE(val); | |
199 | PerlMemShared_free(oentry); | |
200 | } | |
201 | array[i] = NULL; | |
202 | } while (i--); | |
203 | ||
204 | t->items = 0; | |
205 | } | |
206 | } | |
3b32020f | 207 | #endif |
b82b06b8 | 208 | |
3b32020f DM |
209 | /* this function appears to be unused */ |
210 | #if 0 | |
b82b06b8 FC |
211 | STATIC void PTABLE_PREFIX(_free)(pPTBL_ ptable * const t) { |
212 | if (!t) | |
213 | return; | |
214 | PTABLE_PREFIX(_clear)(aPTBL_ t); | |
215 | PerlMemShared_free(t->ary); | |
216 | PerlMemShared_free(t); | |
217 | } | |
3b32020f | 218 | #endif |
b82b06b8 FC |
219 | |
220 | #undef pPTBL | |
221 | #undef pPTBL_ | |
222 | #undef aPTBL | |
223 | #undef aPTBL_ | |
224 | ||
225 | #undef PTABLE_NAME | |
226 | #undef PTABLE_VAL_FREE |