1 /****************************************************************************
2 * Copyright (C) 2006, 2008 by Matteo Franchin *
3 * *
4 * This file is part of Box. *
5 * *
6 * Box is free software: you can redistribute it and/or modify it *
7 * under the terms of the GNU Lesser General Public License as published *
8 * by the Free Software Foundation, either version 3 of the License, or *
9 * (at your option) any later version. *
10 * *
11 * Box is distributed in the hope that it will be useful, *
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
14 * GNU Lesser General Public License for more details. *
15 * *
16 * You should have received a copy of the GNU Lesser General Public *
17 * License along with Box. If not, see <http://www.gnu.org/licenses/>. *
18 ****************************************************************************/
19
20
21 /*#define DEBUG*/
22
23 #include <stdlib.h>
24 #include <stdio.h>
25 #include <assert.h>
26 #include <string.h>
27
28 /* BOX_ABBREV to use UInt as a shorthand of BoxUInt, etc. */
29 #define BOX_ABBREV
30 #include "types.h"
31 #include "error.h"
32 #include "defaults.h"
33 #include "messages.h"
34 #include "array.h"
35 #include "occupation.h"
36
37 /** Index to signal end of the chain of released items */
38 #define END_OF_CHAIN 0
39
40 /** Header which is prepended to each item for recording its occupation state.
41 */
42 typedef struct {
43 struct {
44 unsigned int
45 occupied : 1; /**< NULL if not occupied, otherwise contains the
46 finalizer function to be called */
47 } is;
48 BoxUInt chain; /**< If not the end of chain, then this is the next
49 item in the chain. Must be END_OF_CHAIN if
50 there isn't one */
51 } ItemHeader;
52
BoxOcc_Init(BoxOcc * occ,BoxUInt element_size,BoxUInt initial_size)53 void BoxOcc_Init(BoxOcc *occ, BoxUInt element_size, BoxUInt initial_size) {
54 BoxArr_Init(& occ->array, element_size + sizeof(ItemHeader), initial_size);
55 BoxErr_Set_Tolerance(& occ->array.err, 1); /* So that we can catch errors */
56 occ->elsize = element_size;
57 occ->chain = END_OF_CHAIN;
58 occ->max_idx = 0;
59 occ->fin = NULL;
60 BoxErr_Init(& occ->err);
61 }
62
Internal_Finalizer(BoxUInt idx,void * my_item,void * occ_ptr)63 static int Internal_Finalizer(BoxUInt idx, void *my_item, void *occ_ptr) {
64 ItemHeader *head = (ItemHeader *) my_item;
65 my_item += sizeof(ItemHeader);
66 BoxOcc *occ = (BoxOcc *) occ_ptr;
67 if (head->is.occupied) {
68 if (occ->fin != NULL)
69 occ->fin(my_item);
70 head->is.occupied = 0;
71 }
72 return 1;
73 }
74
BoxOcc_Finish(BoxOcc * occ)75 void BoxOcc_Finish(BoxOcc *occ) {
76 /* Finalize all occupied items */
77 BoxArr_Iter(& occ->array, Internal_Finalizer, occ);
78 /* Destroy BoxOcc.array */
79 BoxArr_Finish(& occ->array);
80 }
81
BoxOcc_New(BoxUInt element_size,BoxUInt initial_size)82 BoxOcc *BoxOcc_New(BoxUInt element_size, BoxUInt initial_size) {
83 BoxOcc *occ = Box_Mem_Alloc(sizeof(BoxOcc));
84 if (occ == NULL) return NULL;
85 BoxOcc_Init(occ, element_size, initial_size);
86 return occ;
87 }
88
BoxOcc_Destroy(BoxOcc * occ)89 void BoxOcc_Destroy(BoxOcc *occ) {
90 BoxOcc_Finish(occ);
91 Box_Mem_Free(occ);
92 }
93
BoxOcc_Set_Finalizer(BoxOcc * occ,BoxOccFinalizer fin)94 void BoxOcc_Set_Finalizer(BoxOcc *occ, BoxOccFinalizer fin) {
95 occ->fin = fin;
96 }
97
BoxOcc_Occupy(BoxOcc * occ,void * item)98 BoxUInt BoxOcc_Occupy(BoxOcc *occ, void *item) {
99 BoxArr *arr = & occ->array;
100 ItemHeader *head;
101 void *my_item;
102
103 if (occ->chain == END_OF_CHAIN) {
104 /* empty chain: add a new item to the tail */
105 BoxUInt idx;
106
107 my_item = BoxArr_Push(arr, NULL);
108 if (BoxErr_Propagate(& occ->err, & arr->err)) return 0;
109
110 head = (ItemHeader *) my_item;
111 my_item += sizeof(ItemHeader);
112
113 head->is.occupied = 1;
114 head->chain = END_OF_CHAIN;
115 memcpy(my_item, item, occ->elsize);
116
117 idx = BoxArr_Num_Items(arr); /* index of tail item */
118 if (idx > occ->max_idx)
119 occ->max_idx = idx;
120 return idx;
121
122 } else {
123 /* non empty chain: recycle an item from the chain */
124 BoxUInt idx = occ->chain;
125 my_item = BoxArr_Item_Ptr(arr, idx);
126 BoxErr_Assert(& arr->err);
127 head = (ItemHeader *) my_item;
128 my_item += sizeof(ItemHeader);
129
130 occ->chain = head->chain;
131 assert(head->is.occupied == 0);
132 head->is.occupied = 1;
133 memcpy(my_item, item, occ->elsize);
134 return idx;
135 }
136 }
137
BoxOcc_Release(BoxOcc * occ,BoxUInt item_index)138 void BoxOcc_Release(BoxOcc *occ, BoxUInt item_index) {
139 BoxArr *arr = & occ->array;
140 ItemHeader *head;
141 void *my_item;
142
143
144 my_item = (void *) BoxArr_Item_Ptr(arr, item_index);
145 if (BoxErr_Propagate(& occ->err, & arr->err)) return;
146
147 head = (ItemHeader *) my_item;
148 if (!head->is.occupied) {
149 BoxErr_Report(& occ->err, BOXERR_DOUBLE_RELEASE);
150 return;
151 }
152
153 (void) Internal_Finalizer(item_index, my_item, occ);
154 head->chain = occ->chain;
155 occ->chain = item_index;
156 }
157
BoxOcc_Item_Ptr(BoxOcc * occ,BoxUInt item_index)158 void *BoxOcc_Item_Ptr(BoxOcc *occ, BoxUInt item_index) {
159 BoxArr *arr = & occ->array;
160 void *my_item = (void *) BoxArr_Item_Ptr(arr, item_index);
161 if (BoxErr_Propagate(& occ->err, & arr->err)) return NULL;
162 return (occ->elsize > 0) ? my_item + sizeof(ItemHeader) : NULL;
163 }
164
BoxOcc_Max_Index(BoxOcc * occ)165 BoxUInt BoxOcc_Max_Index(BoxOcc *occ) {return occ->max_idx;}
166