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-2015, 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 #include "lib/ilist.h"
  22
  23 /*
  24  * Delete 'node' from list.
  25  *
  26  * It is not allowed to delete a 'node' which is not in the list 'head'
  27  *
  28  * Caution: this is O(n); consider using slist_delete_current() instead.
  29  */
  30 void
  31 slist_delete(slist_head *head, slist_node *node)
  32 {
  33         slist_node *last = &head->head;
  34         slist_node *cur;
  35         bool found      PG_USED_FOR_ASSERTS_ONLY = false;
  36
  37         while ((cur = last->next) != NULL)
  38         {
  39                 if (cur == node)
  40                 {
  41                         last->next = cur->next;
  42 #ifdef USE_ASSERT_CHECKING
  43                         found = true;
  44 #endif
  45                         break;
  46                 }
  47                 last = cur;
  48         }
  49         Assert(found);
  50
  51         slist_check(head);
  52 }
  53
  54 #ifdef ILIST_DEBUG
  55 /*
  56  * Verify integrity of a doubly linked list
  57  */
  58 void
  59 dlist_check(dlist_head *head)
  60 {
  61         dlist_node *cur;
  62
  63         if (head == NULL)
  64                 elog(ERROR, "doubly linked list head address is NULL");
  65
  66         if (head->head.next == NULL && head->head.prev == NULL)
  67                 return;                                 /* OK, initialized as zeroes */
  68
  69         /* iterate in forward direction */
  70         for (cur = head->head.next; cur != &head->head; cur = cur->next)
  71         {
  72                 if (cur == NULL ||
  73                         cur->next == NULL ||
  74                         cur->prev == NULL ||
  75                         cur->prev->next != cur ||
  76                         cur->next->prev != cur)
  77                         elog(ERROR, "doubly linked list is corrupted");
  78         }
  79
  80         /* iterate in backward direction */
  81         for (cur = head->head.prev; cur != &head->head; cur = cur->prev)
  82         {
  83                 if (cur == NULL ||
  84                         cur->next == NULL ||
  85                         cur->prev == NULL ||
  86                         cur->prev->next != cur ||
  87                         cur->next->prev != cur)
  88                         elog(ERROR, "doubly linked list is corrupted");
  89         }
  90 }
  91
  92 /*
  93  * Verify integrity of a singly linked list
  94  */
  95 void
  96 slist_check(slist_head *head)
  97 {
  98         slist_node *cur;
  99
 100         if (head == NULL)
 101                 elog(ERROR, "singly linked list head address is NULL");
 102
 103         /*
 104          * there isn't much we can test in a singly linked list except that it
 105          * actually ends sometime, i.e. hasn't introduced a cycle or similar
 106          */
 107         for (cur = head->head.next; cur != NULL; cur = cur->next)
 108                 ;
 109 }
 110
 111 #endif   /* ILIST_DEBUG */