1 /* ncmpc
2 * Copyright (C) 2008 Max Kellermann <max@duempel.org>
3 * This project's homepage is: http://www.musicpd.org
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
19 #include "str_pool.h"
21 #include <assert.h>
22 #include <stddef.h>
23 #include <stdlib.h>
24 #include <string.h>
26 #define NUM_SLOTS 4096
28 struct slot {
29 struct slot *next;
30 unsigned char ref;
31 char value[1];
32 } __attribute__((packed));
34 struct slot *slots[NUM_SLOTS];
36 static inline unsigned
37 calc_hash(const char *p)
38 {
39 unsigned hash = 5381;
41 assert(p != NULL);
43 while (*p != 0)
44 hash = (hash << 5) + hash + *p++;
46 return hash;
47 }
49 static inline struct slot *
50 value_to_slot(char *value)
51 {
52 return (struct slot*)(value - offsetof(struct slot, value));
53 }
55 static struct slot *slot_alloc(struct slot *next, const char *value)
56 {
57 size_t length = strlen(value);
58 struct slot *slot = malloc(sizeof(*slot) + length);
59 if (slot == NULL)
60 abort(); /* XXX */
62 slot->next = next;
63 slot->ref = 1;
64 memcpy(slot->value, value, length + 1);
65 return slot;
66 }
68 char *str_pool_get(const char *value)
69 {
70 struct slot **slot_p, *slot;
72 slot_p = &slots[calc_hash(value) % NUM_SLOTS];
73 for (slot = *slot_p; slot != NULL; slot = slot->next) {
74 if (strcmp(value, slot->value) == 0 && slot->ref < 0xff) {
75 assert(slot->ref > 0);
76 ++slot->ref;
77 return slot->value;
78 }
79 }
81 slot = slot_alloc(*slot_p, value);
82 *slot_p = slot;
83 return slot->value;
84 }
86 char *str_pool_dup(char *value)
87 {
88 struct slot *slot = value_to_slot(value);
90 assert(slot->ref > 0);
92 if (slot->ref < 0xff) {
93 ++slot->ref;
94 return value;
95 } else {
96 /* the reference counter overflows above 0xff;
97 duplicate the value, and start with 1 */
98 struct slot **slot_p =
99 &slots[calc_hash(slot->value) % NUM_SLOTS];
100 slot = slot_alloc(*slot_p, slot->value);
101 *slot_p = slot;
102 return slot->value;
103 }
104 }
106 void str_pool_put(char *value)
107 {
108 struct slot **slot_p, *slot;
110 slot = value_to_slot(value);
111 assert(slot->ref > 0);
112 --slot->ref;
114 if (slot->ref > 0)
115 return;
117 for (slot_p = &slots[calc_hash(value) % NUM_SLOTS];
118 *slot_p != slot;
119 slot_p = &(*slot_p)->next) {
120 assert(*slot_p != NULL);
121 }
123 *slot_p = slot->next;
124 free(slot);
125 }