]>
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" | |
ee89ea7b | 20 | #include "openvswitch/hmap.h" |
c3bd4bfc SH |
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 | { | |
4ec3d7c7 | 72 | struct id_node *id_node; |
c3bd4bfc | 73 | |
4ec3d7c7 | 74 | HMAP_FOR_EACH_POP(id_node, node, &pool->map) { |
27c24749 | 75 | free(id_node); |
c3bd4bfc SH |
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; | |
27c24749 | 85 | struct id_node *id_node; |
c3bd4bfc SH |
86 | |
87 | hash = hash_int(id, 0); | |
27c24749 SH |
88 | HMAP_FOR_EACH_WITH_HASH(id_node, node, hash, &pool->map) { |
89 | if (id == id_node->id) { | |
90 | return id_node; | |
c3bd4bfc SH |
91 | } |
92 | } | |
93 | return NULL; | |
94 | } | |
95 | ||
96 | void | |
97 | id_pool_add(struct id_pool *pool, uint32_t id) | |
98 | { | |
27c24749 | 99 | struct id_node *id_node = xmalloc(sizeof *id_node); |
c3bd4bfc SH |
100 | size_t hash; |
101 | ||
27c24749 | 102 | id_node->id = id; |
c3bd4bfc | 103 | hash = hash_int(id, 0); |
27c24749 | 104 | hmap_insert(&pool->map, &id_node->node, hash); |
c3bd4bfc SH |
105 | } |
106 | ||
27c24749 SH |
107 | bool |
108 | id_pool_alloc_id(struct id_pool *pool, uint32_t *id_) | |
c3bd4bfc SH |
109 | { |
110 | uint32_t id; | |
111 | ||
112 | if (pool->n_ids == 0) { | |
27c24749 | 113 | return false; |
c3bd4bfc SH |
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++) { | |
27c24749 | 122 | if (!id_pool_find(pool, id)) { |
c3bd4bfc SH |
123 | goto found_free_id; |
124 | } | |
125 | } | |
126 | ||
127 | /* Not available. */ | |
27c24749 | 128 | return false; |
c3bd4bfc SH |
129 | |
130 | found_free_id: | |
131 | id_pool_add(pool, id); | |
132 | ||
133 | if (id < pool->base + pool->n_ids) { | |
134 | pool->next_free_id = id + 1; | |
135 | } else { | |
136 | pool->next_free_id = pool->base; | |
137 | } | |
138 | ||
27c24749 SH |
139 | *id_ = id; |
140 | return true; | |
c3bd4bfc SH |
141 | } |
142 | ||
143 | void | |
144 | id_pool_free_id(struct id_pool *pool, uint32_t id) | |
145 | { | |
27c24749 | 146 | struct id_node *id_node; |
c3bd4bfc | 147 | if (id > pool->base && (id <= pool->base + pool->n_ids)) { |
27c24749 SH |
148 | id_node = id_pool_find(pool, id); |
149 | if (id_node) { | |
150 | hmap_remove(&pool->map, &id_node->node); | |
f596e8ed IM |
151 | if (id < pool->next_free_id) { |
152 | pool->next_free_id = id; | |
153 | } | |
849d5648 | 154 | free(id_node); |
c3bd4bfc SH |
155 | } |
156 | } | |
157 | } |