--- /dev/null
+/*
+This is a Optical-Character-Recognition program
+Copyright (C) 2000-2006 Joerg Schulenburg
+
+This program is free software; you can redistribute it and/or
+modify it under the terms of the GNU General Public License
+as published by the Free Software Foundation; either version 2
+of the License, or (at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+ see README for email address
+
+ ***********************************IMPORTANT*********************************
+ Notes to the developers: read the following notes before using these
+ functions.
+ * Be careful when using for_each_data() recursively and calling list_del.
+ It may mangle with the current[] pointers, and possibly segfault or do an
+ unpredictable or just undesirable behavior. We have been working on a
+ solution for this problem, and solved some of the biggest problems.
+ In a few words, the problem is this: when you delete a node, it may be
+ the current node of a lower level loop. The current code takes care of
+ access to previous/next elements of the now defunct node. So, if you do
+ something like:
+
+ for_each_data(l) {
+ for_each_data(l) {
+ list_del(l, header_data);
+ free(header_data);
+ } end_for_each(l);
++ tempnode = list_cur_next(l);
+ } end_for_each(l);
+
+ It will work, even though the current node in the outer loop was deleted.
+ However, if you replace the line marked with + with the following code:
+
+ tempnode = list_next(l, list_get_current(l));
+
+ it will break, since list_get_current is likely to return NULL or garbage,
+ since you deleted header_data().
+ Conclusion: use list_del carefully. The best way to avoid this problem is
+ to not use list_del inside a big stack of loops.
+ * If you have two elements with the same data, the functions will assume
+ that the first one is the wanted one. Not a bug, a feature. ;-)
+ * avoid calling list_prev and list_next. They are intensive and slow
+ functions. Keep the result in a variable or, if you need something more,
+ use list_get_element_from_data.
+
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "list.h"
+#include "progress.h"
+
+void list_init( List *l ) {
+ if ( !l )
+ return;
+
+ l->start.next = &l->stop;
+ l->stop.previous = &l->start;
+ l->start.previous = l->stop.next = NULL;
+ l->start.data = l->stop.data = NULL;
+ l->current = NULL;
+ l->level = -1;
+ l->n = 0;
+}
+
+/* inserts data before data_after. If data_after == NULL, appends.
+ Returns 1 on error, 0 if OK. */
+int list_ins( List *l, void *data_after, void *data) {
+ Element *e, *after_element;
+
+ /* test arguments */
+ if ( !l || !data )
+ return 1;
+
+ if ( !data_after || !l->n )
+ return list_app(l, data);
+
+ /* get data_after element */
+ if ( !(after_element = list_element_from_data(l, data_after)) )
+ return 1;
+
+ /* alloc a new element */
+ if( !(e = (Element *)malloc(sizeof(Element))) )
+ return 1;
+ e->data = data;
+ e->next = after_element;
+ e->previous = after_element->previous;
+ after_element->previous->next = e;
+ after_element->previous = e;
+ l->n++;
+
+ return 0;
+}
+
+/* appends data to the list. Returns 1 on error, 0 if OK. */
+/* same as list_ins(l,NULL,data) ??? */
+int list_app( List *l, void *data ) {
+ Element *e;
+
+ if ( !l || !data )
+ return 1;
+ if ( !(e = (Element *)malloc(sizeof(Element))) )
+ return 1;
+
+ e->data = data;
+ e->previous = l->stop.previous;
+ e->next = l->stop.previous->next;
+ l->stop.previous->next = e;
+ l->stop.previous = e;
+ l->n++;
+ return 0;
+}
+
+/* returns element associated with data. */
+Element *list_element_from_data( List *l, void *data ) {
+ Element *temp;
+
+ if ( !l || !data || !l->n)
+ return NULL;
+
+ temp = l->start.next;
+
+ while ( temp->data != data ) {
+ if ( !temp || temp==&l->stop )
+ return NULL;
+ temp = temp->next;
+ }
+ return temp;
+}
+
+/* deletes (first) element with data from list. User must free data.
+ Returns 0 if OK, 1 on error.
+ This is the internal version, that shouldn't be called usually. Use the
+ list_del() macro instead.
+ */
+int list_del( List *l, void *data ) {
+ Element *temp;
+ int i;
+
+ if (!data) return 1; /* do not delete start or stop element */
+
+ /* find element associated with data */
+ if ( !(temp = list_element_from_data(l, data)) )
+ return 1;
+
+ /* test if the deleted node is current in some nested loop, and fix it. */
+ for ( i = l->level; i >= 0; i-- ) {
+ if ( l->current[i] == temp ) {
+ l->current[i] = temp->previous;
+ }
+ }
+
+ temp->previous->next = temp->next;
+ temp->next->previous = temp->previous;
+ temp->previous = temp->next = NULL; /* mark as freed */
+/*
+ fprintf(stderr,"\n# list_del=%p start=%p stop=%p",temp,&l->start,&l->stop);
+*/
+
+ /* and free stuff */
+ free(temp); /* element pointing to data, fixed mem-leak 0.41 */
+ l->n--;
+ return 0;
+}
+
+/* frees list. See also list_and_data_free() */
+void list_free( List *l ) {
+ Element *temp, *temp2;
+
+ if ( !l || !l->n )
+ return;
+
+ if ( l->current ) {
+ free(l->current);
+ }
+ l->current = NULL;
+
+ temp = l->start.next;
+ while ( temp && temp!=&l->stop) {
+ temp2 = temp->next;
+ free(temp);
+ temp = temp2;
+ }
+ l->start.next = &l->stop;
+ l->stop.previous = &l->start;
+}
+
+/* setup a new level of for_each */
+int list_higher_level( List *l ) {
+ Element **newcur;
+
+ if ( !l ) return(1);
+
+ /*
+ Security-check: NULL pointer passed to realloc.
+ ANSI allows this, but it may cause portability problems.
+ */
+ newcur = (Element **)realloc(l->current, (l->level+2)*sizeof(Element *));
+ if (newcur) {
+ l->current = newcur;
+ l->level++;
+ l->current[l->level] = l->start.next;
+ }
+ g_debug(fprintf(stderr, " level++=%d current[]=%p\n",
+ l->level, l->current);)
+ if ( !newcur ) {
+ fprintf(stderr, " realloc failed! abort\n"); return(1);
+ }
+ return 0;
+}
+
+void list_lower_level( List *l ) {
+ if ( !l )
+ return;
+
+ if (!l->level) {
+ free(l->current); /* calm -lefence */
+ l->current = NULL; /* could be important */
+ } else {
+ l->current = (Element **)realloc(l->current, l->level*sizeof(Element *));
+ }
+ l->level--;
+ g_debug(fprintf(stderr, " level--=%d current[]=%p\n", l->level,
+ l->current);)
+}
+
+/* returns the next item data */
+void *list_next( List *l, void *data ) {
+ Element *temp;
+
+ if ( !l || !(temp = list_element_from_data(l, data)) )
+ return NULL;
+ if( !temp->next ) return NULL;
+ return (temp->next->data);
+}
+
+/* returns the previous item data */
+void *list_prev( List *l, void *data ) {
+ Element *temp;
+
+ if ( !l || !(temp = list_element_from_data(l, data)) )
+ return NULL;
+ if( !temp->previous ) return NULL;
+ return (temp->previous->data);
+}
+
+/* Similar to qsort. Sorts list, using the (*compare) function, which is
+ provided by the user. The comparison function must return an integer less
+ than, equal to, or greater than zero if the first argument is considered to
+ be respectively less than, equal to, or greater than the second.
+ Uses the bubble sort algorithm.
+ */
+void list_sort( List *l, int (*compare)(const void *, const void *) ) {
+ Element *temp, *prev;
+ int i, sorted;
+ progress_counter_t *pc = NULL;
+
+ if ( !l )
+ return;
+
+ /* start progress meter, sorting is slow for huge number of elements */
+ /* l->n is the worst case, real time is less or equal estimated time */
+ pc = open_progress(l->n,"list_sort");
+
+ for (i = 0; i < l->n; i++ ) {
+ sorted = 1; /* Flag for early break */
+ for ( temp = l->start.next->next;
+ temp != NULL && temp != &l->stop; temp = temp->next ) {
+ if ( temp->previous == &l->start ) continue;
+ if ( compare((const void *)temp->previous->data,
+ (const void *)temp->data) > 0 ) {
+
+ sorted = 0; /* rest flag */
+ /* swap with the previous node */
+ prev = temp->previous;
+ prev->previous->next = temp;
+ temp->next->previous = prev;
+ temp->previous = prev->previous;
+ prev->next = temp->next;
+ prev->previous = temp;
+ temp->next = prev;
+ /* and make sure the node in the for loop is correct */
+ temp = prev;
+
+#ifdef SLOWER_BUT_KEEP_BY_NOW
+/* this is a slower version, but guaranteed to work */
+ void *data;
+
+ data = temp->data;
+ prev = temp->previous;
+ list_del(l, data);
+ list_ins(l, prev->data, data);
+ temp = prev;
+#endif
+ }
+ }
+ if (sorted) break;
+ progress(i,pc); /* progress meter */
+ }
+
+ close_progress(pc);
+ g_debug(fprintf(stderr, "list_sort()\n");)
+}
+
+/* calls free_data() for each data in list l,
+ * before free list with list_free() */
+int list_and_data_free( List *l, void (*free_data)(void *data)) {
+ void *data;
+
+ if ( !l ) return 0;
+ if ( !free_data ) return 1;
+
+ for_each_data(l) {
+ if ((data = list_get_current(l)))
+ free_data(data);
+ } end_for_each(l);
+
+ list_free(l);
+
+ g_debug(fprintf(stderr, "list_and_data_free()\n");)
+
+ return 0;
+}
+
git.asbjorn.biz / swftools.git / blobdiff