iofbirddaemon / proto / bgp / map.c @ ef5081af
History  View  Annotate  Download (4.14 KB)
1 
/**


2 
* Copyright (c) 2014 rxi

3 
*

4 
* This library is free software; you can redistribute it and/or modify it

5 
* under the terms of the MIT license. See LICENSE for details.

6 
*/

7  
8 
#include <stdlib.h> 
9 
#include <string.h> 
10 
#include "map.h" 
11  
12 
struct map_node_t {

13 
unsigned hash;

14 
void *value;

15 
map_node_t *next; 
16 
/* char key[]; */

17 
/* char value[]; */

18 
}; 
19  
20  
21 
static unsigned map_hash(const char *str) { 
22 
unsigned hash = 5381; 
23 
while (*str) {

24 
hash = ((hash << 5) + hash) ^ *str++;

25 
} 
26 
return hash;

27 
} 
28  
29  
30 
static map_node_t *map_newnode(const char *key, void *value, int vsize) { 
31 
map_node_t *node; 
32 
int ksize = strlen(key) + 1; 
33 
int voffset = ksize + ((sizeof(void*)  ksize) % sizeof(void*)); 
34 
node = malloc(sizeof(*node) + voffset + vsize);

35 
if (!node) return NULL; 
36 
memcpy(node + 1, key, ksize);

37 
node>hash = map_hash(key); 
38 
node>value = ((char*) (node + 1)) + voffset; 
39 
memcpy(node>value, value, vsize); 
40 
return node;

41 
} 
42  
43  
44 
static int map_bucketidx(map_base_t *m, unsigned hash) { 
45 
/* If the implementation is changed to allow a nonpowerof2 bucket count,

46 
* the line below should be changed to use mod instead of AND */

47 
return hash & (m>nbuckets  1); 
48 
} 
49  
50  
51 
static void map_addnode(map_base_t *m, map_node_t *node) { 
52 
int n = map_bucketidx(m, node>hash);

53 
node>next = m>buckets[n]; 
54 
m>buckets[n] = node; 
55 
} 
56  
57  
58 
static int map_resize(map_base_t *m, int nbuckets) { 
59 
map_node_t *nodes, *node, *next; 
60 
map_node_t **buckets; 
61 
int i;

62 
/* Chain all nodes together */

63 
nodes = NULL;

64 
i = m>nbuckets; 
65 
while (i) {

66 
node = (m>buckets)[i]; 
67 
while (node) {

68 
next = node>next; 
69 
node>next = nodes; 
70 
nodes = node; 
71 
node = next; 
72 
} 
73 
} 
74 
/* Reset buckets */

75 
buckets = realloc(m>buckets, sizeof(*m>buckets) * nbuckets);

76 
if (buckets != NULL) { 
77 
m>buckets = buckets; 
78 
m>nbuckets = nbuckets; 
79 
} 
80 
if (m>buckets) {

81 
memset(m>buckets, 0, sizeof(*m>buckets) * m>nbuckets); 
82 
/* Readd nodes to buckets */

83 
node = nodes; 
84 
while (node) {

85 
next = node>next; 
86 
map_addnode(m, node); 
87 
node = next; 
88 
} 
89 
} 
90 
/* Return error code if realloc() failed */

91 
return (buckets == NULL) ? 1 : 0; 
92 
} 
93  
94  
95 
static map_node_t **map_getref(map_base_t *m, const char *key) { 
96 
unsigned hash = map_hash(key);

97 
map_node_t **next; 
98 
if (m>nbuckets > 0) { 
99 
next = &m>buckets[map_bucketidx(m, hash)]; 
100 
while (*next) {

101 
if ((*next)>hash == hash && !strcmp((char*) (*next + 1), key)) { 
102 
return next;

103 
} 
104 
next = &(*next)>next; 
105 
} 
106 
} 
107 
return NULL; 
108 
} 
109  
110  
111 
void map_deinit_(map_base_t *m) {

112 
map_node_t *next, *node; 
113 
int i;

114 
i = m>nbuckets; 
115 
while (i) {

116 
node = m>buckets[i]; 
117 
while (node) {

118 
next = node>next; 
119 
free(node); 
120 
node = next; 
121 
} 
122 
} 
123 
free(m>buckets); 
124 
} 
125  
126  
127 
void *map_get_(map_base_t *m, const char *key) { 
128 
map_node_t **next = map_getref(m, key); 
129 
return next ? (*next)>value : NULL; 
130 
} 
131  
132  
133 
int map_set_(map_base_t *m, const char *key, void *value, int vsize) { 
134 
int n, err;

135 
map_node_t **next, *node; 
136 
/* Find & replace existing node */

137 
next = map_getref(m, key); 
138 
if (next) {

139 
memcpy((*next)>value, value, vsize); 
140 
return 0; 
141 
} 
142 
/* Add new node */

143 
node = map_newnode(key, value, vsize); 
144 
if (node == NULL) goto fail; 
145 
if (m>nnodes >= m>nbuckets) {

146 
n = (m>nbuckets > 0) ? (m>nbuckets << 1) : 1; 
147 
err = map_resize(m, n); 
148 
if (err) goto fail; 
149 
} 
150 
map_addnode(m, node); 
151 
m>nnodes++; 
152 
return 0; 
153 
fail:

154 
if (node) free(node);

155 
return 1; 
156 
} 
157  
158  
159 
void map_remove_(map_base_t *m, const char *key) { 
160 
map_node_t *node; 
161 
map_node_t **next = map_getref(m, key); 
162 
if (next) {

163 
node = *next; 
164 
*next = (*next)>next; 
165 
free(node); 
166 
m>nnodes; 
167 
} 
168 
} 
169  
170  
171 
map_iter_t map_iter_(void) {

172 
map_iter_t iter; 
173 
iter.bucketidx = 1;

174 
iter.node = NULL;

175 
return iter;

176 
} 
177  
178  
179 
const char *map_next_(map_base_t *m, map_iter_t *iter) { 
180 
if (iter>node) {

181 
iter>node = iter>node>next; 
182 
if (iter>node == NULL) goto nextBucket; 
183 
} else {

184 
nextBucket:

185 
do {

186 
if (++iter>bucketidx >= m>nbuckets) {

187 
return NULL; 
188 
} 
189 
iter>node = m>buckets[iter>bucketidx]; 
190 
} while (iter>node == NULL); 
191 
} 
192 
return (char*) (iter>node + 1); 
193 
} 