src/list.h

   1 /*
   2  * Copyright (C) 2001,2002 Paul Sheer
   3  *
   4  * This file is part of GnuTLS.
   5  *
   6  * GnuTLS is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 3 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * GnuTLS is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  19  */
  20
  21 /*
  22     SOAP:
  23
  24     Academics always want to implement hash tables (i.e. dictionaries),
  25     singly or doubly linked lists, and queues, because ...  well ... they
  26     know how.
  27
  28     These datatypes are nonsense for the following reasons:
  29         hash tables: Hash tables are a mapping of some
  30             string to some data, where that data is going to
  31             be accessed COMPLETELY RANDOMLY. This is what it
  32             is for. However it is extremely rare to have a
  33             large number of data elements which really are
  34             being accessed in a completely random way.
  35
  36         lists: appending and searching through lists is always
  37             slow because these operations search all the way
  38             through the list.
  39
  40         queues: whats the difference between a queue and a list?
  41             very little really.
  42
  43     The system implemented here is a doubly linked list with previous
  44     search index that can be appended or prepended with no overhead,
  45     implemented entirely in macros. It is hence as versatile as a
  46     doubly/singly linked list or queue and blazingly fast. Hence doing
  47     sequential searches where the next search result is likely to be
  48     closely indexed to the previous (usual case), is efficient.
  49
  50     Of course this doesn't mean you should use this as a hash table
  51     where you REALLY need a hash table.
  52
  53 */
  54
  55 /********** example usage **********/
  56 /*
  57
  58 #include "list.h"
  59
  60 extern void free (void *x);
  61 extern char *strdup (char *s);
  62
  63 // consider a list of elements containing an `int' and a `char *'
  64 LIST_TYPE_DECLARE (names, char *s; int i;);
  65
  66 // for sorting, to compare elements
  67 static int cm (names **a, names **b)
  68 {
  69     return strcmp ((*a)->s, (*b)->s);
  70 }
  71
  72 // to free the contents of an element
  73 static void free_item (names *a)
  74 {
  75     free (a->s);
  76     a->s = 0;   // say
  77     a->i = 0;   // say
  78 }
  79
  80 int main (int argc, char **argv)
  81 {
  82 // you can separate these into LIST_TYPE_DECLARE(), LIST_DECLARE() and linit() if needed.
  83     LIST_DECLARE_INIT (l, names, free_item);
  84     names *j;
  85
  86     lappend (l);
  87     l.tail->s = strdup ("hello");
  88     l.tail->i = 1;
  89     lappend (l);
  90     l.tail->s = strdup ("there");
  91     l.tail->i = 2;
  92     lappend (l);
  93     l.tail->s = strdup ("my");
  94     l.tail->i = 3;
  95     lappend (l);
  96     l.tail->s = strdup ("name");
  97     l.tail->i = 4;
  98     lappend (l);
  99     l.tail->s = strdup ("is");
 100     l.tail->i = 5;
 101     lappend (l);
 102     l.tail->s = strdup ("fred");
 103     l.tail->i = 6;
 104
 105     printf ("%ld\n\n", lcount (l));
 106     lloopforward (l, j, printf ("%d %s\n", j->i, j->s));
 107     printf ("\n");
 108
 109     lsort (l, cm);
 110     lloopforward (l, j, printf ("%d %s\n", j->i, j->s));
 111
 112     lloopreverse (l, j, if (j->i <= 3) ldeleteinc (l, j););
 113
 114     printf ("\n");
 115     lloopforward (l, j, printf ("%d %s\n", j->i, j->s));
 116
 117     ldeleteall (l);
 118
 119     printf ("\n");
 120     lloopforward (l, j, printf ("%d %s\n", j->i, j->s));
 121     return 0;
 122 }
 123
 124 */
 125
 126
 127 #ifndef _LIST_H
 128 #define _LIST_H
 129
 130 /* the `search' member points to the last found.
 131    this speeds up repeated searches on the same list-item,
 132    the consecutive list-item, or the pre-consecutive list-item.
 133    this obviates the need for a hash table for 99% of
 134    cercumstances the time */
 135 struct list
 136 {
 137   long length;
 138   long item_size;
 139   struct list_item
 140   {
 141     struct list_item *next;
 142     struct list_item *prev;
 143     char data[1];
 144   } *head, *tail, *search;
 145   void (*free_func) (struct list_item *);
 146 };
 147
 148 /* declare a list of type `x', also called `x' having members `typelist' */
 149
 150 #define LIST_TYPE_DECLARE(type,typelist)                                                \
 151     typedef struct type {                                                               \
 152         struct type *next;                                                              \
 153         struct type *prev;                                                              \
 154         typelist                                                                        \
 155     } type
 156
 157 #define LIST_DECLARE(l,type)                                                            \
 158     struct {                                                                            \
 159         long length;                                                                    \
 160         long item_size;                                                                 \
 161         type *head, *tail, *search;                                                     \
 162         void (*free_func) (type *);                                                     \
 163     } l
 164
 165 #define LIST_DECLARE_INIT(l,type,free)                                                  \
 166     struct {                                                                            \
 167         long length;                                                                    \
 168         long item_size;                                                                 \
 169         type *head, *tail, *search;                                                     \
 170         void (*free_func) (type *);                                                     \
 171     } l = {0, sizeof (type), 0, 0, 0, (void (*) (type *)) free}
 172
 173 #define linit(l,type,free)                                                              \
 174     {                                                                                   \
 175         memset (&(l), 0, sizeof (l));                                                   \
 176         (l).item_size = sizeof (type);                                                  \
 177         (l).free_func = free;                                                           \
 178     }
 179
 180 /* returns a pointer to the data of an item */
 181 #define ldata(i)        ((void *) &((i)->data[0]))
 182
 183 /* returns a pointer to the list head */
 184 #define lhead(l)        ((l).head)
 185
 186 /* returns a pointer to the list tail */
 187 #define ltail(l)        ((l).tail)
 188
 189 #define lnewsearch(l)                                                                   \
 190         (l).search = 0;
 191
 192 /* adds to the beginning of the list */
 193 #define lprepend(l)                                                                     \
 194     {                                                                                   \
 195         struct list_item *__t;                                                          \
 196         __t = (struct list_item *) malloc ((l).item_size);                              \
 197         memset (__t, 0, (l).item_size);                                                 \
 198         __t->next = (l).head;                                                           \
 199         if (__t->next)                                                                  \
 200             __t->next->prev = __t;                                                      \
 201         __t->prev = 0;                                                                  \
 202         if (!(l).tail)                                                                  \
 203             (l).tail = __t;                                                             \
 204         (l).head = __t;                                                                 \
 205         length++;                                                                       \
 206     }
 207
 208 /* adds to the end of the list */
 209 #define lappend(l)                                                                      \
 210     {                                                                                   \
 211         struct list_item *__t;                                                          \
 212         __t = (struct list_item *) malloc ((l).item_size);                              \
 213         memset (__t, 0, (l).item_size);                                                 \
 214         __t->prev = (struct list_item *) (l).tail;                                      \
 215         if (__t->prev)                                                                  \
 216             __t->prev->next = __t;                                                      \
 217         __t->next = 0;                                                                  \
 218         if (!(l).head)                                                                  \
 219             (l).head = (void *) __t;                                                    \
 220         (l).tail = (void *) __t;                                                        \
 221         (l).length++;                                                                   \
 222     }
 223
 224 /* you should free these manually */
 225 #define lunlink(l,e)                                                                    \
 226     {                                                                                   \
 227         struct list_item *__t;                                                          \
 228         (l).search = 0;                                                                 \
 229         __t = (void *) e;                                                               \
 230         if ((void *) (l).head == (void *) __t)                                          \
 231             (l).head = (l).head->next;                                                  \
 232         if ((void *) (l).tail == (void *) __t)                                          \
 233             (l).tail = (l).tail->prev;                                                  \
 234         if (__t->next)                                                                  \
 235             __t->next->prev = __t->prev;                                                \
 236         if (__t->prev)                                                                  \
 237             __t->prev->next = __t->next;                                                \
 238         (l).length--;                                                                   \
 239     }
 240
 241 /* deletes list entry at point e, and increments e to the following list entry */
 242 #define ldeleteinc(l,e)                                                                 \
 243     {                                                                                   \
 244         struct list_item *__t;                                                          \
 245         (l).search = 0;                                                                 \
 246         __t = (void *) e;                                                               \
 247         if ((void *) (l).head == (void *) __t)                                          \
 248             (l).head = (l).head->next;                                                  \
 249         if ((void *) (l).tail == (void *) __t)                                          \
 250             (l).tail = (l).tail->prev;                                                  \
 251         if (__t->next)                                                                  \
 252             __t->next->prev = __t->prev;                                                \
 253         if (__t->prev)                                                                  \
 254             __t->prev->next = __t->next;                                                \
 255         __t = __t->next;                                                                \
 256         if ((l).free_func)                                                              \
 257             (*(l).free_func) ((void *) e);                                              \
 258         free (e);                                                                       \
 259         e = (void *) __t;                                                               \
 260         (l).length--;                                                                   \
 261     }
 262
 263 /* deletes list entry at point e, and deccrements e to the preceding list emtry */
 264 #define ldeletedec(l,e)                                                                 \
 265     {                                                                                   \
 266         struct list_item *__t;                                                          \
 267         (l).search = 0;                                                                 \
 268         __t = (void *) e;                                                               \
 269         if ((void *) (l).head == (void *) __t)                                          \
 270             (l).head = (l).head->next;                                                  \
 271         if ((void *) (l).tail == (void *) __t)                                          \
 272             (l).tail = (l).tail->prev;                                                  \
 273         if (__t->next)                                                                  \
 274             __t->next->prev = __t->prev;                                                \
 275         if (__t->prev)                                                                  \
 276             __t->prev->next = __t->next;                                                \
 277         __t = __t->prev;                                                                \
 278         if ((l).free_func)                                                              \
 279             (*(l).free_func) ((void *) e);                                              \
 280         free (e);                                                                       \
 281         e = (void *) __t;                                                               \
 282         (l).length--;                                                                   \
 283     }
 284
 285 /* p and q must be consecutive and neither must be zero */
 286 #define linsert(l,p,q)                                                                  \
 287     {                                                                                   \
 288         struct list_item *__t;                                                          \
 289         __t = (struct list_item *) malloc ((l).item_size);                              \
 290         memset (__t, 0, (l).item_size);                                                 \
 291         __t->prev = (void *) p;                                                         \
 292         __t->next = (void *) q;                                                         \
 293         q->prev = (void *) __t;                                                         \
 294         p->next = (void *) __t;                                                         \
 295         (l).length++;                                                                   \
 296     }
 297
 298 /* p and q must be consecutive and neither must be zero */
 299 #define ldeleteall(l)                                                                   \
 300     {                                                                                   \
 301         (l).search = 0;                                                                 \
 302         while ((l).head) {                                                              \
 303             struct list_item *__p;                                                      \
 304             __p = (struct list_item *) (l).head;                                        \
 305             lunlink(l, __p);                                                            \
 306             if ((l).free_func)                                                          \
 307                 (*(l).free_func) ((void *) __p);                                        \
 308             free (__p);                                                                 \
 309         }                                                                               \
 310     }
 311
 312 #define lloopstart(l,i)                                                                 \
 313         for (i = (void *) (l).head; i;) {                                               \
 314             struct list_item *__tl;                                                     \
 315             __tl = (void *) i->next;                                                    \
 316
 317 #define lloopend(l,i)                                                                   \
 318             i = (void *) __tl;                                                          \
 319         }                                                                               \
 320
 321 #define lloopforward(l,i,op)                                                            \
 322     {                                                                                   \
 323         for (i = (void *) (l).head; i;) {                                               \
 324             struct list_item *__t;                                                      \
 325             __t = (void *) i->next;                                                     \
 326             op;                                                                         \
 327             i = (void *) __t;                                                           \
 328         }                                                                               \
 329     }
 330
 331 #define lloopreverse(l,i,op)                                                            \
 332     {                                                                                   \
 333         for (i = (void *) (l).tail; i;) {                                               \
 334             struct list_item *__t;                                                      \
 335             __t = (void *) i->prev;                                                     \
 336             op;                                                                         \
 337             i = (void *) __t;                                                           \
 338         }                                                                               \
 339     }
 340
 341 #define lindex(l,i,n)                                                                   \
 342     {                                                                                   \
 343         int __k;                                                                        \
 344         for (__k = 0, i = (void *) (l).head; i && __k != n; i = i->next, __k++);        \
 345     }
 346
 347 #define lsearchforward(l,i,op)                                                          \
 348     {                                                                                   \
 349         int __found = 0;                                                                \
 350         if (!__found)                                                                   \
 351             if ((i = (void *) (l).search)) {                                            \
 352                 if (op) {                                                               \
 353                     __found = 1;                                                        \
 354                     (l).search = (void *) i;                                            \
 355                 }                                                                       \
 356                 if (!__found)                                                           \
 357                     if ((i = (void *) (l).search->next))                                \
 358                         if (op) {                                                       \
 359                             __found = 1;                                                \
 360                             (l).search = (void *) i;                                    \
 361                         }                                                               \
 362                 if (!__found)                                                           \
 363                     if ((i = (void *) (l).search->prev))                                \
 364                         if (op) {                                                       \
 365                             __found = 1;                                                \
 366                             (l).search = (void *) i;                                    \
 367                         }                                                               \
 368             }                                                                           \
 369         if (!__found)                                                                   \
 370             for (i = (void *) (l).head; i; i = i->next)                                 \
 371                 if (op) {                                                               \
 372                     __found = 1;                                                        \
 373                     (l).search = (void *) i;                                            \
 374                     break;                                                              \
 375                 }                                                                       \
 376     }
 377
 378 #define lsearchreverse(l,i,op)                                                          \
 379     {                                                                                   \
 380         int __found = 0;                                                                \
 381         if (!__found)                                                                   \
 382             if ((i = (void *) (l).search)) {                                            \
 383                 if (op) {                                                               \
 384                     __found = 1;                                                        \
 385                     (l).search = (void *) i;                                            \
 386                 }                                                                       \
 387                 if (!__found)                                                           \
 388                     if ((i = (void *) (l).search->prev))                                \
 389                         if (op) {                                                       \
 390                             __found = 1;                                                \
 391                             (l).search = (void *) i;                                    \
 392                         }                                                               \
 393                 if (!__found)                                                           \
 394                     if ((i = (void *) (l).search->next))                                \
 395                         if (op) {                                                       \
 396                             __found = 1;                                                \
 397                             (l).search = (void *) i;                                    \
 398                         }                                                               \
 399             }                                                                           \
 400         if (!__found)                                                                   \
 401             for (i = (void *) (l).tail; i; i = i->prev)                                 \
 402                 if (op) {                                                               \
 403                     __found = 1;                                                        \
 404                     (l).search = (void *) i;                                            \
 405                     break;                                                              \
 406                 }                                                                       \
 407     }
 408
 409 #define lcount(l)       ((l).length)
 410
 411 /* sort with comparison function see qsort(3) */
 412 #define larray(l,a)                                                                     \
 413     {                                                                                   \
 414         long __i;                                                                       \
 415         struct list_item *__p;                                                          \
 416         a = (void *) malloc (((l).length + 1) * sizeof (void *));                       \
 417         for (__i = 0, __p = (void *) (l).head; __p; __p = __p->next, __i++)             \
 418             a[__i] = (void *) __p;                                                      \
 419         a[__i] = 0;                                                                     \
 420     }                                                                                   \
 421
 422 /* sort with comparison function see qsort(3) */
 423 #define llist(l,a)                                                                      \
 424     {                                                                                   \
 425         struct list_item *__p;                                                          \
 426         (l).head = (void *) a[0];                                                       \
 427         (l).search = 0;                                                                 \
 428         __p = (void *) a[0];                                                            \
 429         __p->prev = 0;                                                                  \
 430         for (__j = 1; a[__j]; __j++, __p = __p->next) {                                 \
 431             __p->next = (void *) a[__j];                                                \
 432             __p->next->prev = __p;                                                      \
 433         }                                                                               \
 434         (l).tail = (void *) __p;                                                        \
 435         __p->next = 0;                                                                  \
 436     }                                                                                   \
 437
 438 /* sort with comparison function see qsort(3) */
 439 #define lsort(l,compare)                                                                \
 440     {                                                                                   \
 441         void **__t;                                                                     \
 442         long __j;                                                                       \
 443         larray (l,__t);                                                                 \
 444         qsort (__t, (l).length, sizeof (void *), (int (*) (const void *, const void *)) compare);       \
 445         llist (l,__t);                                                                  \
 446         free (__t);                                                                     \
 447     }                                                                                   \
 448
 449 #endif /* _LIST_H */