Leptonica  1.82.0
Image processing and image analysis suite
list.c
Go to the documentation of this file.
1 /*====================================================================*
2  - Copyright (C) 2001 Leptonica. All rights reserved.
3  -
4  - Redistribution and use in source and binary forms, with or without
5  - modification, are permitted provided that the following conditions
6  - are met:
7  - 1. Redistributions of source code must retain the above copyright
8  - notice, this list of conditions and the following disclaimer.
9  - 2. Redistributions in binary form must reproduce the above
10  - copyright notice, this list of conditions and the following
11  - disclaimer in the documentation and/or other materials
12  - provided with the distribution.
13  -
14  - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15  - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16  - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17  - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18  - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23  - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24  - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  *====================================================================*/
26 
213 #ifdef HAVE_CONFIG_H
214 #include <config_auto.h>
215 #endif /* HAVE_CONFIG_H */
216 
217 #include <string.h>
218 #include "allheaders.h"
219 
220 /*---------------------------------------------------------------------*
221  * Inserting and removing elements *
222  *---------------------------------------------------------------------*/
238 void
240 {
241 DLLIST *elem, *next, *head;
242 
243  PROCNAME("listDestroy");
244 
245  if (phead == NULL) {
246  L_WARNING("ptr address is null!\n", procName);
247  return;
248  }
249 
250  if ((head = *phead) == NULL)
251  return;
252 
253  for (elem = head; elem; elem = next) {
254  if (elem->data)
255  L_WARNING("list data ptr is not null\n", procName);
256  next = elem->next;
257  LEPT_FREE(elem);
258  }
259  *phead = NULL;
260 }
261 
262 
278 l_ok
280  void *data)
281 {
282 DLLIST *cell, *head;
283 
284  PROCNAME("listAddToHead");
285 
286  if (!phead)
287  return ERROR_INT("&head not defined", procName, 1);
288  head = *phead;
289  if (!data)
290  return ERROR_INT("data not defined", procName, 1);
291 
292  cell = (DLLIST *)LEPT_CALLOC(1, sizeof(DLLIST));
293  cell->data = data;
294  if (!head) { /* start the list; initialize the ptrs */
295  cell->prev = NULL;
296  cell->next = NULL;
297  } else {
298  cell->prev = NULL;
299  cell->next = head;
300  head->prev = cell;
301  }
302  *phead = cell;
303  return 0;
304 }
305 
306 
330 l_ok
332  DLLIST **ptail,
333  void *data)
334 {
335 DLLIST *cell, *head, *tail;
336 
337  PROCNAME("listAddToTail");
338 
339  if (!phead)
340  return ERROR_INT("&head not defined", procName, 1);
341  head = *phead;
342  if (!ptail)
343  return ERROR_INT("&tail not defined", procName, 1);
344  if (!data)
345  return ERROR_INT("data not defined", procName, 1);
346 
347  cell = (DLLIST *)LEPT_CALLOC(1, sizeof(DLLIST));
348  cell->data = data;
349  if (!head) { /* Start the list and initialize the ptrs. *ptail
350  * should also have been initialized to NULL */
351  cell->prev = NULL;
352  cell->next = NULL;
353  *phead = cell;
354  *ptail = cell;
355  } else {
356  if ((tail = *ptail) == NULL)
357  tail = listFindTail(head);
358  cell->prev = tail;
359  cell->next = NULL;
360  tail->next = cell;
361  *ptail = cell;
362  }
363 
364  return 0;
365 }
366 
367 
391 l_ok
393  DLLIST *elem,
394  void *data)
395 {
396 DLLIST *cell, *head;
397 
398  PROCNAME("listInsertBefore");
399 
400  if (!phead)
401  return ERROR_INT("&head not defined", procName, 1);
402  head = *phead;
403  if (!data)
404  return ERROR_INT("data not defined", procName, 1);
405  if ((!head && elem) || (head && !elem))
406  return ERROR_INT("head and elem not consistent", procName, 1);
407 
408  /* New cell to insert */
409  cell = (DLLIST *)LEPT_CALLOC(1, sizeof(DLLIST));
410  cell->data = data;
411  if (!head) { /* start the list; initialize the ptrs */
412  cell->prev = NULL;
413  cell->next = NULL;
414  *phead = cell;
415  } else if (head == elem) { /* insert before head of list */
416  cell->prev = NULL;
417  cell->next = head;
418  head->prev = cell;
419  *phead = cell;
420  } else { /* insert before elem and after head of list */
421  cell->prev = elem->prev;
422  cell->next = elem;
423  elem->prev->next = cell;
424  elem->prev = cell;
425  }
426  return 0;
427 }
428 
429 
454 l_ok
456  DLLIST *elem,
457  void *data)
458 {
459 DLLIST *cell, *head;
460 
461  PROCNAME("listInsertAfter");
462 
463  if (!phead)
464  return ERROR_INT("&head not defined", procName, 1);
465  head = *phead;
466  if (!data)
467  return ERROR_INT("data not defined", procName, 1);
468  if ((!head && elem) || (head && !elem))
469  return ERROR_INT("head and elem not consistent", procName, 1);
470 
471  /* New cell to insert */
472  cell = (DLLIST *)LEPT_CALLOC(1, sizeof(DLLIST));
473  cell->data = data;
474  if (!head) { /* start the list; initialize the ptrs */
475  cell->prev = NULL;
476  cell->next = NULL;
477  *phead = cell;
478  } else if (elem->next == NULL) { /* insert after last */
479  cell->prev = elem;
480  cell->next = NULL;
481  elem->next = cell;
482  } else { /* insert after elem and before the end */
483  cell->prev = elem;
484  cell->next = elem->next;
485  elem->next->prev = cell;
486  elem->next = cell;
487  }
488  return 0;
489 }
490 
491 
507 void *
509  DLLIST *elem)
510 {
511 void *data;
512 DLLIST *head;
513 
514  PROCNAME("listRemoveElement");
515 
516  if (!phead)
517  return (void *)ERROR_PTR("&head not defined", procName, NULL);
518  head = *phead;
519  if (!head)
520  return (void *)ERROR_PTR("head not defined", procName, NULL);
521  if (!elem)
522  return (void *)ERROR_PTR("elem not defined", procName, NULL);
523 
524  data = elem->data;
525 
526  if (head->next == NULL) { /* only one */
527  if (elem != head)
528  return (void *)ERROR_PTR("elem must be head", procName, NULL);
529  *phead = NULL;
530  } else if (head == elem) { /* first one */
531  elem->next->prev = NULL;
532  *phead = elem->next;
533  } else if (elem->next == NULL) { /* last one */
534  elem->prev->next = NULL;
535  } else { /* neither the first nor the last one */
536  elem->next->prev = elem->prev;
537  elem->prev->next = elem->next;
538  }
539 
540  LEPT_FREE(elem);
541  return data;
542 }
543 
544 
559 void *
561 {
562 DLLIST *head;
563 void *data;
564 
565  PROCNAME("listRemoveFromHead");
566 
567  if (!phead)
568  return (void *)ERROR_PTR("&head not defined", procName, NULL);
569  if ((head = *phead) == NULL)
570  return (void *)ERROR_PTR("head not defined", procName, NULL);
571 
572  if (head->next == NULL) { /* only one */
573  *phead = NULL;
574  } else {
575  head->next->prev = NULL;
576  *phead = head->next;
577  }
578 
579  data = head->data;
580  LEPT_FREE(head);
581  return data;
582 }
583 
584 
607 void *
609  DLLIST **ptail)
610 {
611 DLLIST *head, *tail;
612 void *data;
613 
614  PROCNAME("listRemoveFromTail");
615 
616  if (!phead)
617  return (void *)ERROR_PTR("&head not defined", procName, NULL);
618  if ((head = *phead) == NULL)
619  return (void *)ERROR_PTR("head not defined", procName, NULL);
620  if (!ptail)
621  return (void *)ERROR_PTR("&tail not defined", procName, NULL);
622  if ((tail = *ptail) == NULL)
623  tail = listFindTail(head);
624 
625  if (head->next == NULL) { /* only one */
626  *phead = NULL;
627  *ptail = NULL;
628  } else {
629  tail->prev->next = NULL;
630  *ptail = tail->prev;
631  }
632 
633  data = tail->data;
634  LEPT_FREE(tail);
635  return data;
636 }
637 
638 
639 
640 /*---------------------------------------------------------------------*
641  * Other list operations *
642  *---------------------------------------------------------------------*/
661 DLLIST *
663  void *data)
664 {
665 DLLIST *cell;
666 
667  PROCNAME("listFindElement");
668 
669  if (!head)
670  return (DLLIST *)ERROR_PTR("head not defined", procName, NULL);
671  if (!data)
672  return (DLLIST *)ERROR_PTR("data not defined", procName, NULL);
673 
674  for (cell = head; cell; cell = cell->next) {
675  if (cell->data == data)
676  return cell;
677  }
678 
679  return NULL;
680 }
681 
682 
689 DLLIST *
691 {
692 DLLIST *cell;
693 
694  PROCNAME("listFindTail");
695 
696  if (!head)
697  return (DLLIST *)ERROR_PTR("head not defined", procName, NULL);
698 
699  for (cell = head; cell; cell = cell->next) {
700  if (cell->next == NULL)
701  return cell;
702  }
703 
704  return (DLLIST *)ERROR_PTR("tail not found !!", procName, NULL);
705 }
706 
707 
714 l_int32
716 {
717 l_int32 count;
718 DLLIST *elem;
719 
720  PROCNAME("listGetCount");
721 
722  if (!head)
723  return ERROR_INT("head not defined", procName, 0);
724 
725  count = 0;
726  for (elem = head; elem; elem = elem->next)
727  count++;
728 
729  return count;
730 }
731 
732 
744 l_ok
746 {
747 void *obj; /* whatever */
748 DLLIST *head, *rhead;
749 
750  PROCNAME("listReverse");
751 
752  if (!phead)
753  return ERROR_INT("&head not defined", procName, 1);
754  if ((head = *phead) == NULL)
755  return ERROR_INT("head not defined", procName, 1);
756 
757  rhead = NULL;
758  while (head) {
759  obj = listRemoveFromHead(&head);
760  listAddToHead(&rhead, obj);
761  }
762 
763  *phead = rhead;
764  return 0;
765 }
766 
767 
781 l_ok
782 listJoin(DLLIST **phead1,
783  DLLIST **phead2)
784 {
785 void *obj;
786 DLLIST *head1, *head2, *tail1;
787 
788  PROCNAME("listJoin");
789 
790  if (!phead1)
791  return ERROR_INT("&head1 not defined", procName, 1);
792  if (!phead2)
793  return ERROR_INT("&head2 not defined", procName, 1);
794 
795  /* If no list2, just return list1 unchanged */
796  if ((head2 = *phead2) == NULL)
797  return 0;
798 
799  /* If no list1, just return list2 */
800  if ((head1 = *phead1) == NULL) {
801  *phead1 = head2;
802  *phead2 = NULL;
803  return 0;
804  }
805 
806  /* General case for concatenation into list 1 */
807  tail1 = listFindTail(head1);
808  while (head2) {
809  obj = listRemoveFromHead(&head2);
810  listAddToTail(&head1, &tail1, obj);
811  }
812  *phead2 = NULL;
813  return 0;
814 }
l_ok listAddToHead(DLLIST **phead, void *data)
listAddToHead()
Definition: list.c:279
void * listRemoveFromTail(DLLIST **phead, DLLIST **ptail)
listRemoveFromTail()
Definition: list.c:608
l_ok listAddToTail(DLLIST **phead, DLLIST **ptail, void *data)
listAddToTail()
Definition: list.c:331
l_ok listInsertAfter(DLLIST **phead, DLLIST *elem, void *data)
listInsertAfter()
Definition: list.c:455
void * listRemoveFromHead(DLLIST **phead)
listRemoveFromHead()
Definition: list.c:560
l_ok listJoin(DLLIST **phead1, DLLIST **phead2)
listJoin()
Definition: list.c:782
void * listRemoveElement(DLLIST **phead, DLLIST *elem)
listRemoveElement()
Definition: list.c:508
DLLIST * listFindTail(DLLIST *head)
listFindTail()
Definition: list.c:690
l_ok listReverse(DLLIST **phead)
listReverse()
Definition: list.c:745
l_ok listInsertBefore(DLLIST **phead, DLLIST *elem, void *data)
listInsertBefore()
Definition: list.c:392
DLLIST * listFindElement(DLLIST *head, void *data)
listFindElement()
Definition: list.c:662
l_int32 listGetCount(DLLIST *head)
listGetCount()
Definition: list.c:715
void listDestroy(DLLIST **phead)
listDestroy()
Definition: list.c:239