Line data    Source code

       1              : /*-------------------------------------------------------------------------
       2              :  *
       3              :  * ilist.c
       4              :  *    support for integrated/inline doubly- and singly- linked lists
       5              :  *
       6              :  * Portions Copyright (c) 1996-2026, 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         6005 : slist_delete(slist_head *head, const slist_node *node)
      32              : {
      33         6005 :     slist_node *last = &head->head;
      34              :     slist_node *cur;
      35         6005 :     bool        found PG_USED_FOR_ASSERTS_ONLY = false;
      36              : 
      37        20020 :     while ((cur = last->next) != NULL)
      38              :     {
      39        20020 :         if (cur == node)
      40              :         {
      41         6005 :             last->next = cur->next;
      42              : #ifdef USE_ASSERT_CHECKING
      43              :             found = true;
      44              : #endif
      45         6005 :             break;
      46              :         }
      47        14015 :         last = cur;
      48              :     }
      49              :     Assert(found);
      50              : 
      51              :     slist_check(head);
      52         6005 : }
      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 */