2 This is a Optical-Character-Recognition program
3 Copyright (C) 2000-2006 Joerg Schulenburg
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.
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.
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.
19 see README for email address
21 ***********************************IMPORTANT*********************************
22 Notes to the developers: read the following notes before using these
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
35 list_del(l, header_data);
38 + tempnode = list_cur_next(l);
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:
44 tempnode = list_next(l, list_get_current(l));
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.
63 void list_init( List *l ) {
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;
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;
85 if ( !data_after || !l->n )
86 return list_app(l, data);
88 /* get data_after element */
89 if ( !(after_element = list_element_from_data(l, data_after)) )
92 /* alloc a new element */
93 if( !(e = (Element *)malloc(sizeof(Element))) )
96 e->next = after_element;
97 e->previous = after_element->previous;
98 after_element->previous->next = e;
99 after_element->previous = e;
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 ) {
112 if ( !(e = (Element *)malloc(sizeof(Element))) )
116 e->previous = l->stop.previous;
117 e->next = l->stop.previous->next;
118 l->stop.previous->next = e;
119 l->stop.previous = e;
124 /* returns element associated with data. */
125 Element *list_element_from_data( List *l, void *data ) {
128 if ( !l || !data || !l->n)
131 temp = l->start.next;
133 while ( temp->data != data ) {
134 if ( !temp || temp==&l->stop )
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.
146 int list_del( List *l, void *data ) {
150 if (!data) return 1; /* do not delete start or stop element */
152 /* find element associated with data */
153 if ( !(temp = list_element_from_data(l, data)) )
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;
163 temp->previous->next = temp->next;
164 temp->next->previous = temp->previous;
165 temp->previous = temp->next = NULL; /* mark as freed */
167 fprintf(stderr,"\n# list_del=%p start=%p stop=%p",temp,&l->start,&l->stop);
171 free(temp); /* element pointing to data, fixed mem-leak 0.41 */
176 /* frees list. See also list_and_data_free() */
177 void list_free( List *l ) {
178 Element *temp, *temp2;
188 temp = l->start.next;
189 while ( temp && temp!=&l->stop) {
194 l->start.next = &l->stop;
195 l->stop.previous = &l->start;
198 /* setup a new level of for_each */
199 int list_higher_level( List *l ) {
205 Security-check: NULL pointer passed to realloc.
206 ANSI allows this, but it may cause portability problems.
208 newcur = (Element **)realloc(l->current, (l->level+2)*sizeof(Element *));
212 l->current[l->level] = l->start.next;
214 g_debug(fprintf(stderr, " level++=%d current[]=%p\n",
215 l->level, l->current);)
217 fprintf(stderr, " realloc failed! abort\n"); return(1);
222 void list_lower_level( List *l ) {
227 free(l->current); /* calm -lefence */
228 l->current = NULL; /* could be important */
230 l->current = (Element **)realloc(l->current, l->level*sizeof(Element *));
233 g_debug(fprintf(stderr, " level--=%d current[]=%p\n", l->level,
237 /* returns the next item data */
238 void *list_next( List *l, void *data ) {
241 if ( !l || !(temp = list_element_from_data(l, data)) )
243 if( !temp->next ) return NULL;
244 return (temp->next->data);
247 /* returns the previous item data */
248 void *list_prev( List *l, void *data ) {
251 if ( !l || !(temp = list_element_from_data(l, data)) )
253 if( !temp->previous ) return NULL;
254 return (temp->previous->data);
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.
263 void list_sort( List *l, int (*compare)(const void *, const void *) ) {
264 Element *temp, *prev;
266 progress_counter_t *pc = NULL;
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");
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 ) {
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;
292 /* and make sure the node in the for loop is correct */
295 #ifdef SLOWER_BUT_KEEP_BY_NOW
296 /* this is a slower version, but guaranteed to work */
300 prev = temp->previous;
302 list_ins(l, prev->data, data);
308 progress(i,pc); /* progress meter */
312 g_debug(fprintf(stderr, "list_sort()\n");)
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)) {
321 if ( !free_data ) return 1;
324 if ((data = list_get_current(l)))
330 g_debug(fprintf(stderr, "list_and_data_free()\n");)