Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / lib / idm.c @ 6b3f1a54

History | View | Annotate | Download (1.32 KB)

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
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
}