Andrew's git - gitweb.git/blob

   1/*
   2 * test-treap.c: code to exercise the svn importer's treap structure
   3 */
   4
   5#include "cache.h"
   6#include "vcs-svn/obj_pool.h"
   7#include "vcs-svn/trp.h"
   8
   9struct int_node {
  10        uintmax_t n;
  11        struct trp_node children;
  12};
  13
  14obj_pool_gen(node, struct int_node, 3)
  15
  16static int node_cmp(struct int_node *a, struct int_node *b)
  17{
  18        return (a->n > b->n) - (a->n < b->n);
  19}
  20
  21trp_gen(static, treap_, struct int_node, children, node, node_cmp)
  22
  23static void strtonode(struct int_node *item, const char *s)
  24{
  25        char *end;
  26        item->n = strtoumax(s, &end, 10);
  27        if (*s == '\0' || (*end != '\n' && *end != '\0'))
  28                die("invalid integer: %s", s);
  29}
  30
  31int main(int argc, char *argv[])
  32{
  33        struct strbuf sb = STRBUF_INIT;
  34        struct trp_root root = { ~0U };
  35        uint32_t item;
  36
  37        if (argc != 1)
  38                usage("test-treap < ints");
  39
  40        while (strbuf_getline(&sb, stdin, '\n') != EOF) {
  41                struct int_node *node = node_pointer(node_alloc(1));
  42
  43                item = node_offset(node);
  44                strtonode(node, sb.buf);
  45                node = treap_insert(&root, node_pointer(item));
  46                if (node_offset(node) != item)
  47                        die("inserted %"PRIu32" in place of %"PRIu32"",
  48                                node_offset(node), item);
  49        }
  50
  51        item = node_offset(treap_first(&root));
  52        while (~item) {
  53                uint32_t next;
  54                struct int_node *tmp = node_pointer(node_alloc(1));
  55
  56                tmp->n = node_pointer(item)->n;
  57                next = node_offset(treap_next(&root, node_pointer(item)));
  58
  59                treap_remove(&root, node_pointer(item));
  60                item = node_offset(treap_nsearch(&root, tmp));
  61
  62                if (item != next && (!~item || node_pointer(item)->n != tmp->n))
  63                        die("found %"PRIuMAX" in place of %"PRIuMAX"",
  64                                ~item ? node_pointer(item)->n : ~(uintmax_t) 0,
  65                                ~next ? node_pointer(next)->n : ~(uintmax_t) 0);
  66                printf("%"PRIuMAX"\n", tmp->n);
  67        }
  68        node_reset();
  69        return 0;
  70}