common/list.h

   1 /*
   2  * list.h - useful list handling header
   3  *
   4  * Copyright © 2008 Julien Danjou <julien@danjou.info>
   5  * Copyright © 2006 Pierre Habouzit <madcoder@debian.org>
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License along
  18  * with this program; if not, write to the Free Software Foundation, Inc.,
  19  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  */
  22
  23 #ifndef AWESOME_COMMON_LIST_H
  24 #define AWESOME_COMMON_LIST_H
  25
  26 #define DO_SLIST(type, prefix, dtor)                                             \
  27     static inline type *prefix##_list_next(type **list __attribute__ ((unused)), \
  28                                            type *item)                           \
  29     {                                                                            \
  30         return item->next;                                                       \
  31     }                                                                            \
  32                                                                                  \
  33     static inline type *prefix##_list_pop(type **list)                           \
  34     {                                                                            \
  35         if (*list)                                                               \
  36         {                                                                        \
  37             type *res = *list;                                                   \
  38             *list = res->next;                                                   \
  39             if(res->next)                                                        \
  40                 res->next->prev = NULL;                                          \
  41             res->next = NULL;                                                    \
  42             return res;                                                          \
  43         }                                                                        \
  44         return NULL;                                                             \
  45     }                                                                            \
  46                                                                                  \
  47     static inline void prefix##_list_push(type **list, type *item)               \
  48     {                                                                            \
  49         if(*list)                                                                \
  50             (*list)->prev = item;                                                \
  51         item->next = *list;                                                      \
  52         *list = item;                                                            \
  53     }                                                                            \
  54                                                                                  \
  55     static inline type **prefix##_list_last(type **list)                         \
  56     {                                                                            \
  57         while (*list && (*list)->next)                                           \
  58             list = &(*list)->next;                                               \
  59         return list;                                                             \
  60     }                                                                            \
  61                                                                                  \
  62     static inline void prefix##_list_append(type **list, type *item)             \
  63     {                                                                            \
  64         if(*(list = prefix##_list_last(list)))                                   \
  65         {                                                                        \
  66             (*list)->next = item;                                                \
  67             item->prev = *list;                                                  \
  68         }                                                                        \
  69         else                                                                     \
  70             (*list) = item;                                                      \
  71     }                                                                            \
  72                                                                                  \
  73     static inline type *prefix##_list_rev(type *list)                            \
  74     {                                                                            \
  75         type *l = NULL;                                                          \
  76         while (list)                                                             \
  77             prefix##_list_push(&l, prefix##_list_pop(&list));                    \
  78         return l;                                                                \
  79     }                                                                            \
  80                                                                                  \
  81     static inline type **prefix##_list_init(type **list)                         \
  82     {                                                                            \
  83         *list = NULL;                                                            \
  84         return list;                                                             \
  85     }                                                                            \
  86                                                                                  \
  87     static inline void prefix##_list_wipe(type **list)                           \
  88     {                                                                            \
  89         while (*list)                                                            \
  90         {                                                                        \
  91             type *item = prefix##_list_pop(list);                                \
  92             dtor(&item);                                                         \
  93         }                                                                        \
  94     }                                                                            \
  95                                                                                  \
  96     static inline type *prefix##_list_prev(type **list __attribute__ ((unused)), \
  97                                            type *item)                           \
  98     {                                                                            \
  99         return item->prev;                                                       \
 100     }                                                                            \
 101                                                                                  \
 102     static inline void prefix##_list_swap(type **list, type *item1, type *item2) \
 103     {                                                                            \
 104         type *i1n, *i2n, *i1p, *i2p;                                             \
 105                                                                                  \
 106         if(!item1 || !item2) return;                                             \
 107                                                                                  \
 108         i1n = item1->next;                                                       \
 109         i2n = item2->next;                                                       \
 110         i1p = item1->prev;                                                       \
 111         i2p = item2->prev;                                                       \
 112                                                                                  \
 113         if(item1 == i2n)                                                         \
 114         {                                                                        \
 115             item1->next = item2;                                                 \
 116             item2->prev = item1;                                                 \
 117             if((item1->prev = i2p))                                              \
 118                 i2p->next = item1;                                               \
 119             if((item2->next = i1n))                                              \
 120                 i1n->prev = item2;                                               \
 121         }                                                                        \
 122         else if(item2 == i1n)                                                    \
 123         {                                                                        \
 124             item2->next = item1;                                                 \
 125             item1->prev = item2;                                                 \
 126             if((item2->prev = i1p))                                              \
 127                 i1p->next = item2;                                               \
 128             if((item1->next = i2n))                                              \
 129                 i2n->prev = item1;                                               \
 130         }                                                                        \
 131         else                                                                     \
 132         {                                                                        \
 133             if((item1->next = i2n))                                              \
 134                 item1->next->prev = item1;                                       \
 135             if((item1->prev = i2p))                                              \
 136                 item1->prev->next = item1;                                       \
 137             if((item2->prev = i1p))                                              \
 138                 item2->prev->next = item2;                                       \
 139             if((item2->next = i1n))                                              \
 140                 item2->next->prev = item2;                                       \
 141         }                                                                        \
 142         if(*list == item1)                                                       \
 143             *list = item2;                                                       \
 144         else if(*list == item2)                                                  \
 145             *list = item1;                                                       \
 146     }                                                                            \
 147                                                                                  \
 148     static inline type *prefix##_list_prev_cycle(type **list, type *item)        \
 149     {                                                                            \
 150         if(!item->prev)                                                          \
 151             return *prefix##_list_last(list);                                    \
 152         return item->prev;                                                       \
 153     }                                                                            \
 154                                                                                  \
 155     static inline type *prefix##_list_next_cycle(type **list, type *item)        \
 156     {                                                                            \
 157         if(item->next)                                                           \
 158             return item->next;                                                   \
 159         return *list;                                                            \
 160     }                                                                            \
 161                                                                                  \
 162     static inline type *prefix##_list_detach(type **list, type *item)            \
 163     {                                                                            \
 164         if(item == *list)                                                        \
 165             *list = item->next;                                                  \
 166         else if(item->prev)                                                      \
 167              item->prev->next = item->next;                                      \
 168         if(item->next)                                                           \
 169              item->next->prev = item->prev;                                      \
 170         item->next = NULL;                                                       \
 171         item->prev = NULL;                                                       \
 172         return item;                                                             \
 173     }                                                                            \
 174     static inline type *prefix##_list_attach_after(type *item1, type *item2)     \
 175     {                                                                            \
 176         item2->prev = item1;                                                     \
 177         item2->next = item1->next;                                               \
 178         if(item1->next)                                                          \
 179             item1->next->prev = item2;                                           \
 180         item1->next = item2;                                                     \
 181         return item2;                                                            \
 182     }
 183
 184 #endif
 185 // vim: filetype=c:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=80