• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /**************************************************************************
2  *
3  * Copyright 2008 VMware, Inc.
4  * All Rights Reserved.
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a
7  * copy of this software and associated documentation files (the
8  * "Software"), to deal in the Software without restriction, including
9  * without limitation the rights to use, copy, modify, merge, publish,
10  * distribute, sub license, and/or sell copies of the Software, and to
11  * permit persons to whom the Software is furnished to do so, subject to
12  * the following conditions:
13  *
14  * The above copyright notice and this permission notice (including the
15  * next paragraph) shall be included in all copies or substantial portions
16  * of the Software.
17  *
18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21  * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25  *
26  **************************************************************************/
27 
28 /**
29  * @file
30  * Generic handle table implementation.
31  *
32  * @author José Fonseca <jfonseca@vmware.com>
33  */
34 
35 
36 #include "pipe/p_compiler.h"
37 #include "util/u_debug.h"
38 
39 #include "util/u_memory.h"
40 #include "util/u_handle_table.h"
41 
42 
43 #define HANDLE_TABLE_INITIAL_SIZE 16
44 
45 
46 struct handle_table
47 {
48    /** Object array. Empty handles have a null object */
49    void **objects;
50 
51    /** Number of objects the handle can currently hold */
52    unsigned size;
53    /** Number of consecutive objects allocated at the start of the table */
54    unsigned filled;
55 
56    /** Optional object destructor */
57    void (*destroy)(void *object);
58 };
59 
60 
61 struct handle_table *
handle_table_create(void)62 handle_table_create(void)
63 {
64    struct handle_table *ht;
65 
66    ht = MALLOC_STRUCT(handle_table);
67    if (!ht)
68       return NULL;
69 
70    ht->objects = (void **)CALLOC(HANDLE_TABLE_INITIAL_SIZE, sizeof(void *));
71    if(!ht->objects) {
72       FREE(ht);
73       return NULL;
74    }
75 
76    ht->size = HANDLE_TABLE_INITIAL_SIZE;
77    ht->filled = 0;
78 
79    ht->destroy = NULL;
80 
81    return ht;
82 }
83 
84 
85 void
handle_table_set_destroy(struct handle_table * ht,void (* destroy)(void * object))86 handle_table_set_destroy(struct handle_table *ht,
87                          void (*destroy)(void *object))
88 {
89    assert(ht);
90    if (!ht)
91       return;
92    ht->destroy = destroy;
93 }
94 
95 
96 /**
97  * Resize the table if necessary
98  */
99 static inline int
handle_table_resize(struct handle_table * ht,unsigned minimum_size)100 handle_table_resize(struct handle_table *ht,
101                     unsigned minimum_size)
102 {
103    unsigned new_size;
104    void **new_objects;
105 
106    if(ht->size > minimum_size)
107       return ht->size;
108 
109    new_size = ht->size;
110    while(!(new_size > minimum_size))
111       new_size *= 2;
112    assert(new_size);
113 
114    new_objects = (void **)REALLOC((void *)ht->objects,
115 				  ht->size*sizeof(void *),
116 				  new_size*sizeof(void *));
117    if (!new_objects)
118       return 0;
119 
120    memset(new_objects + ht->size, 0, (new_size - ht->size)*sizeof(void *));
121 
122    ht->size = new_size;
123    ht->objects = new_objects;
124 
125    return ht->size;
126 }
127 
128 
129 static inline void
handle_table_clear(struct handle_table * ht,unsigned index)130 handle_table_clear(struct handle_table *ht,
131                    unsigned index)
132 {
133    void *object;
134 
135    /* The order here is important so that the object being destroyed is not
136     * present in the table when seen by the destroy callback, because the
137     * destroy callback may directly or indirectly call the other functions in
138     * this module.
139     */
140 
141    object = ht->objects[index];
142    if (object) {
143       ht->objects[index] = NULL;
144 
145       if(ht->destroy)
146          ht->destroy(object);
147    }
148 }
149 
150 
151 unsigned
handle_table_add(struct handle_table * ht,void * object)152 handle_table_add(struct handle_table *ht,
153                  void *object)
154 {
155    unsigned index;
156    unsigned handle;
157 
158    assert(ht);
159    assert(object);
160    if(!object || !ht)
161       return 0;
162 
163    /* linear search for an empty handle */
164    while(ht->filled < ht->size) {
165       if(!ht->objects[ht->filled])
166 	 break;
167       ++ht->filled;
168    }
169 
170    index = ht->filled;
171    handle = index + 1;
172 
173    /* check integer overflow */
174    if(!handle)
175       return 0;
176 
177    /* grow the table if necessary */
178    if(!handle_table_resize(ht, index))
179       return 0;
180 
181    assert(!ht->objects[index]);
182    ht->objects[index] = object;
183    ++ht->filled;
184 
185    return handle;
186 }
187 
188 
189 unsigned
handle_table_set(struct handle_table * ht,unsigned handle,void * object)190 handle_table_set(struct handle_table *ht,
191                  unsigned handle,
192                  void *object)
193 {
194    unsigned index;
195 
196    assert(ht);
197    assert(handle);
198    if(!handle || !ht)
199       return 0;
200 
201    assert(object);
202    if (!object)
203       return 0;
204 
205    index = handle - 1;
206 
207    /* grow the table if necessary */
208    if(!handle_table_resize(ht, index))
209       return 0;
210 
211    handle_table_clear(ht, index);
212 
213    ht->objects[index] = object;
214 
215    return handle;
216 }
217 
218 
219 void *
handle_table_get(struct handle_table * ht,unsigned handle)220 handle_table_get(struct handle_table *ht,
221                  unsigned handle)
222 {
223    void *object;
224 
225    assert(ht);
226    assert(handle);
227    if(!handle || !ht || handle > ht->size)
228       return NULL;
229 
230    object = ht->objects[handle - 1];
231 
232    return object;
233 }
234 
235 
236 void
handle_table_remove(struct handle_table * ht,unsigned handle)237 handle_table_remove(struct handle_table *ht,
238                     unsigned handle)
239 {
240    void *object;
241    unsigned index;
242 
243    assert(ht);
244    assert(handle);
245    if(!handle || !ht || handle > ht->size)
246       return;
247 
248    index = handle - 1;
249    object = ht->objects[index];
250    if (!object)
251       return;
252 
253    handle_table_clear(ht, index);
254 
255    if(index < ht->filled)
256       ht->filled = index;
257 }
258 
259 
260 unsigned
handle_table_get_next_handle(struct handle_table * ht,unsigned handle)261 handle_table_get_next_handle(struct handle_table *ht,
262                              unsigned handle)
263 {
264    unsigned index;
265 
266    for(index = handle; index < ht->size; ++index) {
267       if(ht->objects[index])
268 	 return index + 1;
269    }
270 
271    return 0;
272 }
273 
274 
275 unsigned
handle_table_get_first_handle(struct handle_table * ht)276 handle_table_get_first_handle(struct handle_table *ht)
277 {
278    return handle_table_get_next_handle(ht, 0);
279 }
280 
281 
282 void
handle_table_destroy(struct handle_table * ht)283 handle_table_destroy(struct handle_table *ht)
284 {
285    unsigned index;
286    assert(ht);
287 
288    if (!ht)
289       return;
290 
291    if(ht->destroy)
292       for(index = 0; index < ht->size; ++index)
293          handle_table_clear(ht, index);
294 
295    FREE(ht->objects);
296    FREE(ht);
297 }
298 
299