Leptonica  1.83.1
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  if (phead == NULL) {
244  L_WARNING("ptr address is null!\n", __func__);
245  return;
246  }
247 
248  if ((head = *phead) == NULL)
249  return;
250 
251  for (elem = head; elem; elem = next) {
252  if (elem->data)
253  L_WARNING("list data ptr is not null\n", __func__);
254  next = elem->next;
255  LEPT_FREE(elem);
256  }
257  *phead = NULL;
258 }
259 
260 
276 l_ok
278  void *data)
279 {
280 DLLIST *cell, *head;
281 
282  if (!phead)
283  return ERROR_INT("&head not defined", __func__, 1);
284  head = *phead;
285  if (!data)
286  return ERROR_INT("data not defined", __func__, 1);
287 
288  cell = (DLLIST *)LEPT_CALLOC(1, sizeof(DLLIST));
289  cell->data = data;
290  if (!head) { /* start the list; initialize the ptrs */
291  cell->prev = NULL;
292  cell->next = NULL;
293  } else {
294  cell->prev = NULL;
295  cell->next = head;
296  head->prev = cell;
297  }
298  *phead = cell;
299  return 0;
300 }
301 
302 
326 l_ok
328  DLLIST **ptail,
329  void *data)
330 {
331 DLLIST *cell, *head, *tail;
332 
333  if (!phead)
334  return ERROR_INT("&head not defined", __func__, 1);
335  head = *phead;
336  if (!ptail)
337  return ERROR_INT("&tail not defined", __func__, 1);
338  if (!data)
339  return ERROR_INT("data not defined", __func__, 1);
340 
341  cell = (DLLIST *)LEPT_CALLOC(1, sizeof(DLLIST));
342  cell->data = data;
343  if (!head) { /* Start the list and initialize the ptrs. *ptail
344  * should also have been initialized to NULL */
345  cell->prev = NULL;
346  cell->next = NULL;
347  *phead = cell;
348  *ptail = cell;
349  } else {
350  if ((tail = *ptail) == NULL)
351  tail = listFindTail(head);
352  cell->prev = tail;
353  cell->next = NULL;
354  tail->next = cell;
355  *ptail = cell;
356  }
357 
358  return 0;
359 }
360 
361 
385 l_ok
387  DLLIST *elem,
388  void *data)
389 {
390 DLLIST *cell, *head;
391 
392  if (!phead)
393  return ERROR_INT("&head not defined", __func__, 1);
394  head = *phead;
395  if (!data)
396  return ERROR_INT("data not defined", __func__, 1);
397  if ((!head && elem) || (head && !elem))
398  return ERROR_INT("head and elem not consistent", __func__, 1);
399 
400  /* New cell to insert */
401  cell = (DLLIST *)LEPT_CALLOC(1, sizeof(DLLIST));
402  cell->data = data;
403  if (!head) { /* start the list; initialize the ptrs */
404  cell->prev = NULL;
405  cell->next = NULL;
406  *phead = cell;
407  } else if (head == elem) { /* insert before head of list */
408  cell->prev = NULL;
409  cell->next = head;
410  head->prev = cell;
411  *phead = cell;
412  } else { /* insert before elem and after head of list */
413  cell->prev = elem->prev;
414  cell->next = elem;
415  elem->prev->next = cell;
416  elem->prev = cell;
417  }
418  return 0;
419 }
420 
421 
446 l_ok
448  DLLIST *elem,
449  void *data)
450 {
451 DLLIST *cell, *head;
452 
453  if (!phead)
454  return ERROR_INT("&head not defined", __func__, 1);
455  head = *phead;
456  if (!data)
457  return ERROR_INT("data not defined", __func__, 1);
458  if ((!head && elem) || (head && !elem))
459  return ERROR_INT("head and elem not consistent", __func__, 1);
460 
461  /* New cell to insert */
462  cell = (DLLIST *)LEPT_CALLOC(1, sizeof(DLLIST));
463  cell->data = data;
464  if (!head) { /* start the list; initialize the ptrs */
465  cell->prev = NULL;
466  cell->next = NULL;
467  *phead = cell;
468  } else if (elem->next == NULL) { /* insert after last */
469  cell->prev = elem;
470  cell->next = NULL;
471  elem->next = cell;
472  } else { /* insert after elem and before the end */
473  cell->prev = elem;
474  cell->next = elem->next;
475  elem->next->prev = cell;
476  elem->next = cell;
477  }
478  return 0;
479 }
480 
481 
497 void *
499  DLLIST *elem)
500 {
501 void *data;
502 DLLIST *head;
503 
504  if (!phead)
505  return (void *)ERROR_PTR("&head not defined", __func__, NULL);
506  head = *phead;
507  if (!head)
508  return (void *)ERROR_PTR("head not defined", __func__, NULL);
509  if (!elem)
510  return (void *)ERROR_PTR("elem not defined", __func__, NULL);
511 
512  data = elem->data;
513 
514  if (head->next == NULL) { /* only one */
515  if (elem != head)
516  return (void *)ERROR_PTR("elem must be head", __func__, NULL);
517  *phead = NULL;
518  } else if (head == elem) { /* first one */
519  elem->next->prev = NULL;
520  *phead = elem->next;
521  } else if (elem->next == NULL) { /* last one */
522  elem->prev->next = NULL;
523  } else { /* neither the first nor the last one */
524  elem->next->prev = elem->prev;
525  elem->prev->next = elem->next;
526  }
527 
528  LEPT_FREE(elem);
529  return data;
530 }
531 
532 
547 void *
549 {
550 DLLIST *head;
551 void *data;
552 
553  if (!phead)
554  return (void *)ERROR_PTR("&head not defined", __func__, NULL);
555  if ((head = *phead) == NULL)
556  return (void *)ERROR_PTR("head not defined", __func__, NULL);
557 
558  if (head->next == NULL) { /* only one */
559  *phead = NULL;
560  } else {
561  head->next->prev = NULL;
562  *phead = head->next;
563  }
564 
565  data = head->data;
566  LEPT_FREE(head);
567  return data;
568 }
569 
570 
593 void *
595  DLLIST **ptail)
596 {
597 DLLIST *head, *tail;
598 void *data;
599 
600  if (!phead)
601  return (void *)ERROR_PTR("&head not defined", __func__, NULL);
602  if ((head = *phead) == NULL)
603  return (void *)ERROR_PTR("head not defined", __func__, NULL);
604  if (!ptail)
605  return (void *)ERROR_PTR("&tail not defined", __func__, NULL);
606  if ((tail = *ptail) == NULL)
607  tail = listFindTail(head);
608 
609  if (head->next == NULL) { /* only one */
610  *phead = NULL;
611  *ptail = NULL;
612  } else {
613  tail->prev->next = NULL;
614  *ptail = tail->prev;
615  }
616 
617  data = tail->data;
618  LEPT_FREE(tail);
619  return data;
620 }
621 
622 
623 
624 /*---------------------------------------------------------------------*
625  * Other list operations *
626  *---------------------------------------------------------------------*/
645 DLLIST *
647  void *data)
648 {
649 DLLIST *cell;
650 
651  if (!head)
652  return (DLLIST *)ERROR_PTR("head not defined", __func__, NULL);
653  if (!data)
654  return (DLLIST *)ERROR_PTR("data not defined", __func__, NULL);
655 
656  for (cell = head; cell; cell = cell->next) {
657  if (cell->data == data)
658  return cell;
659  }
660 
661  return NULL;
662 }
663 
664 
671 DLLIST *
673 {
674 DLLIST *cell;
675 
676  if (!head)
677  return (DLLIST *)ERROR_PTR("head not defined", __func__, NULL);
678 
679  for (cell = head; cell; cell = cell->next) {
680  if (cell->next == NULL)
681  return cell;
682  }
683 
684  return (DLLIST *)ERROR_PTR("tail not found !!", __func__, NULL);
685 }
686 
687 
694 l_int32
696 {
697 l_int32 count;
698 DLLIST *elem;
699 
700  if (!head)
701  return ERROR_INT("head not defined", __func__, 0);
702 
703  count = 0;
704  for (elem = head; elem; elem = elem->next)
705  count++;
706 
707  return count;
708 }
709 
710 
722 l_ok
724 {
725 void *obj; /* whatever */
726 DLLIST *head, *rhead;
727 
728  if (!phead)
729  return ERROR_INT("&head not defined", __func__, 1);
730  if ((head = *phead) == NULL)
731  return ERROR_INT("head not defined", __func__, 1);
732 
733  rhead = NULL;
734  while (head) {
735  obj = listRemoveFromHead(&head);
736  listAddToHead(&rhead, obj);
737  }
738 
739  *phead = rhead;
740  return 0;
741 }
742 
743 
757 l_ok
758 listJoin(DLLIST **phead1,
759  DLLIST **phead2)
760 {
761 void *obj;
762 DLLIST *head1, *head2, *tail1;
763 
764  if (!phead1)
765  return ERROR_INT("&head1 not defined", __func__, 1);
766  if (!phead2)
767  return ERROR_INT("&head2 not defined", __func__, 1);
768 
769  /* If no list2, just return list1 unchanged */
770  if ((head2 = *phead2) == NULL)
771  return 0;
772 
773  /* If no list1, just return list2 */
774  if ((head1 = *phead1) == NULL) {
775  *phead1 = head2;
776  *phead2 = NULL;
777  return 0;
778  }
779 
780  /* General case for concatenation into list 1 */
781  tail1 = listFindTail(head1);
782  while (head2) {
783  obj = listRemoveFromHead(&head2);
784  listAddToTail(&head1, &tail1, obj);
785  }
786  *phead2 = NULL;
787  return 0;
788 }
l_ok listAddToHead(DLLIST **phead, void *data)
listAddToHead()
Definition: list.c:277
void * listRemoveFromTail(DLLIST **phead, DLLIST **ptail)
listRemoveFromTail()
Definition: list.c:594
l_ok listAddToTail(DLLIST **phead, DLLIST **ptail, void *data)
listAddToTail()
Definition: list.c:327
l_ok listInsertAfter(DLLIST **phead, DLLIST *elem, void *data)
listInsertAfter()
Definition: list.c:447
void * listRemoveFromHead(DLLIST **phead)
listRemoveFromHead()
Definition: list.c:548
l_ok listJoin(DLLIST **phead1, DLLIST **phead2)
listJoin()
Definition: list.c:758
void * listRemoveElement(DLLIST **phead, DLLIST *elem)
listRemoveElement()
Definition: list.c:498
DLLIST * listFindTail(DLLIST *head)
listFindTail()
Definition: list.c:672
l_ok listReverse(DLLIST **phead)
listReverse()
Definition: list.c:723
l_ok listInsertBefore(DLLIST **phead, DLLIST *elem, void *data)
listInsertBefore()
Definition: list.c:386
DLLIST * listFindElement(DLLIST *head, void *data)
listFindElement()
Definition: list.c:646
l_int32 listGetCount(DLLIST *head)
listGetCount()
Definition: list.c:695
void listDestroy(DLLIST **phead)
listDestroy()
Definition: list.c:239