lib/id_alloc.h

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * FRR ID Number Allocator
   4  * Copyright (C) 2018  Amazon.com, Inc. or its affiliates
   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
  14 #ifdef __cplusplus
  15 extern "C" {
  16 #endif
  17
  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
  81 #ifdef __cplusplus
  82 }
  83 #endif
  84
  85 #endif