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-2024, 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, const 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  * dlist_member_check
  57  *              Validate that 'node' is a member of 'head'
  58  */
  59 void
  60 dlist_member_check(const dlist_head *head, const dlist_node *node)
  61 {
  62         const dlist_node *cur;
  63
  64         /* iteration open-coded to due to the use of const */
  65         for (cur = head->head.next; cur != &head->head; cur = cur->next)
  66         {
  67                 if (cur == node)
  68                         return;
  69         }
  70         elog(ERROR, "double linked list member check failure");
  71 }
  72
  73 /*
  74  * Verify integrity of a doubly linked list
  75  */
  76 void
  77 dlist_check(const dlist_head *head)
  78 {
  79         dlist_node *cur;
  80
  81         if (head == NULL)
  82                 elog(ERROR, "doubly linked list head address is NULL");
  83
  84         if (head->head.next == NULL && head->head.prev == NULL)
  85                 return;                                 /* OK, initialized as zeroes */
  86
  87         /* iterate in forward direction */
  88         for (cur = head->head.next; cur != &head->head; cur = cur->next)
  89         {
  90                 if (cur == NULL ||
  91                         cur->next == NULL ||
  92                         cur->prev == NULL ||
  93                         cur->prev->next != cur ||
  94                         cur->next->prev != cur)
  95                         elog(ERROR, "doubly linked list is corrupted");
  96         }
  97
  98         /* iterate in backward direction */
  99         for (cur = head->head.prev; cur != &head->head; cur = cur->prev)
 100         {
 101                 if (cur == NULL ||
 102                         cur->next == NULL ||
 103                         cur->prev == NULL ||
 104                         cur->prev->next != cur ||
 105                         cur->next->prev != cur)
 106                         elog(ERROR, "doubly linked list is corrupted");
 107         }
 108 }
 109
 110 /*
 111  * Verify integrity of a singly linked list
 112  */
 113 void
 114 slist_check(const slist_head *head)
 115 {
 116         slist_node *cur;
 117
 118         if (head == NULL)
 119                 elog(ERROR, "singly linked list head address is NULL");
 120
 121         /*
 122          * there isn't much we can test in a singly linked list except that it
 123          * actually ends sometime, i.e. hasn't introduced a cycle or similar
 124          */
 125         for (cur = head->head.next; cur != NULL; cur = cur->next)
 126                 ;
 127 }
 128
 129 #endif                                                  /* ILIST_DEBUG */