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