]>
Commit | Line | Data |
---|---|---|
acddc0ed | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
a94eca09 MS |
2 | /* |
3 | * FRR ID Number Allocator | |
4 | * Copyright (C) 2018 Amazon.com, Inc. or its affiliates | |
a94eca09 MS |
5 | */ |
6 | ||
7 | #ifndef _ZEBRA_ID_ALLOC_H | |
8 | #define _ZEBRA_ID_ALLOC_H | |
9 | ||
10 | #include <strings.h> | |
11 | #include <limits.h> | |
12 | #include <stdint.h> | |
13 | ||
5e244469 RW |
14 | #ifdef __cplusplus |
15 | extern "C" { | |
16 | #endif | |
17 | ||
a94eca09 MS |
18 | #define IDALLOC_INVALID 0 |
19 | ||
20 | #define IDALLOC_DIR_BITS 8 | |
21 | #define IDALLOC_SUBDIR_BITS 7 | |
22 | #define IDALLOC_PAGE_BITS 7 | |
23 | #define IDALLOC_WORD_BITS 5 | |
24 | #define IDALLOC_OFFSET_BITS 5 | |
25 | ||
26 | #define IDALLOC_DIR_COUNT (1 << IDALLOC_DIR_BITS) | |
27 | #define IDALLOC_SUBDIR_COUNT (1 << IDALLOC_SUBDIR_BITS) | |
28 | #define IDALLOC_PAGE_COUNT (1 << IDALLOC_PAGE_BITS) | |
29 | #define IDALLOC_WORD_COUNT (1 << IDALLOC_WORD_BITS) | |
30 | ||
31 | struct id_alloc_page { | |
32 | /* Bitmask of allocations. 1s indicates the ID is already allocated. */ | |
33 | uint32_t allocated_mask[IDALLOC_WORD_COUNT]; | |
34 | ||
35 | /* Bitmask for free space in allocated_mask. 1s indicate whole 32 bit | |
36 | * section is full. | |
37 | */ | |
38 | uint32_t full_word_mask; | |
39 | ||
40 | /* The ID that bit 0 in allocated_mask corresponds to. */ | |
41 | uint32_t base_value; | |
42 | ||
43 | struct id_alloc_page | |
44 | *next_has_free; /* Next page with at least one bit open */ | |
45 | }; | |
46 | ||
47 | struct id_alloc_subdir { | |
48 | struct id_alloc_page *sublevels[IDALLOC_PAGE_COUNT]; | |
49 | }; | |
50 | ||
51 | struct id_alloc_dir { | |
52 | struct id_alloc_subdir *sublevels[IDALLOC_SUBDIR_COUNT]; | |
53 | }; | |
54 | ||
55 | struct id_alloc { | |
56 | struct id_alloc_dir *sublevels[IDALLOC_DIR_COUNT]; | |
57 | ||
58 | struct id_alloc_page *has_free; | |
59 | ||
60 | char *name; | |
61 | ||
62 | uint32_t allocated, capacity; | |
63 | }; | |
64 | ||
65 | struct id_alloc_pool { | |
66 | struct id_alloc_pool *next; | |
67 | uint32_t id; | |
68 | }; | |
69 | ||
70 | void idalloc_free(struct id_alloc *alloc, uint32_t id); | |
71 | void idalloc_free_to_pool(struct id_alloc_pool **pool_ptr, uint32_t id); | |
72 | void idalloc_drain_pool(struct id_alloc *alloc, | |
73 | struct id_alloc_pool **pool_ptr); | |
74 | uint32_t idalloc_allocate(struct id_alloc *alloc); | |
75 | uint32_t idalloc_allocate_prefer_pool(struct id_alloc *alloc, | |
76 | struct id_alloc_pool **pool_ptr); | |
77 | uint32_t idalloc_reserve(struct id_alloc *alloc, uint32_t id); | |
78 | struct id_alloc *idalloc_new(const char *name); | |
79 | void idalloc_destroy(struct id_alloc *alloc); | |
80 | ||
5e244469 RW |
81 | #ifdef __cplusplus |
82 | } | |
83 | #endif | |
84 | ||
a94eca09 | 85 | #endif |