← Back to branch summary

~ubuntu-branches/debian/experimental/upstart/experimental

« back to all changes in this revision

Viewing changes to nih/tests/test_hash.c

  • Committer: Bazaar Package Importer
  • Author(s): Michael Biebl
  • Date: 2007-10-22 07:09:12 UTC
  • mfrom: (1.2.1 upstream) (16.1.9 feisty)
  • Revision ID: james.westby@ubuntu.com-20071022070912-4cybewh6m1vwk09p
Tags: 0.3.9-1
http://bugs.debian.org/426598
http://bugs.debian.org/410836
* New upstream release.
* debian/watch
  - Find the latest tarball by parsing the download.html page.
* debian/upstart-compat-sysv.preinst
  - Do not parse /var/lib/dpkg/status directly but use dpkg-query instead.
* debian/control
  - Use the new "Homepage:" field to specify the upstream URL.
  - Drop versioned Build-Depends on dpkg-dev as the version in etch is
    recent enough.
  - Use quilt instead of dpatch for the patch management. Update the
    Build-Depends accordingly.
* debian/rules
  - Do not ignore "make clean" errors.
  - Include quilt.make which provides the patch and unpatch target.
* debian/README.Debian
  - Update the FAQ with regard to boot message logging. Closes: #426598
  - Add some notes that initramfs generators other than initramfs-tools can
    cause problems. Closes: #410836

Show diffs side-by-side

added added

removed removed

Lines of Context:
nih/tests/test_hash.c
2
2
 *
3
3
 * test_hash.c - test suite for nih/hash.c
4
4
 *
5
 
 * Copyright © 2006 Scott James Remnant <scott@netsplit.com>.
 
5
 * Copyright © 2007 Scott James Remnant <scott@netsplit.com>.
6
6
 *
7
7
 * This program is free software; you can redistribute it and/or modify
8
8
 * it under the terms of the GNU General Public License as published by
19
19
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
20
20
 */
21
21
 
22
 
#ifdef HAVE_CONFIG_H
23
 
# include <config.h>
24
 
#endif /* HAVE_CONFIG_H */
25
 
 
26
 
 
27
 
#include <stdio.h>
28
 
#include <assert.h>
29
 
 
 
22
#include <nih/test.h>
 
23
 
 
24
#include <nih/macros.h>
30
25
#include <nih/alloc.h>
31
26
#include <nih/list.h>
32
27
#include <nih/hash.h>
43
38
{
44
39
        HashEntry *entry;
45
40
 
46
 
        assert (key != NULL);
47
 
 
48
41
        entry = nih_new (parent, HashEntry);
49
 
        assert (entry != NULL);
50
42
 
51
43
        nih_list_init (&entry->list);
52
44
        entry->key = key;
57
49
static const char *
58
50
key_function (NihList *entry)
59
51
{
60
 
        assert (entry != NULL);
61
 
 
62
52
        return ((HashEntry *)entry)->key;
63
53
}
64
54
 
65
55
 
66
 
int
 
56
void
67
57
test_new (void)
68
58
{
69
59
        NihHash *hash;
70
60
        size_t   i;
71
 
        int      ret = 0;
72
 
 
73
 
        printf ("Testing nih_hash_new()\n");
74
 
 
75
 
        printf ("...with zero size\n");
76
 
        hash = nih_hash_new (0, key_function);
77
 
 
78
 
        /* Size should be smallest prime number */
79
 
        if (hash->size != 17) {
80
 
                printf ("BAD: size set incorrectly.\n");
81
 
                ret = 1;
82
 
        }
83
 
 
84
 
        /* Bins should be non-NULL */
85
 
        if (hash->bins == NULL) {
86
 
                printf ("BAD: bins not allocated.\n");
87
 
                ret = 1;
88
 
        }
89
 
 
90
 
        /* Bins should be a child of the hash table */
91
 
        if (nih_alloc_parent (hash->bins) != hash) {
92
 
                printf ("BAD: bins not child allocation of hash.\n");
93
 
                ret = 1;
94
 
        }
95
 
 
96
 
        /* All bins should be empty */
97
 
        for (i = 0; i < hash->size; i++) {
98
 
                if (! NIH_LIST_EMPTY (&hash->bins[i])) {
99
 
                        printf ("BAD: bin not initialised.\n");
100
 
                        ret = 1;
101
 
                }
102
 
        }
103
 
 
104
 
        /* Key function should be what we gave */
105
 
        if (hash->key_function != key_function) {
106
 
                printf ("BAD: key_function set incorrectly.\n");
107
 
                ret = 1;
108
 
        }
109
 
 
110
 
        nih_free (hash);
111
 
 
112
 
 
113
 
        printf ("...with medium size\n");
114
 
        hash = nih_hash_new (650, key_function);
115
 
 
116
 
        /* Size should be closest prime number */
117
 
        if (hash->size != 331) {
118
 
                printf ("BAD: size set incorrectly.\n");
119
 
                ret = 1;
120
 
        }
121
 
 
122
 
        /* Bins should be non-NULL */
123
 
        if (hash->bins == NULL) {
124
 
                printf ("BAD: bins not allocated.\n");
125
 
                ret = 1;
126
 
        }
127
 
 
128
 
        /* Bins should be a child of the hash table */
129
 
        if (nih_alloc_parent (hash->bins) != hash) {
130
 
                printf ("BAD: bins not child allocation of hash.\n");
131
 
                ret = 1;
132
 
        }
133
 
 
134
 
        /* All bins should be empty */
135
 
        for (i = 0; i < hash->size; i++) {
136
 
                if (! NIH_LIST_EMPTY (&hash->bins[i])) {
137
 
                        printf ("BAD: bin not initialised.\n");
138
 
                        ret = 1;
139
 
                }
140
 
        }
141
 
 
142
 
        /* Key function should be what we gave */
143
 
        if (hash->key_function != key_function) {
144
 
                printf ("BAD: key_function set incorrectly.\n");
145
 
                ret = 1;
146
 
        }
147
 
 
148
 
        nih_free (hash);
149
 
 
150
 
 
151
 
        printf ("...with large size\n");
152
 
        hash = nih_hash_new (40000000, key_function);
153
 
 
154
 
        /* Size should be largest prime number */
155
 
        if (hash->size != 10250323) {
156
 
                printf ("BAD: size set incorrectly.\n");
157
 
                ret = 1;
158
 
        }
159
 
 
160
 
        /* Bins should be non-NULL */
161
 
        if (hash->bins == NULL) {
162
 
                printf ("BAD: bins not allocated.\n");
163
 
                ret = 1;
164
 
        }
165
 
 
166
 
        /* Bins should be a child of the hash table */
167
 
        if (nih_alloc_parent (hash->bins) != hash) {
168
 
                printf ("BAD: bins not child allocation of hash.\n");
169
 
                ret = 1;
170
 
        }
171
 
 
172
 
        /* All bins should be empty */
173
 
        for (i = 0; i < hash->size; i++) {
174
 
                if (! NIH_LIST_EMPTY (&hash->bins[i])) {
175
 
                        printf ("BAD: bin not initialised.\n");
176
 
                        ret = 1;
177
 
                }
178
 
        }
179
 
 
180
 
        /* Key function should be what we gave */
181
 
        if (hash->key_function != key_function) {
182
 
                printf ("BAD: key_function set incorrectly.\n");
183
 
                ret = 1;
184
 
        }
185
 
 
186
 
        nih_free (hash);
187
 
 
188
 
        return ret;
 
61
 
 
62
        TEST_FUNCTION ("nih_hash_new");
 
63
 
 
64
        /* Check that we can create a small hash table; a small prime number
 
65
         * should be selected for the actual size, and that number of empty
 
66
         * bins should be allocated as a child of the hash table.
 
67
         */
 
68
        TEST_FEATURE ("with zero size");
 
69
        TEST_ALLOC_FAIL {
 
70
                hash = nih_hash_new (NULL, 0, key_function);
 
71
 
 
72
                if (test_alloc_failed) {
 
73
                        TEST_EQ_P (hash, NULL);
 
74
                        continue;
 
75
                }
 
76
 
 
77
                TEST_ALLOC_SIZE (hash, sizeof(NihHash));
 
78
                TEST_EQ_P (hash->key_function, key_function);
 
79
 
 
80
                TEST_EQ (hash->size, 17);
 
81
                TEST_NE_P (hash->bins, NULL);
 
82
                TEST_ALLOC_PARENT (hash->bins, hash);
 
83
 
 
84
                for (i = 0; i < hash->size; i++)
 
85
                        TEST_LIST_EMPTY (&hash->bins[i]);
 
86
 
 
87
                nih_free (hash);
 
88
        }
 
89
 
 
90
 
 
91
        /* Check again with a medium size, which should pick a medium prime
 
92
         * number.
 
93
         */
 
94
        TEST_FEATURE ("with medium size");
 
95
        TEST_ALLOC_FAIL {
 
96
                hash = nih_hash_new (NULL, 650, key_function);
 
97
 
 
98
                if (test_alloc_failed) {
 
99
                        TEST_EQ_P (hash, NULL);
 
100
                        continue;
 
101
                }
 
102
 
 
103
                TEST_EQ (hash->size, 331);
 
104
                TEST_NE_P (hash->bins, NULL);
 
105
                TEST_ALLOC_PARENT (hash->bins, hash);
 
106
 
 
107
                for (i = 0; i < hash->size; i++)
 
108
                        TEST_LIST_EMPTY (&hash->bins[i]);
 
109
 
 
110
                nih_free (hash);
 
111
        }
 
112
 
 
113
 
 
114
        /* Check with a much larger size, which should pick the largest prime
 
115
         * that we know of.
 
116
         */
 
117
        TEST_FEATURE ("with large size");
 
118
        TEST_ALLOC_FAIL {
 
119
                hash = nih_hash_new (NULL, 40000000, key_function);
 
120
 
 
121
                if (test_alloc_failed) {
 
122
                        TEST_EQ_P (hash, NULL);
 
123
                        continue;
 
124
                }
 
125
 
 
126
                TEST_EQ (hash->size, 10250323);
 
127
                TEST_NE_P (hash->bins, NULL);
 
128
                TEST_ALLOC_PARENT (hash->bins, hash);
 
129
 
 
130
                for (i = 0; i < hash->size; i++)
 
131
                        TEST_LIST_EMPTY (&hash->bins[i]);
 
132
 
 
133
                nih_free (hash);
 
134
        }
189
135
}
190
136
 
191
 
 
192
 
int
 
137
void
193
138
test_add (void)
194
139
{
195
140
        NihHash *hash;
196
141
        NihList *entry1, *entry2, *entry3, *entry4, *ptr;
197
 
        int      ret = 0;
198
142
 
199
 
        printf ("Testing nih_hash_add()\n");
200
 
        hash = nih_hash_new (0, key_function);
 
143
        TEST_FUNCTION ("nih_hash_add");
 
144
        hash = nih_hash_new (NULL, 0, key_function);
201
145
        entry1 = new_entry (hash, "entry 1");
202
146
        entry2 = new_entry (hash, "entry 2");
203
147
        entry3 = new_entry (hash, "entry 1");
204
148
        entry4 = new_entry (hash, "entry 4");
205
149
 
206
 
        printf ("...with empty hash\n");
 
150
        /* Check that we can add an entry to an empty hash table; it should
 
151
         * be returned and turn up in the appropriate bin.
 
152
         */
 
153
        TEST_FEATURE ("with empty hash");
207
154
        ptr = nih_hash_add (hash, entry1);
208
155
 
209
 
        /* The added entry should be returned */
210
 
        if (ptr != entry1) {
211
 
                printf ("BAD: return value wasn't what we expected.\n");
212
 
                ret = 1;
213
 
        }
214
 
 
215
 
        /* 15th hash bin head's next pointer should be the entry */
216
 
        if (hash->bins[15].next != entry1) {
217
 
                printf ("BAD: head next pointer set incorrectly.\n");
218
 
                ret = 1;
219
 
        }
220
 
 
221
 
        /* 15th hash bin head's previous pointer should be the entry */
222
 
        if (hash->bins[15].prev != entry1) {
223
 
                printf ("BAD: previous next pointer set incorrectly.\n");
224
 
                ret = 1;
225
 
        }
226
 
 
227
 
        /* Entry's next pointer should be the 15th hash bin */
228
 
        if (entry1->next != &hash->bins[15]) {
229
 
                printf ("BAD: entry next pointer set incorrectly.\n");
230
 
                ret = 1;
231
 
        }
232
 
 
233
 
        /* Entry's previous pointer should be the 15th hash bin */
234
 
        if (entry1->prev != &hash->bins[15]) {
235
 
                printf ("BAD: entry next pointer set incorrectly.\n");
236
 
                ret = 1;
237
 
        }
238
 
 
239
 
 
240
 
        printf ("...with non-empty hash\n");
 
156
        TEST_EQ_P (ptr, entry1);
 
157
 
 
158
        TEST_EQ_P (hash->bins[15].next, entry1);
 
159
        TEST_EQ_P (entry1->next, &hash->bins[15]);
 
160
        TEST_EQ_P (hash->bins[15].prev, entry1);
 
161
        TEST_EQ_P (entry1->prev, &hash->bins[15]);
 
162
 
 
163
 
 
164
        /* Check that we can add an entry to a populated hash table. */
 
165
        TEST_FEATURE ("with non-empty hash");
241
166
        nih_hash_add (hash, entry2);
242
167
 
243
 
        /* 14th hash bin head's next pointer should be the entry */
244
 
        if (hash->bins[14].next != entry2) {
245
 
                printf ("BAD: head next pointer set incorrectly.\n");
246
 
                ret = 1;
247
 
        }
248
 
 
249
 
        /* 14th hash bin head's previous pointer should be the entry */
250
 
        if (hash->bins[14].prev != entry2) {
251
 
                printf ("BAD: head previous pointer set incorrectly.\n");
252
 
                ret = 1;
253
 
        }
254
 
 
255
 
        /* Entry's next pointer should be the 14th hash bin */
256
 
        if (entry2->next != &hash->bins[14]) {
257
 
                printf ("BAD: entry next pointer set incorrectly.\n");
258
 
                ret = 1;
259
 
        }
260
 
 
261
 
        /* Entry's previous pointer should be the 14th hash bin */
262
 
        if (entry2->prev != &hash->bins[14]) {
263
 
                printf ("BAD: entry next pointer set incorrectly.\n");
264
 
                ret = 1;
265
 
        }
266
 
 
267
 
 
268
 
        printf ("...with duplicate key\n");
 
168
        TEST_EQ_P (hash->bins[14].next, entry2);
 
169
        TEST_EQ_P (entry2->next, &hash->bins[14]);
 
170
        TEST_EQ_P (hash->bins[14].prev, entry2);
 
171
        TEST_EQ_P (entry2->prev, &hash->bins[14]);
 
172
 
 
173
 
 
174
        /* Check that we can add an entry with a duplicate key, and it is
 
175
         * added to the end of the same bin as the previous entry with that
 
176
         * key.
 
177
         */
 
178
        TEST_FEATURE ("with duplicate key");
269
179
        nih_hash_add (hash, entry3);
270
180
 
271
 
        /* First entry's next pointer should be the new entry */
272
 
        if (entry1->next != entry3) {
273
 
                printf ("BAD: first entry next pointer set incorrectly.\n");
274
 
                ret = 1;
275
 
        }
276
 
 
277
 
        /* First entry's previous pointer should still be the head */
278
 
        if (entry1->prev != &hash->bins[15]) {
279
 
                printf ("BAD: first entry previous pointer changed.\n");
280
 
                ret = 1;
281
 
        }
282
 
 
283
 
        /* New entry's previous pointer should be the first entry */
284
 
        if (entry3->prev != entry1) {
285
 
                printf ("BAD: entry previous pointer set incorrectly.\n");
286
 
                ret = 1;
287
 
        }
288
 
 
289
 
        /* New entry's next pointer should be the head */
290
 
        if (entry3->next != &hash->bins[15]) {
291
 
                printf ("BAD: entry next pointer set incorrectly.\n");
292
 
                ret = 1;
293
 
        }
294
 
 
295
 
        /* Head's previous pointer should be the new entry */
296
 
        if (hash->bins[15].prev != entry3) {
297
 
                printf ("BAD: head previous pointer set incorrectly.\n");
298
 
                ret = 1;
299
 
        }
300
 
 
301
 
        /* Head's next pointer should still be the first entry */
302
 
        if (hash->bins[15].next != entry1) {
303
 
                printf ("BAD: head next pointer changed.\n");
304
 
                ret = 1;
305
 
        }
306
 
 
307
 
 
308
 
        printf ("...with entry already in a list\n");
309
 
        ptr = nih_list_new ();
 
181
        TEST_EQ_P (hash->bins[15].next, entry1);
 
182
        TEST_EQ_P (entry1->next, entry3);
 
183
        TEST_EQ_P (entry3->next, &hash->bins[15]);
 
184
        TEST_EQ_P (hash->bins[15].prev, entry3);
 
185
        TEST_EQ_P (entry3->prev, entry1);
 
186
        TEST_EQ_P (entry1->prev, &hash->bins[15]);
 
187
 
 
188
 
 
189
        /* Check that nih_hash_add can rip an entry out of an existing list
 
190
         * and place it in the hash table.
 
191
         */
 
192
        TEST_FEATURE ("with entry already in a list");
 
193
        ptr = nih_list_new (NULL);
310
194
        nih_list_add (ptr, entry4);
311
195
        nih_hash_add (hash, entry4);
312
196
 
313
 
        /* List's previous pointer should point back to itself */
314
 
        if (ptr->prev != ptr) {
315
 
                printf ("BAD: list previous pointer set incorrectly.\n");
316
 
                ret = 1;
317
 
        }
318
 
 
319
 
        /* List's next pointer should point back to itself */
320
 
        if (ptr->next != ptr) {
321
 
                printf ("BAD: list next pointer set incorrectly.\n");
322
 
                ret = 1;
323
 
        }
324
 
 
325
 
        /* 3rd hash bin head's next pointer should be the entry */
326
 
        if (hash->bins[3].next != entry4) {
327
 
                printf ("BAD: head next pointer set incorrectly.\n");
328
 
                ret = 1;
329
 
        }
330
 
 
331
 
        /* 3rd hash bin head's previous pointer should be the entry */
332
 
        if (hash->bins[3].prev != entry4) {
333
 
                printf ("BAD: previous next pointer set incorrectly.\n");
334
 
                ret = 1;
335
 
        }
336
 
 
337
 
        /* Entry's next pointer should be the 3rd hash bin */
338
 
        if (entry4->next != &hash->bins[3]) {
339
 
                printf ("BAD: entry next pointer set incorrectly.\n");
340
 
                ret = 1;
341
 
        }
342
 
 
343
 
        /* Entry's previous pointer should be the 3rd hash bin */
344
 
        if (entry4->prev != &hash->bins[3]) {
345
 
                printf ("BAD: entry next pointer set incorrectly.\n");
346
 
                ret = 1;
347
 
        }
 
197
        TEST_EQ_P (ptr->next, ptr);
 
198
        TEST_EQ_P (ptr->prev, ptr);
 
199
 
 
200
        TEST_EQ_P (hash->bins[3].next, entry4);
 
201
        TEST_EQ_P (entry4->next, &hash->bins[3]);
 
202
        TEST_EQ_P (hash->bins[3].prev, entry4);
 
203
        TEST_EQ_P (entry4->prev, &hash->bins[3]);
348
204
 
349
205
        nih_free (hash);
350
206
        nih_free (ptr);
351
 
 
352
 
        return ret;
353
207
}
354
208
 
355
 
int
 
209
void
356
210
test_add_unique (void)
357
211
{
358
212
        NihHash *hash;
359
213
        NihList *entry1, *entry2, *entry3, *entry4, *ptr;
360
 
        int      ret = 0;
361
214
 
362
 
        printf ("Testing nih_hash_add_unique()\n");
363
 
        hash = nih_hash_new (0, key_function);
 
215
        TEST_FUNCTION ("nih_hash_add_unique");
 
216
        hash = nih_hash_new (NULL, 0, key_function);
364
217
        entry1 = new_entry (hash, "entry 1");
365
218
        entry2 = new_entry (hash, "entry 2");
366
219
        entry3 = new_entry (hash, "entry 1");
367
220
        entry4 = new_entry (hash, "entry 4");
368
221
 
369
 
        printf ("...with empty hash\n");
 
222
        /* Check that we can add an entry to an empty hash table; it should
 
223
         * be returned and turn up in the appropriate bin.
 
224
         */
 
225
        TEST_FEATURE ("with empty hash");
370
226
        ptr = nih_hash_add_unique (hash, entry1);
371
227
 
372
 
        /* The added entry should be returned */
373
 
        if (ptr != entry1) {
374
 
                printf ("BAD: return value wasn't what we expected.\n");
375
 
                ret = 1;
376
 
        }
377
 
 
378
 
        /* 15th hash bin head's next pointer should be the entry */
379
 
        if (hash->bins[15].next != entry1) {
380
 
                printf ("BAD: head next pointer set incorrectly.\n");
381
 
                ret = 1;
382
 
        }
383
 
 
384
 
        /* 15th hash bin head's previous pointer should be the entry */
385
 
        if (hash->bins[15].prev != entry1) {
386
 
                printf ("BAD: previous next pointer set incorrectly.\n");
387
 
                ret = 1;
388
 
        }
389
 
 
390
 
        /* Entry's next pointer should be the 15th hash bin */
391
 
        if (entry1->next != &hash->bins[15]) {
392
 
                printf ("BAD: entry next pointer set incorrectly.\n");
393
 
                ret = 1;
394
 
        }
395
 
 
396
 
        /* Entry's previous pointer should be the 15th hash bin */
397
 
        if (entry1->prev != &hash->bins[15]) {
398
 
                printf ("BAD: entry next pointer set incorrectly.\n");
399
 
                ret = 1;
400
 
        }
401
 
 
402
 
 
403
 
        printf ("...with non-empty hash\n");
 
228
        TEST_EQ_P (ptr, entry1);
 
229
 
 
230
        TEST_EQ_P (hash->bins[15].next, entry1);
 
231
        TEST_EQ_P (entry1->next, &hash->bins[15]);
 
232
        TEST_EQ_P (hash->bins[15].prev, entry1);
 
233
        TEST_EQ_P (entry1->prev, &hash->bins[15]);
 
234
 
 
235
 
 
236
        /* Check that we can add an entry to a populated hash table. */
 
237
        TEST_FEATURE ("with non-empty hash");
404
238
        nih_hash_add_unique (hash, entry2);
405
239
 
406
 
        /* 14th hash bin head's next pointer should be the entry */
407
 
        if (hash->bins[14].next != entry2) {
408
 
                printf ("BAD: head next pointer set incorrectly.\n");
409
 
                ret = 1;
410
 
        }
411
 
 
412
 
        /* 14th hash bin head's previous pointer should be the entry */
413
 
        if (hash->bins[14].prev != entry2) {
414
 
                printf ("BAD: head previous pointer set incorrectly.\n");
415
 
                ret = 1;
416
 
        }
417
 
 
418
 
        /* Entry's next pointer should be the 14th hash bin */
419
 
        if (entry2->next != &hash->bins[14]) {
420
 
                printf ("BAD: entry next pointer set incorrectly.\n");
421
 
                ret = 1;
422
 
        }
423
 
 
424
 
        /* Entry's previous pointer should be the 14th hash bin */
425
 
        if (entry2->prev != &hash->bins[14]) {
426
 
                printf ("BAD: entry next pointer set incorrectly.\n");
427
 
                ret = 1;
428
 
        }
429
 
 
430
 
 
431
 
        printf ("...with duplicate key\n");
 
240
        TEST_EQ_P (hash->bins[14].next, entry2);
 
241
        TEST_EQ_P (entry2->next, &hash->bins[14]);
 
242
        TEST_EQ_P (hash->bins[14].prev, entry2);
 
243
        TEST_EQ_P (entry2->prev, &hash->bins[14]);
 
244
 
 
245
 
 
246
        /* Check that we get NULL if we try and add an entry with a
 
247
         * duplicate key, and that the hash table is not altered.
 
248
         */
 
249
        TEST_FEATURE ("with duplicate key");
432
250
        ptr = nih_hash_add_unique (hash, entry3);
433
251
 
434
 
        /* Should have returned NULL */
435
 
        if (ptr != NULL) {
436
 
                printf ("BAD: return value not correct.\n");
437
 
                ret = 1;
438
 
        }
439
 
 
440
 
        /* First entry's next pointer should still be the head */
441
 
        if (entry1->next != &hash->bins[15]) {
442
 
                printf ("BAD: first entry next pointer changed.\n");
443
 
                ret = 1;
444
 
        }
445
 
 
446
 
        /* First entry's previous pointer should still be the head */
447
 
        if (entry1->prev != &hash->bins[15]) {
448
 
                printf ("BAD: first entry previous pointer changed.\n");
449
 
                ret = 1;
450
 
        }
451
 
 
452
 
        /* Head's previous pointer should still be the first entry */
453
 
        if (hash->bins[15].prev != entry1) {
454
 
                printf ("BAD: head previous pointer changed.\n");
455
 
                ret = 1;
456
 
        }
457
 
 
458
 
        /* Head's next pointer should still be the first entry */
459
 
        if (hash->bins[15].next != entry1) {
460
 
                printf ("BAD: head next pointer changed.\n");
461
 
                ret = 1;
462
 
        }
463
 
 
464
 
        /* New entry's previous pointer should still be itself */
465
 
        if (entry3->prev != entry3) {
466
 
                printf ("BAD: entry previous pointer changed.\n");
467
 
                ret = 1;
468
 
        }
469
 
 
470
 
        /* New entry's next pointer should be the head */
471
 
        if (entry3->next != entry3) {
472
 
                printf ("BAD: entry next pointer changed.\n");
473
 
                ret = 1;
474
 
        }
475
 
 
476
 
 
477
 
        printf ("...with entry already in a list\n");
478
 
        ptr = nih_list_new ();
 
252
        TEST_EQ_P (ptr, NULL);
 
253
 
 
254
        TEST_EQ_P (hash->bins[15].next, entry1);
 
255
        TEST_EQ_P (entry1->next, &hash->bins[15]);
 
256
        TEST_EQ_P (hash->bins[15].prev, entry1);
 
257
        TEST_EQ_P (entry1->prev, &hash->bins[15]);
 
258
 
 
259
 
 
260
        /* Check that nih_hash_add can rip an entry out of an existing list
 
261
         * and place it in the hash table.
 
262
         */
 
263
        TEST_FEATURE ("with entry already in a list");
 
264
        ptr = nih_list_new (NULL);
479
265
        nih_list_add (ptr, entry4);
480
266
        nih_hash_add_unique (hash, entry4);
481
267
 
482
 
        /* List's previous pointer should point back to itself */
483
 
        if (ptr->prev != ptr) {
484
 
                printf ("BAD: list previous pointer set incorrectly.\n");
485
 
                ret = 1;
486
 
        }
487
 
 
488
 
        /* List's next pointer should point back to itself */
489
 
        if (ptr->next != ptr) {
490
 
                printf ("BAD: list next pointer set incorrectly.\n");
491
 
                ret = 1;
492
 
        }
493
 
 
494
 
        /* 3rd hash bin head's next pointer should be the entry */
495
 
        if (hash->bins[3].next != entry4) {
496
 
                printf ("BAD: head next pointer set incorrectly.\n");
497
 
                ret = 1;
498
 
        }
499
 
 
500
 
        /* 3rd hash bin head's previous pointer should be the entry */
501
 
        if (hash->bins[3].prev != entry4) {
502
 
                printf ("BAD: previous next pointer set incorrectly.\n");
503
 
                ret = 1;
504
 
        }
505
 
 
506
 
        /* Entry's next pointer should be the 3rd hash bin */
507
 
        if (entry4->next != &hash->bins[3]) {
508
 
                printf ("BAD: entry next pointer set incorrectly.\n");
509
 
                ret = 1;
510
 
        }
511
 
 
512
 
        /* Entry's previous pointer should be the 3rd hash bin */
513
 
        if (entry4->prev != &hash->bins[3]) {
514
 
                printf ("BAD: entry next pointer set incorrectly.\n");
515
 
                ret = 1;
516
 
        }
 
268
        TEST_EQ_P (ptr->next, ptr);
 
269
        TEST_EQ_P (ptr->prev, ptr);
 
270
 
 
271
        TEST_EQ_P (hash->bins[3].next, entry4);
 
272
        TEST_EQ_P (entry4->next, &hash->bins[3]);
 
273
        TEST_EQ_P (hash->bins[3].prev, entry4);
 
274
        TEST_EQ_P (entry4->prev, &hash->bins[3]);
517
275
 
518
276
        nih_free (hash);
519
277
        nih_free (ptr);
520
 
 
521
 
        return ret;
522
278
}
523
279
 
524
 
int
 
280
void
525
281
test_replace (void)
526
282
{
527
283
        NihHash *hash;
528
284
        NihList *entry1, *entry2, *entry3, *entry4, *ptr;
529
 
        int      ret = 0;
530
285
 
531
 
        printf ("Testing nih_hash_replace()\n");
532
 
        hash = nih_hash_new (0, key_function);
 
286
        TEST_FUNCTION ("nih_hash_replace");
 
287
        hash = nih_hash_new (NULL, 0, key_function);
533
288
        entry1 = new_entry (hash, "entry 1");
534
289
        entry2 = new_entry (hash, "entry 2");
535
290
        entry3 = new_entry (hash, "entry 1");
536
291
        entry4 = new_entry (hash, "entry 4");
537
292
 
538
 
        printf ("...with empty hash\n");
 
293
        /* Check that we can add an entry to an empty hash table; NULL should
 
294
         * be returned (nothing replaced) and the entry should turn up in the
 
295
         * appropriate bin.
 
296
         */
 
297
        TEST_FEATURE ("with empty hash");
539
298
        ptr = nih_hash_replace (hash, entry1);
540
299
 
541
 
        /* NULL should be returned */
542
 
        if (ptr != NULL) {
543
 
                printf ("BAD: return value wasn't what we expected.\n");
544
 
                ret = 1;
545
 
        }
546
 
 
547
 
        /* 15th hash bin head's next pointer should be the entry */
548
 
        if (hash->bins[15].next != entry1) {
549
 
                printf ("BAD: head next pointer set incorrectly.\n");
550
 
                ret = 1;
551
 
        }
552
 
 
553
 
        /* 15th hash bin head's previous pointer should be the entry */
554
 
        if (hash->bins[15].prev != entry1) {
555
 
                printf ("BAD: previous next pointer set incorrectly.\n");
556
 
                ret = 1;
557
 
        }
558
 
 
559
 
        /* Entry's next pointer should be the 15th hash bin */
560
 
        if (entry1->next != &hash->bins[15]) {
561
 
                printf ("BAD: entry next pointer set incorrectly.\n");
562
 
                ret = 1;
563
 
        }
564
 
 
565
 
        /* Entry's previous pointer should be the 15th hash bin */
566
 
        if (entry1->prev != &hash->bins[15]) {
567
 
                printf ("BAD: entry next pointer set incorrectly.\n");
568
 
                ret = 1;
569
 
        }
570
 
 
571
 
 
572
 
        printf ("...with non-empty hash\n");
 
300
        TEST_EQ_P (ptr, NULL);
 
301
 
 
302
        TEST_EQ_P (hash->bins[15].next, entry1);
 
303
        TEST_EQ_P (entry1->next, &hash->bins[15]);
 
304
        TEST_EQ_P (hash->bins[15].prev, entry1);
 
305
        TEST_EQ_P (entry1->prev, &hash->bins[15]);
 
306
 
 
307
 
 
308
        /* Check that we can add an entry to a populated hash table. */
 
309
        TEST_FEATURE ("with non-empty hash");
573
310
        nih_hash_replace (hash, entry2);
574
311
 
575
 
        /* 14th hash bin head's next pointer should be the entry */
576
 
        if (hash->bins[14].next != entry2) {
577
 
                printf ("BAD: head next pointer set incorrectly.\n");
578
 
                ret = 1;
579
 
        }
580
 
 
581
 
        /* 14th hash bin head's previous pointer should be the entry */
582
 
        if (hash->bins[14].prev != entry2) {
583
 
                printf ("BAD: head previous pointer set incorrectly.\n");
584
 
                ret = 1;
585
 
        }
586
 
 
587
 
        /* Entry's next pointer should be the 14th hash bin */
588
 
        if (entry2->next != &hash->bins[14]) {
589
 
                printf ("BAD: entry next pointer set incorrectly.\n");
590
 
                ret = 1;
591
 
        }
592
 
 
593
 
        /* Entry's previous pointer should be the 14th hash bin */
594
 
        if (entry2->prev != &hash->bins[14]) {
595
 
                printf ("BAD: entry next pointer set incorrectly.\n");
596
 
                ret = 1;
597
 
        }
598
 
 
599
 
 
600
 
        printf ("...with duplicate key\n");
 
312
        TEST_EQ_P (hash->bins[14].next, entry2);
 
313
        TEST_EQ_P (entry2->next, &hash->bins[14]);
 
314
        TEST_EQ_P (hash->bins[14].prev, entry2);
 
315
        TEST_EQ_P (entry2->prev, &hash->bins[14]);
 
316
 
 
317
 
 
318
        /* Check that we can add an entry with a duplicate key, replacing
 
319
         * the existing one in the hash.  The replaced entry should be
 
320
         * returned, and removed from the bin.
 
321
         */
 
322
        TEST_FEATURE ("with duplicate key");
601
323
        ptr = nih_hash_replace (hash, entry3);
602
324
 
603
 
        /* The replaced entry should be returned */
604
 
        if (ptr != entry1) {
605
 
                printf ("BAD: return value not correct.\n");
606
 
                ret = 1;
607
 
        }
608
 
 
609
 
        /* Replaced entry's next pointer should point back to itself */
610
 
        if (entry1->next != entry1) {
611
 
                printf ("BAD: replaced entry next pointer set incorrectly.\n");
612
 
                ret = 1;
613
 
        }
614
 
 
615
 
        /* Replaced entry's previous pointer should point back to itself */
616
 
        if (entry1->prev != entry1) {
617
 
                printf ("BAD: replaced entry previous set incorrectly.\n");
618
 
                ret = 1;
619
 
        }
620
 
 
621
 
        /* Head's previous pointer should point to the new entry */
622
 
        if (hash->bins[15].prev != entry3) {
623
 
                printf ("BAD: head previous pointer set incorrectly.\n");
624
 
                ret = 1;
625
 
        }
626
 
 
627
 
        /* Head's next pointer should point to the new entry */
628
 
        if (hash->bins[15].next != entry3) {
629
 
                printf ("BAD: head next pointer set incorrectly.\n");
630
 
                ret = 1;
631
 
        }
632
 
 
633
 
        /* New entry's previous pointer should point to the head */
634
 
        if (entry3->prev != &hash->bins[15]) {
635
 
                printf ("BAD: entry previous pointer set incorrectly.\n");
636
 
                ret = 1;
637
 
        }
638
 
 
639
 
        /* New entry's next pointer should point to the head */
640
 
        if (entry3->next != &hash->bins[15]) {
641
 
                printf ("BAD: entry next pointer set incorrectly.\n");
642
 
                ret = 1;
643
 
        }
644
 
 
645
 
 
646
 
        printf ("...with entry already in a list\n");
647
 
        ptr = nih_list_new ();
 
325
        TEST_EQ_P (ptr, entry1);
 
326
 
 
327
        TEST_EQ_P (entry1->next, entry1);
 
328
        TEST_EQ_P (entry1->prev, entry1);
 
329
 
 
330
        TEST_EQ_P (hash->bins[15].next, entry3);
 
331
        TEST_EQ_P (entry3->next, &hash->bins[15]);
 
332
        TEST_EQ_P (hash->bins[15].prev, entry3);
 
333
        TEST_EQ_P (entry3->prev, &hash->bins[15]);
 
334
 
 
335
 
 
336
        /* Check that nih_hash_add can rip an entry out of an existing list
 
337
         * and place it in the hash table.
 
338
         */
 
339
        TEST_FEATURE ("with entry already in a list");
 
340
        ptr = nih_list_new (NULL);
648
341
        nih_list_add (ptr, entry4);
649
342
        nih_hash_replace (hash, entry4);
650
343
 
651
 
        /* List's previous pointer should point back to itself */
652
 
        if (ptr->prev != ptr) {
653
 
                printf ("BAD: list previous pointer set incorrectly.\n");
654
 
                ret = 1;
655
 
        }
656
 
 
657
 
        /* List's next pointer should point back to itself */
658
 
        if (ptr->next != ptr) {
659
 
                printf ("BAD: list next pointer set incorrectly.\n");
660
 
                ret = 1;
661
 
        }
662
 
 
663
 
        /* 3rd hash bin head's next pointer should be the entry */
664
 
        if (hash->bins[3].next != entry4) {
665
 
                printf ("BAD: head next pointer set incorrectly.\n");
666
 
                ret = 1;
667
 
        }
668
 
 
669
 
        /* 3rd hash bin head's previous pointer should be the entry */
670
 
        if (hash->bins[3].prev != entry4) {
671
 
                printf ("BAD: previous next pointer set incorrectly.\n");
672
 
                ret = 1;
673
 
        }
674
 
 
675
 
        /* Entry's next pointer should be the 3rd hash bin */
676
 
        if (entry4->next != &hash->bins[3]) {
677
 
                printf ("BAD: entry next pointer set incorrectly.\n");
678
 
                ret = 1;
679
 
        }
680
 
 
681
 
        /* Entry's previous pointer should be the 3rd hash bin */
682
 
        if (entry4->prev != &hash->bins[3]) {
683
 
                printf ("BAD: entry next pointer set incorrectly.\n");
684
 
                ret = 1;
685
 
        }
 
344
        TEST_EQ_P (ptr->next, ptr);
 
345
        TEST_EQ_P (ptr->prev, ptr);
 
346
 
 
347
        TEST_EQ_P (hash->bins[3].next, entry4);
 
348
        TEST_EQ_P (entry4->next, &hash->bins[3]);
 
349
        TEST_EQ_P (hash->bins[3].prev, entry4);
 
350
        TEST_EQ_P (entry4->prev, &hash->bins[3]);
686
351
 
687
352
        nih_free (hash);
688
353
        nih_free (ptr);
689
 
 
690
 
        return ret;
691
354
}
692
355
 
693
 
int
 
356
void
694
357
test_search (void)
695
358
{
696
359
        NihHash *hash;
697
360
        NihList *entry1, *entry2, *entry3, *ptr;
698
 
        int      ret = 0;
699
361
 
700
 
        printf ("Testing nih_hash_search()\n");
701
 
        hash = nih_hash_new (0, key_function);
 
362
        TEST_FUNCTION ("nih_hash_search");
 
363
        hash = nih_hash_new (NULL, 0, key_function);
702
364
        entry1 = nih_hash_add (hash, new_entry (hash, "entry 1"));
703
365
        entry2 = nih_hash_add (hash, new_entry (hash, "entry 2"));
704
366
        entry3 = nih_hash_add (hash, new_entry (hash, "entry 2"));
705
367
 
706
 
        printf ("...with single match\n");
 
368
        /* Check that we find the sole matching entry. */
707
369
        ptr = nih_hash_search (hash, "entry 1", NULL);
708
370
 
709
 
        /* First return value should be the entry */
710
 
        if (ptr != entry1) {
711
 
                printf ("BAD: return value was not correct.\n");
712
 
                ret = 1;
713
 
        }
 
371
        TEST_EQ_P (ptr, entry1);
714
372
 
 
373
        /* Searching again should find nothing */
715
374
        ptr = nih_hash_search (hash, "entry 1", ptr);
716
375
 
717
 
        /* Second return value should be NULL */
718
 
        if (ptr != NULL) {
719
 
                printf ("BAD: return value was not correct.\n");
720
 
                ret = 1;
721
 
        }
722
 
 
723
 
 
724
 
        printf ("...with multiple matches\n");
 
376
        TEST_EQ_P (ptr, NULL);
 
377
 
 
378
 
 
379
        /* Check that where there's multiple matches, we find the first one. */
 
380
        TEST_FEATURE ("with multiple matches");
725
381
        ptr = nih_hash_search (hash, "entry 2", NULL);
726
382
 
727
 
        /* Return value should be first added */
728
 
        if (ptr != entry2) {
729
 
                printf ("BAD: return value was not correct.\n");
730
 
                ret = 1;
731
 
        }
732
 
 
733
 
        ptr = nih_hash_search (hash, "entry 2", ptr);
734
 
 
735
 
        /* Second return value should be second added */
736
 
        if (ptr != entry3) {
737
 
                printf ("BAD: return value was not correct.\n");
738
 
                ret = 1;
739
 
        }
740
 
 
741
 
        ptr = nih_hash_search (hash, "entry 2", ptr);
742
 
 
743
 
        /* Third return value should be NULL */
744
 
        if (ptr != NULL) {
745
 
                printf ("BAD: return value was not correct.\n");
746
 
                ret = 1;
747
 
        }
748
 
 
749
 
 
750
 
        printf ("...with no matches\n");
 
383
        TEST_EQ_P (ptr, entry2);
 
384
 
 
385
        /* And that searching again finds the second one. */
 
386
        ptr = nih_hash_search (hash, "entry 2", ptr);
 
387
 
 
388
        TEST_EQ_P (ptr, entry3);
 
389
 
 
390
        /* And again finds nothing. */
 
391
        ptr = nih_hash_search (hash, "entry 2", ptr);
 
392
 
 
393
        TEST_EQ_P (ptr, NULL);
 
394
 
 
395
 
 
396
        /* Check that we get NULL if there are no matches. */
 
397
        TEST_FEATURE ("with no matches");
751
398
        ptr = nih_hash_search (hash, "entry 3", NULL);
752
399
 
753
 
        /* Return value should be NULL */
754
 
        if (ptr != NULL) {
755
 
                printf ("BAD: return value was not correct.\n");
756
 
                ret = 1;
757
 
        }
 
400
        TEST_EQ_P (ptr, NULL);
758
401
 
759
402
        nih_free (hash);
760
 
 
761
 
        return ret;
762
403
}
763
404
 
764
 
int
 
405
void
765
406
test_lookup (void)
766
407
{
767
408
        NihHash *hash;
768
409
        NihList *entry1, *entry2, *entry3, *ptr;
769
 
        int      ret = 0;
770
410
 
771
 
        printf ("Testing nih_hash_lookup()\n");
772
 
        hash = nih_hash_new (0, key_function);
 
411
        TEST_FUNCTION ("nih_hash_lookup");
 
412
        hash = nih_hash_new (NULL, 0, key_function);
773
413
        entry1 = nih_hash_add (hash, new_entry (hash, "entry 1"));
774
414
        entry2 = nih_hash_add (hash, new_entry (hash, "entry 2"));
775
415
        entry3 = nih_hash_add (hash, new_entry (hash, "entry 2"));
776
416
 
777
 
        printf ("...with single match\n");
 
417
        /* Check that we find a single matching entry. */
 
418
        TEST_FEATURE ("with single match");
778
419
        ptr = nih_hash_lookup (hash, "entry 1");
779
420
 
780
 
        /* Return value should be the entry */
781
 
        if (ptr != entry1) {
782
 
                printf ("BAD: return value was not correct.\n");
783
 
                ret = 1;
784
 
        }
785
 
 
786
 
 
787
 
        printf ("...with multiple matches\n");
 
421
        TEST_EQ_P (ptr, entry1);
 
422
 
 
423
 
 
424
        /* Check that we find the first matching entry. */
 
425
        TEST_FEATURE ("with multiple matches");
788
426
        ptr = nih_hash_lookup (hash, "entry 2");
789
427
 
790
 
        /* Return value should be first added */
791
 
        if (ptr != entry2) {
792
 
                printf ("BAD: return value was not correct.\n");
793
 
                ret = 1;
794
 
        }
795
 
 
796
 
 
797
 
        printf ("...with no matches\n");
 
428
        TEST_EQ_P (ptr, entry2);
 
429
 
 
430
 
 
431
        /* Check that we get NULL when there are no matching entries. */
 
432
        TEST_FEATURE ("with no matches");
798
433
        ptr = nih_hash_lookup (hash, "entry 3");
799
434
 
800
 
        /* Return value should be NULL */
801
 
        if (ptr != NULL) {
802
 
                printf ("BAD: return value was not correct.\n");
803
 
                ret = 1;
804
 
        }
805
 
 
806
 
        nih_free (hash);
807
 
 
808
 
        return ret;
 
435
        TEST_EQ_P (ptr, NULL);
 
436
 
 
437
        nih_free (hash);
 
438
}
 
439
 
 
440
 
 
441
void
 
442
test_foreach (void)
 
443
{
 
444
        NihHash *hash;
 
445
        NihList *entry[4], *entry0, *entry1, *entry2, *entry3;
 
446
        int      i;
 
447
 
 
448
        /* Check that NIH_HASH_FOREACH iterates the hash correctly in order,
 
449
         * visiting each entry in each bin.  Note that we stage the entries
 
450
         * in the hash in the order we expect them to come out in, but add
 
451
         * them in a different order for sanity.
 
452
         */
 
453
        TEST_FUNCTION ("nih_HASH_FOREACH");
 
454
        hash = nih_hash_new (NULL, 0, key_function);
 
455
        entry0 = entry[2] = new_entry (hash, "entry 1");
 
456
        entry1 = entry[1] = new_entry (hash, "entry 2");
 
457
        entry2 = entry[3] = new_entry (hash, "entry 1");
 
458
        entry3 = entry[0] = new_entry (hash, "entry 4");
 
459
 
 
460
        nih_hash_add (hash, entry0);
 
461
        nih_hash_add (hash, entry1);
 
462
        nih_hash_add (hash, entry2);
 
463
        nih_hash_add (hash, entry3);
 
464
 
 
465
        i = 0;
 
466
        NIH_HASH_FOREACH (hash, iter) {
 
467
                if (i > 3)
 
468
                        TEST_FAILED ("wrong number of iterations, expected %d got %d",
 
469
                                     4, i + 1);
 
470
 
 
471
                if (iter != entry[i])
 
472
                        TEST_FAILED ("wrong list entry, expected %p got %p",
 
473
                                     entry[i], iter);
 
474
 
 
475
                i++;
 
476
        }
 
477
 
 
478
        nih_free (hash);
 
479
}
 
480
 
 
481
void
 
482
test_foreach_safe (void)
 
483
{
 
484
        NihHash *hash;
 
485
        NihList *entry[4], *entry0, *entry1, *entry2, *entry3;
 
486
        int      i;
 
487
 
 
488
        /* Check that NIH_HASH_FOREACH_SAFE iterates the hash correctly in
 
489
         * order, visiting each entry in each bin; and that it's safe to
 
490
         * remove the entries while doing so.
 
491
         */
 
492
        TEST_FUNCTION ("nih_HASH_FOREACH");
 
493
        hash = nih_hash_new (NULL, 0, key_function);
 
494
        entry0 = entry[2] = new_entry (hash, "entry 1");
 
495
        entry1 = entry[1] = new_entry (hash, "entry 2");
 
496
        entry2 = entry[3] = new_entry (hash, "entry 1");
 
497
        entry3 = entry[0] = new_entry (hash, "entry 4");
 
498
 
 
499
        nih_hash_add (hash, entry0);
 
500
        nih_hash_add (hash, entry1);
 
501
        nih_hash_add (hash, entry2);
 
502
        nih_hash_add (hash, entry3);
 
503
 
 
504
        i = 0;
 
505
        NIH_HASH_FOREACH_SAFE (hash, iter) {
 
506
                if (i > 3)
 
507
                        TEST_FAILED ("wrong number of iterations, expected %d got %d",
 
508
                                     4, i + 1);
 
509
 
 
510
                if (iter != entry[i])
 
511
                        TEST_FAILED ("wrong list entry, expected %p got %p",
 
512
                                     entry[i], iter);
 
513
 
 
514
                nih_list_remove (entry[i]);
 
515
 
 
516
                i++;
 
517
        }
 
518
 
 
519
        nih_free (hash);
 
520
}
 
521
 
 
522
 
 
523
void
 
524
test_string_key (void)
 
525
{
 
526
        NihList    *entry;
 
527
        const char *key;
 
528
 
 
529
 
 
530
        /* Check that the string key function returns a pointer to the
 
531
         * key in our test structure.
 
532
         */
 
533
        TEST_FUNCTION ("nih_hash_string_key");
 
534
        entry = new_entry (NULL, "my entry");
 
535
 
 
536
        key = nih_hash_string_key (entry);
 
537
 
 
538
        TEST_EQ_P (key, ((HashEntry *)entry)->key);
 
539
        TEST_EQ_STR (key, "my entry");
 
540
 
 
541
        nih_list_free (entry);
809
542
}
810
543
 
811
544
 
813
546
main (int   argc,
814
547
      char *argv[])
815
548
{
816
 
        int ret = 0;
817
 
 
818
 
        ret |= test_new ();
819
 
        ret |= test_add ();
820
 
        ret |= test_add_unique ();
821
 
        ret |= test_replace ();
822
 
        ret |= test_search ();
823
 
        ret |= test_lookup ();
824
 
 
825
 
        return ret;
 
549
        test_new ();
 
550
        test_add ();
 
551
        test_add_unique ();
 
552
        test_replace ();
 
553
        test_search ();
 
554
        test_lookup ();
 
555
        test_foreach ();
 
556
        test_foreach_safe ();
 
557
        test_string_key ();
 
558
 
 
559
        return 0;
826
560
}