libcharybdis/tools.h

   1 /*
   2  *  ircd-ratbox: A slightly useful ircd.
   3  *  tools.h: Header for the various tool functions.
   4  *
   5  *  Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center
   6  *  Copyright (C) 1996-2002 Hybrid Development Team
   7  *  Copyright (C) 2002-2004 ircd-ratbox development team
   8  *
   9  *  This program is free software; you can redistribute it and/or modify
  10  *  it under the terms of the GNU General Public License as published by
  11  *  the Free Software Foundation; either version 2 of the License, or
  12  *  (at your option) any later version.
  13  *
  14  *  This program is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *  GNU General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU General Public License
  20  *  along with this program; if not, write to the Free Software
  21  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
  22  *  USA
  23  *
  24  *  $Id: tools.h 3201 2007-02-04 01:59:38Z jilles $
  25  */
  26
  27 #ifndef __LIBCHARYBDIS_TOOLS_H__
  28 #define __LIBCHARYBDIS_TOOLS_H__
  29
  30
  31 /*
  32  * double-linked-list stuff
  33  */
  34 typedef struct _dlink_node dlink_node;
  35 typedef struct _dlink_list dlink_list;
  36
  37 struct _dlink_node
  38 {
  39         void *data;
  40         dlink_node *prev;
  41         dlink_node *next;
  42
  43 };
  44
  45 struct _dlink_list
  46 {
  47         dlink_node *head;
  48         dlink_node *tail;
  49         unsigned long length;
  50 };
  51
  52 dlink_node *make_dlink_node(void);
  53 void free_dlink_node(dlink_node * lp);
  54 void init_dlink_nodes(void);
  55
  56 #ifndef NDEBUG
  57 void mem_frob(void *data, int len);
  58 #else
  59 #define mem_frob(x, y)
  60 #endif
  61
  62 /* This macros are basically swiped from the linux kernel
  63  * they are simple yet effective
  64  */
  65
  66 /*
  67  * Walks forward of a list.
  68  * pos is your node
  69  * head is your list head
  70  */
  71 #define DLINK_FOREACH(pos, head) for (pos = (head); pos != NULL; pos = pos->next)
  72
  73 /*
  74  * Walks forward of a list safely while removing nodes
  75  * pos is your node
  76  * n is another list head for temporary storage
  77  * head is your list head
  78  */
  79 #define DLINK_FOREACH_SAFE(pos, n, head) for (pos = (head), n = pos ? pos->next : NULL; pos != NULL; pos = n, n = pos ? pos->next : NULL)
  80
  81 #define DLINK_FOREACH_PREV(pos, head) for (pos = (head); pos != NULL; pos = pos->prev)
  82
  83
  84 /* Returns the list length */
  85 #define dlink_list_length(list) (list)->length
  86 #define dlink_move_list(oldlist, newlist, node)
  87
  88 #define dlinkAddAlloc(data, list) dlinkAdd(data, make_dlink_node(), list)
  89 #define dlinkAddTailAlloc(data, list) dlinkAddTail(data, make_dlink_node(), list)
  90 #define dlinkDestroy(node, list) do { dlinkDelete(node, list); free_dlink_node(node); } while(0)
  91
  92
  93 /*
  94  * The functions below are included for the sake of inlining
  95  * hopefully this will speed up things just a bit
  96  *
  97  */
  98
  99 /*
 100  * dlink_ routines are stolen from squid, except for dlinkAddBefore,
 101  * which is mine.
 102  *   -- adrian
 103  */
 104
 105 /* I hate C sometimes */
 106 #if defined __OPTIMIZE__ && !defined __OPTIMIZE_SIZE__ && !defined __NO_INLINE__
 107 #define INLINE_FUNC extern inline
 108 #define NEED_INLINES
 109 #else
 110 #undef INLINE_FUNC
 111 #define INLINE_FUNC
 112 #endif
 113
 114 #ifdef TOOLS_C
 115 #undef INLINE_FUNC
 116 #define INLINE_FUNC
 117 #endif
 118
 119 void dlinkMoveNode(dlink_node * m, dlink_list * oldlist, dlink_list * newlist);
 120 void dlinkAdd(void *data, dlink_node * m, dlink_list * list);
 121 void dlinkAddBefore(dlink_node * b, void *data, dlink_node * m, dlink_list * list);
 122 void dlinkMoveTail(dlink_node *m, dlink_list *list);
 123 void dlinkAddTail(void *data, dlink_node * m, dlink_list * list);
 124 void dlinkDelete(dlink_node * m, dlink_list * list);
 125 dlink_node *dlinkFindDelete(void *data, dlink_list *list);
 126 int dlinkFindDestroy(void *data, dlink_list *list);
 127 dlink_node *dlinkFind(void *data, dlink_list *list);
 128 void dlinkMoveList(dlink_list * from, dlink_list * to);
 129
 130 #if defined(NEED_INLINES) || defined(TOOLS_C)
 131 INLINE_FUNC void
 132 dlinkMoveNode(dlink_node * m, dlink_list * oldlist, dlink_list * newlist)
 133 {
 134         /* Assumption: If m->next == NULL, then list->tail == m
 135          *      and:   If m->prev == NULL, then list->head == m
 136          */
 137         assert(m != NULL);
 138         assert(oldlist != NULL);
 139         assert(newlist != NULL);
 140
 141         if(m->next)
 142                 m->next->prev = m->prev;
 143         else
 144                 oldlist->tail = m->prev;
 145
 146         if(m->prev)
 147                 m->prev->next = m->next;
 148         else
 149                 oldlist->head = m->next;
 150
 151         m->prev = NULL;
 152         m->next = newlist->head;
 153         if(newlist->head != NULL)
 154                 newlist->head->prev = m;
 155         else if(newlist->tail == NULL)
 156                 newlist->tail = m;
 157         newlist->head = m;
 158
 159         oldlist->length--;
 160         newlist->length++;
 161 }
 162
 163 INLINE_FUNC void
 164 dlinkAdd(void *data, dlink_node * m, dlink_list * list)
 165 {
 166         assert(data != NULL);
 167         assert(m != NULL);
 168         assert(list != NULL);
 169         m->data = data;
 170         m->prev = NULL;
 171         m->next = list->head;
 172
 173         /* Assumption: If list->tail != NULL, list->head != NULL */
 174         if(list->head != NULL)
 175                 list->head->prev = m;
 176         else if(list->tail == NULL)
 177                 list->tail = m;
 178
 179         list->head = m;
 180         list->length++;
 181 }
 182
 183 INLINE_FUNC void
 184 dlinkAddBefore(dlink_node * b, void *data, dlink_node * m, dlink_list * list)
 185 {
 186         assert(b != NULL);
 187         assert(data != NULL);
 188         assert(m != NULL);
 189         assert(list != NULL);
 190
 191         /* Shortcut - if its the first one, call dlinkAdd only */
 192         if(b == list->head)
 193         {
 194                 dlinkAdd(data, m, list);
 195         }
 196         else
 197         {
 198                 m->data = data;
 199                 b->prev->next = m;
 200                 m->prev = b->prev;
 201                 b->prev = m;
 202                 m->next = b;
 203                 list->length++;
 204         }
 205 }
 206
 207 INLINE_FUNC void
 208 dlinkMoveTail(dlink_node *m, dlink_list *list)
 209 {
 210         if(list->tail == m)
 211                 return;
 212
 213         /* From here assume that m->next != NULL as that can only
 214          * be at the tail and assume that the node is on the list
 215          */
 216
 217         m->next->prev = m->prev;
 218
 219         if(m->prev != NULL)
 220                 m->prev->next = m->next;
 221         else
 222                 list->head = m->next;
 223
 224         list->tail->next = m;
 225         m->prev = list->tail;
 226         m->next = NULL;
 227         list->tail = m;
 228 }
 229
 230 INLINE_FUNC void
 231 dlinkAddTail(void *data, dlink_node * m, dlink_list * list)
 232 {
 233         assert(m != NULL);
 234         assert(list != NULL);
 235         assert(data != NULL);
 236         m->data = data;
 237         m->next = NULL;
 238         m->prev = list->tail;
 239
 240         /* Assumption: If list->tail != NULL, list->head != NULL */
 241         if(list->tail != NULL)
 242                 list->tail->next = m;
 243         else if(list->head == NULL)
 244                 list->head = m;
 245
 246         list->tail = m;
 247         list->length++;
 248 }
 249
 250 /* Execution profiles show that this function is called the most
 251  * often of all non-spontaneous functions. So it had better be
 252  * efficient. */
 253 INLINE_FUNC void
 254 dlinkDelete(dlink_node * m, dlink_list * list)
 255 {
 256         assert(m != NULL);
 257         assert(list != NULL);
 258
 259         /* Assumption: If m->next == NULL, then list->tail == m
 260          *      and:   If m->prev == NULL, then list->head == m
 261          */
 262         if(m->next)
 263                 m->next->prev = m->prev;
 264         else
 265                 list->tail = m->prev;
 266
 267         if(m->prev)
 268                 m->prev->next = m->next;
 269         else
 270                 list->head = m->next;
 271
 272         m->next = m->prev = NULL;
 273         list->length--;
 274 }
 275
 276 INLINE_FUNC dlink_node *
 277 dlinkFindDelete(void *data, dlink_list *list)
 278 {
 279         dlink_node *m;
 280         assert(list != NULL);
 281         assert(data != NULL);
 282
 283         DLINK_FOREACH(m, list->head)
 284         {
 285                 if(m->data != data)
 286                         continue;
 287
 288                 if(m->next)
 289                         m->next->prev = m->prev;
 290                 else
 291                         list->tail = m->prev;
 292
 293                 if(m->prev)
 294                         m->prev->next = m->next;
 295                 else
 296                         list->head = m->next;
 297
 298                 m->next = m->prev = NULL;
 299                 list->length--;
 300                 return m;
 301         }
 302
 303         return NULL;
 304 }
 305
 306 INLINE_FUNC int
 307 dlinkFindDestroy(void *data, dlink_list *list)
 308 {
 309         void *ptr;
 310
 311         assert(list != NULL);
 312         assert(data != NULL);
 313
 314         ptr = dlinkFindDelete(data, list);
 315
 316         if(ptr != NULL)
 317         {
 318                 free_dlink_node(ptr);
 319                 return 1;
 320         }
 321         return 0;
 322 }
 323
 324 /*
 325  * dlinkFind
 326  * inputs       - list to search
 327  *              - data
 328  * output       - pointer to link or NULL if not found
 329  * side effects - Look for ptr in the linked listed pointed to by link.
 330  */
 331 INLINE_FUNC dlink_node *
 332 dlinkFind(void *data, dlink_list *list)
 333 {
 334         dlink_node *ptr;
 335         assert(list != NULL);
 336         assert(data != NULL);
 337
 338         DLINK_FOREACH(ptr, list->head)
 339         {
 340                 if(ptr->data == data)
 341                         return (ptr);
 342         }
 343         return (NULL);
 344 }
 345
 346 INLINE_FUNC void
 347 dlinkMoveList(dlink_list * from, dlink_list * to)
 348 {
 349         assert(from != NULL);
 350         assert(to != NULL);
 351
 352         /* There are three cases */
 353         /* case one, nothing in from list */
 354         if(from->head == NULL)
 355                 return;
 356
 357         /* case two, nothing in to list */
 358         if(to->head == NULL)
 359         {
 360                 to->head = from->head;
 361                 to->tail = from->tail;
 362                 from->head = from->tail = NULL;
 363                 to->length = from->length;
 364                 from->length = 0;
 365                 return;
 366         }
 367
 368         /* third case play with the links */
 369         from->tail->next = to->head;
 370         to->head->prev = from->tail;
 371         to->head = from->head;
 372         from->head = from->tail = NULL;
 373         to->length += from->length;
 374         from->length = 0;
 375 }
 376 #endif
 377
 378 #endif /* __TOOLS_H__ */