lib/id-pool.c

   1 /*
   2  * Copyright (c) 2014 Nicira, Inc.
   3  * Copyright (c) 2014 Netronome.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at:
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18 #include <config.h>
  19 #include "id-pool.h"
  20 #include "hmap.h"
  21 #include "hash.h"
  22
  23 struct id_node {
  24     struct hmap_node node;
  25     uint32_t id;
  26 };
  27
  28 struct id_pool {
  29     struct hmap map;
  30     uint32_t base;         /* IDs in the range of [base, base + n_ids). */
  31     uint32_t n_ids;        /* Total number of ids in the pool. */
  32     uint32_t next_free_id; /* Possible next free id. */
  33 };
  34
  35 static void id_pool_init(struct id_pool *pool,
  36                          uint32_t base, uint32_t n_ids);
  37 static void id_pool_uninit(struct id_pool *pool);
  38 static struct id_node *id_pool_find(struct id_pool *pool, uint32_t id);
  39
  40 struct id_pool *
  41 id_pool_create(uint32_t base, uint32_t n_ids)
  42 {
  43     struct id_pool *pool;
  44
  45     pool = xmalloc(sizeof *pool);
  46     id_pool_init(pool, base, n_ids);
  47
  48     return pool;
  49 }
  50
  51 void
  52 id_pool_destroy(struct id_pool *pool)
  53 {
  54     if (pool) {
  55         id_pool_uninit(pool);
  56         free(pool);
  57     }
  58 }
  59
  60 static void
  61 id_pool_init(struct id_pool *pool, uint32_t base, uint32_t n_ids)
  62 {
  63     pool->base = base;
  64     pool->n_ids = n_ids;
  65     pool->next_free_id = base;
  66     hmap_init(&pool->map);
  67 }
  68
  69 static void
  70 id_pool_uninit(struct id_pool *pool)
  71 {
  72     struct id_node *id_node, *next;
  73
  74     HMAP_FOR_EACH_SAFE(id_node, next, node, &pool->map) {
  75         hmap_remove(&pool->map, &id_node->node);
  76         free(id_node);
  77     }
  78
  79     hmap_destroy(&pool->map);
  80 }
  81
  82 static struct id_node *
  83 id_pool_find(struct id_pool *pool, uint32_t id)
  84 {
  85     size_t hash;
  86     struct id_node *id_node;
  87
  88     hash = hash_int(id, 0);
  89     HMAP_FOR_EACH_WITH_HASH(id_node, node, hash, &pool->map) {
  90         if (id == id_node->id) {
  91             return id_node;
  92         }
  93     }
  94     return NULL;
  95 }
  96
  97 void
  98 id_pool_add(struct id_pool *pool, uint32_t id)
  99 {
 100     struct id_node *id_node = xmalloc(sizeof *id_node);
 101     size_t hash;
 102
 103     id_node->id = id;
 104     hash = hash_int(id, 0);
 105     hmap_insert(&pool->map, &id_node->node, hash);
 106 }
 107
 108 bool
 109 id_pool_alloc_id(struct id_pool *pool, uint32_t *id_)
 110 {
 111     uint32_t id;
 112
 113     if (pool->n_ids == 0) {
 114         return false;
 115     }
 116
 117     if (!(id_pool_find(pool, pool->next_free_id))) {
 118         id = pool->next_free_id;
 119         goto found_free_id;
 120     }
 121
 122     for(id = pool->base; id < pool->base + pool->n_ids; id++) {
 123         if (!id_pool_find(pool, id)) {
 124             goto found_free_id;
 125         }
 126     }
 127
 128     /* Not available. */
 129     return false;
 130
 131 found_free_id:
 132     id_pool_add(pool, id);
 133
 134     if (id < pool->base + pool->n_ids) {
 135         pool->next_free_id = id + 1;
 136     } else {
 137         pool->next_free_id = pool->base;
 138     }
 139
 140     *id_ = id;
 141     return true;
 142 }
 143
 144 void
 145 id_pool_free_id(struct id_pool *pool, uint32_t id)
 146 {
 147     struct id_node *id_node;
 148     if (id > pool->base && (id <= pool->base + pool->n_ids)) {
 149         id_node = id_pool_find(pool, id);
 150         if (id_node) {
 151             hmap_remove(&pool->map, &id_node->node);
 152             free(id_node);
 153         }
 154     }
 155 }