1 /*
2 Copyright (C) 2003 Cedric Cellier, Dominique Lavault
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 */
18 #include "list.h"
19 #include "log.h"
20 #include "memspool.h"
21 #include "stack.h"
22 #include <assert.h>
23
24 /* no pointers because of reallocation */
25 struct s_entry {
26 unsigned next; /* next=0 means last, =1 means vaccant */
27 unsigned previous;
28 void *value;
29 };
30 typedef struct s_entry entry;
31
32 struct s_gltv_list {
33 unsigned nb_usable_entries;
34 unsigned nb_used_entries;
35 unsigned begin;
36 unsigned end;
37 unsigned last_accessed_order; /* order into the list */
38 unsigned last_accessed_index; /* indices are thoses of entries */
39 entry *entries;
40 unsigned next_free_entry; /* index of the next free entry in entries */
41 unsigned full_until; /* index of the first entry which usage might be vaccant */
42 gltv_stack *removed; /* indexes of thet lasts removed entries */
43 char optimize_for_size;
44 };
45 typedef struct s_gltv_list list;
46
gltv_list_new(unsigned total,int optimize_for_size)47 GLTV_LIST gltv_list_new(unsigned total, int optimize_for_size) {
48 list *this_list;
49 this_list = gltv_memspool_alloc(sizeof(list));
50 if (!this_list) return 0;
51 this_list->entries = gltv_memspool_alloc(total*sizeof(entry));
52 if (! this_list->entries) {
53 gltv_memspool_unregister(this_list);
54 return 0;
55 }
56 if (!(this_list->removed = gltv_stack_new(1+(total>>3), !optimize_for_size)) ) {
57 gltv_memspool_unregister(this_list->entries);
58 gltv_memspool_unregister(this_list);
59 return 0;
60 }
61 this_list->nb_usable_entries = total;
62 /* the 0th entry is unusable in practice because when next=0 it means : last entry.
63 * the 1st entry is unusable also because we tag vaccant entries with next=1 */
64 this_list->nb_used_entries = 2;
65 this_list->begin = 0; /* should be == entries[0].next */
66 this_list->end = 0;
67 this_list->last_accessed_index = 0; /* means none. last_accessed_order is then irrelevant */
68 this_list->next_free_entry = 2;
69 this_list->full_until = 2;
70 this_list->optimize_for_size = optimize_for_size;
71 return (GLTV_LIST)this_list;
72 }
73
gltv_list_del(GLTV_LIST l)74 void gltv_list_del(GLTV_LIST l) {
75 gltv_memspool_unregister(l->entries);
76 gltv_stack_del(l->removed);
77 gltv_memspool_unregister(l);
78 }
79
resize(list * l,unsigned nb_entries)80 static void resize(list *l, unsigned nb_entries) {
81 /* resizing is for entries, not lines */
82 entry *ptr;
83 assert(l->next_free_entry<=nb_entries);
84 ptr = (entry*) gltv_memspool_realloc(l->entries, nb_entries*sizeof(entry));
85 if (!ptr) gltv_log_fatal("list:resize : can't resize");
86 l->entries = ptr;
87 l->nb_usable_entries = nb_entries;
88 }
89
alloc_vaccant_index(list * l)90 static unsigned alloc_vaccant_index(list *l) {
91 /* trouver un emplacement vide dans entries
92 * y loger la valeur et changer les liens, etc */
93 unsigned index;
94 start:
95 if (l->next_free_entry < l->nb_usable_entries) {
96 index = l->next_free_entry;
97 if (l->full_until == l->next_free_entry) l->full_until ++;
98 l->next_free_entry ++;
99 } else {
100 if (gltv_stack_size(l->removed)) {
101 index = (unsigned) gltv_stack_pop(l->removed);
102 assert(l->entries[index].next==1);
103 } else {
104 if (l->nb_used_entries == l->nb_usable_entries) {
105 resize(l, (l->nb_usable_entries*3)>>1);
106 goto start;
107 }
108 assert(l->optimize_for_size); /* otherwise we should have had something on the stack */
109 for (index=l->full_until; index<l->nb_usable_entries; index++)
110 if (1 == l->entries[index].next) {
111 l->full_until = index;
112 break;
113 }
114 assert(index<l->nb_usable_entries);
115 }
116 }
117 l->nb_used_entries++;
118 return index;
119 }
120
desalloc_index(GLTV_LIST l,unsigned index)121 static void desalloc_index(GLTV_LIST l, unsigned index) {
122 if (index == l->next_free_entry-1) {
123 l->next_free_entry--;
124 } else {
125 if (index < l->full_until)
126 l->full_until = index;
127 gltv_stack_push(l->removed, (void*)index);
128 l->entries[index].next=1; /* tag as vaccant */
129 }
130 l->nb_used_entries--;
131 if (l->last_accessed_index == index) l->last_accessed_index=0;
132 }
133
gltv_list_push(GLTV_LIST l,void * value)134 int gltv_list_push(GLTV_LIST l, void *value) {
135 unsigned index = alloc_vaccant_index(l);
136 l->entries[index].value = value;
137 l->entries[index].next = 0;
138 l->entries[index].previous = l->end;
139 l->entries[l->end].next = index;
140 l->end = index;
141 /* perhaps useless if entries[0].next always equals begin */
142 if (1==gltv_list_size(l)) l->begin = index;
143 return 1;
144 }
145
gltv_list_pop(GLTV_LIST l)146 void *gltv_list_pop(GLTV_LIST l) {
147 void *value;
148 unsigned new_end;
149 assert(l->begin != 0);
150 assert(l->entries[l->end].next == 0);
151 value = l->entries[l->end].value;
152 new_end = l->entries[l->end].previous;
153 desalloc_index(l, l->end);
154 l->end = new_end;
155 l->entries[new_end].next = 0;
156 /* perhaps useless if entries[0].next always equals begin */
157 if (0==gltv_list_size(l)) l->begin = 0;
158 return value;
159 }
160
order_to_index(GLTV_LIST l,unsigned order)161 static unsigned order_to_index(GLTV_LIST l, unsigned order) {
162 unsigned length = gltv_list_size(l);
163 unsigned dend, dlast;
164 unsigned index, dexterm, o;
165 assert(order<length);
166 assert(l->last_accessed_index<l->next_free_entry);
167 dend = length-1-order;
168 if (order < dend) {
169 dexterm = order;
170 } else {
171 dexterm = dend;
172 }
173 if (!l->last_accessed_index)
174 goto from_extrem;
175 dlast = order - l->last_accessed_order;
176 if (order < l->last_accessed_order)
177 dlast = 0 - dlast;
178 if (dexterm < dlast)
179 goto from_extrem;
180 /* search index from last accessed */
181 index = l->last_accessed_index;
182 if (order > l->last_accessed_order) {
183 while (dlast) {
184 index = l->entries[index].next;
185 dlast --;
186 }
187 } else {
188 while (dlast) {
189 index = l->entries[index].previous;
190 dlast --;
191 }
192 }
193 l->last_accessed_order = order;
194 l->last_accessed_index = index;
195 assert(index>1);
196 return index;
197 from_extrem:
198 /* search index from extremums */
199 o = dexterm;
200 if (order < dend) { /* from beginning */
201 index = l->begin;
202 while (o) {
203 index = l->entries[index].next;
204 o --;
205 }
206 } else {
207 index = l->end;
208 while (o) {
209 index = l->entries[index].previous;
210 o --;
211 }
212 }
213 if (dexterm>5) {
214 l->last_accessed_order = order;
215 l->last_accessed_index = index;
216 }
217 assert(index>1);
218 return index;
219 }
220
gltv_list_get(GLTV_LIST l,unsigned order)221 void *gltv_list_get(GLTV_LIST l, unsigned order) {
222 unsigned index = order_to_index(l, order);
223 return l->entries[index].value;
224 }
225
gltv_list_set(GLTV_LIST l,unsigned order,void * value)226 void gltv_list_set(GLTV_LIST l, unsigned order, void *value) {
227 unsigned index = order_to_index(l, order);
228 l->entries[index].value = value;
229 }
230
gltv_list_insert(GLTV_LIST l,unsigned order,void * value)231 void gltv_list_insert(GLTV_LIST l, unsigned order, void *value) {
232 unsigned size = gltv_list_size(l);
233 if (order==size) { /* we asked for a push */
234 gltv_list_push(l, value);
235 } else {
236 unsigned free_idx;
237 unsigned index, previous;
238 assert(order<=size);
239 index = order_to_index(l, order);
240 free_idx = alloc_vaccant_index(l);
241 previous = l->entries[index].previous;
242 l->entries[free_idx].value = value;
243 l->entries[free_idx].previous = previous;
244 l->entries[free_idx].next = index;
245 l->entries[index].previous = free_idx;
246 l->entries[previous].next = free_idx;
247 /* as we change the order of elements after this one... */
248 l->last_accessed_index = free_idx;
249 l->last_accessed_order = order;
250 /* perhaps useless if entries[0].next always equals begin */
251 if (0==order) l->begin = free_idx;
252 }
253 }
254
gltv_list_remove(GLTV_LIST l,unsigned order)255 void *gltv_list_remove(GLTV_LIST l, unsigned order) {
256 unsigned index = order_to_index(l, order);
257 void *value = l->entries[index].value;
258 unsigned previous = l->entries[index].previous;
259 unsigned next = l->entries[index].next;
260 l->entries[previous].next = next;
261 l->entries[next].previous = previous;
262 desalloc_index(l, index);
263 /* as we change the order of elements after this one... */
264 l->last_accessed_index = next;
265 l->last_accessed_order = order;
266 /* perhaps useless if entries[0].next always equals begin */
267 if (index==l->begin) l->begin = next;
268 if (index==l->end) l->end = previous;
269 return value;
270 }
271
gltv_list_clear(GLTV_LIST l)272 void gltv_list_clear(GLTV_LIST l) {
273 gltv_stack_clear(l->removed);
274 l->nb_used_entries = 2;
275 l->begin = 0; /* should be == entries[0].next */
276 l->end = 0;
277 l->last_accessed_index = 0; /* means none. last_accessed_order is then irrelevant */
278 l->next_free_entry = 2;
279 l->full_until = 2;
280 }
281
gltv_list_size(GLTV_LIST l)282 unsigned gltv_list_size(GLTV_LIST l) {
283 return l->nb_used_entries -2;
284 }
285
286