Return to idm.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib

Annotation of embedaddon/bird2/lib/idm.c, revision 1.1.1.1

1.1       misho       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: }