]>
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
27 #define IDALLOC_INVALID 0
29 #define IDALLOC_DIR_BITS 8
30 #define IDALLOC_SUBDIR_BITS 7
31 #define IDALLOC_PAGE_BITS 7
32 #define IDALLOC_WORD_BITS 5
33 #define IDALLOC_OFFSET_BITS 5
35 #define IDALLOC_DIR_COUNT (1 << IDALLOC_DIR_BITS)
36 #define IDALLOC_SUBDIR_COUNT (1 << IDALLOC_SUBDIR_BITS)
37 #define IDALLOC_PAGE_COUNT (1 << IDALLOC_PAGE_BITS)
38 #define IDALLOC_WORD_COUNT (1 << IDALLOC_WORD_BITS)
40 struct id_alloc_page
{
41 /* Bitmask of allocations. 1s indicates the ID is already allocated. */
42 uint32_t allocated_mask
[IDALLOC_WORD_COUNT
];
44 /* Bitmask for free space in allocated_mask. 1s indicate whole 32 bit
47 uint32_t full_word_mask
;
49 /* The ID that bit 0 in allocated_mask corresponds to. */
53 *next_has_free
; /* Next page with at least one bit open */
56 struct id_alloc_subdir
{
57 struct id_alloc_page
*sublevels
[IDALLOC_PAGE_COUNT
];
61 struct id_alloc_subdir
*sublevels
[IDALLOC_SUBDIR_COUNT
];
65 struct id_alloc_dir
*sublevels
[IDALLOC_DIR_COUNT
];
67 struct id_alloc_page
*has_free
;
71 uint32_t allocated
, capacity
;
74 struct id_alloc_pool
{
75 struct id_alloc_pool
*next
;
79 void idalloc_free(struct id_alloc
*alloc
, uint32_t id
);
80 void idalloc_free_to_pool(struct id_alloc_pool
**pool_ptr
, uint32_t id
);
81 void idalloc_drain_pool(struct id_alloc
*alloc
,
82 struct id_alloc_pool
**pool_ptr
);
83 uint32_t idalloc_allocate(struct id_alloc
*alloc
);
84 uint32_t idalloc_allocate_prefer_pool(struct id_alloc
*alloc
,
85 struct id_alloc_pool
**pool_ptr
);
86 uint32_t idalloc_reserve(struct id_alloc
*alloc
, uint32_t id
);
87 struct id_alloc
*idalloc_new(const char *name
);
88 void idalloc_destroy(struct id_alloc
*alloc
);