src/str_pool.c

   1 /* libmpdclient
   2    (c) 2003-2008 The Music Player Daemon Project
   3    This project's homepage is: http://www.musicpd.org
   4
   5    Redistribution and use in source and binary forms, with or without
   6    modification, are permitted provided that the following conditions
   7    are met:
   8
   9    - Redistributions of source code must retain the above copyright
  10    notice, this list of conditions and the following disclaimer.
  11
  12    - Redistributions in binary form must reproduce the above copyright
  13    notice, this list of conditions and the following disclaimer in the
  14    documentation and/or other materials provided with the distribution.
  15
  16    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19    A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
  20    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  21    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  22    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  23    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  24    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  25    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  26    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27 */
  28
  29 #include "str_pool.h"
  30
  31 #include <assert.h>
  32 #include <stddef.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35
  36 #define NUM_SLOTS 4096
  37
  38 struct slot {
  39         struct slot *next;
  40         unsigned char ref;
  41         char value[1];
  42 } __attribute__((packed));
  43
  44 static struct slot *slots[NUM_SLOTS];
  45
  46 static inline unsigned
  47 calc_hash(const char *p)
  48 {
  49         unsigned hash = 5381;
  50
  51         assert(p != NULL);
  52
  53         while (*p != 0)
  54                 hash = (hash << 5) + hash + *p++;
  55
  56         return hash;
  57 }
  58
  59 static inline struct slot *
  60 value_to_slot(char *value)
  61 {
  62         return (struct slot*)(value - offsetof(struct slot, value));
  63 }
  64
  65 static struct slot *slot_alloc(struct slot *next, const char *value)
  66 {
  67         size_t length = strlen(value);
  68         struct slot *slot = malloc(sizeof(*slot) + length);
  69         if (slot == NULL)
  70                 abort(); /* XXX */
  71
  72         slot->next = next;
  73         slot->ref = 1;
  74         memcpy(slot->value, value, length + 1);
  75         return slot;
  76 }
  77
  78 char *str_pool_get(const char *value)
  79 {
  80         struct slot **slot_p, *slot;
  81
  82         slot_p = &slots[calc_hash(value) % NUM_SLOTS];
  83         for (slot = *slot_p; slot != NULL; slot = slot->next) {
  84                 if (strcmp(value, slot->value) == 0 && slot->ref < 0xff) {
  85                         assert(slot->ref > 0);
  86                         ++slot->ref;
  87                         return slot->value;
  88                 }
  89         }
  90
  91         slot = slot_alloc(*slot_p, value);
  92         *slot_p = slot;
  93         return slot->value;
  94 }
  95
  96 char *str_pool_dup(char *value)
  97 {
  98         struct slot *slot = value_to_slot(value);
  99
 100         assert(slot->ref > 0);
 101
 102         if (slot->ref < 0xff) {
 103                 ++slot->ref;
 104                 return value;
 105         } else {
 106                 /* the reference counter overflows above 0xff;
 107                    duplicate the value, and start with 1 */
 108                 struct slot **slot_p =
 109                         &slots[calc_hash(slot->value) % NUM_SLOTS];
 110                 slot = slot_alloc(*slot_p, slot->value);
 111                 *slot_p = slot;
 112                 return slot->value;
 113         }
 114 }
 115
 116 void str_pool_put(char *value)
 117 {
 118         struct slot **slot_p, *slot;
 119
 120         slot = value_to_slot(value);
 121         assert(slot->ref > 0);
 122         --slot->ref;
 123
 124         if (slot->ref > 0)
 125                 return;
 126
 127         for (slot_p = &slots[calc_hash(value) % NUM_SLOTS];
 128              *slot_p != slot;
 129              slot_p = &(*slot_p)->next) {
 130                 assert(*slot_p != NULL);
 131         }
 132
 133         *slot_p = slot->next;
 134         free(slot);
 135 }