]>
git.proxmox.com Git - mirror_frr.git/blob - lib/id_alloc.h
2 * FRR ID Number Allocator
3 * Copyright (C) 2018 Amazon.com, Inc. or its affiliates
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the Free
7 * Software Foundation; either version 2 of the License, or (at your option)
10 * This program is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 * You should have received a copy of the GNU General Public License along
16 * with this program; see the file COPYING; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 #ifndef _ZEBRA_ID_ALLOC_H
21 #define _ZEBRA_ID_ALLOC_H
31 #define IDALLOC_INVALID 0
33 #define IDALLOC_DIR_BITS 8
34 #define IDALLOC_SUBDIR_BITS 7
35 #define IDALLOC_PAGE_BITS 7
36 #define IDALLOC_WORD_BITS 5
37 #define IDALLOC_OFFSET_BITS 5
39 #define IDALLOC_DIR_COUNT (1 << IDALLOC_DIR_BITS)
40 #define IDALLOC_SUBDIR_COUNT (1 << IDALLOC_SUBDIR_BITS)
41 #define IDALLOC_PAGE_COUNT (1 << IDALLOC_PAGE_BITS)
42 #define IDALLOC_WORD_COUNT (1 << IDALLOC_WORD_BITS)
44 struct id_alloc_page
{
45 /* Bitmask of allocations. 1s indicates the ID is already allocated. */
46 uint32_t allocated_mask
[IDALLOC_WORD_COUNT
];
48 /* Bitmask for free space in allocated_mask. 1s indicate whole 32 bit
51 uint32_t full_word_mask
;
53 /* The ID that bit 0 in allocated_mask corresponds to. */
57 *next_has_free
; /* Next page with at least one bit open */
60 struct id_alloc_subdir
{
61 struct id_alloc_page
*sublevels
[IDALLOC_PAGE_COUNT
];
65 struct id_alloc_subdir
*sublevels
[IDALLOC_SUBDIR_COUNT
];
69 struct id_alloc_dir
*sublevels
[IDALLOC_DIR_COUNT
];
71 struct id_alloc_page
*has_free
;
75 uint32_t allocated
, capacity
;
78 struct id_alloc_pool
{
79 struct id_alloc_pool
*next
;
83 void idalloc_free(struct id_alloc
*alloc
, uint32_t id
);
84 void idalloc_free_to_pool(struct id_alloc_pool
**pool_ptr
, uint32_t id
);
85 void idalloc_drain_pool(struct id_alloc
*alloc
,
86 struct id_alloc_pool
**pool_ptr
);
87 uint32_t idalloc_allocate(struct id_alloc
*alloc
);
88 uint32_t idalloc_allocate_prefer_pool(struct id_alloc
*alloc
,
89 struct id_alloc_pool
**pool_ptr
);
90 uint32_t idalloc_reserve(struct id_alloc
*alloc
, uint32_t id
);
91 struct id_alloc
*idalloc_new(const char *name
);
92 void idalloc_destroy(struct id_alloc
*alloc
);