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 "openvswitch/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;
  73
  74     HMAP_FOR_EACH_POP(id_node, node, &pool->map) {
  75         free(id_node);
  76     }
  77
  78     hmap_destroy(&pool->map);
  79 }
  80
  81 static struct id_node *
  82 id_pool_find(struct id_pool *pool, uint32_t id)
  83 {
  84     size_t hash;
  85     struct id_node *id_node;
  86
  87     hash = hash_int(id, 0);
  88     HMAP_FOR_EACH_WITH_HASH(id_node, node, hash, &pool->map) {
  89         if (id == id_node->id) {
  90             return id_node;
  91         }
  92     }
  93     return NULL;
  94 }
  95
  96 void
  97 id_pool_add(struct id_pool *pool, uint32_t id)
  98 {
  99     struct id_node *id_node = xmalloc(sizeof *id_node);
 100     size_t hash;
 101
 102     id_node->id = id;
 103     hash = hash_int(id, 0);
 104     hmap_insert(&pool->map, &id_node->node, hash);
 105 }
 106
 107 bool
 108 id_pool_alloc_id(struct id_pool *pool, uint32_t *id_)
 109 {
 110     uint32_t id;
 111
 112     if (pool->n_ids == 0) {
 113         return false;
 114     }
 115
 116     if (!(id_pool_find(pool, pool->next_free_id))) {
 117         id = pool->next_free_id;
 118         goto found_free_id;
 119     }
 120
 121     for(id = pool->base; id < pool->base + pool->n_ids; id++) {
 122         if (!id_pool_find(pool, id)) {
 123             goto found_free_id;
 124         }
 125     }
 126
 127     /* Not available. */
 128     return false;
 129
 130 found_free_id:
 131     id_pool_add(pool, id);
 132
 133     if (id + 1 < pool->base + pool->n_ids) {
 134         pool->next_free_id = id + 1;
 135     } else {
 136         pool->next_free_id = pool->base;
 137     }
 138
 139     *id_ = id;
 140     return true;
 141 }
 142
 143 void
 144 id_pool_free_id(struct id_pool *pool, uint32_t id)
 145 {
 146     struct id_node *id_node;
 147     if (id >= pool->base && (id < pool->base + pool->n_ids)) {
 148         id_node = id_pool_find(pool, id);
 149         if (id_node) {
 150             hmap_remove(&pool->map, &id_node->node);
 151             if (id < pool->next_free_id) {
 152                 pool->next_free_id = id;
 153             }
 154             free(id_node);
 155         }
 156     }
 157 }