iofbird / bird2.0.1 / lib / idm.c @ 6b3f1a54
History  View  Annotate  Download (1.32 KB)
1 
/*


2 
* BIRD Library  ID Map

3 
*

4 
* (c) 20132015 Ondrej Zajicek <santiago@crfreenet.org>

5 
* (c) 20132015 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

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  
30 
static inline int u32_cto(uint x) { return ffs(~x)  1; } 
31  
32 
u32 
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

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 
} 