lib/id_alloc.h

   1 /*
   2  * FRR ID Number Allocator
   3  * Copyright (C) 2018  Amazon.com, Inc. or its affiliates
   4  *
   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)
   8  * any later version.
   9  *
  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
  13  * more details.
  14  *
  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
  18  */
  19
  20 #ifndef _ZEBRA_ID_ALLOC_H
  21 #define _ZEBRA_ID_ALLOC_H
  22
  23 #include <strings.h>
  24 #include <limits.h>
  25 #include <stdint.h>
  26
  27 #ifdef __cplusplus
  28 extern "C" {
  29 #endif
  30
  31 #define IDALLOC_INVALID 0
  32
  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
  38
  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)
  43
  44 struct id_alloc_page {
  45         /* Bitmask of allocations. 1s indicates the ID is already allocated. */
  46         uint32_t allocated_mask[IDALLOC_WORD_COUNT];
  47
  48         /* Bitmask for free space in allocated_mask. 1s indicate whole 32 bit
  49          * section is full.
  50          */
  51         uint32_t full_word_mask;
  52
  53         /* The ID that bit 0 in allocated_mask corresponds to. */
  54         uint32_t base_value;
  55
  56         struct id_alloc_page
  57                 *next_has_free; /* Next page with at least one bit open */
  58 };
  59
  60 struct id_alloc_subdir {
  61         struct id_alloc_page *sublevels[IDALLOC_PAGE_COUNT];
  62 };
  63
  64 struct id_alloc_dir {
  65         struct id_alloc_subdir *sublevels[IDALLOC_SUBDIR_COUNT];
  66 };
  67
  68 struct id_alloc {
  69         struct id_alloc_dir *sublevels[IDALLOC_DIR_COUNT];
  70
  71         struct id_alloc_page *has_free;
  72
  73         char *name;
  74
  75         uint32_t allocated, capacity;
  76 };
  77
  78 struct id_alloc_pool {
  79         struct id_alloc_pool *next;
  80         uint32_t id;
  81 };
  82
  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);
  93
  94 #ifdef __cplusplus
  95 }
  96 #endif
  97
  98 #endif