Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (c) 2007 Intel Corporation. All Rights Reserved.
  3.  *
  4.  * Permission is hereby granted, free of charge, to any person obtaining a
  5.  * copy of this software and associated documentation files (the
  6.  * "Software"), to deal in the Software without restriction, including
  7.  * without limitation the rights to use, copy, modify, merge, publish,
  8.  * distribute, sub license, and/or sell copies of the Software, and to
  9.  * permit persons to whom the Software is furnished to do so, subject to
  10.  * the following conditions:
  11.  *
  12.  * The above copyright notice and this permission notice (including the
  13.  * next paragraph) shall be included in all copies or substantial portions
  14.  * of the Software.
  15.  *
  16.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  17.  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  18.  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  19.  * IN NO EVENT SHALL PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR
  20.  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  21.  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  22.  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  23.  */
  24.  
  25. #include "object_heap.h"
  26.  
  27. #include "assert.h"
  28. #include <stdio.h>
  29. #include <string.h>
  30. #include <stdlib.h>
  31.  
  32. #define ASSERT  assert
  33.  
  34. #define LAST_FREE       -1
  35. #define ALLOCATED       -2
  36.  
  37. /*
  38.  * Expands the heap
  39.  * Return 0 on success, -1 on error
  40.  */
  41. static int object_heap_expand( object_heap_p heap )
  42. {
  43.     int i;
  44.     void *new_heap_index;
  45.     int next_free;
  46.     int new_heap_size = heap->heap_size + heap->heap_increment;
  47.     int bucket_index = new_heap_size / heap->heap_increment - 1;
  48.  
  49.     if (bucket_index >= heap->num_buckets) {
  50.         int new_num_buckets = heap->num_buckets + 8;
  51.         void **new_bucket;
  52.  
  53.         new_bucket = realloc(heap->bucket, new_num_buckets * sizeof(void *));
  54.         if (NULL == new_bucket) {
  55.             return -1;
  56.         }
  57.  
  58.         heap->num_buckets = new_num_buckets;
  59.         heap->bucket = new_bucket;
  60.     }
  61.  
  62.     new_heap_index = (void *) malloc( heap->heap_increment * heap->object_size );
  63.     if ( NULL == new_heap_index )
  64.     {
  65.         return -1; /* Out of memory */
  66.     }
  67.  
  68.     heap->bucket[bucket_index] = new_heap_index;
  69.     next_free = heap->next_free;
  70.     for(i = new_heap_size; i-- > heap->heap_size; )
  71.     {
  72.         object_base_p obj = (object_base_p) (new_heap_index + (i - heap->heap_size) * heap->object_size);
  73.         obj->id = i + heap->id_offset;
  74.         obj->next_free = next_free;
  75.         next_free = i;
  76.     }
  77.     heap->next_free = next_free;
  78.     heap->heap_size = new_heap_size;
  79.     return 0; /* Success */
  80. }
  81.  
  82. /*
  83.  * Return 0 on success, -1 on error
  84.  */
  85. int object_heap_init( object_heap_p heap, int object_size, int id_offset)
  86. {
  87.     heap->object_size = object_size;
  88.     heap->id_offset = id_offset & OBJECT_HEAP_OFFSET_MASK;
  89.     heap->heap_size = 0;
  90.     heap->heap_increment = 16;
  91.     heap->next_free = LAST_FREE;
  92.     _i965InitMutex(&heap->mutex);
  93.     heap->num_buckets = 0;
  94.     heap->bucket = NULL;
  95.     return object_heap_expand(heap);
  96. }
  97.  
  98. /*
  99.  * Allocates an object
  100.  * Returns the object ID on success, returns -1 on error
  101.  */
  102. int object_heap_allocate( object_heap_p heap )
  103. {
  104.     object_base_p obj;
  105.     int bucket_index, obj_index;
  106.  
  107.     _i965LockMutex(&heap->mutex);
  108.     if ( LAST_FREE == heap->next_free )
  109.     {
  110.         if( -1 == object_heap_expand( heap ) )
  111.         {
  112.             _i965UnlockMutex(&heap->mutex);
  113.             return -1; /* Out of memory */
  114.         }
  115.     }
  116.     ASSERT( heap->next_free >= 0 );
  117.  
  118.     bucket_index = heap->next_free / heap->heap_increment;
  119.     obj_index = heap->next_free % heap->heap_increment;
  120.  
  121.     obj = (object_base_p) (heap->bucket[bucket_index] + obj_index * heap->object_size);
  122.     heap->next_free = obj->next_free;
  123.     _i965UnlockMutex(&heap->mutex);
  124.    
  125.     obj->next_free = ALLOCATED;
  126.     return obj->id;
  127. }
  128.  
  129. /*
  130.  * Lookup an object by object ID
  131.  * Returns a pointer to the object on success, returns NULL on error
  132.  */
  133. object_base_p object_heap_lookup( object_heap_p heap, int id )
  134. {
  135.     object_base_p obj;
  136.     int bucket_index, obj_index;
  137.  
  138.     _i965LockMutex(&heap->mutex);
  139.     if ( (id < heap->id_offset) || (id > (heap->heap_size+heap->id_offset)) )
  140.     {
  141.         _i965UnlockMutex(&heap->mutex);
  142.         return NULL;
  143.     }
  144.     id &= OBJECT_HEAP_ID_MASK;
  145.     bucket_index = id / heap->heap_increment;
  146.     obj_index = id % heap->heap_increment;
  147.     obj = (object_base_p) (heap->bucket[bucket_index] + obj_index * heap->object_size);
  148.     _i965UnlockMutex(&heap->mutex);
  149.  
  150.         /* Check if the object has in fact been allocated */
  151.         if ( obj->next_free != ALLOCATED )
  152.     {
  153.         return NULL;
  154.     }
  155.     return obj;
  156. }
  157.  
  158. /*
  159.  * Iterate over all objects in the heap.
  160.  * Returns a pointer to the first object on the heap, returns NULL if heap is empty.
  161.  */
  162. object_base_p object_heap_first( object_heap_p heap, object_heap_iterator *iter )
  163. {
  164.     *iter = -1;
  165.     return object_heap_next( heap, iter );
  166. }
  167.  
  168. /*
  169.  * Iterate over all objects in the heap.
  170.  * Returns a pointer to the next object on the heap, returns NULL if heap is empty.
  171.  */
  172. object_base_p object_heap_next( object_heap_p heap, object_heap_iterator *iter )
  173. {
  174.     object_base_p obj;
  175.     int i = *iter + 1;
  176.     int bucket_index, obj_index;
  177.  
  178.     _i965LockMutex(&heap->mutex);
  179.     while ( i < heap->heap_size)
  180.     {
  181.         bucket_index = i / heap->heap_increment;
  182.         obj_index = i % heap->heap_increment;
  183.  
  184.         obj = (object_base_p) (heap->bucket[bucket_index] + obj_index * heap->object_size);
  185.         if (obj->next_free == ALLOCATED)
  186.         {
  187.             _i965UnlockMutex(&heap->mutex);
  188.             *iter = i;
  189.             return obj;
  190.         }
  191.         i++;
  192.     }
  193.     _i965UnlockMutex(&heap->mutex);
  194.     *iter = i;
  195.     return NULL;
  196. }
  197.  
  198.  
  199.  
  200. /*
  201.  * Frees an object
  202.  */
  203. void object_heap_free( object_heap_p heap, object_base_p obj )
  204. {
  205.     /* Don't complain about NULL pointers */
  206.     if (NULL != obj)
  207.     {
  208.         /* Check if the object has in fact been allocated */
  209.         ASSERT( obj->next_free == ALLOCATED );
  210.    
  211.         _i965LockMutex(&heap->mutex);
  212.         obj->next_free = heap->next_free;
  213.         heap->next_free = obj->id & OBJECT_HEAP_ID_MASK;
  214.         _i965UnlockMutex(&heap->mutex);
  215.     }
  216. }
  217.  
  218. /*
  219.  * Destroys a heap, the heap must be empty.
  220.  */
  221. void object_heap_destroy( object_heap_p heap )
  222. {
  223.     object_base_p obj;
  224.     int i;
  225.     int bucket_index, obj_index;
  226.  
  227.     _i965DestroyMutex(&heap->mutex);
  228.  
  229.     /* Check if heap is empty */
  230.     for (i = 0; i < heap->heap_size; i++)
  231.     {
  232.         /* Check if object is not still allocated */
  233.         bucket_index = i / heap->heap_increment;
  234.         obj_index = i % heap->heap_increment;
  235.         obj = (object_base_p) (heap->bucket[bucket_index] + obj_index * heap->object_size);
  236.         ASSERT( obj->next_free != ALLOCATED );
  237.     }
  238.  
  239.     for (i = 0; i < heap->heap_size / heap->heap_increment; i++) {
  240.         free(heap->bucket[i]);
  241.     }
  242.  
  243.     free(heap->bucket);
  244.     heap->bucket = NULL;
  245.     heap->heap_size = 0;
  246.     heap->next_free = LAST_FREE;
  247. }
  248.