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