]>
Commit | Line | Data |
---|---|---|
c3bd4bfc SH |
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 | { | |
18ac06d3 SH |
54 | if (pool) { |
55 | id_pool_uninit(pool); | |
56 | free(pool); | |
57 | } | |
c3bd4bfc SH |
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 | { | |
27c24749 | 72 | struct id_node *id_node, *next; |
c3bd4bfc | 73 | |
27c24749 SH |
74 | HMAP_FOR_EACH_SAFE(id_node, next, node, &pool->map) { |
75 | hmap_remove(&pool->map, &id_node->node); | |
76 | free(id_node); | |
c3bd4bfc SH |
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; | |
27c24749 | 86 | struct id_node *id_node; |
c3bd4bfc SH |
87 | |
88 | hash = hash_int(id, 0); | |
27c24749 SH |
89 | HMAP_FOR_EACH_WITH_HASH(id_node, node, hash, &pool->map) { |
90 | if (id == id_node->id) { | |
91 | return id_node; | |
c3bd4bfc SH |
92 | } |
93 | } | |
94 | return NULL; | |
95 | } | |
96 | ||
97 | void | |
98 | id_pool_add(struct id_pool *pool, uint32_t id) | |
99 | { | |
27c24749 | 100 | struct id_node *id_node = xmalloc(sizeof *id_node); |
c3bd4bfc SH |
101 | size_t hash; |
102 | ||
27c24749 | 103 | id_node->id = id; |
c3bd4bfc | 104 | hash = hash_int(id, 0); |
27c24749 | 105 | hmap_insert(&pool->map, &id_node->node, hash); |
c3bd4bfc SH |
106 | } |
107 | ||
27c24749 SH |
108 | bool |
109 | id_pool_alloc_id(struct id_pool *pool, uint32_t *id_) | |
c3bd4bfc SH |
110 | { |
111 | uint32_t id; | |
112 | ||
113 | if (pool->n_ids == 0) { | |
27c24749 | 114 | return false; |
c3bd4bfc SH |
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++) { | |
27c24749 | 123 | if (!id_pool_find(pool, id)) { |
c3bd4bfc SH |
124 | goto found_free_id; |
125 | } | |
126 | } | |
127 | ||
128 | /* Not available. */ | |
27c24749 | 129 | return false; |
c3bd4bfc SH |
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 | ||
27c24749 SH |
140 | *id_ = id; |
141 | return true; | |
c3bd4bfc SH |
142 | } |
143 | ||
144 | void | |
145 | id_pool_free_id(struct id_pool *pool, uint32_t id) | |
146 | { | |
27c24749 | 147 | struct id_node *id_node; |
c3bd4bfc | 148 | if (id > pool->base && (id <= pool->base + pool->n_ids)) { |
27c24749 SH |
149 | id_node = id_pool_find(pool, id); |
150 | if (id_node) { | |
151 | hmap_remove(&pool->map, &id_node->node); | |
849d5648 | 152 | free(id_node); |
c3bd4bfc SH |
153 | } |
154 | } | |
155 | } |