string_pool.c

   1 /******************************************************************************
   2  *
   3  * Copyright (C) 2010 David Barr <david.barr@cordelta.com>.
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice(s), this list of conditions and the following disclaimer
  11  *    unmodified other than the allowable addition of one or more
  12  *    copyright notices.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice(s), this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
  19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  21  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
  22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  25  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  26  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
  27  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  28  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  *
  30  ******************************************************************************/
  31
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <stdbool.h>
  35 #include <stdint.h>
  36 #include <string.h>
  37
  38 #define NDEBUG
  39 #include <assert.h>
  40 #include "trp.h"
  41 #include "obj_pool.h"
  42 #include "string_pool.h"
  43
  44 typedef struct node_s node_t;
  45
  46 struct node_s {
  47     uint32_t offset;
  48      trp_node(node_t) children;
  49 };
  50
  51 typedef trp(node_t) tree_t;
  52
  53 static tree_t tree = { ~0 };
  54
  55 obj_pool_gen(node, node_t, 4096);
  56 obj_pool_gen(string, char, 4096);
  57
  58 static char *node_value(node_t * node)
  59 {
  60     return node ? string_pointer(node->offset) : NULL;
  61 }
  62
  63 static int node_value_cmp(node_t * a, node_t * b)
  64 {
  65     return strcmp(node_value(a), node_value(b));
  66 }
  67
  68 static int node_indentity_cmp(node_t * a, node_t * b)
  69 {
  70     int r = node_value_cmp(a, b);
  71     return r ? r : (((uintptr_t) a) > ((uintptr_t) b))
  72         - (((uintptr_t) a) < ((uintptr_t) b));
  73 }
  74
  75 trp_gen(static, tree_, tree_t, node_t, children, node,
  76         node_indentity_cmp);
  77
  78 static char *pool_fetch(uint32_t entry)
  79 {
  80     return node_value(node_pointer(entry));
  81 }
  82
  83 uint32_t pool_intern(char *key)
  84 {
  85     node_t *match = NULL;
  86     uint32_t key_len = strlen(key) + 1;
  87     node_t *node = node_pointer(node_alloc(1));
  88     node->offset = string_alloc(key_len);
  89     strcpy(node_value(node), key);
  90     match = tree_psearch(&tree, node);
  91     if (!match || node_value_cmp(node, match)) {
  92         tree_insert(&tree, node);
  93     } else {
  94         node_free(1);
  95         string_free(key_len);
  96         node = match;
  97     }
  98     return node_offset(node);
  99 }
 100
 101 uint32_t pool_tok_r(char *str, const char *delim, char **saveptr)
 102 {
 103     char *token = strtok_r(str, delim, saveptr);
 104     return token ? pool_intern(token) : ~0;
 105 }
 106
 107 void pool_print_seq(uint32_t len, uint32_t * seq, char delim, FILE * stream)
 108 {
 109     uint32_t i;
 110     for (i = 0; i < len; i++) {
 111         fputs(pool_fetch(seq[i]), stream);
 112         if (i < len - 1)
 113             fputc(delim, stream);
 114     }
 115 }
 116