Home | History | Annotate | Download | only in src 
      1 /*
      2  * Copyright (c) 2011 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  * Authors:
     25  *    Waldo Bastian <waldo.bastian (at) intel.com>
     26  *
     27  */
     28 
     29 #include "object_heap.h"
     30 
     31 #include <stdlib.h>
     32 #include <string.h>
     33 
     34 #include "psb_def.h"
     35 #include "psb_drv_debug.h"
     36 
     37 #define LAST_FREE    -1
     38 #define ALLOCATED    -2
     39 #define SUSPENDED    -3
     40 
     41 /*
     42  * Expands the heap
     43  * Return 0 on success, -1 on error
     44  */
     45 static int object_heap_expand(object_heap_p heap)
     46 {
     47     int i;
     48     int malloc_error = FALSE;
     49     object_base_p *new_heap_index;
     50     int next_free;
     51     int new_heap_size = heap->heap_size + heap->heap_increment;
     52 
     53     new_heap_index = (object_base_p *) realloc(heap->heap_index, new_heap_size * sizeof(object_base_p));
     54     if (NULL == new_heap_index) {
     55         return -1; /* Out of memory */
     56     }
     57     heap->heap_index = new_heap_index;
     58     next_free = heap->next_free;
     59     for (i = new_heap_size; i-- > heap->heap_size;) {
     60         object_base_p obj = (object_base_p) calloc(1, heap->object_size);
     61         heap->heap_index[i] = obj;
     62         if (NULL == obj) {
     63             malloc_error = TRUE;
     64             continue; /* Clean up after the loop is completely done */
     65         }
     66         obj->id = i + heap->id_offset;
     67         obj->next_free = next_free;
     68         next_free = i;
     69     }
     70 
     71     if (malloc_error) {
     72         /* Clean up the mess */
     73         for (i = new_heap_size; i-- > heap->heap_size;) {
     74             if (heap->heap_index[i]) {
     75                 free(heap->heap_index[i]);
     76             }
     77         }
     78         /* heap->heap_index is left as is */
     79         return -1; /* Out of memory */
     80     }
     81     heap->next_free = next_free;
     82     heap->heap_size = new_heap_size;
     83     return 0; /* Success */
     84 }
     85 
     86 /*
     87  * Return 0 on success, -1 on error
     88  */
     89 int object_heap_init(object_heap_p heap, int object_size, int id_offset)
     90 {
     91     heap->object_size = object_size;
     92     heap->id_offset = id_offset & OBJECT_HEAP_OFFSET_MASK;
     93     heap->heap_size = 0;
     94     heap->heap_increment = 16;
     95     heap->heap_index = NULL;
     96     heap->next_free = LAST_FREE;
     97     return object_heap_expand(heap);
     98 }
     99 
    100 /*
    101  * Allocates an object
    102  * Returns the object ID on success, returns -1 on error
    103  */
    104 int object_heap_allocate(object_heap_p heap)
    105 {
    106     object_base_p obj;
    107     if (LAST_FREE == heap->next_free) {
    108         if (-1 == object_heap_expand(heap)) {
    109             return -1; /* Out of memory */
    110         }
    111     }
    112     ASSERT(heap->next_free >= 0);
    113 
    114     obj = heap->heap_index[heap->next_free];
    115     heap->next_free = obj->next_free;
    116     obj->next_free = ALLOCATED;
    117     return obj->id;
    118 }
    119 
    120 /*
    121  * Lookup an object by object ID
    122  * Returns a pointer to the object on success, returns NULL on error
    123  */
    124 object_base_p object_heap_lookup(object_heap_p heap, int id)
    125 {
    126     object_base_p obj;
    127     if ((id < heap->id_offset) || (id > (heap->heap_size + heap->id_offset))) {
    128         return NULL;
    129     }
    130     id &= OBJECT_HEAP_ID_MASK;
    131     obj = heap->heap_index[id];
    132 
    133     /* Check if the object has in fact been allocated */
    134 #if 0
    135     if (obj->next_free != ALLOCATED) {
    136         return NULL;
    137     }
    138 #endif
    139     return obj;
    140 }
    141 
    142 /*
    143  * Iterate over all objects in the heap.
    144  * Returns a pointer to the first object on the heap, returns NULL if heap is empty.
    145  */
    146 object_base_p object_heap_first(object_heap_p heap, object_heap_iterator *iter)
    147 {
    148     *iter = -1;
    149     return object_heap_next(heap, iter);
    150 }
    151 
    152 /*
    153  * Iterate over all objects in the heap.
    154  * Returns a pointer to the next object on the heap, returns NULL if heap is empty.
    155  */
    156 object_base_p object_heap_next(object_heap_p heap, object_heap_iterator *iter)
    157 {
    158     object_base_p obj;
    159     int i = *iter + 1;
    160     while (i < heap->heap_size) {
    161         obj = heap->heap_index[i];
    162         if ((obj->next_free == ALLOCATED) || (obj->next_free == SUSPENDED)) {
    163             *iter = i;
    164             return obj;
    165         }
    166         i++;
    167     }
    168     *iter = i;
    169     return NULL;
    170 }
    171 
    172 
    173 
    174 /*
    175  * Frees an object
    176  */
    177 void object_heap_free(object_heap_p heap, object_base_p obj)
    178 {
    179     /* Don't complain about NULL pointers */
    180     if (NULL != obj) {
    181         /* Check if the object has in fact been allocated */
    182         ASSERT((obj->next_free == ALLOCATED) || (obj->next_free == SUSPENDED));
    183 
    184         obj->next_free = heap->next_free;
    185         heap->next_free = obj->id & OBJECT_HEAP_ID_MASK;
    186     }
    187 }
    188 
    189 /*
    190  * Destroys a heap, the heap must be empty.
    191  */
    192 void object_heap_destroy(object_heap_p heap)
    193 {
    194     object_base_p obj;
    195     int i;
    196     for (i = 0; i < heap->heap_size; i++) {
    197         /* Check if object is not still allocated */
    198         obj = heap->heap_index[i];
    199         ASSERT(obj->next_free != ALLOCATED);
    200         ASSERT(obj->next_free != SUSPENDED);
    201         /* Free object itself */
    202         free(obj);
    203     }
    204     free(heap->heap_index);
    205     heap->heap_size = 0;
    206     heap->heap_index = NULL;
    207     heap->next_free = LAST_FREE;
    208 }
    209 
    210 /*
    211  * Suspend an object
    212  * Suspended objects can not be looked up
    213  */
    214 void object_heap_suspend_object(object_base_p obj, int suspend)
    215 {
    216     if (suspend) {
    217         ASSERT(obj->next_free == ALLOCATED);
    218         obj->next_free = SUSPENDED;
    219     } else {
    220         ASSERT(obj->next_free == SUSPENDED);
    221         obj->next_free = ALLOCATED;
    222     }
    223 }
    224