dlink.h

   1 /* DLIFE Copyright (C) 2000 Richard W.M. Jones <rich@annexia.org>
   2  * and other authors listed in the ``AUTHORS'' file.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  17  *
  18  * $Id: dlink.h,v 1.1 2002/04/05 14:40:26 rich Exp $
  19  */
  20
  21 #ifndef dlink_h
  22 #define dlink_h
  23
  24 /* This was snarfed from the source for Python 1.5. */
  25 #ifdef HAVE_STDDEF_H
  26 #include <stddef.h>
  27 #endif
  28
  29 #ifndef offsetof
  30 #define offsetof(type, member) ( (int) & ((type*)0) -> member )
  31 #endif
  32
  33 typedef struct dlink_list_element
  34 {
  35   void *next;
  36   void *prev;
  37 } dlink_list_element_t;
  38
  39 typedef struct dlink_list
  40 {
  41   void *first;
  42   void *last;
  43   int offset;
  44 } dlink_list_t;
  45
  46 #define DLINK_LIST_INIT(offset) { 0, 0, (offset) }
  47
  48 #define _DLINK_ELEMENT_PTRS(element,list) ((dlink_list_element_t *) ((element) + (list)->offset))
  49 #define _DLINK_FIRST_PTRS(list) _DLINK_ELEMENT_PTRS((list)->first,(list))
  50 #define _DLINK_LAST_PTRS(list) _DLINK_ELEMENT_PTRS((list)->last,(list))
  51
  52 extern inline void
  53 dlink_list_init (dlink_list_t *list, int offset)
  54 {
  55   list->first = list->last = 0;
  56   list->offset = offset;
  57 }
  58
  59 extern inline void
  60 insert_before_first (void *element, dlink_list_t *list)
  61 {
  62   dlink_list_element_t *eptrs = _DLINK_ELEMENT_PTRS (element, list);
  63
  64   eptrs->prev = 0;
  65   eptrs->next = list->first;
  66   if (list->first)
  67     _DLINK_FIRST_PTRS(list)->prev = element;
  68   else
  69     list->last = element;
  70   list->first = element;
  71 }
  72
  73 extern inline void
  74 insert_before_last (void *element, dlink_list_t *list)
  75 {
  76   dlink_list_element_t *eptrs = _DLINK_ELEMENT_PTRS (element, list);
  77
  78   eptrs->next = 0;
  79   eptrs->prev = list->last;
  80   if (list->last)
  81     _DLINK_LAST_PTRS(list)->next = element;
  82   else
  83     list->first = element;
  84   list->last = element;
  85 }
  86
  87 extern inline void
  88 move_towards_last (void *e, dlink_list_t *list)
  89 {
  90   dlink_list_element_t *eptrs = _DLINK_ELEMENT_PTRS (e, list);
  91
  92   void *e0 = eptrs->prev;
  93   dlink_list_element_t *e0ptrs = _DLINK_ELEMENT_PTRS (e0, list);
  94
  95   void *e1 = eptrs->next;
  96   dlink_list_element_t *e1ptrs = _DLINK_ELEMENT_PTRS (e1, list);
  97
  98   void *e2 = e1ptrs->next;
  99   dlink_list_element_t *e2ptrs = _DLINK_ELEMENT_PTRS (e2, list);
 100
 101   /* The elements are:   e0 <---> e <---> e1 <---> e2.
 102    *
 103    * We know that e and e1 exist, but e0 and e2 may or may not exist.
 104    *
 105    * We want the arrangement to be:
 106    *                     e0 <---> e1 <---> e <---> e2.
 107    */
 108   e1ptrs->prev = e0;
 109   if (e0)
 110     e0ptrs->next = e1;
 111   else
 112     list->first = e1;
 113
 114   e1ptrs->next = e;
 115   eptrs->prev = e1;
 116
 117   eptrs->next = e2;
 118   if (e2)
 119     e2ptrs->prev = e;
 120   else
 121     list->last = e;
 122 }
 123
 124 extern inline void
 125 remove_element (void *element, dlink_list_t *list)
 126 {
 127   dlink_list_element_t *eptrs = _DLINK_ELEMENT_PTRS (element, list);
 128
 129   void *eprev = eptrs->prev;
 130   dlink_list_element_t *eprevptrs = _DLINK_ELEMENT_PTRS (eprev, list);
 131
 132   void *enext = eptrs->next;
 133   dlink_list_element_t *enextptrs = _DLINK_ELEMENT_PTRS (enext, list);
 134
 135   if (eptrs->next)
 136     enextptrs->prev = eprev;
 137   else
 138     list->last = eprev;
 139
 140   if (eptrs->prev)
 141     eprevptrs->next = enext;
 142   else
 143     list->first = enext;
 144 }
 145
 146 #endif /* dlink_h */