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 "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 *
  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    if (!ht)
  91       return;
  92    ht->destroy = destroy;
  93 }
  94
  95
  96 /**
  97  * Resize the table if necessary
  98  */
  99 static INLINE int
 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
 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
 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
 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 *
 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
 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
 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
 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
 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