btrfs: Attempt to fix GCC2 build.
[haiku.git] / src / system / kernel / device_manager / id_generator.cpp
blob29904a7fb73f7689fbafcda9229daea0c6ad8725
1 /*
2 * Copyright 2004-2008, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
3 * Copyright 2002-2004, Thomas Kurschel. All rights reserved.
5 * Distributed under the terms of the MIT License.
6 */
8 /*! Generators are created on demand and deleted if all their
9 IDs are freed. They have a ref_count which is increased
10 whenever someone messes with the generator.
12 Whenever a generator is searched for, generator_lock is held.
14 To find out which ID are allocated, a bitmap is used that
15 contain up to GENERATOR_MAX_ID bits. This is a hard limit,
16 but it's simple to implement. If someone really needs lots of
17 IDs, we can still rewrite the code. For simplicity, we use
18 sGeneratorLock instead of a generator specific lock during
19 allocation; changing it is straightforward as everything
20 is prepared for that.
24 #include "id_generator.h"
26 #include <new>
27 #include <stdlib.h>
28 #include <string.h>
30 #include <KernelExport.h>
32 #include <util/AutoLock.h>
33 #include <util/DoublyLinkedList.h>
36 //#define TRACE_ID_GENERATOR
37 #ifdef TRACE_ID_GENERATOR
38 # define TRACE(x) dprintf x
39 #else
40 # define TRACE(x) ;
41 #endif
43 #define GENERATOR_MAX_ID 64
45 struct id_generator : DoublyLinkedListLinkImpl<id_generator> {
46 id_generator(const char* name)
48 ref_count(1),
49 name(strdup(name)),
50 num_ids(0)
52 memset(&alloc_map, 0, sizeof(alloc_map));
55 ~id_generator()
57 free(name);
60 int32 ref_count;
61 char* name;
62 uint32 num_ids;
63 uint8 alloc_map[(GENERATOR_MAX_ID + 7) / 8];
66 typedef DoublyLinkedList<id_generator> GeneratorList;
69 GeneratorList sGenerators;
70 static mutex sLock = MUTEX_INITIALIZER("id generator");
73 /*! Create new generator.
74 sLock must be held.
76 static id_generator*
77 create_generator(const char* name)
79 TRACE(("create_generator(name: %s)\n", name));
81 id_generator* generator = new(std::nothrow) id_generator(name);
82 if (generator == NULL)
83 return NULL;
85 if (generator->name == NULL) {
86 delete generator;
87 return NULL;
90 sGenerators.Add(generator);
91 return generator;
95 /*! Allocate ID */
96 static int32
97 create_id_internal(id_generator* generator)
99 uint32 id;
101 TRACE(("create_id_internal(name: %s)\n", generator->name));
103 // see above: we use global instead of local lock
104 MutexLocker _(sLock);
106 // simple bit search
107 for (id = 0; id < GENERATOR_MAX_ID; ++id) {
108 if ((generator->alloc_map[id / 8] & (1 << (id & 7))) == 0) {
109 TRACE((" id: %lu\n", id));
111 generator->alloc_map[id / 8] |= 1 << (id & 7);
112 generator->num_ids++;
114 return id;
118 return B_ERROR;
122 /*! Gets a generator by name, and acquires a reference to it.
123 sLock must be held.
125 static id_generator*
126 get_generator(const char* name)
128 TRACE(("find_generator(name: %s)\n", name));
130 GeneratorList::Iterator iterator = sGenerators.GetIterator();
131 while (iterator.HasNext()) {
132 id_generator* generator = iterator.Next();
134 if (!strcmp(generator->name, name)) {
135 // increase ref_count, so it won't go away
136 generator->ref_count++;
137 return generator;
141 return NULL;
145 /*! Decrease ref_count, deleting generator if not used anymore */
146 static void
147 release_generator(id_generator *generator)
149 TRACE(("release_generator(name: %s)\n", generator->name));
151 MutexLocker _(sLock);
153 if (--generator->ref_count == 0) {
154 // no one messes with generator
155 if (generator->num_ids == 0) {
156 TRACE((" Destroy %s\n", generator->name));
157 // no IDs is allocated - destroy generator
158 sGenerators.Remove(generator);
159 delete generator;
165 // #pragma mark - Private kernel API
168 void
169 dm_init_id_generator(void)
171 new(&sGenerators) GeneratorList;
175 // #pragma mark - Public module API
178 /*! Create automatic ID */
179 int32
180 dm_create_id(const char* name)
183 // find generator, create new if not there
184 mutex_lock(&sLock);
186 id_generator* generator = get_generator(name);
187 if (generator == NULL)
188 generator = create_generator(name);
190 mutex_unlock(&sLock);
192 if (generator == NULL)
193 return B_NO_MEMORY;
195 // get ID
196 int32 id = create_id_internal(generator);
198 release_generator(generator);
200 TRACE(("dm_create_id: name: %s, id: %ld\n", name, id));
201 return id;
205 /*! Free automatically generated ID */
206 status_t
207 dm_free_id(const char* name, uint32 id)
209 TRACE(("dm_free_id(name: %s, id: %ld)\n", name, id));
211 // find generator
212 mutex_lock(&sLock);
214 id_generator* generator = get_generator(name);
216 mutex_unlock(&sLock);
218 if (generator == NULL) {
219 TRACE((" Generator %s doesn't exist\n", name));
220 return B_NAME_NOT_FOUND;
223 // free ID
225 // make sure it's really allocated
226 // (very important to keep <num_ids> in sync
227 if ((generator->alloc_map[id / 8] & (1 << (id & 7))) == 0) {
228 dprintf("id %" B_PRIu32 " of generator %s wasn't allocated\n", id,
229 generator->name);
231 release_generator(generator);
232 return B_BAD_VALUE;
235 generator->alloc_map[id / 8] &= ~(1 << (id & 7));
236 generator->num_ids--;
238 release_generator(generator);
239 return B_OK;