diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 09:53:30 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 09:53:30 +0000 |
commit | 2c7cac91ed6e7db0f6937923d2b57f97dbdbc337 (patch) | |
tree | c05dc0f8e6aa3accc84e3e5cffc933ed94941383 /lib/id_alloc.h | |
parent | Initial commit. (diff) | |
download | frr-upstream.tar.xz frr-upstream.zip |
Adding upstream version 8.4.4.upstream/8.4.4upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'lib/id_alloc.h')
-rw-r--r-- | lib/id_alloc.h | 98 |
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 |