static void test_trivial(void) {
stringmap(int) map = stringmap_new(NULL);
+ ok1(stringmap_lookup(map, "") == NULL);
+ *stringmap_enter(map, "") = -1;
+
+ ok1(stringmap_lookup(map, "0") == NULL);
+ *stringmap_enter(map, "0") = 0;
+
ok1(stringmap_lookup(map, "one") == NULL);
*stringmap_enter(map, "one") = 1;
ok1(*stringmap_lookup(map, "one") == 1);
ok1(*stringmap_lookup(map, "four") == 4);
ok1(*stringmap_lookup(map, "two") == 2);
+ ok1(*stringmap_lookup(map, "") == -1);
+ ok1(*stringmap_lookup(map, "0") == 0);
- ok1(map.t.count == 4);
+ ok1(map.t.count == 6);
stringmap_free(map);
}
//#define RANDOM_STRING_READABLE
-static char *random_string(struct block_pool *bp) {
- size_t len = random() % 100;
- char *str = block_pool_alloc(bp, len+1);
+static char *random_string(struct block_pool *bp, size_t *len_out) {
+ #ifndef RANDOM_STRING_READABLE
+ size_t len = random()%5 ? random()%10 : random()%1000;
+ #else
+ size_t len = random() % 10;
+ #endif
+ char *str = block_pool_alloc(bp, len);
char *i;
+ *len_out = len;
+
for (i=str; len--; i++) {
#ifndef RANDOM_STRING_READABLE
char c = random();
- *i = c ? c : ' ';
+ *i = c;
#else
- //only generate characters [32,126]
- char c = random()%95 + 32;
+ //only generate characters a-z
+ char c = random()%26 + 'a';
*i = c;
#endif
}
- *i = 0;
return str;
}
struct test_entry {
+ //note: struct layout needs to match *stringmap(char*).last
const char *str;
+ size_t len;
+
char *value;
/* value is not a string, but a pointer to char marking that
this key has been entered already. */
};
-static int by_str(const void *ap, const void *bp) {
- return strcmp(((struct test_entry*)ap)->str, ((struct test_entry*)bp)->str);
+static int tecmp(const struct test_entry *ap, const struct test_entry *bp) {
+ const unsigned char *a = (unsigned char*)ap->str, *ae = a+ap->len;
+ const unsigned char *b = (unsigned char*)bp->str, *be = b+bp->len;
+
+ for (;;a++, b++) {
+ if (a >= ae) {
+ if (b >= be)
+ return 0; //strings are the same
+ return -1; //a is shorter than b
+ }
+ if (b >= be)
+ return 1; //b is shorter than a
+ if (*a != *b) //there is a differing character
+ return (unsigned int)*a - (unsigned int)*b;
+ }
+}
+
+static int by_str(const void *a, const void *b) {
+ return tecmp(a, b);
}
static void cull_duplicates(struct test_entry *entries, size_t *count) {
for (i=entries, o=entries; i<e;) {
//skip repeated strings
- if (i>entries) {
- const char *last = i[-1].str;
- if (!strcmp(last, i->str)) {
- do i++; while(i<e && !strcmp(last, i->str));
+ if (o>entries) {
+ struct test_entry *last = &o[-1];
+ if (!tecmp(last, i)) {
+ do i++; while(i<e && !tecmp(last, i));
continue;
}
}
*count = o-entries;
}
+#define print(tag, fmt, ...) do { \
+ if (out) \
+ fprintf(out, tag fmt "\n", ##__VA_ARGS__); \
+ } while(0)
+#define err(...) do { \
+ print("error: ", __VA_ARGS__); \
+ goto fail; \
+ } while(0)
+//#define debug(...) print("debug: ", __VA_ARGS__)
+#define debug(...) do {} while(0)
+#define msg(...) print("info: ", __VA_ARGS__)
+
+static int test_traverse(struct stringmap *map, struct test_entry *strings, size_t size, FILE *out) {
+ size_t sp = 0;
+ size_t stack_alloc = 16;
+ struct stringmap_node **stack = NULL;
+ struct stringmap_node *n;
+ void *leaf;
+ #define check(lri) do { \
+ leaf = n->lr[lri]; \
+ if (!size--) \
+ err("Fewer items in tree than counted"); \
+ if (tecmp(leaf, strings++)) \
+ err("%s leaf has incorrect string", lri ? "Left" : "Right"); \
+ } while(0)
+ #define check_left() check(0)
+ #define check_right() check(1)
+
+ if (map->count != size)
+ err("map->count != size");
+
+ if (map->count == 0)
+ return 1;
+
+ if (map->count == 1) {
+ leaf = (struct test_entry*)map->root;
+ if (!tecmp(leaf, &strings[0]))
+ return 1;
+ else
+ err("Only leaf in tree has incorrect value");
+ }
+
+ stack = malloc(sizeof(*stack) * stack_alloc);
+ n = map->root;
+
+ for (;;) {
+ //descend left
+ while (!n->left_is_leaf) {
+ stack[sp++] = n;
+ n = n->lr[0];
+
+ if (sp >= stack_alloc) {
+ stack_alloc += stack_alloc;
+ stack = realloc(stack, sizeof(*stack) * stack_alloc);
+ }
+ }
+
+ check_left();
+
+ ascend_right:
+ while (n->right_is_leaf) {
+ check_right();
+
+ if (!sp)
+ goto done; //we finished up the last entry
+ n = stack[--sp];
+ }
+
+ //descend right
+ n = n->lr[1];
+ while (n->left_is_leaf) {
+ check_left();
+
+ if (n->right_is_leaf) {
+ check_right();
+
+ if (!sp)
+ goto done;
+ n = stack[--sp];
+ goto ascend_right; //sorry
+ }
+ n = n->lr[1];
+ }
+ }
+
+done:
+ if (size != 0)
+ err("More items in tree than counted");
+
+ free(stack);
+ return 1;
+
+fail:
+ if (stack)
+ free(stack);
+ return 0;
+
+ #undef check
+ #undef check_left
+ #undef check_right
+}
+
static int test_stringmap(size_t count, FILE *out) {
stringmap(char*) map = stringmap_new(NULL);
- #define print(tag, fmt, ...) do { \
- if (out) \
- fprintf(out, tag fmt "\n", ##__VA_ARGS__); \
- } while(0)
- #define err(...) do { \
- print("error: ", __VA_ARGS__); \
- goto fail; \
- } while(0)
- #define debug(...) print("debug: ", __VA_ARGS__)
- #define msg(...) print("info: ", __VA_ARGS__)
-
struct block_pool *bp = block_pool_new(NULL);
struct test_entry *entries = block_pool_alloc(bp, sizeof(*entries) * count);
- struct test_entry *i, *e = entries+count;
+ struct test_entry *i, *e = entries+count, *o;
char *value_base = block_pool_alloc(bp, count), *value = value_base;
- size_t unique_count = 0;
+ size_t unique_count;
//we use value to track whether an entry has been added or not
memset(value, 0, count);
msg("Generating %zu test entries...", count);
for (i=entries; i<e; value++) {
- char *str = random_string(bp);
+ size_t len;
+ char *str = random_string(bp, &len);
size_t same_count = (random()%5 ? random()%3 : random()%10) + 1;
for (;same_count-- && i<e; i++) {
i->str = str;
+ i->len = len;
i->value = value;
}
}
msg("Inserting/looking up %zu entries...", count);
- for (i=entries; i<e; i++) {
+ for (i=entries, o=entries; i<e; i++) {
char **node;
debug("Looking up %s", i->str);
- node = stringmap_lookup(map, i->str);
+ node = stringmap_lookup_n(map, i->str, i->len);
if (!node) {
if (*i->value)
err("Previously inserted entry not found");
- debug("Not found; entering");
+ debug("Not found; entering %s", i->str);
- node = stringmap_enter(map, i->str);
- if (!node || strcmp(i->str, map.last->str))
+ node = stringmap_enter_n(map, i->str, i->len);
+ if (!node || tecmp(i, (void*)map.last))
err("Node not properly entered");
+ if (map.last->str[map.last->len])
+ err("Entered string not zero-terminated");
*node = i->value;
*i->value = 1; //mark that the entry is entered
- unique_count++;
+ //write this unique entry to the entry list to traverse later
+ *o++ = *i;
} else {
- if (strcmp(i->str, map.last->str))
+ if (tecmp(i, (void*)map.last))
err("lookup returned incorrect string");
+ if (map.last->str[map.last->len])
+ err("Looked-up string not zero-terminated");
if (i->value != *node)
err("lookup returned incorrect value");
if (!*i->value)
}
}
+ unique_count = o-entries;
+
if (map.t.count != unique_count)
err("Map has incorrect count");
- printf("stringmap test passed after %zu inserts, %zu lookups (%zu total operations)\n", unique_count, (i-entries)-unique_count, i-entries);
+ qsort(entries, unique_count, sizeof(*entries), by_str);
+
+ msg("Traversing forward through %zu items", unique_count);
+ if (!test_traverse(&map.t, entries, unique_count, out))
+ err("Traversal does not produce the strings in order");
+
+ printf("stringmap test passed after %zu inserts, %zu lookups (%zu total operations)\n",
+ unique_count, (i-entries)-unique_count, i-entries);
block_pool_free(bp);
stringmap_free(map);
return 1;
fail:
- printf("stringmap test failed after %zu inserts, %zu lookups (%zu total operations)\n", unique_count, (i-entries)-unique_count, i-entries);
+ printf("stringmap test failed after %zu inserts, %zu lookups (%zu total operations)\n",
+ unique_count, (i-entries)-unique_count, i-entries);
block_pool_free(bp);
stringmap_free(map);
return 0;
-
- #undef print
- #undef err
- #undef debug
- #undef msg
}
+#undef print
+#undef err
+#undef debug
+#undef msg
+
int main(void)
{
- plan_tests(10);
+ plan_tests(14);
test_trivial();
- ok1(test_stringmap(10000, NULL));
+ ok1(test_stringmap(10000, stdout));
return exit_status();
}
projects / ccan / blobdiff