src/gallium/auxiliary/util/u_handle_table.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2008 Tungsten Graphics, Inc., Cedar Park, Texas.
   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 TUNGSTEN GRAPHICS 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 <jrfonseca@tungstengraphics.com>
  33  */
  34
  35
  36 #include "pipe/p_compiler.h"
  37 #include "pipe/p_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 *
  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
  86 handle_table_set_destroy(struct handle_table *ht,
  87                          void (*destroy)(void *object))
  88 {
  89    assert(ht);
  90    ht->destroy = destroy;
  91 }
  92
  93
  94 /**
  95  * Resize the table if necessary
  96  */
  97 static INLINE int
  98 handle_table_resize(struct handle_table *ht,
  99                     unsigned minimum_size)
 100 {
 101    unsigned new_size;
 102    void **new_objects;
 103
 104    if(ht->size > minimum_size)
 105       return ht->size;
 106
 107    new_size = ht->size;
 108    while(!(new_size > minimum_size))
 109       new_size *= 2;
 110    assert(new_size);
 111
 112    new_objects = (void **)REALLOC((void *)ht->objects,
 113                                   ht->size*sizeof(void *),
 114                                   new_size*sizeof(void *));
 115    if(!new_objects)
 116       return 0;
 117
 118    memset(new_objects + ht->size, 0, (new_size - ht->size)*sizeof(void *));
 119
 120    ht->size = new_size;
 121    ht->objects = new_objects;
 122
 123    return ht->size;
 124 }
 125
 126
 127 static INLINE void
 128 handle_table_clear(struct handle_table *ht,
 129                    unsigned index)
 130 {
 131    void *object;
 132
 133    /* The order here is important so that the object being destroyed is not
 134     * present in the table when seen by the destroy callback, because the
 135     * destroy callback may directly or indirectly call the other functions in
 136     * this module.
 137     */
 138
 139    object = ht->objects[index];
 140    if(object) {
 141       ht->objects[index] = NULL;
 142
 143       if(ht->destroy)
 144          ht->destroy(object);
 145    }
 146 }
 147
 148
 149 unsigned
 150 handle_table_add(struct handle_table *ht,
 151                  void *object)
 152 {
 153    unsigned index;
 154    unsigned handle;
 155
 156    assert(ht);
 157    assert(object);
 158    if(!object)
 159       return 0;
 160
 161    /* linear search for an empty handle */
 162    while(ht->filled < ht->size) {
 163       if(!ht->objects[ht->filled])
 164          break;
 165       ++ht->filled;
 166    }
 167
 168    index = ht->filled;
 169    handle = index + 1;
 170
 171    /* check integer overflow */
 172    if(!handle)
 173       return 0;
 174
 175    /* grow the table if necessary */
 176    if(!handle_table_resize(ht, index))
 177       return 0;
 178
 179    assert(!ht->objects[index]);
 180    ht->objects[index] = object;
 181    ++ht->filled;
 182
 183    return handle;
 184 }
 185
 186
 187 unsigned
 188 handle_table_set(struct handle_table *ht,
 189                  unsigned handle,
 190                  void *object)
 191 {
 192    unsigned index;
 193
 194    assert(ht);
 195    assert(handle);
 196    if(!handle)
 197       return 0;
 198
 199    assert(object);
 200    if(!object)
 201       return 0;
 202
 203    index = handle - 1;
 204
 205    /* grow the table if necessary */
 206    if(!handle_table_resize(ht, index))
 207       return 0;
 208
 209    handle_table_clear(ht, index);
 210
 211    ht->objects[index] = object;
 212
 213    return handle;
 214 }
 215
 216
 217 void *
 218 handle_table_get(struct handle_table *ht,
 219                  unsigned handle)
 220 {
 221    void *object;
 222
 223    assert(ht);
 224    assert(handle);
 225    if(!handle || handle > ht->size)
 226       return NULL;
 227
 228    object = ht->objects[handle - 1];
 229
 230    return object;
 231 }
 232
 233
 234 void
 235 handle_table_remove(struct handle_table *ht,
 236                     unsigned handle)
 237 {
 238    void *object;
 239    unsigned index;
 240
 241    assert(ht);
 242    assert(handle);
 243    if(!handle || handle > ht->size)
 244       return;
 245
 246    index = handle - 1;
 247    object = ht->objects[index];
 248    if(!object)
 249       return;
 250
 251    handle_table_clear(ht, index);
 252
 253    if(index < ht->filled)
 254       ht->filled = index;
 255 }
 256
 257
 258 unsigned
 259 handle_table_get_next_handle(struct handle_table *ht,
 260                              unsigned handle)
 261 {
 262    unsigned index;
 263
 264    for(index = handle; index < ht->size; ++index) {
 265       if(ht->objects[index])
 266          return index + 1;
 267    }
 268
 269    return 0;
 270 }
 271
 272
 273 unsigned
 274 handle_table_get_first_handle(struct handle_table *ht)
 275 {
 276    return handle_table_get_next_handle(ht, 0);
 277 }
 278
 279
 280 void
 281 handle_table_destroy(struct handle_table *ht)
 282 {
 283    unsigned index;
 284    assert(ht);
 285
 286    if(ht->destroy)
 287       for(index = 0; index < ht->size; ++index)
 288          handle_table_clear(ht, index);
 289
 290    FREE(ht->objects);
 291    FREE(ht);
 292 }
 293