chiark - git - mdw - xyla/blob - t/example.c

   1 /* simple example of a search tree with string keys and indexing */
   2
   3 #include <assert.h>
   4 #include <ctype.h>
   5 #include <errno.h>
   6 #include <stdarg.h>
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10
  11 #include "lib.h"
  12
  13 #include "bt.h"
  14 #include "avl.h"
  15
  16 struct node {
  17   struct xyla_avl_node avl;             /* intrusion */
  18   char *key, *value;                    /* string key and value */
  19   size_t n;                             /* subtree node count */
  20 };
  21
  22 static NORETURN PRINTF_LIKE(1, 2) void bail(const char *msg, ...)
  23 {
  24   /* Print a `printf'-style message MSG to stderr and exit nonzero. */
  25   va_list ap;
  26
  27   va_start(ap, msg); vfprintf(stderr, msg, ap); va_end(ap);
  28   fputc('\n', stderr); exit(2);
  29 }
  30
  31 static void idx_upd(struct xyla_bt_nodecls *cls, struct xyla_bt_node *node)
  32 {
  33   /* Update function to maintain the node count. */
  34
  35   struct node *n = (struct node *)node,
  36     *l = (struct node *)n->avl.bt.left,
  37     *r = (struct node *)n->avl.bt.right;
  38
  39   /* The node count is one more than the sum of the child node counts. */
  40   n->n = 1 + (l ? l->n : 0) + (r ? r->n : 0);
  41 }
  42
  43 static int str_nav(struct xyla_bt_nodecls *cls,
  44                    const struct xyla_bt_node *node, void *arg)
  45 {
  46   /* Navigation function to search by string key. */
  47
  48   const struct node *n = (const struct node *)node;
  49   const char *k = arg;
  50
  51   return (strcmp(k, n->key));
  52 }
  53
  54 static int idx_nav(struct xyla_bt_nodecls *cls,
  55                    const struct xyla_bt_node *node, void *arg)
  56 {
  57   /* Navigation function to search by integer index. */
  58
  59   const struct node *n = (const struct node *)node,
  60     *l = (const struct node *)n->avl.bt.left;
  61   size_t *i_inout = arg, i = *i_inout, ln;
  62
  63   /* Invariant: *I_INOUT is the index of the node we want /within/ the
  64    * current subtree.
  65    */
  66
  67   if (l) {
  68     /* The left subtree is not empty.  If i is less than the left-subtree's
  69      * node count, then the node we want is in there.  Otherwise, adjust the
  70      * index so that it counts from this node.
  71      */
  72
  73     ln = l->n;
  74     if (i < ln) return (-1);
  75     else i -= ln;
  76   }
  77
  78   /* If the index is now zero, then it's this node that we want.  Otherwise,
  79    * subtract off one, for this node, and continue the search into the right
  80    * subtree.
  81    */
  82   if (!i) return (0);
  83   else { *i_inout = i - 1; return (+1); }
  84 }
  85
  86 static const void *str_key(struct xyla_bt_nodecls *cls,
  87                            const struct xyla_bt_node *node)
  88 {
  89   /* String key projection. */
  90
  91   const struct node *n = (const struct node *)node;
  92
  93   return (n->key);
  94 }
  95
  96 static int node_chk(unsigned op, const struct xyla_bt_check *chk)
  97 {
  98   /* Node checking function. */
  99
 100   const struct node *node, *left, *right;
 101   size_t n;
 102   int rc = XYLA_RC_OK, subrc;
 103
 104   if (op == XYLA_CHKOP_AFTER) {
 105     /* Children are checked, so check the parent. */
 106
 107     /* Check the node count. */
 108     node = (const struct node *)chk->node;
 109     left = (const struct node *)chk->left;
 110     right = (const struct node *)chk->right;
 111     n = 1 + (left ? left->n : 0) + (right ? right->n : 0);
 112     if (node->n != n) {
 113       if (chk->fp) {
 114         xyla_bt_bughdr("EXAMPLE", chk->root, chk->fp);
 115         fputs("node ", chk->fp);
 116         xyla_bt_printnode(chk->cls, &node->avl.bt, chk->fp);
 117         fprintf(chk->fp, " count %lu /= %lu expected\n",
 118                 (unsigned long)node->n, (unsigned long)n);
 119       }
 120       rc = XYLA_RC_BAD;
 121     }
 122   }
 123
 124   /* Check ordering. */
 125   subrc = xyla_bt_chkorder(op, chk);
 126     if (!subrc);
 127     else if (subrc == XYLA_RC_BAD) rc = subrc;
 128     else return (subrc);
 129   return (rc);
 130 }
 131
 132 static void node_id(struct xyla_bt_nodecls *cls,
 133                     const struct xyla_bt_node *node, FILE *fp)
 134 {
 135   const struct node *n = (const struct node *)n;
 136
 137   fprintf(fp, "#<node `%s' = `%s'>", n->key, n->value);
 138 }
 139
 140 /* Node class operations. */
 141 static const struct xyla_bt_chkops node_ops = {
 142   { sizeof(node_ops), idx_upd },
 143   { str_nav, str_key },
 144   { node_chk, sizeof(struct xyla_bt_ordinfo), node_id }
 145 };
 146
 147 static int idx_ascend(struct xyla_bt_node *node,
 148                       struct xyla_bt_node *parent,
 149                       struct xyla_bt_node *sibling,
 150                       unsigned pos, void *arg)
 151 {
 152   /* Ascension function to determine a node's index. */
 153
 154   const struct node *s = (const struct node *)sibling;
 155   size_t *i_inout = arg;
 156
 157   /* Invariant: *I_INOUT is the index of the original node within the
 158    * subtree rooted at NODE.
 159    */
 160
 161   /* Update the index ready for its parent.  If we're the left child, then
 162    * there's nothing to do.  Otherwise, there's the parent, and its left
 163    * subtree before us.
 164    */
 165   if (pos == XYLA_BTPOS_RIGHT) *i_inout += 1 + (s ? s->n : 0);
 166   return (0);
 167 }
 168
 169 static size_t read_index(const char *p)
 170 {
 171   char *q;
 172   unsigned long n;
 173
 174   errno = 0;
 175   if (!isdigit((unsigned char)*p)) bail("integer expected");
 176   n = strtoul(p, &q, 0);
 177   if (errno || *q) bail("integer expected");
 178   if (n > (size_t)-1) bail("out of range");
 179   return (n);
 180 }
 181
 182 int main(void)
 183 {
 184   struct xyla_bt_node *root = 0;        /* tree root */
 185   struct xyla_bt_nodecls cls;           /* node class */
 186   struct xyla_avl_iter it;              /* iterator */
 187   struct xyla_avl_path path;            /* path for insert, remove, ascend */
 188   struct node *node;                    /* a node pointer */
 189   const struct node *t;                 /* a temporary node pointer */
 190   char buf[256]; size_t len;            /* input buffer and line length */
 191   char *p, *q;                          /* cursors for parsing input line */
 192   size_t kn, vn;                        /* key and value lengths */
 193   size_t i, j;                          /* indices */
 194   size_t n;                             /* total node count */
 195   int rc;                               /* return code */
 196
 197   /* Establish the node class operations. */
 198   cls.ops = &node_ops.node;
 199
 200   while (fgets(buf, sizeof(buf), stdin)) {
 201     /* Read command lines from stdin and process them. */
 202
 203     /* Check for overrun and chomp the trailing newline. */
 204     len = strlen(buf); assert(len);
 205       if (buf[len - 1] != '\n') bail("line too long");
 206     p = buf; buf[--len] = 0;
 207
 208     /* Dispatch based on the first character. */
 209     if (*p == ';' || !*p) {
 210       /* ;COMMENT | EMPTY -- copy to output. */
 211
 212       puts(buf);
 213     } else if (*p == '?') {
 214       /* ?KEY | ?#INDEX -- print the node with KEY, or at INDEX. */
 215
 216       p++;
 217       if (*p == '#') {
 218         /* Lookup by index. */
 219
 220         /* Read and check the index. */
 221         p++; i = read_index(p);
 222         n = root ? ((const struct node *)root)->n : 0;
 223         if (i >= n) { fputs("(out of range)\n", stdout); goto next; }
 224
 225         /* Find the right node.  This clobbers the provided index, so work on
 226          * a copy.  We don't need a path, so `lookup' is good enough.
 227          */
 228         j = i; node = xyla_avl_lookup(&cls, &root, idx_nav, &j);
 229           assert(node);
 230       } else {
 231         /* Lookup by key. */
 232
 233         /* Find the node.  We'll need the path to find the index, so `probe'
 234          * here.
 235          */
 236         node = xyla_avl_probe(&cls, &root, 0, p, &path);
 237         if (!node) { fputs("(not found)\n", stdout); goto next; }
 238
 239         /* Discover the node index.  The ascension invariant is that `i'
 240          * holds the index of the target node within the subtree rooted at
 241          * the current node.
 242          */
 243         t = (struct node *)node->avl.bt.left; i = t ? t->n : 0;
 244         rc = xyla_avl_ascend(idx_ascend, &path, &i); assert(!rc);
 245       }
 246
 247       /* Print the node. */
 248       printf("[%lu]: %s -> %s\n", (unsigned long)i, node->key, node->value);
 249     } else if (*p == '-') {
 250       /* -KEY | -#INDEX -- remove the node with KEY or at INDEX. */
 251
 252       p++;
 253       if (*p == '#') {
 254         /* Lookup by index. */
 255
 256         /* Read and check the index. */
 257         p++; i = read_index(p);
 258         n = root ? ((const struct node *)root)->n : 0;
 259         if (i >= n) { fputs("(out of range)\n", stdout); goto next; }
 260
 261         /* Find the right node.  We'll need the path to remove the node, so
 262          * `probe'.
 263          */
 264         node = xyla_avl_probe(&cls, &root, idx_nav, &i, &path); assert(node);
 265       } else {
 266         /* Lookup by key. */
 267
 268         /* Find the node.  Again, `probe', because we need the path to remove
 269          * the node.
 270          */
 271         node = xyla_avl_probe(&cls, &root, 0, p, &path);
 272         if (!node) { fputs("(not found)\n", stdout); goto next; }
 273       }
 274
 275       /* Remove the node from the tree and update the count. */
 276       xyla_avl_remove(&cls, &path);
 277
 278       /* Free the node. */
 279       free(node->key); free(node->value); free(node);
 280     } else if (*p == '*' && !p[1]) {
 281       /* * -- print all of the nodes in order. */
 282
 283       /* Parallel iteration over the nodes and index. */
 284       for (xyla_avl_inititer(root, &it), i = 0;
 285            !!(node = xyla_avl_next(&it));
 286            i++)
 287         printf("[%lu]: %s -> %s\n",
 288                (unsigned long)i, node->key, node->value);
 289     } else {
 290       /* [+]KEY=VALUE | #INDEX=VALUE -- set the VALUE of the node with KEY or
 291        * at VALUE; if there is no node with KEY, insert a new one.
 292        */
 293
 294       if (*p == '#') {
 295         /* Lookup by index. */
 296
 297         /* Read the index and value, and check the index. */
 298         p++; q = strchr(p, '='); if (!q) bail("missing `='");
 299         *q++ = 0; i = read_index(p); vn = strlen(q);
 300         n = root ? ((const struct node *)root)->n : 0;
 301         if (i >= n) { fputs("out of range)\n", stdout); goto next; }
 302
 303         /* Find the right node.  It must exist, so we won't need to insert,
 304          * so we can use `lookup' here.
 305          */
 306         node = xyla_avl_lookup(&cls, &root, idx_nav, &i); assert(node);
 307
 308         /* We're going to replace the node's value, so free the old one. */
 309         free(node->value);
 310       } else {
 311         /* Lookup by key. */
 312
 313         /* Read the key and value. */
 314         if (*p == '+') p++;
 315         q = strchr(p, '='); if (!q) bail("unknown command");
 316         *q++ = 0; kn = strlen(p); vn = strlen(q);
 317
 318         /* Find the right node.  If there isn't one, then we'll insert a new
 319          * one, so we'll need a path, and must use `probe'.
 320          */
 321         node = xyla_avl_probe(&cls, &root, 0, p, &path);
 322
 323         if (node) {
 324           /* The node exists.  Free its old value so we can replace it. */
 325
 326           free(node->value);
 327         } else {
 328           /* There's no existing node, so we must create and insert a new
 329            * one.
 330            */
 331
 332           /* Make the new node and fill in the key.  We'll set the value in
 333            * the common epilogue below.
 334            */
 335           node = malloc(sizeof(struct node));
 336             if (!node) bail("out of memory");
 337           node->key = malloc(kn + 1); if (!node->key) bail("out of memory");
 338           memcpy(node->key, p, kn + 1);
 339
 340           /* Insert the new node and bump the node count. */
 341           xyla_avl_insert(&cls, &path, &node->avl);
 342         }
 343       }
 344
 345       /* Set the node value. */
 346       node->value = malloc(vn + 1); if (!node->key) bail("out of memory");
 347       memcpy(node->value, q, vn + 1);
 348     }
 349
 350   next:;
 351   }
 352
 353   /* Check that the final tree is well-formed. */
 354   if (xyla_avl_check(&cls, &root, stderr, 0, -1, 0))
 355     bail("tree corrupted");
 356
 357   /* Free all of the nodes. */
 358   while (!!(node = xyla_bt_severfirst(&root)))
 359     { free(node->key); free(node->value); free(node); }
 360
 361   /* Check that all of the I/O worked properly. */
 362   if (ferror(stdin))
 363     bail("input error: %s", strerror(errno));
 364   if (fflush(stdout) || ferror(stdout))
 365     bail("output error: %s", strerror(errno));
 366
 367   /* All done. */
 368   return (0);
 369 }