Line data    Source code

       1             : /*
       2             :  * list - double linked list routines
       3             :  * Author: Rusty Russell <rusty@rustcorp.com.au>
       4             :  *
       5             :  * The list header contains routines for manipulating double linked lists.
       6             :  * It defines two types: struct list_head used for anchoring lists, and
       7             :  * struct list_node which is usually embedded in the structure which is placed
       8             :  * in the list.
       9             :  *
      10             :  * Permission is hereby granted, free of charge, to any person obtaining a
      11             :  * copy of this software and associated documentation files (the
      12             :  * "Software"), to deal in the Software without restriction, including
      13             :  * without limitation the rights to use, copy, modify, merge, publish,
      14             :  * distribute, sublicense, and/or sell copies of the Software, and to permit
      15             :  * persons to whom the Software is furnished to do so, subject to the
      16             :  * following conditions:
      17             :  *
      18             :  * The above copyright notice and this permission notice shall be included
      19             :  * in all copies or substantial portions of the Software.
      20             :  *
      21             :  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
      22             :  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
      23             :  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
      24             :  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
      25             :  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
      26             :  * OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
      27             :  * THE USE OR OTHER DEALINGS IN THE SOFTWARE.
      28             :  */
      29             : 
      30             : #include <stdio.h>
      31             : #include <stdlib.h>
      32             : 
      33             : #include "list.h"
      34             : 
      35             : #ifndef NDEBUG
      36             : static struct list_node poison_node_1 = {.next = (void *)0xdeadbeef,
      37             :                                          .prev = (void *)0xbebacafe};
      38             : static struct list_node poison_node_2 = {.next = (void *)0xbebacafe,
      39             :                                          .prev = (void *)0xdeadbeef};
      40             : 
      41         796 : void list_poison_node(struct list_node *node)
      42             : {
      43         796 :     node->prev = &poison_node_1;
      44         796 :     node->next = &poison_node_2;
      45         796 : }
      46             : 
      47        5010 : static bool is_poisoned(const struct list_node *node)
      48             : {
      49        5010 :     assert(poison_node_1.next == poison_node_2.prev);
      50        5010 :     assert(poison_node_1.prev == poison_node_2.next);
      51        5010 :     assert(poison_node_1.next == (void *)0xdeadbeef);
      52        5010 :     assert(poison_node_1.prev == (void *)0xbebacafe);
      53             : 
      54       10020 :     return (node->prev == &poison_node_1 || node->prev == &poison_node_2) ||
      55        5010 :            (node->next == &poison_node_1 || node->next == &poison_node_2);
      56             : }
      57             : 
      58           0 : static void *corrupt(const char *abortstr,
      59             :                      const struct list_node *head,
      60             :                      const struct list_node *node,
      61             :                      unsigned int count)
      62             : {
      63           0 :     if (abortstr) {
      64           0 :         fprintf(stderr, "%s: prev corrupt in node %p (%u) of %p\n", abortstr,
      65             :                 node, count, head);
      66           0 :         abort();
      67             :     }
      68           0 :     return NULL;
      69             : }
      70             : #endif
      71             : 
      72        5010 : struct list_node *list_check_node(const struct list_node *node,
      73             :                                   const char *abortstr)
      74             : {
      75             : #ifndef NDEBUG
      76             :     const struct list_node *p, *n;
      77        5010 :     unsigned int count = 0;
      78             : 
      79        5010 :     if (is_poisoned(node))
      80           0 :         return corrupt(abortstr, node, node, 0);
      81             : 
      82        8075 :     for (p = node, n = node->next; n != node; p = n, n = n->next) {
      83        3065 :         count++;
      84        3065 :         if (n->prev != p)
      85           0 :             return corrupt(abortstr, node, n, count);
      86             :     }
      87             :     /* Check prev on head node. */
      88        5010 :     if (node->prev != p)
      89           0 :         return corrupt(abortstr, node, node, 0);
      90             : #else
      91             :     (void)abortstr;
      92             : #endif
      93             : 
      94        5010 :     return (struct list_node *)node;
      95             : }
      96             : 
      97        4214 : struct list_head *list_check(const struct list_head *h, const char *abortstr)
      98             : {
      99        4214 :     if (!list_check_node(&h->n, abortstr))
     100           0 :         return NULL;
     101        4214 :     return (struct list_head *)h;
     102             : }