t/helper/test-hashmap.c

   1 #include "test-tool.h"
   2 #include "git-compat-util.h"
   3 #include "hashmap.h"
   4 #include "strbuf.h"
   5 #include "string-list.h"
   6
   7 struct test_entry
   8 {
   9         int padding; /* hashmap entry no longer needs to be the first member */
  10         struct hashmap_entry ent;
  11         /* key and value as two \0-terminated strings */
  12         char key[FLEX_ARRAY];
  13 };
  14
  15 static int test_entry_cmp(const void *cmp_data,
  16                           const struct hashmap_entry *eptr,
  17                           const struct hashmap_entry *entry_or_key,
  18                           const void *keydata)
  19 {
  20         const int ignore_case = cmp_data ? *((int *)cmp_data) : 0;
  21         const struct test_entry *e1, *e2;
  22         const char *key = keydata;
  23
  24         e1 = container_of(eptr, const struct test_entry, ent);
  25         e2 = container_of(entry_or_key, const struct test_entry, ent);
  26
  27         if (ignore_case)
  28                 return strcasecmp(e1->key, key ? key : e2->key);
  29         else
  30                 return strcmp(e1->key, key ? key : e2->key);
  31 }
  32
  33 static struct test_entry *alloc_test_entry(unsigned int hash,
  34                                            const char *key,
  35                                            const char *value)
  36 {
  37         size_t klen = strlen(key);
  38         size_t vlen = strlen(value);
  39         struct test_entry *entry = xmalloc(st_add4(sizeof(*entry), klen, vlen, 2));
  40         hashmap_entry_init(&entry->ent, hash);
  41         memcpy(entry->key, key, klen + 1);
  42         memcpy(entry->key + klen + 1, value, vlen + 1);
  43         return entry;
  44 }
  45
  46 #define HASH_METHOD_FNV 0
  47 #define HASH_METHOD_I 1
  48 #define HASH_METHOD_IDIV10 2
  49 #define HASH_METHOD_0 3
  50 #define HASH_METHOD_X2 4
  51 #define TEST_SPARSE 8
  52 #define TEST_ADD 16
  53 #define TEST_SIZE 100000
  54
  55 static unsigned int hash(unsigned int method, unsigned int i, const char *key)
  56 {
  57         unsigned int hash = 0;
  58         switch (method & 3)
  59         {
  60         case HASH_METHOD_FNV:
  61                 hash = strhash(key);
  62                 break;
  63         case HASH_METHOD_I:
  64                 hash = i;
  65                 break;
  66         case HASH_METHOD_IDIV10:
  67                 hash = i / 10;
  68                 break;
  69         case HASH_METHOD_0:
  70                 hash = 0;
  71                 break;
  72         }
  73
  74         if (method & HASH_METHOD_X2)
  75                 hash = 2 * hash;
  76         return hash;
  77 }
  78
  79 /*
  80  * Test performance of hashmap.[ch]
  81  * Usage: time echo "perfhashmap method rounds" | test-tool hashmap
  82  */
  83 static void perf_hashmap(unsigned int method, unsigned int rounds)
  84 {
  85         struct hashmap map;
  86         char buf[16];
  87         struct test_entry **entries;
  88         unsigned int *hashes;
  89         unsigned int i, j;
  90
  91         ALLOC_ARRAY(entries, TEST_SIZE);
  92         ALLOC_ARRAY(hashes, TEST_SIZE);
  93         for (i = 0; i < TEST_SIZE; i++) {
  94                 xsnprintf(buf, sizeof(buf), "%i", i);
  95                 entries[i] = alloc_test_entry(0, buf, "");
  96                 hashes[i] = hash(method, i, entries[i]->key);
  97         }
  98
  99         if (method & TEST_ADD) {
 100                 /* test adding to the map */
 101                 for (j = 0; j < rounds; j++) {
 102                         hashmap_init(&map, test_entry_cmp, NULL, 0);
 103
 104                         /* add entries */
 105                         for (i = 0; i < TEST_SIZE; i++) {
 106                                 hashmap_entry_init(&entries[i]->ent, hashes[i]);
 107                                 hashmap_add(&map, &entries[i]->ent);
 108                         }
 109
 110                         hashmap_clear(&map);
 111                 }
 112         } else {
 113                 /* test map lookups */
 114                 hashmap_init(&map, test_entry_cmp, NULL, 0);
 115
 116                 /* fill the map (sparsely if specified) */
 117                 j = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE;
 118                 for (i = 0; i < j; i++) {
 119                         hashmap_entry_init(&entries[i]->ent, hashes[i]);
 120                         hashmap_add(&map, &entries[i]->ent);
 121                 }
 122
 123                 for (j = 0; j < rounds; j++) {
 124                         for (i = 0; i < TEST_SIZE; i++) {
 125                                 hashmap_get_from_hash(&map, hashes[i],
 126                                                       entries[i]->key);
 127                         }
 128                 }
 129
 130                 hashmap_clear(&map);
 131         }
 132 }
 133
 134 #define DELIM " \t\r\n"
 135
 136 /*
 137  * Read stdin line by line and print result of commands to stdout:
 138  *
 139  * perfhashmap method rounds -> test hashmap.[ch] performance
 140  */
 141 int cmd__hashmap(int argc UNUSED, const char **argv UNUSED)
 142 {
 143         struct string_list parts = STRING_LIST_INIT_NODUP;
 144         struct strbuf line = STRBUF_INIT;
 145
 146         /* process commands from stdin */
 147         while (strbuf_getline(&line, stdin) != EOF) {
 148                 char *cmd, *p1, *p2;
 149
 150                 /* break line into command and up to two parameters */
 151                 string_list_setlen(&parts, 0);
 152                 string_list_split_in_place(&parts, line.buf, DELIM, 2);
 153                 string_list_remove_empty_items(&parts, 0);
 154
 155                 /* ignore empty lines */
 156                 if (!parts.nr)
 157                         continue;
 158                 if (!*parts.items[0].string || *parts.items[0].string == '#')
 159                         continue;
 160
 161                 cmd = parts.items[0].string;
 162                 p1 = parts.nr >= 1 ? parts.items[1].string : NULL;
 163                 p2 = parts.nr >= 2 ? parts.items[2].string : NULL;
 164
 165                 if (!strcmp("perfhashmap", cmd) && p1 && p2) {
 166
 167                         perf_hashmap(atoi(p1), atoi(p2));
 168
 169                 } else {
 170
 171                         printf("Unknown command %s\n", cmd);
 172
 173                 }
 174         }
 175
 176         string_list_clear(&parts, 0);
 177         strbuf_release(&line);
 178         return 0;
 179 }