summaryrefslogtreecommitdiffstats
path: root/lib/id_alloc.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--lib/id_alloc.h98
1 files changed, 98 insertions, 0 deletions
diff --git a/lib/id_alloc.h b/lib/id_alloc.h
new file mode 100644
index 0000000..8705ffb
--- /dev/null
+++ b/lib/id_alloc.h
@@ -0,0 +1,98 @@
+/*
+ * FRR ID Number Allocator
+ * Copyright (C) 2018 Amazon.com, Inc. or its affiliates
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 2 of the License, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; see the file COPYING; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef _ZEBRA_ID_ALLOC_H
+#define _ZEBRA_ID_ALLOC_H
+
+#include <strings.h>
+#include <limits.h>
+#include <stdint.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define IDALLOC_INVALID 0
+
+#define IDALLOC_DIR_BITS 8
+#define IDALLOC_SUBDIR_BITS 7
+#define IDALLOC_PAGE_BITS 7
+#define IDALLOC_WORD_BITS 5
+#define IDALLOC_OFFSET_BITS 5
+
+#define IDALLOC_DIR_COUNT (1 << IDALLOC_DIR_BITS)
+#define IDALLOC_SUBDIR_COUNT (1 << IDALLOC_SUBDIR_BITS)
+#define IDALLOC_PAGE_COUNT (1 << IDALLOC_PAGE_BITS)
+#define IDALLOC_WORD_COUNT (1 << IDALLOC_WORD_BITS)
+
+struct id_alloc_page {
+ /* Bitmask of allocations. 1s indicates the ID is already allocated. */
+ uint32_t allocated_mask[IDALLOC_WORD_COUNT];
+
+ /* Bitmask for free space in allocated_mask. 1s indicate whole 32 bit
+ * section is full.
+ */
+ uint32_t full_word_mask;
+
+ /* The ID that bit 0 in allocated_mask corresponds to. */
+ uint32_t base_value;
+
+ struct id_alloc_page
+ *next_has_free; /* Next page with at least one bit open */
+};
+
+struct id_alloc_subdir {
+ struct id_alloc_page *sublevels[IDALLOC_PAGE_COUNT];
+};
+
+struct id_alloc_dir {
+ struct id_alloc_subdir *sublevels[IDALLOC_SUBDIR_COUNT];
+};
+
+struct id_alloc {
+ struct id_alloc_dir *sublevels[IDALLOC_DIR_COUNT];
+
+ struct id_alloc_page *has_free;
+
+ char *name;
+
+ uint32_t allocated, capacity;
+};
+
+struct id_alloc_pool {
+ struct id_alloc_pool *next;
+ uint32_t id;
+};
+
+void idalloc_free(struct id_alloc *alloc, uint32_t id);
+void idalloc_free_to_pool(struct id_alloc_pool **pool_ptr, uint32_t id);
+void idalloc_drain_pool(struct id_alloc *alloc,
+ struct id_alloc_pool **pool_ptr);
+uint32_t idalloc_allocate(struct id_alloc *alloc);
+uint32_t idalloc_allocate_prefer_pool(struct id_alloc *alloc,
+ struct id_alloc_pool **pool_ptr);
+uint32_t idalloc_reserve(struct id_alloc *alloc, uint32_t id);
+struct id_alloc *idalloc_new(const char *name);
+void idalloc_destroy(struct id_alloc *alloc);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif