h48map_tests.c (1851B)
1 #include "../test.h" 2 3 #define MAP_KEYSHIFT UINT64_C(40) 4 #define MAXPOS 1000 5 6 typedef struct { 7 uint64_t n; 8 uint64_t capacity; 9 uint64_t randomizer; 10 uint64_t *table; 11 } h48map_t; 12 13 typedef struct { 14 uint64_t key; 15 uint64_t val; 16 } kvpair_t; 17 18 void h48map_create(h48map_t *, uint64_t, uint64_t); 19 void h48map_destroy(h48map_t *); 20 void h48map_insertmin(h48map_t *, uint64_t, uint64_t); 21 uint64_t h48map_value(h48map_t *, uint64_t); 22 kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *); 23 24 char str[STRLENMAX]; 25 26 int compare(const void *x, const void *y) { 27 uint64_t a = ((kvpair_t *)x)->key; 28 uint64_t b = ((kvpair_t *)y)->key; 29 30 if (a > b) return 1; 31 if (a == b) return 0; 32 return -1; 33 } 34 35 uint64_t readl(void) { 36 fgets(str, STRLENMAX, stdin); 37 return atoll(str); 38 } 39 40 void run(void) { 41 h48map_t map; 42 uint64_t n, i, j, capacity, randomizer, x, y, v; 43 kvpair_t kv, a[MAXPOS], b[MAXPOS]; 44 45 capacity = readl(); 46 randomizer = readl(); 47 n = readl(); 48 49 for (i = 0; i < n; i++) { 50 x = readl(); 51 y = readl(); 52 a[i] = (kvpair_t) { .key = x, .val = y }; 53 } 54 55 h48map_create(&map, capacity, randomizer); 56 for (i = 0; i < n; i++) 57 h48map_insertmin(&map, a[i].key, a[i].val); 58 59 i = 0; 60 for (kv = h48map_nextkvpair(&map, &i), j = 0; 61 i != map.capacity && j < MAXPOS; 62 kv = h48map_nextkvpair(&map, &i) 63 ) { 64 b[j++] = kv; 65 } 66 qsort(b, j, sizeof(kvpair_t), compare); 67 68 printf("%" PRIu64 "\n", map.n); 69 for (i = 0; i < j; i++) 70 printf("%" PRIu64 " %" PRIu64 "\n", b[i].key, b[i].val); 71 if (map.n != j) 72 printf("Wrong number of elements: map->n = %" PRIu64 ", " 73 "but scan returns %" PRIu64 "\n", map.n, j); 74 for (i = 0; i < n; i++) { 75 v = h48map_value(&map, a[i].key); 76 if (v > a[i].val) 77 printf("Value for key %" PRId64 " is larger than " 78 "expected (%" PRIu64 " > %" PRIu64 ")\n", 79 a[i].key, v, a[i].val); 80 } 81 82 h48map_destroy(&map); 83 }