engine/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   if (!list); else                              \
  58     for (LList node = llist_get_head (list);    \
  59          ! llist_is_end (node, list);           \
  60          llist_forward (&node))
  61
  62 #define LLIST_FOREACH_REV(list, node)           \
  63   if (!list); else                              \
  64     for (LList node = llist_get_tail (list);    \
  65          ! llist_is_end (node, list);           \
  66          llist_backward (&node))
  67
  68 #define LLIST_WHILE_HEAD(list, head)            \
  69   if (!list); else                              \
  70     for (LList head = llist_get_head (list);    \
  71          !llist_is_empty (list);                \
  72          head = llist_get_head (list))
  73
  74 #define LLIST_WHILE_TAIL(list, tail)            \
  75   if (!list); else                              \
  76     for (LList tail = llist_get_tail (list);    \
  77          !llist_is_empty (list);                \
  78          tail = llist_get_tail (list))
  79
  80
  81 /*
  82  * Type of a llist node.
  83  */
  84 struct llist_struct
  85 {
  86   struct llist_struct *next;
  87   struct llist_struct *prev;
  88 };
  89 typedef struct llist_struct llist;
  90 typedef llist * LList;
  91 typedef const llist * const_LList;
  92 typedef llist ** LList_ref;
  93
  94 /*
  95  * handy macro to instantiate a local llist 'name' becomes a LList handle and
  96  * the underlying instance is hidden as name_llist_, this list is statically initialized
  97  */
  98 #define LLIST_INITIALIZER(name) {&name,&name}
  99 #define LLIST_AUTO(name) \
 100 llist name##_llist_ = LLIST_STATIC_INITIALIZER(name##_llist_);\
 101 LList name = &name##_llist_
 102
 103 LLIST_MACRO void llist_init (LList self);
 104 LLIST_MACRO int llist_is_empty (const_LList self);
 105 LLIST_MACRO int llist_is_single (const_LList self);
 106 LLIST_MACRO int llist_is_head (const_LList self, const_LList list);
 107 LLIST_MACRO int llist_is_tail (const_LList self, const_LList list);
 108 LLIST_MACRO int llist_is_end (const_LList self, const_LList list);
 109 LLIST_MACRO int llist_is_member (const_LList self, const_LList list);
 110 LLIST_MACRO int llist_is_before (const_LList self, const_LList other, const_LList list);
 111 LLIST_MACRO int llist_is_after (const_LList self, const_LList other, const_LList list);
 112 LLIST_MACRO unsigned llist_count (const_LList self);
 113 LLIST_MACRO unsigned llist_distance (const_LList self, const_LList other, const_LList list);
 114 LLIST_MACRO void llist_unlink_fast_ (LList self);
 115 LLIST_MACRO LList llist_unlink (LList self);
 116 LLIST_MACRO LList llist_relocate (LList self);
 117 LLIST_MACRO LList llist_insert_before (LList self, LList successor);
 118 LLIST_MACRO LList llist_insert_after (LList self, LList predcessor);
 119 LLIST_MACRO LList llist_insert_list_before (LList self, LList successor);
 120 LLIST_MACRO LList llist_insert_list_after (LList self, LList predcessor);
 121 LLIST_MACRO LList llist_insert_range_before (LList self, LList start, LList end);
 122 LLIST_MACRO LList llist_insert_range_after (LList self, LList start, LList end);
 123 LLIST_MACRO LList llist_advance (LList self);
 124 LLIST_MACRO LList llist_retreat (LList self);
 125 LLIST_MACRO LList llist_get_next (const_LList self);
 126 LLIST_MACRO LList llist_get_prev (const_LList self);
 127 LLIST_MACRO void llist_forward (LList_ref self);
 128 LLIST_MACRO void llist_backward (LList_ref self);
 129 LLIST_MACRO LList llist_get_nth (LList self, int n);
 130 LLIST_MACRO LList llist_get_nth_stop (LList self, int n, const_LList stop);
 131
 132 #endif /*LLIST_INTERFACE*/
 133
 134
 135
 136 #ifdef LLIST_IMPLEMENTATION
 137
 138 #define llist_insert_head(list,element) llist_insert_after(element,list)
 139 #define llist_insert_tail(list,element) llist_insert_before(element,list)
 140 #define llist_get_head llist_get_next
 141 #define llist_get_tail llist_get_prev
 142
 143
 144 /*
 145  * initialize a new llist. Must not be
 146  * applied to a list which is not empty! Lists need to be initialized
 147  * before any other operation on them is called.
 148  */
 149 LLIST_MACRO void
 150 llist_init (LList self)
 151 {
 152   self->next = self->prev = self;
 153 }
 154
 155 /*
 156  * check if a node is linked with some other node
 157  */
 158 LLIST_MACRO int
 159 llist_is_empty (const_LList self)
 160 {
 161   return self->next == self;
 162 }
 163
 164 /*
 165  * check if self is the only node in a list or self is not in a list
 166  */
 167 LLIST_MACRO int
 168 llist_is_single (const_LList self)
 169 {
 170   return self->next->next == self;
 171 }
 172
 173 /*
 174  * check if self is the head of list
 175  */
 176 LLIST_MACRO int
 177 llist_is_head (const_LList self, const_LList list)
 178 {
 179   return list->next == self;
 180 }
 181
 182 /*
 183  * check if self is the tail of list
 184  */
 185 LLIST_MACRO int
 186 llist_is_tail (const_LList self, const_LList list)
 187 {
 188   return list->prev == self;
 189 }
 190
 191 /*
 192  * check if self is the end of list
 193  */
 194 LLIST_MACRO int
 195 llist_is_end (const_LList self, const_LList list)
 196 {
 197   return list == self;
 198 }
 199
 200 /*
 201  * check if self is a member of list
 202  */
 203 LLIST_MACRO int
 204 llist_is_member (const_LList self, const_LList list)
 205 {
 206   const_LList i = self->next;
 207   for (; i != self; i = i->next)
 208     {
 209       if (i == list)
 210         return 1;
 211     }
 212   return 0;
 213 }
 214
 215 /*
 216  * check if self is before other in list
 217  */
 218 LLIST_MACRO int
 219 llist_is_before (const_LList self, const_LList other, const_LList list)
 220 {
 221   assert (llist_is_member (self, list));
 222   assert (llist_is_member (other, list));
 223   const_LList i = self->next;
 224   if (self != other)
 225     {
 226       for (; i != list; i = i->next)
 227         {
 228           if (i == other)
 229             return 1;
 230         }
 231     }
 232   return 0;
 233 }
 234
 235 /*
 236  * check if self is after other in list
 237  */
 238 LLIST_MACRO int
 239 llist_is_after (const_LList self, const_LList other, const_LList list)
 240 {
 241   assert (llist_is_member (self, list));
 242   assert (llist_is_member (other, list));
 243   const_LList i = self->prev;
 244   if (self != other)
 245     {
 246       for (; i != list; i = i->prev)
 247         {
 248           if (i == other)
 249             return 1;
 250         }
 251     }
 252   return 0;
 253 }
 254
 255
 256 /*
 257  * count the nodes of self
 258  */
 259 LLIST_MACRO unsigned
 260 llist_count (const_LList self)
 261 {
 262   unsigned cnt = 0;
 263   const_LList i = self;
 264   for (; i->next != self; ++cnt, i = i->next);
 265   return cnt;
 266 }
 267
 268 /*
 269  * count distance from self to other in list
 270  */
 271 LLIST_MACRO unsigned
 272 llist_distance (const_LList self, const_LList other, const_LList list)
 273 {
 274   assert (llist_is_member (self, list));
 275   assert (llist_is_member (other, list));
 276
 277   unsigned cnt = 0;
 278   const_LList i = self;
 279   for (; i->next != other && i->next != list; ++cnt, i = i->next);
 280   if (i->next == list)
 281     for (cnt = 0, i = self; i->prev != other; ++cnt, i = i->prev);
 282   return cnt;
 283 }
 284
 285 /* private */
 286 LLIST_MACRO void
 287 llist_unlink_fast_ (LList self)
 288 {
 289   LList nxt = self->next, pre = self->prev;
 290   nxt->prev = pre;
 291   pre->next = nxt;
 292 }
 293
 294 /*
 295  * removes self from its list
 296  */
 297 LLIST_MACRO LList
 298 llist_unlink (LList self)
 299 {
 300   llist_unlink_fast_ (self);
 301   return self->next = self->prev = self;
 302 }
 303
 304 /*
 305  * fixes a list if self got relocated in memory
 306  */
 307 LLIST_MACRO LList
 308 llist_relocate (LList self)
 309 {
 310   return self->next->prev = self->prev->next = self;
 311 }
 312
 313 /*
 314  * inserts self before successor,
 315  * self can already linked to a list where it will be removed
 316  */
 317 LLIST_MACRO LList
 318 llist_insert_before (LList self, LList successor)
 319 {
 320   llist_unlink_fast_ (self);
 321   self->prev = successor->prev;
 322   self->next = successor;
 323   return successor->prev = self->prev->next = self;
 324 }
 325
 326
 327 /*
 328  * inserts self after predcessor,
 329  * self can already linked to a list where it will be removed
 330  */
 331 LLIST_MACRO LList
 332 llist_insert_after (LList self, LList predcessor)
 333 {
 334   llist_unlink_fast_ (self);
 335   self->next = predcessor->next;
 336   self->prev = predcessor;
 337   return predcessor->next = self->next->prev = self;
 338 }
 339
 340 /*
 341  * move the content of list self before node successor
 342  */
 343 LLIST_MACRO LList
 344 llist_insert_list_before (LList self, LList successor)
 345 {
 346   if (!llist_is_empty (self))
 347     {
 348       self->next->prev = successor->prev;
 349       self->prev->next = successor;
 350       successor->prev->next = self->next;
 351       successor->prev = self->prev;
 352       self->prev = self->next = self;
 353     }
 354   return self;
 355 }
 356
 357 /*
 358  * move the content of list self after node predcessor
 359  */
 360 LLIST_MACRO LList
 361 llist_insert_list_after (LList self, LList predcessor)
 362 {
 363   if (!llist_is_empty (self))
 364     {
 365       self->prev->next = predcessor->next;
 366       self->next->prev = predcessor;
 367       predcessor->next->prev = self->prev;
 368       predcessor->next = self->next;
 369       self->prev = self->next = self;
 370     }
 371   return self;
 372 }
 373
 374 /*
 375  * move members from start to end->prev before self
 376  */
 377 LLIST_MACRO
 378 LList llist_insert_range_before (LList self, LList start, LList end)
 379 {
 380   LList tmp = self->prev;
 381   start->prev->next = end;
 382   end->prev->next = self;
 383   self->prev->next = start;
 384
 385   self->prev = end->prev;
 386   end->prev = start->prev;
 387   start->prev = tmp;
 388
 389   return self;
 390 }
 391
 392 /*
 393  * move members from start to end->prev after self
 394  */
 395 LLIST_MACRO
 396 LList llist_insert_range_after (LList self, LList start, LList end)
 397 {
 398   start->prev->next = end;
 399   end->prev->next = self->next;
 400   self->next->prev = end->prev;
 401   self->next = start;
 402   end->prev = start->prev;
 403   start->prev = self;
 404   return self;
 405 }
 406
 407 /*
 408  * swap a node with its next node
 409  */
 410 LLIST_MACRO LList
 411 llist_advance (LList self)
 412 {
 413   LList tmp = self->next->next;
 414   tmp->prev = self;
 415   self->next->prev = self->prev;
 416   self->prev->next = self->next;
 417   self->prev = self->next;
 418   self->next->next = self;
 419   self->next = tmp;
 420   return self;
 421 }
 422
 423 /*
 424  * swap a node with its previous node
 425  */
 426 LLIST_MACRO LList
 427 llist_retreat (LList self)
 428 {
 429   LList tmp = self->prev->prev;
 430   tmp->next = self;
 431   self->prev->next = self->next;
 432   self->next->prev = self->prev;
 433   self->next = self->prev;
 434   self->prev->prev = self;
 435   self->prev = tmp;
 436   return self;
 437 }
 438
 439
 440
 441 /*
 442  * return the member after self
 443  */
 444 LLIST_MACRO LList
 445 llist_get_next (const_LList self)
 446 {
 447   return self->next;
 448 }
 449
 450 /*
 451  * return the member before self
 452  */
 453 LLIST_MACRO LList
 454 llist_get_prev (const_LList self)
 455 {
 456   return self->prev;
 457 }
 458
 459 /*
 460  * put self to the next node
 461  */
 462 LLIST_MACRO void
 463 llist_forward (LList_ref self)
 464 {
 465   *self = (*self)->next;
 466 }
 467
 468 /*
 469  * put self to the previous node
 470  */
 471 LLIST_MACRO void
 472 llist_backward (LList_ref self)
 473 {
 474   *self = (*self)->prev;
 475 }
 476
 477 /*
 478  * get the nth element after (positive n) or before (negative n) self
 479  */
 480 LLIST_MACRO LList
 481 llist_get_nth (LList self, int n)
 482 {
 483   if (n>0)
 484     while (n--)
 485       self = llist_get_next (self);
 486   else
 487     while (n++)
 488       self = llist_get_prev (self);
 489
 490   return self;
 491 }
 492
 493 /*
 494  * get the nth element after (positive n) or before (negative n) self
 495  * return NULL if node stop is hit
 496  */
 497 LLIST_MACRO LList
 498 llist_get_nth_stop (LList self, int n, const_LList stop)
 499 {
 500   if (n>0)
 501     while (n--)
 502       {
 503         self = llist_get_next (self);
 504         if (self == stop)
 505           return NULL;
 506       }
 507   else
 508     while (n++)
 509       {
 510         self = llist_get_prev (self);
 511         if (self == stop)
 512           return NULL;
 513       }
 514   return self;
 515 }
 516
 517 #endif /*LLIST_IMPLEMENTATION*/
 518
 519 #endif /*LLIST_H */
 520 /*
 521 // Local Variables:
 522 // mode: C
 523 // c-file-style: "gnu"
 524 // End:
 525 // arch-tag: e8fe4a59-fd55-4c45-b860-5cd1e0771213
 526 // end_of_file
 527 */