src/lists.c

   1 /*
   2  * Copyright 1993, 1995 Christopher Seiwald.
   3  *
   4  * This file is part of Jam - see jam.c for Copyright information.
   5  */
   6
   7 /*
   8  * lists.c - maintain lists of strings
   9  *
  10  * This implementation essentially uses a singly linked list, but
  11  * guarantees that the head element of every list has a valid pointer
  12  * to the tail of the list, so the new elements can efficiently and
  13  * properly be appended to the end of a list.
  14  *
  15  * To avoid massive allocation, list_free() just tacks the whole freed
  16  * chain onto freelist and list_new() looks on freelist first for an
  17  * available list struct.  list_free() does not free the strings in the
  18  * chain: it lazily lets list_new() do so.
  19  *
  20  * 08/23/94 (seiwald) - new list_append()
  21  * 09/07/00 (seiwald) - documented lol_*() functions
  22  * 10/22/02 (seiwald) - list_new() now does its own newstr()/copystr()
  23  * 11/04/02 (seiwald) - const-ing for string literals
  24  * 12/09/02 (seiwald) - new list_printq() for writing lists to Jambase
  25  */
  26
  27 # include "jam.h"
  28 # include "newstr.h"
  29 # include "lists.h"
  30
  31 static LIST *freelist = 0;  /* junkpile for list_free() */
  32
  33
  34 /*
  35  * list_append() - append a list onto another one, returning total
  36  */
  37 LIST *list_append (LIST *l, LIST *nl) {
  38   if (!nl) {
  39     /* Just return l */
  40   } else if (!l) {
  41     l = nl;
  42   } else {
  43     /* Graft two non-empty lists. */
  44     l->tail->next = nl;
  45     l->tail = nl->tail;
  46   }
  47   return l;
  48 }
  49
  50
  51 static int contains (LIST *l, const char *str) {
  52   for (; l != NULL; l = l->next) if (strcmp(l->string, str) == 0) return 1;
  53   return 0;
  54 }
  55
  56
  57 /*
  58  * list_removeall() - remove all occurences of `nl` items from `l`
  59  */
  60 LIST *list_removeall (LIST *l, LIST *nl) {
  61   if (nl && l) {
  62     LIST *p = NULL, *h = NULL;
  63     //
  64     while (l != NULL) {
  65       LIST *n = l->next;
  66       //
  67       if (contains(nl, l->string)) {
  68         // remove (i.e. move node to freelist)
  69         if (p != NULL) p->next = n;
  70         if (n == NULL && h != NULL) h->tail = p;
  71         l->next = freelist;
  72         freelist = l;
  73       } else {
  74         // skip
  75         if (h == NULL) h = l; // save list head
  76         p = l;
  77         if (n == NULL && h != NULL) h->tail = l;
  78       }
  79       l = n;
  80     }
  81     l = h;
  82   }
  83   return l;
  84 }
  85
  86
  87 /*
  88  * list_new() - tack a string onto the end of a list of strings
  89  */
  90 /* copy!=0: copystr; else newstr */
  91 LIST *list_new (LIST *head, const char *string, int copy) {
  92   LIST *l;
  93
  94   if (DEBUG_LISTS) printf("list > %s <\n", string);
  95
  96   /* Copy/newstr as needed */
  97   string = copy?copystr(string):newstr(string);
  98
  99   /* Get list struct from freelist, if one available.  */
 100   /* Otherwise allocate. */
 101   /* If from freelist, must free string first */
 102   if (freelist) {
 103     l = freelist;
 104     freestr(l->string);
 105     freelist = freelist->next;
 106   } else {
 107     l = (LIST *)malloc(sizeof(*l));
 108   }
 109
 110   /* If first on chain, head points here. */
 111   /* If adding to chain, tack us on. */
 112   /* Tail must point to this new, last element. */
 113   if (!head) head = l; else head->tail->next = l;
 114   head->tail = l;
 115   l->next = 0;
 116   l->string = string;
 117   return head;
 118 }
 119
 120
 121 /*
 122  * list_copy() - copy a whole list of strings (nl) onto end of another (l)
 123  */
 124 LIST *list_copy (LIST *l, LIST *nl) {
 125   for (; nl; nl = list_next(nl)) l = list_new(l, nl->string, 1);
 126   return l;
 127 }
 128
 129
 130 /*
 131  * list_sublist() - copy a subset of a list of strings
 132  */
 133 LIST *list_sublist (LIST *l, int start, int count) {
 134   LIST *nl = 0;
 135
 136   for (; l && start--; l = list_next(l)) ;
 137   for (; l && count--; l = list_next(l)) nl = list_new(nl, l->string, 1);
 138   return nl;
 139 }
 140
 141
 142 /* backported from boost-jam; TEST IT!!! */
 143 /*
 144  * list_sort() - sort list
 145  */
 146 LIST *list_sort (LIST *l) {
 147   LIST *first = 0;
 148   LIST *second = 0;
 149   LIST *merged = l;
 150   LIST *result;
 151
 152   if (!l) return L0;
 153   for (;;) {
 154     /* Split the list in two */
 155     LIST **dst = &first;
 156     LIST *src = merged;
 157     for (;;) {
 158       *dst = list_append(*dst, list_new(0, src->string, 1));
 159       if (!src->next) break;
 160       if (strcmp(src->string, src->next->string) > 0) dst = (dst==&first)?&second:&first;
 161       src = src->next;
 162     }
 163     if (merged != l) list_free(merged);
 164     merged = 0;
 165     if (second == 0) { result = first; break; }
 166     /* Merge lists 'first' and 'second' into 'merged' and free 'first'/'second'. */
 167     {
 168       LIST *f = first;
 169       LIST *s = second;
 170       while (f && s) {
 171         if (strcmp(f->string, s->string) < 0) {
 172           merged = list_append(merged, list_new(0, f->string, 1));
 173           f = f->next;
 174         } else {
 175           merged = list_append(merged, list_new(0, s->string, 1));
 176           s = s->next;
 177         }
 178       }
 179       merged = list_copy(merged, f);
 180       merged = list_copy(merged, s);
 181       list_free(first);
 182       list_free(second);
 183       first = second = 0;
 184     }
 185   }
 186   return result;
 187 }
 188
 189
 190 /*
 191  * list_free() - free a list of strings
 192  */
 193 void list_free (LIST *head) {
 194   /* Just tack onto freelist. */
 195   if (head) {
 196     head->tail->next = freelist;
 197     freelist = head;
 198   }
 199 }
 200
 201
 202 /*
 203  * list_print() - print a list of strings to stdout
 204  */
 205 void list_print (LIST *l) {
 206   for (; l; l = list_next(l)) printf("%s ", l->string);
 207 }
 208
 209
 210 /* FIXME! */
 211 /*
 212  * list_printq() - print a list of safely quoted strings to a file
 213  */
 214 void list_printq (FILE *out, LIST *l) {
 215   /* Dump each word, enclosed in "s */
 216   /* Suitable for Jambase use. */
 217   for (; l; l = list_next(l)) {
 218     const char *p = l->string;
 219     const char *ep = p+strlen(p);
 220     const char *op = p;
 221
 222     fputc('\n', out);
 223     fputc('\t', out);
 224     fputc('"', out);
 225     /* Any embedded "'s?  Escape them */
 226     while ((p = (char *)memchr(op, '"', ep-op))) {
 227       fwrite(op, p-op, 1, out);
 228       fputc('\\', out);
 229       fputc('"', out);
 230       op = p+1;
 231     }
 232     /* Write remainder */
 233     fwrite(op, ep-op, 1, out);
 234     fputc('"', out);
 235     fputc(' ', out);
 236   }
 237 }
 238
 239
 240 /*
 241  * list_length() - return the number of items in the list
 242  */
 243 int list_length (LIST *l) {
 244   int n = 0;
 245
 246   for (; l; l = list_next(l), ++n) ;
 247   return n;
 248 }
 249
 250
 251 /*
 252  * lol_init() - initialize a LOL (list of lists)
 253  */
 254 void lol_init (LOL *lol) {
 255   lol->count = 0;
 256 }
 257
 258
 259 /*
 260  * lol_add() - append a LIST onto an LOL
 261  */
 262 void lol_add (LOL *lol, LIST *l) {
 263   if (lol->count < LOL_MAX) lol->list[lol->count++] = l;
 264 }
 265
 266
 267 /*
 268  * lol_free() - free the LOL and its LISTs
 269  */
 270 void lol_free (LOL *lol) {
 271   int i;
 272
 273   for (i = 0; i < lol->count; i++) list_free(lol->list[i]);
 274   lol->count = 0;
 275 }
 276
 277
 278 /*
 279  * lol_get() - return one of the LISTs in the LOL
 280  */
 281 LIST *lol_get (LOL *lol, int i) {
 282   return i<lol->count?lol->list[i]:0;
 283 }
 284
 285
 286 /*
 287  * lol_print() - debug print LISTS separated by ":"
 288  */
 289 void lol_print (LOL *lol) {
 290   int i;
 291
 292   for (i = 0; i < lol->count; i++) {
 293     if (i) printf(" : ");
 294     list_print(lol->list[i]);
 295   }
 296 }