File Coverage

File:ptable.h
Coverage:85.6%

linestmtbrancondsubpodtimecode
1/* This file is part of the autovivification Perl module.
2 * See http://search.cpan.org/dist/autovivification/ */
3
4/* This is a pointer table implementation essentially copied from the ptr_table
5 * implementation in perl's sv.c, except that it has been modified to use memory
6 * shared across threads.
7 * Copyright goes to the original authors, bug reports to me. */
8
9/* This header is designed to be included several times with different
10 * definitions for PTABLE_NAME and PTABLE_VAL_FREE(). */
11
12#undef VOID2
13#ifdef __cplusplus
14# define VOID2(T, P) static_cast<T>(P)
15#else
16# define VOID2(T, P) (P)
17#endif
18
19#undef pPTBLMS
20#undef pPTBLMS_
21#undef aPTBLMS
22#undef aPTBLMS_
23
24/* Context for PerlMemShared_* functions */
25
26#ifdef PERL_IMPLICIT_SYS
27# define pPTBLMS pTHX
28# define pPTBLMS_ pTHX_
29# define aPTBLMS aTHX
30# define aPTBLMS_ aTHX_
31#else
32# define pPTBLMS void
33# define pPTBLMS_
34# define aPTBLMS
35# define aPTBLMS_
36#endif
37
38#ifndef pPTBL
39# define pPTBL pPTBLMS
40#endif
41#ifndef pPTBL_
42# define pPTBL_ pPTBLMS_
43#endif
44#ifndef aPTBL
45# define aPTBL aPTBLMS
46#endif
47#ifndef aPTBL_
48# define aPTBL_ aPTBLMS_
49#endif
50
51#ifndef PTABLE_NAME
52# define PTABLE_NAME ptable
53#endif
54
55#ifndef PTABLE_VAL_FREE
56# define PTABLE_VAL_FREE(V)
57#endif
58
59#ifndef PTABLE_JOIN
60# define PTABLE_PASTE(A, B) A ## B
61# define PTABLE_JOIN(A, B) PTABLE_PASTE(A, B)
62#endif
63
64#ifndef PTABLE_PREFIX
65# define PTABLE_PREFIX(X) PTABLE_JOIN(PTABLE_NAME, X)
66#endif
67
68#ifndef ptable_ent
69typedef struct ptable_ent {
70 struct ptable_ent *next;
71 const void * key;
72 void * val;
73} ptable_ent;
74#define ptable_ent ptable_ent
75#endif /* !ptable_ent */
76
77#ifndef ptable
78typedef struct ptable {
79 ptable_ent **ary;
80 size_t max;
81 size_t items;
82} ptable;
83#define ptable ptable
84#endif /* !ptable */
85
86#ifndef ptable_new
87
30
STATIC ptable *ptable_new(pPTBLMS) {
88#define ptable_new() ptable_new(aPTBLMS)
89
30
 ptable *t = VOID2(ptable *, PerlMemShared_malloc(sizeof *t));
90
30
 t->max = 63;
91
30
 t->items = 0;
92
30
 t->ary = VOID2(ptable_ent **,
93                              PerlMemShared_calloc(t->max + 1, sizeof *t->ary));
94
30
 return t;
95}
96#endif /* !ptable_new */
97
98#ifndef PTABLE_HASH
99# define PTABLE_HASH(ptr) \
100     ((PTR2UV(ptr) >> 3) ^ (PTR2UV(ptr) >> (3 + 7)) ^ (PTR2UV(ptr) >> (3 + 17)))
101#endif
102
103#ifndef ptable_find
104
3620470
STATIC ptable_ent *ptable_find(const ptable * const t, const void * const key) {
105#define ptable_find ptable_find
106 ptable_ent *ent;
107
3620470
 const UV hash = PTABLE_HASH(key);
108
109
3620470
 ent = t->ary[hash & t->max];
110
4413674
 for (; ent; ent = ent->next) {
111
878297
  if (ent->key == key)
112
85093
   return ent;
113 }
114
115
3620470
 return NULL;
116}
117#endif /* !ptable_find */
118
119#ifndef ptable_fetch
120
1919695
STATIC void *ptable_fetch(const ptable * const t, const void * const key) {
121#define ptable_fetch ptable_fetch
122
1919695
 const ptable_ent *const ent = ptable_find(t, key);
123
124
1919695
 return ent ? ent->val : NULL;
125}
126#endif /* !ptable_fetch */
127
128#ifndef ptable_split
129
65
STATIC void ptable_split(pPTBLMS_ ptable * const t) {
130#define ptable_split(T) ptable_split(aPTBLMS_ (T))
131
65
 ptable_ent **ary = t->ary;
132
65
 const size_t oldsize = t->max + 1;
133
65
 size_t newsize = oldsize * 2;
134 size_t i;
135
136
65
 ary = VOID2(ptable_ent **, PerlMemShared_realloc(ary, newsize * sizeof(*ary)));
137
65
 Zero(&ary[oldsize], newsize - oldsize, sizeof(*ary));
138
65
 t->max = --newsize;
139
65
 t->ary = ary;
140
141
57665
 for (i = 0; i < oldsize; i++, ary++) {
142  ptable_ent **curentp, **entp, *ent;
143
57600
  if (!*ary)
144
23091
   continue;
145
34509
  curentp = ary + oldsize;
146
87034
  for (entp = ary, ent = *ary; ent; ent = *entp) {
147
52525
   if ((newsize & PTABLE_HASH(ent->key)) != i) {
148
25999
    *entp = ent->next;
149
25999
    ent->next = *curentp;
150
25999
    *curentp = ent;
151
25999
    continue;
152   } else
153
26526
    entp = &ent->next;
154  }
155 }
156
65
}
157#endif /* !ptable_split */
158
159
1700775
STATIC void PTABLE_PREFIX(_store)(pPTBL_ ptable * const t, const void * const key, void * const val) {
160
1700775
 ptable_ent *ent = ptable_find(t, key);
161
162
1700775
 if (ent) {
163
0
  void *oldval = ent->val;
164
0
  PTABLE_VAL_FREE(oldval);
165
0
  ent->val = val;
166
1700775
 } else if (val) {
167
1700775
  const size_t i = PTABLE_HASH(key) & t->max;
168
1700775
  ent = VOID2(ptable_ent *, PerlMemShared_malloc(sizeof *ent));
169
1700775
  ent->key = key;
170
1700775
  ent->val = val;
171
1700775
  ent->next = t->ary[i];
172
1700775
  t->ary[i] = ent;
173
1700775
  t->items++;
174
1700775
  if (ent->next && t->items > t->max)
175
65
   ptable_split(t);
176 }
177
1700775
}
178
179
252160
STATIC void PTABLE_PREFIX(_delete)(pPTBL_ ptable * const t, const void * const key) {
180 ptable_ent *prev, *ent;
181
252160
 const size_t i = PTABLE_HASH(key) & t->max;
182
183
252160
 prev = NULL;
184
252160
 ent = t->ary[i];
185
417161
 for (; ent; prev = ent, ent = ent->next) {
186
168615
  if (ent->key == key)
187
3614
   break;
188 }
189
190
252160
 if (ent) {
191
3614
  if (prev)
192
25
   prev->next = ent->next;
193  else
194
3589
   t->ary[i] = ent->next;
195
3614
  PTABLE_VAL_FREE(ent->val);
196
3614
  PerlMemShared_free(ent);
197 }
198
252160
}
199
200#ifndef ptable_walk
201
0
STATIC void ptable_walk(pTHX_ ptable * const t, void (*cb)(pTHX_ ptable_ent *ent, void *userdata), void *userdata) {
202#define ptable_walk(T, CB, UD) ptable_walk(aTHX_ (T), (CB), (UD))
203
0
 if (t && t->items) {
204
0
  register ptable_ent ** const array = t->ary;
205
0
  size_t i = t->max;
206  do {
207   ptable_ent *entry;
208
0
   for (entry = array[i]; entry; entry = entry->next)
209
0
    if (entry->val)
210
0
     cb(aTHX_ entry, userdata);
211
0
  } while (i--);
212 }
213
0
}
214#endif /* !ptable_walk */
215
216
99249
STATIC void PTABLE_PREFIX(_clear)(pPTBL_ ptable * const t) {
217
99249
 if (t && t->items) {
218
49617
  register ptable_ent ** const array = t->ary;
219
49617
  size_t i = t->max;
220
221  do {
222
6687424
   ptable_ent *entry = array[i];
223
8352421
   while (entry) {
224
1664997
    ptable_ent * const oentry = entry;
225
1664997
    void *val = oentry->val;
226
1664997
    entry = entry->next;
227
0
    PTABLE_VAL_FREE(val);
228
1664997
    PerlMemShared_free(oentry);
229   }
230
6687424
   array[i] = NULL;
231
6687424
  } while (i--);
232
233
49617
  t->items = 0;
234 }
235
99249
}
236
237
15
STATIC void PTABLE_PREFIX(_free)(pPTBL_ ptable * const t) {
238
15
 if (!t)
239
0
  return;
240
15
 PTABLE_PREFIX(_clear)(aPTBL_ t);
241
15
 PerlMemShared_free(t->ary);
242
15
 PerlMemShared_free(t);
243}
244
245#undef pPTBL
246#undef pPTBL_
247#undef aPTBL
248#undef aPTBL_
249
250#undef PTABLE_NAME
251#undef PTABLE_VAL_FREE