Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / proto / bgp / map.c @ 6b3f1a54

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 non-power-of-2 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
    /* Re-add 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
}