Return to idm.c CVS log

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

bird2 ver 2.0.7

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