← Back to branch summary

~ubuntu-branches/ubuntu/saucy/sssd/saucy

« back to all changes in this revision

Viewing changes to common/dhash/dhash_test.c

  • Committer: Stéphane Graber
  • Date: 2011-06-15 16:23:14 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: stgraber@ubuntu.com-20110615162314-rbhoppnpaxfqo5q7
Merge 1.5.8

Show diffs side-by-side

added added

removed removed

Lines of Context:
common/dhash/dhash_test.c
1
 
#include <stdio.h>
2
 
#include <assert.h>
3
 
#include <string.h>
4
 
#include <stdlib.h>
5
 
#include <time.h>
6
 
#include <getopt.h>
7
 
#include "dhash.h"
8
 
 
9
 
#define DEFAULT_MAX_TEST (500)
10
 
hash_entry_t *iter_result_1 = NULL;
11
 
hash_entry_t *iter_result_2 = NULL;
12
 
 
13
 
unsigned long max_test = DEFAULT_MAX_TEST;
14
 
int verbose = 0;
15
 
 
16
 
const char *error_string(int error)
17
 
{
18
 
    if (IS_HASH_ERROR(error))
19
 
        return hash_error_string(error);
20
 
 
21
 
    return strerror(error);
22
 
}
23
 
 
24
 
char *key_string(hash_key_t *key)
25
 
{
26
 
    static char buf[1024];
27
 
 
28
 
    switch(key->type) {
29
 
    case HASH_KEY_ULONG:
30
 
        snprintf(buf, sizeof(buf), "key ulong = %lu", key->ul);
31
 
        break;
32
 
    case HASH_KEY_STRING:
33
 
        snprintf(buf, sizeof(buf), "key string = \"%s\"", key->str);
34
 
        break;
35
 
    default:
36
 
        snprintf(buf, sizeof(buf), "unknown key type = %d", key->type);
37
 
        break;
38
 
    }
39
 
    return buf;
40
 
}
41
 
 
42
 
char *value_string(hash_value_t *value)
43
 
{
44
 
    static char buf[1024];
45
 
 
46
 
    switch(value->type) {
47
 
    case HASH_VALUE_UNDEF:
48
 
        snprintf(buf, sizeof(buf), "value undefined");
49
 
        break;
50
 
    case HASH_VALUE_PTR:
51
 
        snprintf(buf, sizeof(buf), "value str = \"%s\"", (char *)value->ptr);
52
 
        break;
53
 
    case HASH_VALUE_INT:
54
 
        snprintf(buf, sizeof(buf), "value int = %d", value->i);
55
 
        break;
56
 
    case HASH_VALUE_UINT:
57
 
        snprintf(buf, sizeof(buf), "value unsigned int = %u", value->ui);
58
 
        break;
59
 
    case HASH_VALUE_LONG:
60
 
        snprintf(buf, sizeof(buf), "value long = %ld", value->l);
61
 
        break;
62
 
    case HASH_VALUE_ULONG:
63
 
        snprintf(buf, sizeof(buf), "value unsigned long = %lu", value->ul);
64
 
        break;
65
 
    case HASH_VALUE_FLOAT:
66
 
        snprintf(buf, sizeof(buf), "value float = %f", value->f);
67
 
        break;
68
 
    case HASH_VALUE_DOUBLE:
69
 
        snprintf(buf, sizeof(buf), "value double = %f", value->f);
70
 
        break;
71
 
    default:
72
 
        snprintf(buf, sizeof(buf), "unknown value type = %d", value->type);
73
 
        break;
74
 
    }
75
 
 
76
 
    return buf;
77
 
}
78
 
 
79
 
char *entry_string(hash_entry_t *entry)
80
 
{
81
 
    static char buf[1024];
82
 
 
83
 
    snprintf(buf, sizeof(buf), "[%s] = [%s]", key_string(&entry->key), value_string(&entry->value));
84
 
 
85
 
    return buf;
86
 
 
87
 
}
88
 
 
89
 
bool callback(hash_entry_t *item, void *user_data)
90
 
{
91
 
    unsigned long *callback_count = (unsigned long *)user_data;
92
 
 
93
 
    iter_result_1[*callback_count] = *item;
94
 
 
95
 
    (*callback_count)++;
96
 
 
97
 
    if (verbose) printf("%s\n", entry_string(item));
98
 
    return true;
99
 
}
100
 
 
101
 
void delete_callback(hash_entry_t *item, hash_destroy_enum type, void *pvt)
102
 
{
103
 
    if (item->value.type == HASH_VALUE_PTR) free(item->value.ptr);
104
 
}
105
 
 
106
 
typedef struct test_val_t {
107
 
    long val;
108
 
    char *str;
109
 
} test_val_t;
110
 
 
111
 
 
112
 
int main(int argc, char **argv)
113
 
{
114
 
    test_val_t *test = NULL;
115
 
    long i, k;
116
 
    int status;
117
 
    hash_value_t value;
118
 
    hash_key_t key;
119
 
    char buf[1024];
120
 
    hash_table_t *table = NULL;
121
 
    unsigned long callback_count = 0;
122
 
    unsigned int directory_bits = HASH_DEFAULT_DIRECTORY_BITS;
123
 
    unsigned int segment_bits = HASH_DEFAULT_SEGMENT_BITS;
124
 
    unsigned long min_load_factor = HASH_DEFAULT_MIN_LOAD_FACTOR;
125
 
    unsigned long max_load_factor = HASH_DEFAULT_MAX_LOAD_FACTOR;
126
 
 
127
 
    while (1) {
128
 
        int arg;
129
 
        int option_index = 0;
130
 
        static struct option long_options[] = {
131
 
            {"count", 1, 0, 'c'},
132
 
            {"verbose", 1, 0, 'v'},
133
 
            {"quiet", 1, 0, 'q'},
134
 
            {"directory-bits", 1, 0, 'd'},
135
 
            {"segment-bits", 1, 0, 's'},
136
 
            {"min-load-factor", 1, 0, 'l'},
137
 
            {"max-load-factor", 1, 0, 'h'},
138
 
            {0, 0, 0, 0}
139
 
        };
140
 
 
141
 
        arg = getopt_long(argc, argv, "c:vqd:s:l:h:",
142
 
                          long_options, &option_index);
143
 
        if (arg == -1) break;
144
 
 
145
 
        switch (arg) {
146
 
        case 'c':
147
 
            max_test = atol(optarg);
148
 
            break;
149
 
        case 'v':
150
 
            verbose = 1;
151
 
            break;
152
 
        case 'q':
153
 
            verbose = 0;
154
 
            break;
155
 
        case 'd':
156
 
            directory_bits = atoi(optarg);
157
 
            break;
158
 
        case 's':
159
 
            segment_bits = atoi(optarg);
160
 
            break;
161
 
        case 'l':
162
 
            min_load_factor = atol(optarg);
163
 
            break;
164
 
        case 'h':
165
 
            max_load_factor = atol(optarg);
166
 
            break;
167
 
        }
168
 
    }
169
 
 
170
 
    if ((test = (test_val_t *) calloc(max_test, sizeof(test_val_t))) == NULL) {
171
 
        fprintf(stderr, "Failed to allocate test array\n");
172
 
        exit(1);
173
 
    }
174
 
    if ((iter_result_1 = (hash_entry_t *) calloc(max_test, sizeof(hash_entry_t))) == NULL) {
175
 
        fprintf(stderr, "Failed to allocate iter_result_1 array\n");
176
 
        exit(1);
177
 
    }
178
 
    if ((iter_result_2 = (hash_entry_t *) calloc(max_test, sizeof(hash_entry_t))) == NULL) {
179
 
        fprintf(stderr, "Failed to allocate iter_result_2 array\n");
180
 
        exit(1);
181
 
    }
182
 
 
183
 
 
184
 
    /* Initialize the random number generator */
185
 
    srandom(time(0));
186
 
 
187
 
    /* Create the hash table as small as possible to exercise growth */
188
 
    if ((status = hash_create_ex(1, &table,
189
 
                                 directory_bits, segment_bits,
190
 
                                 min_load_factor, max_load_factor,
191
 
                                 NULL, NULL, NULL,
192
 
                                 delete_callback, NULL)) != HASH_SUCCESS) {
193
 
        fprintf(stderr, "table creation failed at line %d (%s)\n", __LINE__, error_string(status));
194
 
        exit(1);
195
 
    }
196
 
 
197
 
    /* Initialize the array of test values */
198
 
    for (i = 0; i < max_test; i++) {
199
 
        test[i].val = random();
200
 
        /* If the value is odd we'll use a string as the key,
201
 
         * otherwise we'll use an unsigned long as the key */
202
 
        if (test[i].val & 1) {
203
 
            key.type = HASH_KEY_STRING;
204
 
            sprintf(buf, "%ld", test[i].val);
205
 
            test[i].str = strdup(buf);
206
 
        }
207
 
    }
208
 
 
209
 
    /* Enter all the test values into the hash table */
210
 
    for (i = 0; i < max_test; i++) {
211
 
        if (test[i].val & 1) {
212
 
            key.type = HASH_KEY_STRING;
213
 
            key.str = test[i].str;
214
 
            value.type = HASH_VALUE_PTR;
215
 
            value.ptr = (void *) strdup(test[i].str);
216
 
        }
217
 
        else {
218
 
            key.type = HASH_KEY_ULONG;
219
 
            key.ul = test[i].val;
220
 
            value.type = HASH_VALUE_LONG;
221
 
            value.l = test[i].val;
222
 
        }
223
 
 
224
 
        if (hash_has_key(table, &key)) {
225
 
            fprintf(stderr, "Error: %ld already in table when inserting, i = %lu, at line %d\n",
226
 
                    test[i].val, i, __LINE__);
227
 
            exit(1);
228
 
        }
229
 
        if ((status = hash_enter(table, &key, &value)) != HASH_SUCCESS) {
230
 
            fprintf(stderr, "Error: %ld failed insertion at line %d (%s) \n",
231
 
                    test[i].val, __LINE__, error_string(status));
232
 
            exit(1);
233
 
        }
234
 
    }
235
 
 
236
 
    /* Now visit each entry in the table using a callback iterator,
237
 
     * store what we found in iter_result_1 for testing the iterator object later on */
238
 
    if (verbose) printf("callback iterate:\n");
239
 
    callback_count = 0;
240
 
    if ((status = hash_iterate(table, callback, &callback_count)) != HASH_SUCCESS) {
241
 
        fprintf(stderr, "hash_iterate failed at line %d (%s)\n", __LINE__, error_string(status));
242
 
        exit(1);
243
 
    }
244
 
    if (verbose) printf("hash_count=%ld,  callback_count=%ld\n", hash_count(table), callback_count);
245
 
 
246
 
    if (hash_count(table) != callback_count) {
247
 
        fprintf(stderr, "Error: hash_count(%ld) != callback_count(%ld) at line %d\n",
248
 
                hash_count(table), callback_count, __LINE__);
249
 
        exit(1);
250
 
    }
251
 
 
252
 
    /* Now vist each entry in the table using an iterator object */
253
 
    {
254
 
        struct hash_iter_context_t *iter;
255
 
        unsigned long n_items;
256
 
        hash_entry_t *entry;
257
 
 
258
 
        if (verbose) printf("iter iterate:\n");
259
 
 
260
 
        n_items = 0;
261
 
        iter = new_hash_iter_context(table);
262
 
 
263
 
        while ((entry = iter->next(iter)) != NULL) {
264
 
            if (verbose) printf("%s\n", entry_string(entry));
265
 
            iter_result_2[n_items] = *entry;
266
 
            n_items++;
267
 
        }
268
 
        if (verbose) printf("hash_count=%ld,  n_items=%ld\n", hash_count(table), n_items);
269
 
 
270
 
        if (hash_count(table) != n_items) {
271
 
            fprintf(stderr, "Error: hash_count(%ld) != n_items(%ld) at line %d\n",
272
 
                    hash_count(table), n_items, __LINE__);
273
 
            exit(1);
274
 
        }
275
 
        free(iter);
276
 
    }
277
 
 
278
 
    /* Both iterators should have visited each item in the same order, verify ... */
279
 
    for (i = 0; i < max_test; i++) {
280
 
        if (memcmp(&iter_result_1[i], &iter_result_2[i], sizeof(iter_result_1[0])) != 0) {
281
 
            fprintf(stderr, "Error: iter_result_1[%lu] != iter_result_2[%lu] at line %d\n",
282
 
                    i, i, __LINE__);
283
 
            exit(1);
284
 
        }
285
 
    }
286
 
 
287
 
    /* Get an array of keys in the table, print them out */
288
 
    {
289
 
        unsigned long count;
290
 
        hash_key_t *keys;
291
 
 
292
 
        if (verbose) printf("\nhash_keys:\n");
293
 
        if ((status = hash_keys(table, &count, &keys)) != HASH_SUCCESS) {
294
 
            fprintf(stderr, "hash_keys failed at line %d (%s)\n",
295
 
                    __LINE__, error_string(status));
296
 
            exit(1);
297
 
        }
298
 
 
299
 
        if (hash_count(table) != count) {
300
 
            fprintf(stderr, "Error: hash_count(%ld) != hash_keys() count(%ld) at line %d\n",
301
 
                    hash_count(table), count, __LINE__);
302
 
            exit(1);
303
 
        }
304
 
 
305
 
        for (i = 0; i < count; i++) {
306
 
            if (verbose) printf("%s\n", key_string(&keys[i]));
307
 
        }
308
 
        free(keys);
309
 
    }
310
 
 
311
 
    /* Get an array of values in the table, print them out */
312
 
    {
313
 
        unsigned long count;
314
 
        hash_value_t *values;
315
 
 
316
 
        if (verbose) printf("\nhash_values:\n");
317
 
        hash_values(table, &count, &values);
318
 
 
319
 
        if (hash_count(table) != count) {
320
 
            fprintf(stderr, "Error: hash_count(%ld) != hash_values() count(%ld) at line %d\n",
321
 
                    hash_count(table), count, __LINE__);
322
 
            exit(1);
323
 
        }
324
 
 
325
 
        for (i = 0; i < count; i++) {
326
 
            if (verbose) printf("%s\n", value_string(&values[i]));
327
 
        }
328
 
        free(values);
329
 
    }
330
 
 
331
 
    /* Get an array of items in the table, print them out */
332
 
    {
333
 
        unsigned long count;
334
 
        hash_entry_t *entries;
335
 
 
336
 
        if (verbose) printf("\nhash_entries:\n");
337
 
        hash_entries(table, &count, &entries);
338
 
 
339
 
        if (hash_count(table) != count) {
340
 
            fprintf(stderr, "Error: hash_count(%ld) != hash_entries() count(%ld) at line %d\n",
341
 
                    hash_count(table), count, __LINE__);
342
 
            exit(1);
343
 
        }
344
 
 
345
 
        for (i = 0; i < count; i++) {
346
 
            if (verbose) printf("%s\n", entry_string(&entries[i]));
347
 
        }
348
 
        free(entries);
349
 
    }
350
 
 
351
 
    /* See if we can find every key */
352
 
    for (i = max_test - 1; i >= 0; i--) {
353
 
        if (test[i].val & 1) {
354
 
            key.type = HASH_KEY_STRING;
355
 
            key.str = test[i].str;
356
 
        }
357
 
        else {
358
 
            key.type = HASH_KEY_ULONG;
359
 
            key.ul = test[i].val;
360
 
        }
361
 
        if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) {
362
 
            fprintf(stderr, "Error: failed first lookup for value %ld at index %ld at line %d (%s)\n",
363
 
                    test[i].val, i, __LINE__, error_string(status));
364
 
            exit(1);
365
 
        }
366
 
        else {
367
 
            switch(value.type) {
368
 
            case HASH_VALUE_PTR:
369
 
                if (strcmp((char *)value.ptr, test[i].str) != 0) {
370
 
                    fprintf(stderr, "Error: corrupt ptr data for %lu at line %d\n", i, __LINE__);
371
 
                    exit(1);
372
 
                }
373
 
                break;
374
 
            case HASH_VALUE_LONG:
375
 
                if (value.l != test[i].val) {
376
 
                    fprintf(stderr, "Error: corrupt long data for %lu at line %d\n", i, __LINE__);
377
 
                    exit(1);
378
 
                }
379
 
                break;
380
 
            default:
381
 
                fprintf(stderr, "Error: unknown value type for %lu\n", i);
382
 
                break;
383
 
            }
384
 
        }
385
 
    }
386
 
 
387
 
 
388
 
    /*
389
 
     * Delete a key, make sure we can't find it, assure we can find all other
390
 
     * keys.
391
 
     */
392
 
    for (i = 0; i < max_test; i++) {
393
 
        if (test[i].val & 1) {
394
 
            key.type = HASH_KEY_STRING;
395
 
            key.str = test[i].str;
396
 
        }
397
 
        else {
398
 
            key.type = HASH_KEY_ULONG;
399
 
            key.ul = test[i].val;
400
 
        }
401
 
 
402
 
        if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) {
403
 
            fprintf(stderr, "Error: failed delete lookup for value %ld at index %ld at line %d (%s)\n",
404
 
                    test[i].val, i, __LINE__, error_string(status));
405
 
            exit(1);
406
 
        }
407
 
 
408
 
        if ((status = hash_delete(table, &key)) != HASH_SUCCESS) {
409
 
            fprintf(stderr, "Error: %ld not in table when deleting, i = %lu at line %d (%s)\n",
410
 
                    test[i].val, i, __LINE__, error_string(status));
411
 
            exit(1);
412
 
        }
413
 
 
414
 
        if (hash_lookup(table, &key, &value) != HASH_ERROR_KEY_NOT_FOUND) {
415
 
            fprintf(stderr, "Error: found in table after deletion, value = %ld at index %ld at line %d\n",
416
 
                    test[i].val, i, __LINE__);
417
 
            exit(1);
418
 
        }
419
 
        /* See if we can find all remaining keys */
420
 
        for (k = i + 1; k < max_test; k++) {
421
 
            if (test[k].val & 1) {
422
 
                key.type = HASH_KEY_STRING;
423
 
                key.str = test[k].str;
424
 
            } else {
425
 
                key.type = HASH_KEY_ULONG;
426
 
                key.ul = test[k].val;
427
 
            }
428
 
            if ((status = hash_lookup(table, &key, &value)) != HASH_SUCCESS) {
429
 
                fprintf(stderr, "Error: failed second lookup for value %ld, i = %lu k = %lu at line %d (%s)\n",
430
 
                        test[k].val, i, k, __LINE__, error_string(status));
431
 
                exit(1);
432
 
            } else {
433
 
                switch(value.type) {
434
 
                case HASH_VALUE_PTR:
435
 
                    if (strcmp((char *)value.ptr, test[k].str) != 0) {
436
 
                        fprintf(stderr, "Error: corrupt ptr data for %lu at line %d\n", k, __LINE__);
437
 
                        exit(1);
438
 
                    }
439
 
                    break;
440
 
                case HASH_VALUE_LONG:
441
 
                    if (value.l != test[k].val) {
442
 
                        fprintf(stderr, "Error: corrupt long data for %lu at line %d\n", k, __LINE__);
443
 
                        exit(1);
444
 
                    }
445
 
                    break;
446
 
                default:
447
 
                    fprintf(stderr, "Error: unknown value type (%d) for %lu\n", value.type, k);
448
 
                    break;
449
 
                }
450
 
            }
451
 
        }
452
 
    }
453
 
 
454
 
    if (verbose) printf("\n");
455
 
 
456
 
#ifdef HASH_STATISTICS
457
 
    {
458
 
        hash_statistics_t stats;
459
 
 
460
 
        if ((status = hash_get_statistics(table, &stats)) != HASH_SUCCESS) {
461
 
            fprintf(stderr, "Error: could not get statistics at line %d (%s)\n",
462
 
                    __LINE__, error_string(status));
463
 
            exit(1);
464
 
        }
465
 
 
466
 
        printf("Statistics: Accesses = %ld, Collisions = %ld, Collision Rate = %.2f, Expansions = %ld, Contractions = %ld\n",
467
 
               stats.hash_accesses, stats.hash_collisions,
468
 
               ((float)stats.hash_collisions / (float)stats.hash_accesses),
469
 
               stats.table_expansions, stats.table_contractions);
470
 
    }
471
 
#endif
472
 
 
473
 
    if ((status = hash_destroy(table)) != HASH_SUCCESS) {
474
 
        fprintf(stderr, "table destruction failed at line %d (%s)\n",
475
 
                __LINE__, error_string(status));
476
 
        exit(1);
477
 
    }
478
 
 
479
 
    for (i = 0; i < max_test; i++) {
480
 
        if (test[i].val & 1) {
481
 
            free(test[i].str);
482
 
        }
483
 
    }
484
 
    free(test);
485
 
    free(iter_result_1);
486
 
    free(iter_result_2);
487
 
 
488
 
    printf("Successfully tested %lu values\n", max_test);
489
 
    return 0;
490
 
}