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 #include "pipe/p_util.h"
  39
  40 #include "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 unsigned
 128 handle_table_add(struct handle_table *ht,
 129                  void *object)
 130 {
 131    unsigned index;
 132    unsigned handle;
 133
 134    assert(ht);
 135    assert(object);
 136    if(!object)
 137       return 0;
 138
 139    /* linear search for an empty handle */
 140    while(ht->filled < ht->size) {
 141       if(!ht->objects[ht->filled])
 142          break;
 143       ++ht->filled;
 144    }
 145
 146    index = ht->filled;
 147    handle = index + 1;
 148
 149    /* check integer overflow */
 150    if(!handle)
 151       return 0;
 152
 153    /* grow the table if necessary */
 154    if(!handle_table_resize(ht, index))
 155       return 0;
 156
 157    assert(!ht->objects[index]);
 158    ht->objects[index] = object;
 159    ++ht->filled;
 160
 161    return handle;
 162 }
 163
 164
 165 unsigned
 166 handle_table_set(struct handle_table *ht,
 167                  unsigned handle,
 168                  void *object)
 169 {
 170    unsigned index;
 171
 172    assert(ht);
 173    assert(handle > 0);
 174    assert(handle <= ht->size);
 175    if(!handle || handle > ht->size)
 176       return 0;
 177
 178    assert(object);
 179    if(!object)
 180       return 0;
 181
 182    index = handle - 1;
 183
 184    /* grow the table if necessary */
 185    if(!handle_table_resize(ht, index))
 186       return 0;
 187
 188    assert(!ht->objects[index]);
 189    ht->objects[index] = object;
 190
 191    return handle;
 192 }
 193
 194
 195 void *
 196 handle_table_get(struct handle_table *ht,
 197                  unsigned handle)
 198 {
 199    void *object;
 200
 201    assert(ht);
 202    assert(handle > 0);
 203    assert(handle <= ht->size);
 204    if(!handle || handle > ht->size)
 205       return NULL;
 206
 207    object = ht->objects[handle - 1];
 208    assert(object);
 209
 210    return object;
 211 }
 212
 213
 214 void
 215 handle_table_remove(struct handle_table *ht,
 216                     unsigned handle)
 217 {
 218    void *object;
 219    unsigned index;
 220
 221    assert(ht);
 222    assert(handle > 0);
 223    assert(handle <= ht->size);
 224    if(!handle || handle > ht->size)
 225       return;
 226
 227    index = handle - 1;
 228    object = ht->objects[index];
 229    if(!object) {
 230       /* XXX: this warning may be noisy for legitimate use -- remove later */
 231       debug_warning("removing empty handle");
 232       return;
 233    }
 234
 235    if(ht->destroy)
 236       ht->destroy(object);
 237
 238    ht->objects[index] = NULL;
 239    if(index < ht->filled)
 240       ht->filled = index;
 241 }
 242
 243
 244 void
 245 handle_table_destroy(struct handle_table *ht)
 246 {
 247    unsigned index;
 248    assert(ht);
 249
 250    if(ht->destroy)
 251       for(index = 0; index < ht->size; ++index)
 252          if(ht->objects[index])
 253             ht->destroy(ht->objects[index]);
 254
 255    FREE(ht->objects);
 256    FREE(ht);
 257 }
 258