more build fixes
[swftools.git] / lib / gocr / list.c
1 /*
2 This is a Optical-Character-Recognition program
3 Copyright (C) 2000-2006  Joerg Schulenburg
4
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License
7 as published by the Free Software Foundation; either version 2
8 of the License, or (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18
19  see README for email address
20  
21  ***********************************IMPORTANT*********************************
22  Notes to the developers: read the following notes before using these
23  functions.
24    * Be careful when using for_each_data() recursively and calling list_del.
25     It may mangle with the current[] pointers, and possibly segfault or do an
26     unpredictable or just undesirable behavior. We have been working on a 
27     solution for this problem, and solved some of the biggest problems.
28      In a few words, the problem is this: when you delete a node, it may be
29     the current node of a lower level loop. The current code takes care of
30     access to previous/next elements of the now defunct node. So, if you do
31     something like:
32   
33     for_each_data(l) {
34       for_each_data(l) {
35         list_del(l, header_data);
36         free(header_data);
37       } end_for_each(l);
38 +     tempnode = list_cur_next(l);
39     } end_for_each(l);
40
41     It will work, even though the current node in the outer loop was deleted.
42     However, if you replace the line marked with + with the following code:
43
44       tempnode = list_next(l, list_get_current(l));
45
46     it will break, since list_get_current is likely to return NULL or garbage,
47     since you deleted header_data().
48      Conclusion: use list_del carefully. The best way to avoid this problem is
49     to not use list_del inside a big stack of loops.
50    * If you have two elements with the same data, the functions will assume 
51     that the first one is the wanted one. Not a bug, a feature. ;-)
52    * avoid calling list_prev and list_next. They are intensive and slow 
53     functions. Keep the result in a variable or, if you need something more,
54     use list_get_element_from_data.
55
56  */
57
58 #include <stdio.h>
59 #include <stdlib.h>
60 #include "list.h"
61 #include "progress.h"
62
63 void list_init( List *l ) {
64   if ( !l )
65      return;
66
67   l->start.next     = &l->stop;
68   l->stop.previous  = &l->start;
69   l->start.previous = l->stop.next = NULL;
70   l->start.data = l->stop.data = NULL;
71   l->current = NULL;
72   l->level = -1;
73   l->n = 0;
74 }
75
76 /* inserts data before data_after. If data_after == NULL, appends.
77    Returns 1 on error, 0 if OK. */
78 int list_ins( List *l, void *data_after, void *data) {
79   Element *e, *after_element;
80
81   /* test arguments */
82   if ( !l || !data )
83     return 1;
84
85   if ( !data_after || !l->n )
86     return list_app(l, data);
87
88   /* get data_after element */
89   if ( !(after_element = list_element_from_data(l, data_after)) )
90     return 1;
91
92   /* alloc a new element */
93   if( !(e = (Element *)malloc(sizeof(Element))) )
94     return 1;
95   e->data     = data;
96   e->next     = after_element;
97   e->previous = after_element->previous;
98   after_element->previous->next = e;
99   after_element->previous       = e;
100   l->n++;
101
102   return 0;
103 }
104
105 /* appends data to the list. Returns 1 on error, 0 if OK. */
106 /* same as list_ins(l,NULL,data) ??? */
107 int list_app( List *l, void *data ) {
108   Element *e;
109   
110   if ( !l || !data )
111      return 1;
112   if ( !(e = (Element *)malloc(sizeof(Element))) )
113     return 1;
114   
115   e->data     = data;
116   e->previous = l->stop.previous;
117   e->next     = l->stop.previous->next;
118   l->stop.previous->next = e;
119   l->stop.previous       = e;
120   l->n++;
121   return 0;
122 }
123
124 /* returns element associated with data. */
125 Element *list_element_from_data( List *l, void *data ) {
126   Element *temp;
127
128   if ( !l || !data || !l->n)
129     return NULL;
130
131   temp = l->start.next;
132
133   while ( temp->data != data ) {
134     if ( !temp || temp==&l->stop )
135       return NULL;
136     temp = temp->next;
137   }
138   return temp;
139 }
140
141 /* deletes (first) element with data from list. User must free data.
142    Returns 0 if OK, 1 on error.
143    This is the internal version, that shouldn't be called usually. Use the
144    list_del() macro instead.
145  */
146 int list_del( List *l, void *data ) {
147   Element *temp;
148   int i;
149
150   if (!data) return 1; /* do not delete start or stop element */
151
152   /* find element associated with data */
153   if ( !(temp = list_element_from_data(l, data)) )
154     return 1;
155
156   /* test if the deleted node is current in some nested loop, and fix it. */
157   for ( i = l->level; i >= 0; i-- ) {
158     if ( l->current[i] == temp ) {
159       l->current[i] = temp->previous;
160     }
161   }
162
163   temp->previous->next = temp->next;
164   temp->next->previous = temp->previous;
165   temp->previous = temp->next = NULL; /* mark as freed */
166 /*
167   fprintf(stderr,"\n# list_del=%p start=%p stop=%p",temp,&l->start,&l->stop);
168 */
169
170   /* and free stuff */
171   free(temp); /* element pointing to data, fixed mem-leak 0.41 */
172   l->n--;
173   return 0;
174 }
175
176 /* frees list. See also list_and_data_free() */
177 void list_free( List *l ) {
178   Element *temp, *temp2;
179
180   if ( !l || !l->n )
181     return;
182
183   if ( l->current ) {
184     free(l->current);
185   }
186   l->current = NULL;
187
188   temp = l->start.next;
189   while ( temp && temp!=&l->stop) {
190     temp2 = temp->next;
191     free(temp);
192     temp = temp2;
193   }
194   l->start.next    = &l->stop;
195   l->stop.previous = &l->start;
196 }
197
198 /* setup a new level of for_each */
199 int list_higher_level( List *l ) {
200   Element **newcur;
201   
202   if ( !l ) return(1);
203
204   /*
205      Security-check: NULL pointer passed to realloc.
206       ANSI allows this, but it may cause portability problems.
207   */    
208   newcur = (Element **)realloc(l->current, (l->level+2)*sizeof(Element *));
209   if (newcur) {
210     l->current = newcur;
211     l->level++;
212     l->current[l->level] = l->start.next;
213   }
214   g_debug(fprintf(stderr, " level++=%d current[]=%p\n",
215      l->level, l->current);)
216   if ( !newcur  ) {
217     fprintf(stderr, " realloc failed! abort\n"); return(1);
218   }
219   return 0;
220 }
221
222 void list_lower_level( List *l ) {
223   if ( !l ) 
224     return;
225
226   if (!l->level) {
227     free(l->current); /* calm -lefence */
228     l->current = NULL; /* could be important */
229   } else {
230     l->current = (Element **)realloc(l->current, l->level*sizeof(Element *));
231   }
232   l->level--;
233   g_debug(fprintf(stderr, " level--=%d current[]=%p\n", l->level, 
234       l->current);)
235 }
236
237 /* returns the next item data */
238 void *list_next( List *l, void *data ) {
239   Element *temp;
240
241   if ( !l || !(temp = list_element_from_data(l, data)) )
242     return NULL;
243   if( !temp->next ) return NULL;
244   return (temp->next->data);
245 }
246
247 /* returns the previous item data */
248 void *list_prev( List *l, void *data ) {
249   Element *temp;
250
251   if ( !l || !(temp = list_element_from_data(l, data)) )
252     return NULL;
253   if( !temp->previous ) return NULL;
254   return (temp->previous->data);
255 }
256
257 /* Similar to qsort. Sorts list, using the (*compare) function, which is 
258   provided by the user. The comparison function must return an integer less 
259   than, equal to, or greater than zero if the first argument is considered to 
260   be respectively less than, equal to, or greater than the second. 
261   Uses the bubble sort algorithm.
262   */
263 void list_sort( List *l, int (*compare)(const void *, const void *) ) {
264   Element *temp, *prev;
265   int i, sorted;
266   progress_counter_t *pc = NULL;
267
268   if ( !l )
269     return;
270
271   /* start progress meter, sorting is slow for huge number of elements */
272   /* l->n is the worst case, real time is less or equal estimated time */
273   pc = open_progress(l->n,"list_sort");
274   
275   for (i = 0; i < l->n; i++ ) {
276     sorted = 1; /* Flag for early break */
277     for ( temp = l->start.next->next;
278           temp != NULL && temp != &l->stop; temp = temp->next ) {
279       if ( temp->previous == &l->start ) continue;
280       if ( compare((const void *)temp->previous->data,
281                    (const void *)temp->data) > 0 ) {
282
283         sorted = 0;  /* rest flag */
284         /* swap with the previous node */
285         prev = temp->previous;
286         prev->previous->next = temp;
287         temp->next->previous = prev;
288         temp->previous = prev->previous;
289         prev->next     = temp->next;
290         prev->previous = temp;
291         temp->next     = prev;
292         /* and make sure the node in the for loop is correct */
293         temp = prev;
294
295 #ifdef SLOWER_BUT_KEEP_BY_NOW
296 /* this is a slower version, but guaranteed to work */
297         void *data;
298
299         data = temp->data;
300         prev = temp->previous;
301         list_del(l, data);
302         list_ins(l, prev->data, data);
303         temp = prev;
304 #endif
305       }
306     }
307     if (sorted) break;
308     progress(i,pc); /* progress meter */
309   }
310
311   close_progress(pc);
312   g_debug(fprintf(stderr, "list_sort()\n");)
313 }
314
315 /* calls free_data() for each data in list l, 
316  * before free list with list_free() */
317 int list_and_data_free( List *l, void (*free_data)(void *data)) {
318   void *data;
319
320   if ( !l ) return 0;
321   if ( !free_data ) return 1;
322
323   for_each_data(l) {
324     if ((data = list_get_current(l)))
325       free_data(data);
326   } end_for_each(l);
327   
328   list_free(l);
329
330   g_debug(fprintf(stderr, "list_and_data_free()\n");)
331
332   return 0;
333 }
334