granicus.if.org Git - postgresql/blob - src/backend/lib/ilist.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * ilist.c
   4  *        support for integrated/inline doubly- and singly- linked lists
   5  *
   6  * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        src/backend/lib/ilist.c
  12  *
  13  * NOTES
  14  *        This file only contains functions that are too big to be considered
  15  *        for inlining.  See ilist.h for most of the goodies.
  16  *
  17  *-------------------------------------------------------------------------
  18  */
  19 #include "postgres.h"
  20
  21 /* See ilist.h */
  22 #define ILIST_INCLUDE_DEFINITIONS
  23
  24 #include "lib/ilist.h"
  25
  26 /*
  27  * Delete 'node' from list.
  28  *
  29  * It is not allowed to delete a 'node' which is not in the list 'head'
  30  *
  31  * Caution: this is O(n); consider using slist_delete_current() instead.
  32  */
  33 void
  34 slist_delete(slist_head *head, slist_node *node)
  35 {
  36         slist_node *last = &head->head;
  37         slist_node *cur;
  38         bool found      PG_USED_FOR_ASSERTS_ONLY = false;
  39
  40         while ((cur = last->next) != NULL)
  41         {
  42                 if (cur == node)
  43                 {
  44                         last->next = cur->next;
  45 #ifdef USE_ASSERT_CHECKING
  46                         found = true;
  47 #endif
  48                         break;
  49                 }
  50                 last = cur;
  51         }
  52         Assert(found);
  53
  54         slist_check(head);
  55 }
  56
  57 #ifdef ILIST_DEBUG
  58 /*
  59  * Verify integrity of a doubly linked list
  60  */
  61 void
  62 dlist_check(dlist_head *head)
  63 {
  64         dlist_node *cur;
  65
  66         if (head == NULL)
  67                 elog(ERROR, "doubly linked list head address is NULL");
  68
  69         if (head->head.next == NULL && head->head.prev == NULL)
  70                 return;                                 /* OK, initialized as zeroes */
  71
  72         /* iterate in forward direction */
  73         for (cur = head->head.next; cur != &head->head; cur = cur->next)
  74         {
  75                 if (cur == NULL ||
  76                         cur->next == NULL ||
  77                         cur->prev == NULL ||
  78                         cur->prev->next != cur ||
  79                         cur->next->prev != cur)
  80                         elog(ERROR, "doubly linked list is corrupted");
  81         }
  82
  83         /* iterate in backward direction */
  84         for (cur = head->head.prev; cur != &head->head; cur = cur->prev)
  85         {
  86                 if (cur == NULL ||
  87                         cur->next == NULL ||
  88                         cur->prev == NULL ||
  89                         cur->prev->next != cur ||
  90                         cur->next->prev != cur)
  91                         elog(ERROR, "doubly linked list is corrupted");
  92         }
  93 }
  94
  95 /*
  96  * Verify integrity of a singly linked list
  97  */
  98 void
  99 slist_check(slist_head *head)
 100 {
 101         slist_node *cur;
 102
 103         if (head == NULL)
 104                 elog(ERROR, "singly linked list head address is NULL");
 105
 106         /*
 107          * there isn't much we can test in a singly linked list except that it
 108          * actually ends sometime, i.e. hasn't introduced a cycle or similar
 109          */
 110         for (cur = head->head.next; cur != NULL; cur = cur->next)
 111                 ;
 112 }
 113
 114 #endif   /* ILIST_DEBUG */