string_pool.c

   1 /*
   2  * Licensed under a two-clause BSD-style license.
   3  * See LICENSE for details.
   4  */
   5
   6 #include <string.h>
   7 #include <stdint.h>
   8
   9 #include "trp.h"
  10 #include "obj_pool.h"
  11 #include "string_pool.h"
  12
  13 typedef struct node_s node_t;
  14 static struct trp_root tree = { ~0 };
  15
  16 struct node_s {
  17         uint32_t offset;
  18         struct trp_node children;
  19 };
  20
  21 /* Create two memory pools: one for node_t, and another for strings */
  22 obj_pool_gen(node, node_t, 4096);
  23 obj_pool_gen(string, char, 4096);
  24
  25 static char *node_value(node_t *node)
  26 {
  27         return node ? string_pointer(node->offset) : NULL;
  28 }
  29
  30 static int node_cmp(node_t *a, node_t *b)
  31 {
  32         return strcmp(node_value(a), node_value(b));
  33 }
  34
  35 /* Build a Treap from the node_s structure (a trp_node w/ offset) */
  36 trp_gen(static, tree_, node_t, children, node, node_cmp);
  37
  38 char *pool_fetch(uint32_t entry)
  39 {
  40         return node_value(node_pointer(entry));
  41 }
  42
  43 uint32_t pool_intern(char *key)
  44 {
  45         /* Canonicalize key */
  46         node_t *match = NULL;
  47         uint32_t key_len;
  48         if (key == NULL)
  49                 return ~0;
  50         key_len = strlen(key) + 1;
  51         node_t *node = node_pointer(node_alloc(1));
  52         node->offset = string_alloc(key_len);
  53         strcpy(node_value(node), key);
  54         match = tree_search(&tree, node);
  55         if (!match) {
  56                 tree_insert(&tree, node);
  57         } else {
  58                 node_free(1);
  59                 string_free(key_len);
  60                 node = match;
  61         }
  62         return node_offset(node);
  63 }
  64
  65 uint32_t pool_tok_r(char *str, const char *delim, char **saveptr)
  66 {
  67         char *token = strtok_r(str, delim, saveptr);
  68         return token ? pool_intern(token) : ~0;
  69 }
  70
  71 void pool_print_seq(uint32_t len, uint32_t *seq, char delim, FILE *stream)
  72 {
  73         uint32_t i;
  74         for (i = 0; i < len && ~seq[i]; i++) {
  75                 fputs(pool_fetch(seq[i]), stream);
  76                 if (i < len - 1 && ~seq[i + 1])
  77                         fputc(delim, stream);
  78         }
  79 }
  80
  81 uint32_t pool_tok_seq(uint32_t max, uint32_t *seq, char *delim, char *str)
  82 {
  83         char *context = NULL;
  84         uint32_t length = 0, token = str ? pool_tok_r(str, delim, &context) : ~0;
  85         while (length < max) {
  86                 seq[length++] = token;
  87                 if (token == ~0)
  88                         break;
  89                 token = pool_tok_r(NULL, delim, &context);
  90         }
  91         seq[length ? length - 1 : 0] = ~0;
  92         return length;
  93 }
  94
  95 void pool_init(void)
  96 {
  97         uint32_t node;
  98         node_init();
  99         string_init();
 100         for (node = 0; node < node_pool.size; node++) {
 101                 tree_insert(&tree, node_pointer(node));
 102         }
 103 }
 104
 105 void pool_reset(void)
 106 {
 107         node_reset();
 108         string_reset();
 109 }