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 #define IDALLOC_INVALID 0
  28
  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
  34
  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)
  39
  40 struct id_alloc_page {
  41         /* Bitmask of allocations. 1s indicates the ID is already allocated. */
  42         uint32_t allocated_mask[IDALLOC_WORD_COUNT];
  43
  44         /* Bitmask for free space in allocated_mask. 1s indicate whole 32 bit
  45          * section is full.
  46          */
  47         uint32_t full_word_mask;
  48
  49         /* The ID that bit 0 in allocated_mask corresponds to. */
  50         uint32_t base_value;
  51
  52         struct id_alloc_page
  53                 *next_has_free; /* Next page with at least one bit open */
  54 };
  55
  56 struct id_alloc_subdir {
  57         struct id_alloc_page *sublevels[IDALLOC_PAGE_COUNT];
  58 };
  59
  60 struct id_alloc_dir {
  61         struct id_alloc_subdir *sublevels[IDALLOC_SUBDIR_COUNT];
  62 };
  63
  64 struct id_alloc {
  65         struct id_alloc_dir *sublevels[IDALLOC_DIR_COUNT];
  66
  67         struct id_alloc_page *has_free;
  68
  69         char *name;
  70
  71         uint32_t allocated, capacity;
  72 };
  73
  74 struct id_alloc_pool {
  75         struct id_alloc_pool *next;
  76         uint32_t id;
  77 };
  78
  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);
  89
  90 #endif