1 /*
2 * BIRD Library -- ID Map
3 *
4 * (c) 2013--2015 Ondrej Zajicek <santiago@crfreenet.org>
5 * (c) 2013--2015 CZ.NIC z.s.p.o.
6 *
7 * Can be freely distributed and used under the terms of the GNU GPL.
8 */
9
10 #include <stdlib.h>
11
12 #include "nest/bird.h"
13 #include "lib/idm.h"
14 #include "lib/resource.h"
15 #include "lib/string.h"
16
17
18 void
idm_init(struct idm * m,pool * p,uint size)19 idm_init(struct idm *m, pool *p, uint size)
20 {
21 m->pos = 0;
22 m->used = 1;
23 m->size = size;
24 m->data = mb_allocz(p, m->size * sizeof(u32));
25
26 /* ID 0 is reserved */
27 m->data[0] = 1;
28 }
29
u32_cto(uint x)30 static inline int u32_cto(uint x) { return ffs(~x) - 1; }
31
32 u32
idm_alloc(struct idm * m)33 idm_alloc(struct idm *m)
34 {
35 uint i, j;
36
37 for (i = m->pos; i < m->size; i++)
38 if (m->data[i] != 0xffffffff)
39 goto found;
40
41 /* If we are at least 7/8 full, expand */
42 if (m->used > (m->size * 28))
43 {
44 m->size *= 2;
45 m->data = mb_realloc(m->data, m->size * sizeof(u32));
46 memset(m->data + i, 0, (m->size - i) * sizeof(u32));
47 goto found;
48 }
49
50 for (i = 0; i < m->pos; i++)
51 if (m->data[i] != 0xffffffff)
52 goto found;
53
54 ASSERT(0);
55
56 found:
57 ASSERT(i < 0x8000000);
58
59 m->pos = i;
60 j = u32_cto(m->data[i]);
61
62 m->data[i] |= (1 << j);
63 m->used++;
64 return 32 * i + j;
65 }
66
67 void
idm_free(struct idm * m,u32 id)68 idm_free(struct idm *m, u32 id)
69 {
70 uint i = id / 32;
71 uint j = id % 32;
72
73 ASSERT((i < m->size) && (m->data[i] & (1 << j)));
74 m->data[i] &= ~(1 << j);
75 m->used--;
76 }
77