Pillow

1
/*
2
 * The Python Imaging Library
3
 * $Id$
4
 *
5
 * hash tables used by the image quantizer
6
 *
7
 * history:
8
 * 98-09-10 tjs  Contributed
9
 * 98-12-29 fl   Added to PIL 1.0b1
10
 *
11
 * Written by Toby J Sargeant <tjs@longford.cs.monash.edu.au>.
12
 *
13
 * Copyright (c) 1998 by Toby J Sargeant
14
 * Copyright (c) 1998 by Secret Labs AB
15
 *
16
 * See the README file for information on usage and redistribution.
17
 */
18

19
#include <stdio.h>
20
#include <stdlib.h>
21
#include <string.h>
22
#include <math.h>
23

24
#include "QuantHash.h"
25

26
typedef struct _HashNode {
27
    struct _HashNode *next;
28
    HashKey_t key;
29
    HashVal_t value;
30
} HashNode;
31

32
struct _HashTable {
33
    HashNode **table;
34
    uint32_t length;
35
    uint32_t count;
36
    HashFunc hashFunc;
37
    HashCmpFunc cmpFunc;
38
    void *userData;
39
};
40

41
#define MIN_LENGTH 11
42
#define RESIZE_FACTOR 3
43

44
static int
45
_hashtable_insert_node(HashTable *, HashNode *, int, int, CollisionFunc);
46

47
HashTable *
48
hashtable_new(HashFunc hf, HashCmpFunc cf) {
49
    HashTable *h;
50
    h = malloc(sizeof(HashTable));
51
    if (!h) {
52
        return NULL;
53
    }
54
    h->hashFunc = hf;
55
    h->cmpFunc = cf;
56
    h->length = MIN_LENGTH;
57
    h->count = 0;
58
    h->userData = NULL;
59
    h->table = malloc(sizeof(HashNode *) * h->length);
60
    if (!h->table) {
61
        free(h);
62
        return NULL;
63
    }
64
    memset(h->table, 0, sizeof(HashNode *) * h->length);
65
    return h;
66
}
67

68
static uint32_t
69
_findPrime(uint32_t start, int dir) {
70
    static int unit[] = {0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0};
71
    uint32_t t;
72
    while (start > 1) {
73
        if (!unit[start & 0x0f]) {
74
            start += dir;
75
            continue;
76
        }
77
        for (t = 2; t < sqrt((double)start); t++) {
78
            if (!start % t) {
79
                break;
80
            }
81
        }
82
        if (t >= sqrt((double)start)) {
83
            break;
84
        }
85
        start += dir;
86
    }
87
    return start;
88
}
89

90
static void
91
_hashtable_rehash(HashTable *h, CollisionFunc cf, uint32_t newSize) {
92
    HashNode **oldTable = h->table;
93
    uint32_t i;
94
    HashNode *n, *nn;
95
    uint32_t oldSize;
96
    oldSize = h->length;
97
    h->table = malloc(sizeof(HashNode *) * newSize);
98
    if (!h->table) {
99
        h->table = oldTable;
100
        return;
101
    }
102
    h->length = newSize;
103
    h->count = 0;
104
    memset(h->table, 0, sizeof(HashNode *) * h->length);
105
    for (i = 0; i < oldSize; i++) {
106
        for (n = oldTable[i]; n; n = nn) {
107
            nn = n->next;
108
            _hashtable_insert_node(h, n, 0, 0, cf);
109
        }
110
    }
111
    free(oldTable);
112
}
113

114
static void
115
_hashtable_resize(HashTable *h) {
116
    uint32_t newSize;
117
    uint32_t oldSize;
118
    oldSize = h->length;
119
    newSize = oldSize;
120
    if (h->count * RESIZE_FACTOR < h->length) {
121
        newSize = _findPrime(h->length / 2 - 1, -1);
122
    } else if (h->length * RESIZE_FACTOR < h->count) {
123
        newSize = _findPrime(h->length * 2 + 1, +1);
124
    }
125
    if (newSize < MIN_LENGTH) {
126
        newSize = oldSize;
127
    }
128
    if (newSize != oldSize) {
129
        _hashtable_rehash(h, NULL, newSize);
130
    }
131
}
132

133
static int
134
_hashtable_insert_node(
135
    HashTable *h, HashNode *node, int resize, int update, CollisionFunc cf
136
) {
137
    uint32_t hash = h->hashFunc(h, node->key) % h->length;
138
    HashNode **n, *nv;
139
    int i;
140

141
    for (n = &(h->table[hash]); *n; n = &((*n)->next)) {
142
        nv = *n;
143
        i = h->cmpFunc(h, nv->key, node->key);
144
        if (!i) {
145
            if (cf) {
146
                nv->key = node->key;
147
                cf(h, &(nv->key), &(nv->value), node->key, node->value);
148
                free(node);
149
                return 1;
150
            } else {
151
                nv->key = node->key;
152
                nv->value = node->value;
153
                free(node);
154
                return 1;
155
            }
156
        } else if (i > 0) {
157
            break;
158
        }
159
    }
160
    if (!update) {
161
        node->next = *n;
162
        *n = node;
163
        h->count++;
164
        if (resize) {
165
            _hashtable_resize(h);
166
        }
167
        return 1;
168
    } else {
169
        return 0;
170
    }
171
}
172

173
static int
174
_hashtable_insert(HashTable *h, HashKey_t key, HashVal_t val, int resize, int update) {
175
    HashNode **n, *nv;
176
    HashNode *t;
177
    int i;
178
    uint32_t hash = h->hashFunc(h, key) % h->length;
179

180
    for (n = &(h->table[hash]); *n; n = &((*n)->next)) {
181
        nv = *n;
182
        i = h->cmpFunc(h, nv->key, key);
183
        if (!i) {
184
            nv->value = val;
185
            return 1;
186
        } else if (i > 0) {
187
            break;
188
        }
189
    }
190
    if (!update) {
191
        t = malloc(sizeof(HashNode));
192
        if (!t) {
193
            return 0;
194
        }
195
        t->next = *n;
196
        *n = t;
197
        t->key = key;
198
        t->value = val;
199
        h->count++;
200
        if (resize) {
201
            _hashtable_resize(h);
202
        }
203
        return 1;
204
    } else {
205
        return 0;
206
    }
207
}
208

209
int
210
hashtable_insert_or_update_computed(
211
    HashTable *h, HashKey_t key, ComputeFunc newFunc, ComputeFunc existsFunc
212
) {
213
    HashNode **n, *nv;
214
    HashNode *t;
215
    int i;
216
    uint32_t hash = h->hashFunc(h, key) % h->length;
217

218
    for (n = &(h->table[hash]); *n; n = &((*n)->next)) {
219
        nv = *n;
220
        i = h->cmpFunc(h, nv->key, key);
221
        if (!i) {
222
            if (existsFunc) {
223
                existsFunc(h, nv->key, &(nv->value));
224
            } else {
225
                return 0;
226
            }
227
            return 1;
228
        } else if (i > 0) {
229
            break;
230
        }
231
    }
232
    t = malloc(sizeof(HashNode));
233
    if (!t) {
234
        return 0;
235
    }
236
    t->key = key;
237
    t->next = *n;
238
    *n = t;
239
    if (newFunc) {
240
        newFunc(h, t->key, &(t->value));
241
    } else {
242
        free(t);
243
        return 0;
244
    }
245
    h->count++;
246
    _hashtable_resize(h);
247
    return 1;
248
}
249

250
int
251
hashtable_insert(HashTable *h, HashKey_t key, HashVal_t val) {
252
    return _hashtable_insert(h, key, val, 1, 0);
253
}
254

255
void
256
hashtable_foreach_update(HashTable *h, IteratorUpdateFunc i, void *u) {
257
    HashNode *n;
258
    uint32_t x;
259

260
    if (h->table) {
261
        for (x = 0; x < h->length; x++) {
262
            for (n = h->table[x]; n; n = n->next) {
263
                i(h, n->key, &(n->value), u);
264
            }
265
        }
266
    }
267
}
268

269
void
270
hashtable_foreach(HashTable *h, IteratorFunc i, void *u) {
271
    HashNode *n;
272
    uint32_t x;
273

274
    if (h->table) {
275
        for (x = 0; x < h->length; x++) {
276
            for (n = h->table[x]; n; n = n->next) {
277
                i(h, n->key, n->value, u);
278
            }
279
        }
280
    }
281
}
282

283
void
284
hashtable_free(HashTable *h) {
285
    HashNode *n, *nn;
286
    uint32_t i;
287

288
    if (h->table) {
289
        for (i = 0; i < h->length; i++) {
290
            for (n = h->table[i]; n; n = nn) {
291
                nn = n->next;
292
                free(n);
293
            }
294
        }
295
        free(h->table);
296
    }
297
    free(h);
298
}
299

300
void
301
hashtable_rehash_compute(HashTable *h, CollisionFunc cf) {
302
    _hashtable_rehash(h, cf, h->length);
303
}
304

305
int
306
hashtable_lookup(const HashTable *h, const HashKey_t key, HashVal_t *valp) {
307
    uint32_t hash = h->hashFunc(h, key) % h->length;
308
    HashNode *n;
309
    int i;
310

311
    for (n = h->table[hash]; n; n = n->next) {
312
        i = h->cmpFunc(h, n->key, key);
313
        if (!i) {
314
            *valp = n->value;
315
            return 1;
316
        } else if (i > 0) {
317
            break;
318
        }
319
    }
320
    return 0;
321
}
322

323
uint32_t
324
hashtable_get_count(const HashTable *h) {
325
    return h->count;
326
}
327

328
void *
329
hashtable_get_user_data(const HashTable *h) {
330
    return h->userData;
331
}
332

333
void *
334
hashtable_set_user_data(HashTable *h, void *data) {
335
    void *r = h->userData;
336
    h->userData = data;
337
    return r;
338
}
339