Move ID allocator to a separate file and use it also in OSPF

3 files changed, 104 insertions, 1 deletions

diff --git a/lib/Modules b/lib/Modules
index 21830875..6b9b4b0f 100644
--- a/lib/Modules
+++ b/lib/Modules
@@ -7,8 +7,10 @@ sha1.h
 birdlib.h
 bitops.c
 bitops.h
-ip.h
+idm.c
+idm.h
 ip.c
+ip.h
 lists.c
 lists.h
 md5.c
diff --git a/lib/idm.c b/lib/idm.c
new file mode 100644
index 00000000..16d0e855
--- /dev/null
+++ b/lib/idm.c
@@ -0,0 +1,76 @@
+/*
+ *	BIRD Library -- ID Map
+ *
+ *	(c) 2013--2015 Ondrej Zajicek <santiago@crfreenet.org>
+ *	(c) 2013--2015 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include <stdlib.h>
+
+#include "nest/bird.h"
+#include "lib/idm.h"
+#include "lib/resource.h"
+#include "lib/string.h"
+
+
+void
+idm_init(struct idm *m, pool *p, uint size)
+{
+  m->pos = 0;
+  m->used = 1;
+  m->size = size;
+  m->data = mb_allocz(p, m->size * sizeof(u32));
+
+  /* ID 0 is reserved */
+  m->data[0] = 1;
+}
+
+static inline int u32_cto(uint x) { return ffs(~x) - 1; }
+
+u32
+idm_alloc(struct idm *m)
+{
+  uint i, j;
+
+  for (i = m->pos; i < m->size; i++)
+    if (m->data[i] != 0xffffffff)
+      goto found;
+
+  /* If we are at least 7/8 full, expand */
+  if (m->used > (m->size * 28))
+  {
+    m->size *= 2;
+    m->data = mb_realloc(m->data, m->size * sizeof(u32));
+    memset(m->data + i, 0, (m->size - i) * sizeof(u32));
+    goto found;
+  }
+
+  for (i = 0; i < m->pos; i++)
+    if (m->data[i] != 0xffffffff)
+      goto found;
+
+  ASSERT(0);
+
+ found:
+  ASSERT(i < 0x8000000);
+
+  m->pos = i;
+  j = u32_cto(m->data[i]);
+
+  m->data[i] |= (1 << j);
+  m->used++;
+  return 32 * i + j;
+}
+
+void
+idm_free(struct idm *m, u32 id)
+{
+  uint i = id / 32;
+  uint j = id % 32;
+
+  ASSERT((i < m->size) && (m->data[i] & (1 << j)));
+  m->data[i] &= ~(1 << j);
+  m->used--;
+}
diff --git a/lib/idm.h b/lib/idm.h
new file mode 100644
index 00000000..e3380cce
--- /dev/null
+++ b/lib/idm.h
@@ -0,0 +1,25 @@
+/*
+ *	BIRD Library -- ID Map
+ *
+ *	(c) 2013--2015 Ondrej Zajicek <santiago@crfreenet.org>
+ *	(c) 2013--2015 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#ifndef _BIRD_IDM_H_
+#define _BIRD_IDM_H_
+
+struct idm
+{
+  u32 *data;
+  u32 pos;
+  u32 used;
+  u32 size;
+};
+
+void idm_init(struct idm *m, pool *p, uint size);
+u32 idm_alloc(struct idm *m);
+void idm_free(struct idm *m, u32 id);
+
+#endif