llist.h

   1 /*
   2     llist.h - simple intrusive cyclic double linked list
   3
   4   Copyright (C) 2003, 2005, Christian Thaeter <chth@gmx.net>
   5
   6   This program is free software; you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License version 2 as
   8   published by the Free Software Foundation.
   9
  10   This program is distributed in the hope that it will be useful,
  11   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13   GNU General Public License for more details.
  14
  15   You should have received a copy of the GNU General Public License
  16   along with this program; if not, contact me.
  17
  18 */
  19
  20 #ifndef LLIST_H
  21 #define LLIST_H
  22
  23 #include <stddef.h>
  24 #include <assert.h>
  25
  26 #ifndef LLIST_SPECIAL_BUILD
  27 #define LLIST_INTERFACE
  28 #define LLIST_IMPLEMENTATION
  29 #endif
  30
  31 #ifdef HAVE_INLINE
  32 #       define LLIST_MACRO static inline
  33 #else
  34 #       ifdef __GNUC__
  35 #               define LLIST_MACRO static __inline__
  36 #       else
  37 #               define LLIST_MACRO static
  38 #       endif
  39 #endif
  40
  41 #ifdef LLIST_INTERFACE
  42
  43 /* we have a llist node in a structure and want to get the structure which embedds it */
  44 /*
  45 //struct foo
  46 //{
  47 // int bar;
  48 // llist l;
  49 //} x;
  50
  51 LLIST_TO_STRUCTP (&x.l, foo, l)->bar
  52 */
  53 #define LLIST_TO_STRUCTP(llist, type, member) \
  54   ((type*)(((char*)(llist)) - offsetof(type, member)))
  55
  56 #define LLIST_FOREACH(list, node)               \
  57   for (LList node = llist_get_head (list);      \
  58        ! llist_is_end (node, list);             \
  59        llist_forward (&node))
  60
  61 #define LLIST_FOREACH_REV(list, node)           \
  62   for (LList node = llist_get_tail (list);      \
  63        ! llist_is_end (node, list);             \
  64        llist_backward (&node))
  65
  66 /*
  67  * Type of a llist node.
  68  */
  69 struct llist_struct
  70 {
  71   struct llist_struct *next;
  72   struct llist_struct *prev;
  73 };
  74 typedef struct llist_struct llist;
  75 typedef llist * LList;
  76 typedef const llist * const_LList;
  77 typedef llist ** LList_ref;
  78
  79 /*
  80  * handy macro to instantiate a local llist 'name' becomes a LList handle and
  81  * the underlying instance is hidden as name_llist_, this list is statically initialized
  82  */
  83 #define LLIST_STATIC_INITIALIZER(name) {&name,&name}
  84 #define LLIST_AUTO(name) \
  85 llist name##_llist_ = LLIST_STATIC_INITIALIZER(name##_llist_);\
  86 LList name = &name##_llist_
  87
  88 LLIST_MACRO void llist_init (LList self);
  89 LLIST_MACRO int llist_is_empty (const_LList self);
  90 LLIST_MACRO int llist_is_single (const_LList self);
  91 LLIST_MACRO int llist_is_head (const_LList self, const_LList list);
  92 LLIST_MACRO int llist_is_tail (const_LList self, const_LList list);
  93 LLIST_MACRO int llist_is_end (const_LList self, const_LList list);
  94 LLIST_MACRO int llist_is_member (const_LList self, const_LList list);
  95 LLIST_MACRO int llist_is_before (const_LList self, const_LList other, const_LList list);
  96 LLIST_MACRO int llist_is_after (const_LList self, const_LList other, const_LList list);
  97 LLIST_MACRO unsigned llist_count (const_LList self);
  98 LLIST_MACRO unsigned llist_distance (const_LList self, const_LList other, const_LList list);
  99 LLIST_MACRO void llist_unlink_fast_ (LList self);
 100 LLIST_MACRO LList llist_unlink (LList self);
 101 LLIST_MACRO LList llist_relocate (LList self);
 102 LLIST_MACRO LList llist_insert_before (LList self, LList successor);
 103 LLIST_MACRO LList llist_insert_after (LList self, LList predcessor);
 104 LLIST_MACRO LList llist_insert_list_before (LList self, LList successor);
 105 LLIST_MACRO LList llist_insert_list_after (LList self, LList predcessor);
 106 LLIST_MACRO LList llist_insert_range_before (LList self, LList start, LList end);
 107 LLIST_MACRO LList llist_insert_range_after (LList self, LList start, LList end);
 108 LLIST_MACRO LList llist_advance (LList self);
 109 LLIST_MACRO LList llist_retreat (LList self);
 110 LLIST_MACRO LList llist_get_next (const_LList self);
 111 LLIST_MACRO LList llist_get_prev (const_LList self);
 112 LLIST_MACRO void llist_forward (LList_ref self);
 113 LLIST_MACRO void llist_backward (LList_ref self);
 114 LLIST_MACRO LList llist_get_nth (LList self, int n);
 115
 116 #endif /*LLIST_INTERFACE*/
 117
 118
 119
 120 #ifdef LLIST_IMPLEMENTATION
 121
 122 #define llist_insert_head(list,element) llist_insert_after(element,list)
 123 #define llist_insert_tail(list,element) llist_insert_before(element,list)
 124 #define llist_get_head llist_get_next
 125 #define llist_get_tail llist_get_prev
 126
 127
 128 /*
 129  * initialize a new llist. Must not be
 130  * applied to a list which is not empty! Lists need to be initialized
 131  * before any other operation on them is called.
 132  */
 133 LLIST_MACRO void
 134 llist_init (LList self)
 135 {
 136   self->next = self->prev = self;
 137 }
 138
 139 /*
 140  * check if a node is linked with some other node
 141  */
 142 LLIST_MACRO int
 143 llist_is_empty (const_LList self)
 144 {
 145   return self->next == self;
 146 }
 147
 148 /*
 149  * check if self is the only node in a list or self is not in a list
 150  */
 151 LLIST_MACRO int
 152 llist_is_single (const_LList self)
 153 {
 154   return self->next->next == self;
 155 }
 156
 157 /*
 158  * check if self is the head of list
 159  */
 160 LLIST_MACRO int
 161 llist_is_head (const_LList self, const_LList list)
 162 {
 163   return list->next == self;
 164 }
 165
 166 /*
 167  * check if self is the tail of list
 168  */
 169 LLIST_MACRO int
 170 llist_is_tail (const_LList self, const_LList list)
 171 {
 172   return list->prev == self;
 173 }
 174
 175 /*
 176  * check if self is the end of list
 177  */
 178 LLIST_MACRO int
 179 llist_is_end (const_LList self, const_LList list)
 180 {
 181   return list == self;
 182 }
 183
 184 /*
 185  * check if self is a member of list
 186  */
 187 LLIST_MACRO int
 188 llist_is_member (const_LList self, const_LList list)
 189 {
 190   const_LList i = self->next;
 191   for (; i != self; i = i->next)
 192     {
 193       if (i == list)
 194         return 1;
 195     }
 196   return 0;
 197 }
 198
 199 /*
 200  * check if self is before other in list
 201  */
 202 LLIST_MACRO int
 203 llist_is_before (const_LList self, const_LList other, const_LList list)
 204 {
 205   assert (llist_is_member (self, list));
 206   assert (llist_is_member (other, list));
 207   const_LList i = self->next;
 208   if (self != other)
 209     {
 210       for (; i != list; i = i->next)
 211         {
 212           if (i == other)
 213             return 1;
 214         }
 215     }
 216   return 0;
 217 }
 218
 219 /*
 220  * check if self is after other in list
 221  */
 222 LLIST_MACRO int
 223 llist_is_after (const_LList self, const_LList other, const_LList list)
 224 {
 225   assert (llist_is_member (self, list));
 226   assert (llist_is_member (other, list));
 227   const_LList i = self->prev;
 228   if (self != other)
 229     {
 230       for (; i != list; i = i->prev)
 231         {
 232           if (i == other)
 233             return 1;
 234         }
 235     }
 236   return 0;
 237 }
 238
 239
 240 /*
 241  * count the nodes of self
 242  */
 243 LLIST_MACRO unsigned
 244 llist_count (const_LList self)
 245 {
 246   unsigned cnt = 0;
 247   const_LList i = self;
 248   for (; i->next != self; ++cnt, i = i->next);
 249   return cnt;
 250 }
 251
 252 /*
 253  * count distance from self to other in list
 254  */
 255 LLIST_MACRO unsigned
 256 llist_distance (const_LList self, const_LList other, const_LList list)
 257 {
 258   assert (llist_is_member (self, list));
 259   assert (llist_is_member (other, list));
 260
 261   unsigned cnt = 0;
 262   const_LList i = self;
 263   for (; i->next != other && i->next != list; ++cnt, i = i->next);
 264   if (i->next == list)
 265     for (cnt = 0, i = self; i->prev != other; ++cnt, i = i->prev);
 266   return cnt;
 267 }
 268
 269 /* private */
 270 LLIST_MACRO void
 271 llist_unlink_fast_ (LList self)
 272 {
 273   LList nxt = self->next, pre = self->prev;
 274   nxt->prev = pre;
 275   pre->next = nxt;
 276 }
 277
 278 /*
 279  * removes self from its list
 280  */
 281 LLIST_MACRO LList
 282 llist_unlink (LList self)
 283 {
 284   llist_unlink_fast_ (self);
 285   return self->next = self->prev = self;
 286 }
 287
 288 /*
 289  * fixes a list if self got relocated in memory
 290  */
 291 LLIST_MACRO LList
 292 llist_relocate (LList self)
 293 {
 294   return self->next->prev = self->prev->next = self;
 295 }
 296
 297 /*
 298  * inserts self before successor,
 299  * self can already linked to a list where it will be removed
 300  */
 301 LLIST_MACRO LList
 302 llist_insert_before (LList self, LList successor)
 303 {
 304   llist_unlink_fast_ (self);
 305   self->prev = successor->prev;
 306   self->next = successor;
 307   return successor->prev = self->prev->next = self;
 308 }
 309
 310
 311 /*
 312  * inserts self after predcessor,
 313  * self can already linked to a list where it will be removed
 314  */
 315 LLIST_MACRO LList
 316 llist_insert_after (LList self, LList predcessor)
 317 {
 318   llist_unlink_fast_ (self);
 319   self->next = predcessor->next;
 320   self->prev = predcessor;
 321   return predcessor->next = self->next->prev = self;
 322 }
 323
 324 /*
 325  * move the content of list self before node successor
 326  */
 327 LLIST_MACRO LList
 328 llist_insert_list_before (LList self, LList successor)
 329 {
 330   self->next->prev = successor->prev;
 331   self->prev->next = successor;
 332   successor->prev->next = self->next;
 333   successor->prev = self->prev;
 334   self->prev = self->next = self;
 335   return self;
 336 }
 337
 338 /*
 339  * move the content of list self after node predcessor
 340  */
 341 LLIST_MACRO LList
 342 llist_insert_list_after (LList self, LList predcessor)
 343 {
 344   self->prev->next = predcessor->next;
 345   self->next->prev = predcessor;
 346   predcessor->next->prev = self->prev;
 347   predcessor->next = self->next;
 348   self->prev = self->next = self;
 349   return self;
 350 }
 351
 352 /*
 353  * move members from start to end->prev before self
 354  */
 355 LLIST_MACRO
 356 LList llist_insert_range_before (LList self, LList start, LList end)
 357 {
 358   LList tmp = self->prev;
 359   start->prev->next = end;
 360   end->prev->next = self;
 361   self->prev->next = start;
 362
 363   self->prev = end->prev;
 364   end->prev = start->prev;
 365   start->prev = tmp;
 366
 367   return self;
 368 }
 369
 370 /*
 371  * move members from start to end->prev after self
 372  */
 373 LLIST_MACRO
 374 LList llist_insert_range_after (LList self, LList start, LList end)
 375 {
 376   start->prev->next = end;
 377   end->prev->next = self->next;
 378   self->next->prev = end->prev;
 379   self->next = start;
 380   end->prev = start->prev;
 381   start->prev = self;
 382   return self;
 383 }
 384
 385 /*
 386  * swap a node with its next node
 387  */
 388 LLIST_MACRO LList
 389 llist_advance (LList self)
 390 {
 391   LList tmp = self->next->next;
 392   tmp->prev = self;
 393   self->next->prev = self->prev;
 394   self->prev->next = self->next;
 395   self->prev = self->next;
 396   self->next->next = self;
 397   self->next = tmp;
 398   return self;
 399 }
 400
 401 /*
 402  * swap a node with its previous node
 403  */
 404 LLIST_MACRO LList
 405 llist_retreat (LList self)
 406 {
 407   LList tmp = self->prev->prev;
 408   tmp->next = self;
 409   self->prev->next = self->next;
 410   self->next->prev = self->prev;
 411   self->next = self->prev;
 412   self->prev->prev = self;
 413   self->prev = tmp;
 414   return self;
 415 }
 416
 417
 418
 419 /*
 420  * return the member after self
 421  */
 422 LLIST_MACRO LList
 423 llist_get_next (const_LList self)
 424 {
 425   return self->next;
 426 }
 427
 428 /*
 429  * return the member before self
 430  */
 431 LLIST_MACRO LList
 432 llist_get_prev (const_LList self)
 433 {
 434   return self->prev;
 435 }
 436
 437 /*
 438  * put self to the next node
 439  */
 440 LLIST_MACRO void
 441 llist_forward (LList_ref self)
 442 {
 443   *self = (*self)->next;
 444 }
 445
 446 /*
 447  * put self to the previous node
 448  */
 449 LLIST_MACRO void
 450 llist_backward (LList_ref self)
 451 {
 452   *self = (*self)->prev;
 453 }
 454
 455 /*
 456  * get the nth element after (positive n) or before (negative n) self
 457  */
 458 LLIST_MACRO LList
 459 llist_get_nth (LList self, int n)
 460 {
 461   if (n>0)
 462     while (n--)
 463       self = llist_get_next (self);
 464   else
 465     while (n++)
 466       self = llist_get_prev (self);
 467
 468   return (LList) self;
 469 }
 470
 471 #endif /*LLIST_IMPLEMENTATION*/
 472
 473 #endif /*LLIST_H */
 474 /*
 475 // Local Variables:
 476 // mode: C
 477 // c-file-style: "gnu"
 478 // End:
 479 // arch-tag: e8fe4a59-fd55-4c45-b860-5cd1e0771213
 480 // end_of_file
 481 */