1 /*
2 * Copyright (c) 2013, Bjorn Andersson <bjorn@kryo.se>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * 3. Neither the name of the copyright holder nor the names of its contributors
16 * may be used to endorse or promote products derived from this software without
17 * specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #include <assert.h>
33 #include <stdlib.h>
34 #include <stdio.h>
35 #include <string.h>
36
37 #include "assoc.h"
38
assoc_hash(const char * value)39 static unsigned long assoc_hash(const char *value)
40 {
41 unsigned long hash = 0;
42 unsigned long g;
43 const char *v = value;
44
45 while (*v) {
46 hash = (hash << 4) + *(v++);
47 g = hash & 0xF0000000L;
48 if (g)
49 hash ^= g >> 24;
50 hash &= ~g;
51 }
52
53 return hash;
54 }
55
assoc_init(struct assoc * assoc,unsigned long size)56 void assoc_init(struct assoc *assoc, unsigned long size)
57 {
58 assert(size > 0);
59
60 assoc->size = size;
61 assoc->fill = 0;
62 assoc->keys = calloc(size, sizeof(const char *));
63 assoc->values = malloc(size * sizeof(void *));
64 }
65
assoc_get(struct assoc * assoc,const char * key)66 void *assoc_get(struct assoc *assoc, const char *key)
67 {
68 unsigned long hash;
69
70 hash = assoc_hash(key) % assoc->size;
71 while (assoc->keys[hash]) {
72 if (!strcmp(assoc->keys[hash], key))
73 return assoc->values[hash];
74
75 hash = (hash + 1) % assoc->size;
76 }
77
78 return NULL;
79 }
80
_assoc_set(struct assoc * assoc,const char * key,void * value)81 static void _assoc_set(struct assoc *assoc, const char *key, void *value)
82 {
83 struct assoc new_set;
84 unsigned long hash;
85 unsigned long i;
86
87 assert(assoc->fill < assoc->size);
88
89 /* Grow set at 80% utilization */
90 if (5 * assoc->fill > 4 * assoc->size) {
91 assoc_init(&new_set, assoc->size * 5 / 4);
92
93 for (i = 0; i < assoc->size; i++)
94 if (assoc->keys[i])
95 assoc_set(&new_set, assoc->keys[i],
96 assoc->values[i]);
97
98 free(assoc->keys);
99 free(assoc->values);
100
101 assoc->keys = new_set.keys;
102 assoc->values = new_set.values;
103 assoc->fill = new_set.fill;
104 assoc->size = new_set.size;
105 }
106
107 hash = assoc_hash(key) % assoc->size;
108 while (assoc->keys[hash]) {
109 if (!strcmp(assoc->keys[hash], key)) {
110 assoc->values[hash] = value;
111 return;
112 }
113
114 hash = (hash + 1) % assoc->size;
115 }
116
117 assoc->keys[hash] = key;
118 assoc->values[hash] = value;
119 assoc->fill++;
120 }
121
assoc_set(struct assoc * assoc,const char * key,void * value)122 void assoc_set(struct assoc *assoc, const char *key, void *value)
123 {
124 _assoc_set(assoc, strdup(key), value);
125 }
126
assoc_next(struct assoc * assoc,void ** value,unsigned long * iter)127 const char *assoc_next(struct assoc *assoc, void **value, unsigned long *iter)
128 {
129 unsigned long it = *iter;
130
131 while (it < assoc->size && !assoc->keys[it])
132 it++;
133
134 if (it == assoc->size)
135 return NULL;
136
137 *iter = it + 1;
138
139 if (it < assoc->size) {
140 if (value)
141 *value = assoc->values[it];
142 return assoc->keys[it];
143 } else {
144 return NULL;
145 }
146 }
147
assoc_destroy(struct assoc * assoc)148 void assoc_destroy(struct assoc *assoc)
149 {
150 unsigned long i;
151
152 for (i = 0; i < assoc->size; i++)
153 free((void*)assoc->keys[i]);
154
155 free(assoc->keys);
156 free(assoc->values);
157 assoc->size = 0;
158 }
159