Branch data Line data Source code
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 : 12 : id_pool_create(uint32_t base, uint32_t n_ids)
42 : : {
43 : : struct id_pool *pool;
44 : :
45 : 12 : pool = xmalloc(sizeof *pool);
46 : 12 : id_pool_init(pool, base, n_ids);
47 : :
48 : 12 : return pool;
49 : : }
50 : :
51 : : void
52 : 60 : id_pool_destroy(struct id_pool *pool)
53 : : {
54 [ + + ]: 60 : if (pool) {
55 : 12 : id_pool_uninit(pool);
56 : 12 : free(pool);
57 : : }
58 : 60 : }
59 : :
60 : : static void
61 : 12 : id_pool_init(struct id_pool *pool, uint32_t base, uint32_t n_ids)
62 : : {
63 : 12 : pool->base = base;
64 : 12 : pool->n_ids = n_ids;
65 : 12 : pool->next_free_id = base;
66 : 12 : hmap_init(&pool->map);
67 : 12 : }
68 : :
69 : : static void
70 : 12 : id_pool_uninit(struct id_pool *pool)
71 : : {
72 : : struct id_node *id_node;
73 : :
74 [ + + ][ - + ]: 39 : HMAP_FOR_EACH_POP(id_node, node, &pool->map) {
[ + + ]
75 : 27 : free(id_node);
76 : : }
77 : :
78 : 12 : hmap_destroy(&pool->map);
79 : 12 : }
80 : :
81 : : static struct id_node *
82 : 29 : id_pool_find(struct id_pool *pool, uint32_t id)
83 : : {
84 : : size_t hash;
85 : : struct id_node *id_node;
86 : :
87 : 29 : hash = hash_int(id, 0);
88 [ + + ][ - + ]: 29 : HMAP_FOR_EACH_WITH_HASH(id_node, node, hash, &pool->map) {
89 [ + - ]: 6 : if (id == id_node->id) {
90 : 6 : return id_node;
91 : : }
92 : : }
93 : 23 : return NULL;
94 : : }
95 : :
96 : : void
97 : 27 : id_pool_add(struct id_pool *pool, uint32_t id)
98 : : {
99 : 27 : struct id_node *id_node = xmalloc(sizeof *id_node);
100 : : size_t hash;
101 : :
102 : 27 : id_node->id = id;
103 : 27 : hash = hash_int(id, 0);
104 : 27 : hmap_insert(&pool->map, &id_node->node, hash);
105 : 27 : }
106 : :
107 : : bool
108 : 23 : id_pool_alloc_id(struct id_pool *pool, uint32_t *id_)
109 : : {
110 : : uint32_t id;
111 : :
112 [ - + ]: 23 : if (pool->n_ids == 0) {
113 : 0 : return false;
114 : : }
115 : :
116 [ + + ]: 23 : if (!(id_pool_find(pool, pool->next_free_id))) {
117 : 21 : id = pool->next_free_id;
118 : 21 : goto found_free_id;
119 : : }
120 : :
121 [ + - ]: 6 : for(id = pool->base; id < pool->base + pool->n_ids; id++) {
122 [ + + ]: 6 : if (!id_pool_find(pool, id)) {
123 : 2 : goto found_free_id;
124 : : }
125 : : }
126 : :
127 : : /* Not available. */
128 : 0 : return false;
129 : :
130 : : found_free_id:
131 : 23 : id_pool_add(pool, id);
132 : :
133 [ + - ]: 23 : if (id < pool->base + pool->n_ids) {
134 : 23 : pool->next_free_id = id + 1;
135 : : } else {
136 : 0 : pool->next_free_id = pool->base;
137 : : }
138 : :
139 : 23 : *id_ = id;
140 : 23 : return true;
141 : : }
142 : :
143 : : void
144 : 0 : id_pool_free_id(struct id_pool *pool, uint32_t id)
145 : : {
146 : : struct id_node *id_node;
147 [ # # ][ # # ]: 0 : if (id > pool->base && (id <= pool->base + pool->n_ids)) {
148 : 0 : id_node = id_pool_find(pool, id);
149 [ # # ]: 0 : if (id_node) {
150 : 0 : hmap_remove(&pool->map, &id_node->node);
151 : 0 : free(id_node);
152 : : }
153 : : }
154 : 0 : }
|
