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@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 */
object_heap_expand(object_heap_p heap)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 */
object_heap_init(object_heap_p heap,int object_size,int id_offset)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 */
object_heap_allocate(object_heap_p heap)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 */
object_heap_lookup(object_heap_p heap,int id)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 */
object_heap_first(object_heap_p heap,object_heap_iterator * iter)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 */
object_heap_next(object_heap_p heap,object_heap_iterator * iter)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 */
object_heap_free(object_heap_p heap,object_base_p obj)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 */
object_heap_destroy(object_heap_p heap)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 */
object_heap_suspend_object(object_base_p obj,int suspend)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