Header And Logo

PostgreSQL
| The world's most advanced open source database.

ilist.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * ilist.c
00004  *    support for integrated/inline doubly- and singly- linked lists
00005  *
00006  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00007  * Portions Copyright (c) 1994, Regents of the University of California
00008  *
00009  *
00010  * IDENTIFICATION
00011  *    src/backend/lib/ilist.c
00012  *
00013  * NOTES
00014  *    This file only contains functions that are too big to be considered
00015  *    for inlining.  See ilist.h for most of the goodies.
00016  *
00017  *-------------------------------------------------------------------------
00018  */
00019 #include "postgres.h"
00020 
00021 /* See ilist.h */
00022 #define ILIST_INCLUDE_DEFINITIONS
00023 
00024 #include "lib/ilist.h"
00025 
00026 /*
00027  * Delete 'node' from list.
00028  *
00029  * It is not allowed to delete a 'node' which is is not in the list 'head'
00030  *
00031  * Caution: this is O(n)
00032  */
00033 void
00034 slist_delete(slist_head *head, slist_node *node)
00035 {
00036     slist_node *last = &head->head;
00037     slist_node *cur;
00038     bool found  PG_USED_FOR_ASSERTS_ONLY = false;
00039 
00040     while ((cur = last->next) != NULL)
00041     {
00042         if (cur == node)
00043         {
00044             last->next = cur->next;
00045 #ifdef USE_ASSERT_CHECKING
00046             found = true;
00047 #endif
00048             break;
00049         }
00050         last = cur;
00051     }
00052     Assert(found);
00053 
00054     slist_check(head);
00055 }
00056 
00057 #ifdef ILIST_DEBUG
00058 /*
00059  * Verify integrity of a doubly linked list
00060  */
00061 void
00062 dlist_check(dlist_head *head)
00063 {
00064     dlist_node *cur;
00065 
00066     if (head == NULL)
00067         elog(ERROR, "doubly linked list head address is NULL");
00068 
00069     if (head->head.next == NULL && head->head.prev == NULL)
00070         return;                 /* OK, initialized as zeroes */
00071 
00072     /* iterate in forward direction */
00073     for (cur = head->head.next; cur != &head->head; cur = cur->next)
00074     {
00075         if (cur == NULL ||
00076             cur->next == NULL ||
00077             cur->prev == NULL ||
00078             cur->prev->next != cur ||
00079             cur->next->prev != cur)
00080             elog(ERROR, "doubly linked list is corrupted");
00081     }
00082 
00083     /* iterate in backward direction */
00084     for (cur = head->head.prev; cur != &head->head; cur = cur->prev)
00085     {
00086         if (cur == NULL ||
00087             cur->next == NULL ||
00088             cur->prev == NULL ||
00089             cur->prev->next != cur ||
00090             cur->next->prev != cur)
00091             elog(ERROR, "doubly linked list is corrupted");
00092     }
00093 }
00094 
00095 /*
00096  * Verify integrity of a singly linked list
00097  */
00098 void
00099 slist_check(slist_head *head)
00100 {
00101     slist_node *cur;
00102 
00103     if (head == NULL)
00104         elog(ERROR, "singly linked list head address is NULL");
00105 
00106     /*
00107      * there isn't much we can test in a singly linked list except that it
00108      * actually ends sometime, i.e. hasn't introduced a cycle or similar
00109      */
00110     for (cur = head->head.next; cur != NULL; cur = cur->next)
00111         ;
00112 }
00113 
00114 #endif   /* ILIST_DEBUG */