Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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 *
  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.  
  299.