← Back to branch summary

~ubuntu-branches/ubuntu/trusty/libsereal-encoder-perl/trusty-proposed

« back to all changes in this revision

Viewing changes to ptable.h

  • Committer: Package Import Robot
  • Author(s): Alexandre Mestiashvili
  • Date: 2013-02-20 08:29:14 UTC
  • Revision ID: package-import@ubuntu.com-20130220082914-dljb6eixvtj2m1v2
Tags: upstream-0.31
Import upstream version 0.31

Show diffs side-by-side

added added

removed removed

Lines of Context:
ptable.h
 
1
/* Taken from Chocolateboy's autobox module. License same as perl's and
 
2
 * this same as this module's license.
 
3
 */
 
4
 
 
5
/*
 
6
 * This is a customized version of the pointer table implementation in sv.c
 
7
 */
 
8
 
 
9
#ifndef PTABLE_H_
 
10
#define PTABLE_H_
 
11
 
 
12
#include "ppport.h"
 
13
#include <limits.h>
 
14
 
 
15
#if PTRSIZE == 8
 
16
    /*
 
17
     * This is one of Thomas Wang's hash functions for 64-bit integers from:
 
18
     * http://www.concentric.net/~Ttwang/tech/inthash.htm
 
19
     */
 
20
    STATIC U32 ptr_hash(PTRV u) {
 
21
        u = (~u) + (u << 18);
 
22
        u = u ^ (u >> 31);
 
23
        u = u * 21;
 
24
        u = u ^ (u >> 11);
 
25
        u = u + (u << 6);
 
26
        u = u ^ (u >> 22);
 
27
        return (U32)u;
 
28
    }
 
29
#else
 
30
    /*
 
31
     * This is one of Bob Jenkins' hash functions for 32-bit integers
 
32
     * from: http://burtleburtle.net/bob/hash/integer.html
 
33
     */
 
34
    STATIC U32 ptr_hash(PTRV u) {
 
35
        u = (u + 0x7ed55d16) + (u << 12);
 
36
        u = (u ^ 0xc761c23c) ^ (u >> 19);
 
37
        u = (u + 0x165667b1) + (u << 5);
 
38
        u = (u + 0xd3a2646c) ^ (u << 9);
 
39
        u = (u + 0xfd7046c5) + (u << 3);
 
40
        u = (u ^ 0xb55a4f09) ^ (u >> 16);
 
41
        return u;
 
42
    }
 
43
#endif
 
44
 
 
45
#define PTABLE_HASH(ptr) ptr_hash(PTR2nat(ptr))
 
46
 
 
47
struct PTABLE_entry {
 
48
    struct PTABLE_entry     *next;
 
49
    void                    *key;
 
50
    void                    *value;
 
51
};
 
52
 
 
53
struct PTABLE {
 
54
    struct PTABLE_entry     **tbl_ary;
 
55
    UV                      tbl_max;
 
56
    UV                      tbl_items;
 
57
};
 
58
 
 
59
struct PTABLE_iter {
 
60
    struct PTABLE           *table;
 
61
    UV                      bucket_num;
 
62
    struct PTABLE_entry     *cur_entry;
 
63
};
 
64
 
 
65
typedef struct PTABLE_entry PTABLE_ENTRY_t;
 
66
typedef struct PTABLE       PTABLE_t;
 
67
typedef struct PTABLE_iter  PTABLE_ITER_t;
 
68
 
 
69
 
 
70
STATIC PTABLE_t * PTABLE_new(void);
 
71
STATIC PTABLE_t * PTABLE_new_size(const U8 size_base2_exponent);
 
72
STATIC PTABLE_ENTRY_t * PTABLE_find(PTABLE_t *tbl, const void *key);
 
73
STATIC void * PTABLE_fetch(PTABLE_t *tbl, const void *key);
 
74
STATIC void PTABLE_store(PTABLE_t *tbl, void *key, void *value);
 
75
STATIC void PTABLE_delete(PTABLE_t *tbl, void *key);
 
76
STATIC void PTABLE_grow(PTABLE_t *tbl);
 
77
STATIC void PTABLE_clear(PTABLE_t *tbl);
 
78
STATIC void PTABLE_free(PTABLE_t *tbl);
 
79
 
 
80
STATIC PTABLE_ITER_t * PTABLE_iter_new(PTABLE_t *tbl);
 
81
STATIC PTABLE_ENTRY_t * PTABLE_iter_next(PTABLE_ITER_t *iter);
 
82
STATIC void PTABLE_iter_free(PTABLE_ITER_t *iter);
 
83
 
 
84
/* create a new pointer => pointer table */
 
85
SRL_STATIC_INLINE PTABLE_t *
 
86
PTABLE_new(void)
 
87
{
 
88
    return PTABLE_new_size(9);
 
89
}
 
90
 
 
91
STATIC PTABLE_t *
 
92
PTABLE_new_size(const U8 size_base2_exponent)
 
93
{
 
94
    PTABLE_t *tbl;
 
95
    Newxz(tbl, 1, PTABLE_t);
 
96
    tbl->tbl_max = (1 << size_base2_exponent) - 1;
 
97
    tbl->tbl_items = 0;
 
98
    Newxz(tbl->tbl_ary, tbl->tbl_max + 1, PTABLE_ENTRY_t*);
 
99
    return tbl;
 
100
}
 
101
 
 
102
/* map an existing pointer using a table */
 
103
STATIC PTABLE_ENTRY_t *
 
104
PTABLE_find(PTABLE_t *tbl, const void *key) {
 
105
    PTABLE_ENTRY_t *tblent;
 
106
    const UV hash = PTABLE_HASH(key);
 
107
    tblent = tbl->tbl_ary[hash & tbl->tbl_max];
 
108
    for (; tblent; tblent = tblent->next) {
 
109
        if (tblent->key == key)
 
110
            return tblent;
 
111
    }
 
112
    return NULL;
 
113
}
 
114
 
 
115
SRL_STATIC_INLINE void *
 
116
PTABLE_fetch(PTABLE_t *tbl, const void *key)
 
117
{
 
118
    PTABLE_ENTRY_t const *const tblent = PTABLE_find(tbl, key);
 
119
    return tblent ? tblent->value : NULL;
 
120
}
 
121
 
 
122
/* add a new entry to a pointer => pointer table */
 
123
 
 
124
STATIC void
 
125
PTABLE_store(PTABLE_t *tbl, void *key, void *value)
 
126
{
 
127
    PTABLE_ENTRY_t *tblent = PTABLE_find(tbl, key);
 
128
 
 
129
    if (tblent) {
 
130
        tblent->value = value;
 
131
    } else {
 
132
        const UV entry = PTABLE_HASH(key) & tbl->tbl_max;
 
133
        Newx(tblent, 1, PTABLE_ENTRY_t);
 
134
 
 
135
        tblent->key = key;
 
136
        tblent->value = value;
 
137
        tblent->next = tbl->tbl_ary[entry];
 
138
        tbl->tbl_ary[entry] = tblent;
 
139
        tbl->tbl_items++;
 
140
        if (tblent->next && (tbl->tbl_items > tbl->tbl_max))
 
141
            PTABLE_grow(tbl);
 
142
    }
 
143
 
 
144
}
 
145
 
 
146
/* double the hash bucket size of an existing ptr table */
 
147
 
 
148
STATIC void
 
149
PTABLE_grow(PTABLE_t *tbl)
 
150
{
 
151
    PTABLE_ENTRY_t **ary = tbl->tbl_ary;
 
152
    const UV oldsize = tbl->tbl_max + 1;
 
153
    UV newsize = oldsize * 2;
 
154
    UV i;
 
155
 
 
156
    Renew(ary, newsize, PTABLE_ENTRY_t*);
 
157
    Zero(&ary[oldsize], newsize - oldsize, PTABLE_ENTRY_t*);
 
158
    tbl->tbl_max = --newsize;
 
159
    tbl->tbl_ary = ary;
 
160
 
 
161
    for (i = 0; i < oldsize; i++, ary++) {
 
162
        PTABLE_ENTRY_t **curentp, **entp, *ent;
 
163
        if (!*ary)
 
164
            continue;
 
165
        curentp = ary + oldsize;
 
166
        for (entp = ary, ent = *ary; ent; ent = *entp) {
 
167
            if ((newsize & PTABLE_HASH(ent->key)) != i) {
 
168
                *entp = ent->next;
 
169
                ent->next = *curentp;
 
170
                *curentp = ent;
 
171
                continue;
 
172
            } else {
 
173
                entp = &ent->next;
 
174
            }
 
175
        }
 
176
    }
 
177
}
 
178
 
 
179
/* remove all the entries from a ptr table */
 
180
 
 
181
STATIC void
 
182
PTABLE_clear(PTABLE_t *tbl)
 
183
{
 
184
    if (tbl && tbl->tbl_items) {
 
185
        register PTABLE_ENTRY_t * * const array = tbl->tbl_ary;
 
186
        UV riter = tbl->tbl_max;
 
187
 
 
188
        do {
 
189
            PTABLE_ENTRY_t *entry = array[riter];
 
190
 
 
191
            while (entry) {
 
192
                PTABLE_ENTRY_t * const oentry = entry;
 
193
                entry = entry->next;
 
194
                Safefree(oentry);
 
195
            }
 
196
 
 
197
            /* chocolateboy 2008-01-08
 
198
             *
 
199
             * make sure we clear the array entry, so that subsequent probes fail
 
200
             */
 
201
 
 
202
            array[riter] = NULL;
 
203
        } while (riter--);
 
204
 
 
205
        tbl->tbl_items = 0;
 
206
    }
 
207
}
 
208
 
 
209
/* remove one entry from a ptr table */
 
210
 
 
211
STATIC void
 
212
PTABLE_delete(PTABLE_t *tbl, void *key)
 
213
{
 
214
    PTABLE_ENTRY_t *tblent;
 
215
    PTABLE_ENTRY_t *tblent_prev;
 
216
 
 
217
    if (!tbl || !tbl->tbl_items) {
 
218
        return;
 
219
    } else {
 
220
        const UV hash = PTABLE_HASH(key);
 
221
        tblent_prev = NULL;
 
222
        tblent = tbl->tbl_ary[hash & tbl->tbl_max];
 
223
 
 
224
        for (; tblent; tblent_prev = tblent, tblent = tblent->next) {
 
225
            if (tblent->key == key) {
 
226
                if (tblent_prev != NULL) {
 
227
                    tblent_prev->next = tblent->next;
 
228
                }
 
229
                else {
 
230
                    /* First entry in chain */
 
231
                    tbl->tbl_ary[hash & tbl->tbl_max] = tblent->next;
 
232
                }
 
233
                Safefree(tblent);
 
234
                break;
 
235
            }
 
236
        }
 
237
    }
 
238
}
 
239
 
 
240
/* clear and free a ptr table */
 
241
 
 
242
STATIC void
 
243
PTABLE_free(PTABLE_t *tbl)
 
244
{
 
245
    if (!tbl) {
 
246
        return;
 
247
    }
 
248
    PTABLE_clear(tbl);
 
249
    Safefree(tbl->tbl_ary);
 
250
    Safefree(tbl);
 
251
}
 
252
 
 
253
 
 
254
#define PTABLE_ITER_NEXT_ELEM(iter, tbl)                                    \
 
255
    STMT_START {                                                            \
 
256
        if ((iter)->cur_entry && (iter)->cur_entry->next) {                 \
 
257
            (iter)->cur_entry = (iter)->cur_entry->next;                    \
 
258
        }                                                                   \
 
259
        else {                                                              \
 
260
            do {                                                            \
 
261
                if ((iter)->bucket_num > (tbl)->tbl_max) {                  \
 
262
                    (iter)->cur_entry = NULL;                               \
 
263
                    break;                                                  \
 
264
                }                                                           \
 
265
                (iter)->cur_entry = (tbl)->tbl_ary[(iter)->bucket_num++];   \
 
266
            } while ((iter)->cur_entry == NULL);                            \
 
267
        }                                                                   \
 
268
    } STMT_END
 
269
 
 
270
/* Create new iterator object */
 
271
STATIC PTABLE_ITER_t *
 
272
PTABLE_iter_new(PTABLE_t *tbl)
 
273
{
 
274
    PTABLE_ITER_t *iter;
 
275
    Newx(iter, 1, PTABLE_ITER_t);
 
276
    iter->table = tbl;
 
277
    iter->bucket_num = 0;
 
278
    iter->cur_entry = NULL;
 
279
    if (tbl->tbl_items == 0) {
 
280
        /* Prevent hash bucket scanning.
 
281
         * This can be a significant optimization on large, empty hashes. */
 
282
        iter->bucket_num = INT_MAX;
 
283
        return iter;
 
284
    }
 
285
    PTABLE_ITER_NEXT_ELEM(iter, tbl);
 
286
    assert(iter->cur_entry != NULL);
 
287
    return iter;
 
288
}
 
289
 
 
290
/* Return next item from hash, NULL if at end */
 
291
STATIC PTABLE_ENTRY_t *
 
292
PTABLE_iter_next(PTABLE_ITER_t *iter)
 
293
{
 
294
    PTABLE_ENTRY_t *retval = iter->cur_entry;
 
295
    PTABLE_t *tbl = iter->table;
 
296
    PTABLE_ITER_NEXT_ELEM(iter, tbl);
 
297
    return retval;
 
298
}
 
299
 
 
300
/* Free iterator object */
 
301
STATIC void
 
302
PTABLE_iter_free(PTABLE_ITER_t *iter)
 
303
{
 
304
    Safefree(iter);
 
305
}
 
306
 
 
307
 
 
308
#endif