1 : /*
2 : * Copyright 2008 The Native Client Authors. All rights reserved.
3 : * Use of this source code is governed by a BSD-style license that can
4 : * be found in the LICENSE file.
5 : */
6 :
7 : /*
8 : * NaCl Generic containers.
9 : */
10 : #include "native_client/src/include/portability.h"
11 : #include <stdio.h>
12 : #include <stdlib.h>
13 :
14 : #include "native_client/src/trusted/service_runtime/generic_container/container.h"
15 :
16 : static struct NaClContainerVtbl const kNaClContainerListVtbl = {
17 : NaClContainerListInsert,
18 : NaClContainerListFind,
19 : NaClContainerListDtor,
20 : sizeof(struct NaClContainerListIter),
21 : NaClContainerListIterCtor,
22 : };
23 :
24 :
25 : /*
26 : * functor_obj is the comparison functor, and is the first argument to
27 : * cmp_fn as the "self" (or more commonly "this") argument. arguably
28 : * we should create an explicit object with a vtable containing the
29 : * single comparison function pointer, but this is so simple that that
30 : * seems overkill.
31 : */
32 : int NaClContainerListCtor(struct NaClContainerList *self,
33 0 : struct NaClCmpFunctor *cmp_functor) {
34 0 : self->cmp_functor = cmp_functor;
35 0 : self->head = 0;
36 :
37 0 : self->base.vtbl = &kNaClContainerListVtbl;
38 0 : return 1;
39 : }
40 :
41 :
42 0 : int NaClContainerListIterAtEnd(struct NaClContainerIter *vself) {
43 0 : struct NaClContainerListIter *self = (struct NaClContainerListIter *) vself;
44 :
45 0 : return *self->cur == 0;
46 : }
47 :
48 :
49 0 : void *NaClContainerListIterStar(struct NaClContainerIter *vself) {
50 0 : struct NaClContainerListIter *self = (struct NaClContainerListIter *) vself;
51 :
52 0 : return (*self->cur)->datum;
53 : }
54 :
55 :
56 0 : void NaClContainerListIterIncr(struct NaClContainerIter *vself) {
57 0 : struct NaClContainerListIter *self = (struct NaClContainerListIter *) vself;
58 :
59 0 : self->cur = &(*self->cur)->next;
60 0 : }
61 :
62 :
63 0 : void NaClContainerListIterErase(struct NaClContainerIter *vself) {
64 0 : struct NaClContainerListIter *self = (struct NaClContainerListIter *) vself;
65 0 : struct NaClItemList *doomed = *self->cur;
66 0 : struct NaClItemList *next = (*self->cur)->next;
67 :
68 0 : *self->cur = next;
69 0 : free(doomed->datum);
70 0 : free(doomed);
71 0 : }
72 :
73 :
74 0 : void *NaClContainerListIterExtract(struct NaClContainerIter *vself) {
75 0 : struct NaClContainerListIter *self = (struct NaClContainerListIter *) vself;
76 0 : struct NaClItemList *doomed = *self->cur;
77 0 : struct NaClItemList *next = (*self->cur)->next;
78 : void *datum;
79 :
80 0 : *self->cur = next;
81 0 : datum = doomed->datum;
82 0 : free(doomed);
83 0 : return datum;
84 : }
85 :
86 : static struct NaClContainerIterVtbl const kNaClContainerListIterVtbl = {
87 : NaClContainerListIterAtEnd,
88 : NaClContainerListIterStar,
89 : NaClContainerListIterIncr,
90 : NaClContainerListIterErase,
91 : NaClContainerListIterExtract,
92 : };
93 :
94 :
95 : int NaClContainerListInsert(struct NaClContainer *vself,
96 0 : void *obj) {
97 0 : struct NaClContainerList *self = (struct NaClContainerList *) vself;
98 0 : struct NaClItemList *new_entry = malloc(sizeof *new_entry);
99 : struct NaClItemList **ipp;
100 : struct NaClItemList *ip;
101 :
102 0 : if (!new_entry)
103 0 : return 0;
104 :
105 0 : new_entry->datum = obj;
106 :
107 0 : for (ipp = &self->head; 0 != (ip = *ipp); ipp = &ip->next) {
108 0 : if ((*self->cmp_functor->vtbl->OrderCmp)(self->cmp_functor,
109 : obj, ip->datum) >= 0) {
110 0 : break;
111 : }
112 : }
113 :
114 0 : new_entry->next = ip;
115 0 : *ipp = new_entry;
116 0 : return 1;
117 : }
118 :
119 :
120 : struct NaClContainerIter *NaClContainerListFind(
121 : struct NaClContainer *vself,
122 : void *key,
123 0 : struct NaClContainerIter *vout) {
124 0 : struct NaClContainerList *self = (struct NaClContainerList *) vself;
125 : struct NaClItemList **ipp;
126 : struct NaClItemList *ip;
127 0 : struct NaClContainerListIter *out = (struct NaClContainerListIter *) vout;
128 :
129 0 : for (ipp = &self->head; (ip = *ipp) != 0; ipp = &ip->next) {
130 0 : if ((*self->cmp_functor->vtbl->OrderCmp)(self->cmp_functor,
131 : key, ip->datum) == 0) {
132 0 : break;
133 : }
134 : }
135 0 : out->cur = ipp;
136 :
137 0 : vout->vtbl = &kNaClContainerListIterVtbl;
138 0 : return vout;
139 : }
140 :
141 :
142 0 : void NaClContainerListDtor(struct NaClContainer *vself) {
143 0 : struct NaClContainerList *self = (struct NaClContainerList *) vself;
144 : struct NaClItemList *cur, *next;
145 :
146 0 : for (cur = self->head; cur; cur = next) {
147 0 : next = cur->next;
148 0 : free(cur->datum);
149 0 : free(cur);
150 : }
151 0 : }
152 :
153 :
154 : int NaClContainerListIterCtor(struct NaClContainer *vself,
155 0 : struct NaClContainerIter *viter) {
156 0 : struct NaClContainerList *self = (struct NaClContainerList *) vself;
157 0 : struct NaClContainerListIter *iter = (struct NaClContainerListIter *) viter;
158 :
159 0 : iter->cur = &self->head;
160 :
161 0 : viter->vtbl = &kNaClContainerListIterVtbl;
162 0 : return 1;
163 : }
164 :
165 :
166 : static struct NaClContainerVtbl const kNaClContainerHashTblVtbl = {
167 : NaClContainerHashTblInsert,
168 : NaClContainerHashTblFind,
169 : NaClContainerHashTblDtor,
170 : sizeof(struct NaClContainerHashTblIter),
171 : NaClContainerHashTblIterCtor,
172 : };
173 :
174 : #define HASH_TABLE_LOAD_FACTOR 2
175 : #define HASH_TABLE_STRIDE 17
176 : /*
177 : * The stride p is prime, so it is co-prime with any num_bucket value
178 : * (except for its own multiples) and thus linear probing by
179 : * increments of the stride will visit every bucket. (I.e., the
180 : * stride value is a generator for the additive group Z_k^+, where
181 : * k=num_bucket.) Assume that (k,p)=1.
182 : *
183 : * (p,+) is a generator is another way of saying that
184 : * 0,p,2p,3p,...,(k-1)p (mod k) is a permutation of 0,1,...,k-1.
185 : *
186 : * assume otherwise, so (p,+) generates a subgroup of Z_k^+. let n be
187 : * the least integer greater than 0 where np=0 mod k, i.e., 0 < n < k.
188 : * since (p) doesn't generate Z_k^+, we have n < k. then np=mk for
189 : * some integer m>0. since p is prime and p \not| k but p divides mk,
190 : * p must divide m. write m=pq. then np = pqk, so n = qk. =><=
191 : *
192 : * The co-primality of the stride and number of bucket is a
193 : * precondition for the insertion algorithm terminating. (Another
194 : * precondition is that there is an unused slot.)
195 : *
196 : * We expand the hash table by doubling the number of buckets. Thus,
197 : * if num_bucket starts off co-prime with the stride, it will remain
198 : * so.
199 : */
200 : #define HASH_TABLE_MIN_BUCKETS 32
201 : /*
202 : * must be greater than HASH_TABLE_STRIDE and not a multiple so that
203 : * they're co-prime.
204 : */
205 :
206 : static struct NaClContainerHashTblEntry *NaClContainerHashTblMakeBucket(
207 240 : size_t size) {
208 : struct NaClContainerHashTblEntry *bucket;
209 :
210 240 : if (SIZE_T_MAX / sizeof *bucket < size) {
211 0 : return NULL;
212 : }
213 240 : bucket = calloc(size, sizeof *bucket);
214 240 : return bucket;
215 : }
216 :
217 :
218 : /*
219 : * The functor_obj is the comparison and hash functor. It is always
220 : * passed as the first arguments to cmp_fn and hash_fn to allow these
221 : * member functions to use its members to determine how to
222 : * compare/hash. Arguably we should define a class with a vtable
223 : * containing two virtual functions, but we don't expect there to be
224 : * many object instances.
225 : */
226 : int NaClContainerHashTblCtor(struct NaClContainerHashTbl *self,
227 : struct NaClHashFunctor *hash_functor,
228 48 : size_t num_buckets) {
229 : int success;
230 :
231 48 : self->base.vtbl = (struct NaClContainerVtbl *) NULL;
232 :
233 : /* silently increase number of buckets if too small */
234 48 : if (num_buckets < HASH_TABLE_MIN_BUCKETS) {
235 0 : num_buckets = HASH_TABLE_MIN_BUCKETS;
236 : }
237 : /* if a multiple of stride, silently increase it */
238 48 : if (0 == (num_buckets % HASH_TABLE_STRIDE)) {
239 0 : ++num_buckets;
240 : }
241 :
242 48 : self->hash_functor = hash_functor;
243 48 : self->num_buckets = num_buckets;
244 48 : self->num_entries = 0;
245 48 : self->bucket = NaClContainerHashTblMakeBucket(num_buckets);
246 :
247 48 : success = self->bucket != 0;
248 :
249 48 : if (success) {
250 48 : self->base.vtbl = &kNaClContainerHashTblVtbl;
251 : }
252 48 : return success;
253 : }
254 :
255 :
256 190848 : int NaClContainerHashTblCheckLoad(struct NaClContainerHashTbl *self) {
257 : struct NaClContainerHashTblEntry *entry;
258 : struct NaClContainerHashTblEntry *new_table;
259 : struct NaClContainerHashTblEntry *old_table;
260 : size_t new_size;
261 : size_t old_size;
262 : size_t i;
263 :
264 : /*
265 : * Check load factor. If greater than THRESHOLD, double number of
266 : * buckets and rehash.
267 : */
268 190848 : if (HASH_TABLE_LOAD_FACTOR * self->num_entries < self->num_buckets)
269 190656 : return 1;
270 :
271 192 : old_size = self->num_buckets;
272 192 : new_size = 2 * old_size;
273 : /*
274 : * arithmetic overflow?!? we normally would not have enough memory
275 : */
276 192 : if (new_size < old_size)
277 0 : return 0;
278 :
279 192 : new_table = NaClContainerHashTblMakeBucket(new_size);
280 192 : if (!new_table)
281 0 : return 0;
282 :
283 192 : old_table = self->bucket;
284 192 : self->bucket = new_table;
285 :
286 192 : self->num_buckets = new_size;
287 192 : self->num_entries = 0;
288 :
289 : /*
290 : * The rehash/transfer to the new, expanded table should not fail,
291 : * since the Insert method (below) does not fail.
292 : */
293 185232 : for (i = 0; i < old_size; i++) {
294 185040 : entry = &old_table[i];
295 185040 : if (NACL_CHTE_USED != entry->flags) {
296 92496 : continue;
297 : }
298 92544 : (*self->base.vtbl->Insert)((struct NaClContainer *) self,
299 : entry->datum);
300 : }
301 :
302 192 : free(old_table);
303 192 : return 1;
304 : }
305 :
306 :
307 : static uintptr_t HashNext(uintptr_t idx,
308 168915 : size_t modulus) {
309 168915 : idx += HASH_TABLE_STRIDE;
310 339076 : while (idx >= modulus) {
311 1246 : idx -= modulus;
312 : }
313 168915 : return idx;
314 : }
315 :
316 :
317 : int NaClContainerHashTblInsert(struct NaClContainer *vself,
318 190848 : void *obj) {
319 190848 : struct NaClContainerHashTbl *self = (struct NaClContainerHashTbl *) vself;
320 : uintptr_t idx;
321 :
322 : for (idx = (*self->hash_functor->vtbl->Hash)(self->hash_functor,
323 190848 : obj) % self->num_buckets;
324 428394 : NACL_CHTE_USED == self->bucket[idx].flags;
325 46698 : idx = HashNext(idx, self->num_buckets)) {
326 : }
327 : /* unused or deleted */
328 190848 : self->bucket[idx].datum = obj;
329 190848 : self->bucket[idx].flags = NACL_CHTE_USED;
330 190848 : ++self->num_entries;
331 :
332 190848 : return NaClContainerHashTblCheckLoad(self);
333 : }
334 :
335 :
336 : /* fwd */
337 : static struct NaClContainerIterVtbl const kNaClContainerHashTblIterVtbl;
338 :
339 :
340 : struct NaClContainerIter *NaClContainerHashTblFind(
341 : struct NaClContainer *vself,
342 : void *key,
343 344016 : struct NaClContainerIter *vout) {
344 : struct NaClContainerHashTbl *self
345 344016 : = (struct NaClContainerHashTbl *) vself;
346 : uintptr_t idx;
347 : struct NaClContainerHashTblIter *out
348 344016 : = (struct NaClContainerHashTblIter *) vout;
349 :
350 : for (idx = (*self->hash_functor->vtbl->Hash)(self->hash_functor,
351 344016 : key) % self->num_buckets;
352 810249 : 0 != self->bucket[idx].flags;
353 122217 : idx = HashNext(idx, self->num_buckets)) {
354 318777 : if (0 != (self->bucket[idx].flags & NACL_CHTE_USED)
355 : && ((*self->hash_functor->vtbl->base.OrderCmp)
356 : ((struct NaClCmpFunctor *) self->hash_functor,
357 : self->bucket[idx].datum, key)) == 0) {
358 196560 : break;
359 : }
360 : }
361 344016 : if (0 == self->bucket[idx].flags) {
362 : /* not found */
363 147456 : idx = self->num_buckets;
364 : }
365 :
366 344016 : out->htbl = self;
367 344016 : out->idx = idx;
368 :
369 344016 : vout->vtbl = &kNaClContainerHashTblIterVtbl;
370 344016 : return vout;
371 : }
372 :
373 :
374 48 : void NaClContainerHashTblDtor(struct NaClContainer *vself) {
375 48 : struct NaClContainerHashTbl *self = (struct NaClContainerHashTbl *) vself;
376 : unsigned int idx;
377 :
378 197424 : for (idx = 0; idx < self->num_buckets; ++idx) {
379 197376 : if (self->bucket[idx].flags & NACL_CHTE_USED) {
380 98304 : free(self->bucket[idx].datum);
381 : }
382 : }
383 48 : free(self->bucket);
384 48 : self->bucket = 0;
385 48 : }
386 :
387 :
388 344016 : int NaClContainerHashTblIterAtEnd(struct NaClContainerIter *vself) {
389 : struct NaClContainerHashTblIter *self
390 344016 : = (struct NaClContainerHashTblIter *) vself;
391 :
392 344016 : return self->idx >= self->htbl->num_buckets;
393 : }
394 :
395 :
396 196560 : void *NaClContainerHashTblIterStar(struct NaClContainerIter *vself) {
397 : struct NaClContainerHashTblIter *self
398 196560 : = (struct NaClContainerHashTblIter *) vself;
399 :
400 196560 : return self->htbl->bucket[self->idx].datum;
401 : }
402 :
403 :
404 0 : void NaClContainerHashTblIterIncr(struct NaClContainerIter *vself) {
405 : struct NaClContainerHashTblIter *self
406 0 : = (struct NaClContainerHashTblIter *) vself;
407 :
408 0 : while (++self->idx < self->htbl->num_buckets) {
409 0 : if (self->htbl->bucket[self->idx].flags == NACL_CHTE_USED)
410 0 : return;
411 : }
412 : /* self->idx == self->htbl->num_buckets imply AtEnd */
413 0 : return;
414 : }
415 :
416 :
417 0 : void NaClContainerHashTblIterErase(struct NaClContainerIter *vself) {
418 : struct NaClContainerHashTblIter *self
419 0 : = (struct NaClContainerHashTblIter *) vself;
420 :
421 0 : if (self->htbl->bucket[self->idx].flags == NACL_CHTE_USED) {
422 0 : --self->htbl->num_entries;
423 : }
424 0 : self->htbl->bucket[self->idx].flags = NACL_CHTE_DELETED;
425 0 : free(self->htbl->bucket[self->idx].datum);
426 0 : self->htbl->bucket[self->idx].datum = 0;
427 0 : (*vself->vtbl->Incr)(vself);
428 0 : }
429 :
430 :
431 0 : void *NaClContainerHashTblIterExtract(struct NaClContainerIter *vself) {
432 : struct NaClContainerHashTblIter *self
433 0 : = (struct NaClContainerHashTblIter *) vself;
434 : void *datum;
435 :
436 0 : if (self->htbl->bucket[self->idx].flags == NACL_CHTE_USED) {
437 0 : --self->htbl->num_entries;
438 : }
439 0 : self->htbl->bucket[self->idx].flags = NACL_CHTE_DELETED;
440 0 : datum = self->htbl->bucket[self->idx].datum;
441 0 : self->htbl->bucket[self->idx].datum = 0;
442 0 : (*vself->vtbl->Incr)(vself);
443 :
444 0 : return datum;
445 : }
446 :
447 :
448 : static struct NaClContainerIterVtbl const kNaClContainerHashTblIterVtbl = {
449 : NaClContainerHashTblIterAtEnd,
450 : NaClContainerHashTblIterStar,
451 : NaClContainerHashTblIterIncr,
452 : NaClContainerHashTblIterErase,
453 : NaClContainerHashTblIterExtract,
454 : };
455 :
456 :
457 : int NaClContainerHashTblIterCtor(struct NaClContainer *vself,
458 0 : struct NaClContainerIter *viter) {
459 : struct NaClContainerHashTbl *self
460 0 : = (struct NaClContainerHashTbl *) vself;
461 : struct NaClContainerHashTblIter *iter
462 0 : = (struct NaClContainerHashTblIter *) viter;
463 :
464 0 : viter->vtbl = &kNaClContainerHashTblIterVtbl;
465 0 : iter->htbl = self;
466 0 : iter->idx = 0;
467 0 : if (0 == (self->bucket[0].flags & NACL_CHTE_USED)) {
468 0 : NaClContainerHashTblIterIncr(viter);
469 : }
470 0 : return 1;
471 : }
|
