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