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