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 #include "jam.h"
  27 #include "newstr.h"
  28 #include "lists.h"
  29
  30
  31 static LIST *freelist = NULL;  /* 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 JAMFA_PURE 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     while (l != NULL) {
  64       LIST *n = l->next;
  65       if (contains(nl, l->string)) {
  66         // remove (i.e. move node to freelist)
  67         if (p != NULL) p->next = n;
  68         if (n == NULL && h != NULL) h->tail = p;
  69         l->next = freelist;
  70         freelist = l;
  71       } else {
  72         // skip
  73         if (h == NULL) h = l; // save list head
  74         p = l;
  75         if (n == NULL && h != NULL) h->tail = l;
  76       }
  77       l = n;
  78     }
  79     l = h;
  80   }
  81   return l;
  82 }
  83
  84
  85 /*
  86  * list_new() - tack a string onto the end of a list of strings
  87  */
  88 /* copy!=0: copystr; else newstr */
  89 LIST *list_new (LIST *head, const char *string, int copy) {
  90   LIST *l;
  91   if (DEBUG_LISTS) printf("list > %s <\n", string);
  92   /* copy/newstr as needed */
  93   string = copy?copystr(string):newstr(string);
  94   /* get list struct from freelist, if one available, otherwise allocate */
  95   /* if from freelist, must free string first */
  96   if (freelist) {
  97     l = freelist;
  98     freestr(l->string);
  99     freelist = freelist->next;
 100   } else {
 101     l = (LIST *)malloc(sizeof(*l));
 102   }
 103   /* if first on chain, head points here */
 104   /* if adding to chain, tack us on */
 105   /* tail must point to this new, last element */
 106   if (!head) head = l; else head->tail->next = l;
 107   head->tail = l;
 108   l->next = 0;
 109   l->string = string;
 110   return head;
 111 }
 112
 113
 114 /*
 115  * list_copy() - copy a whole list of strings (nl) onto end of another (l)
 116  */
 117 LIST *list_copy (LIST *l, LIST *nl) {
 118   for (; nl; nl = list_next(nl)) l = list_new(l, nl->string, 1);
 119   return l;
 120 }
 121
 122
 123 /*
 124  * list_sublist() - copy a subset of a list of strings
 125  */
 126 LIST *list_sublist (LIST *l, int start, int count) {
 127   LIST *nl = NULL;
 128   for (; l && start--; l = list_next(l)) ;
 129   for (; l && count--; l = list_next(l)) nl = list_new(nl, l->string, 1);
 130   return nl;
 131 }
 132
 133
 134 /* backported from boost-jam; TEST IT!!! */
 135 /*
 136  * list_sort() - sort list
 137  */
 138 LIST *list_sort (LIST *l) {
 139   LIST *first = NULL, *second = NULL, *merged = l, *result;
 140   if (!l) return L0;
 141   for (;;) {
 142     /* split the list in two */
 143     LIST **dst = &first;
 144     LIST *src = merged;
 145     for (;;) {
 146       *dst = list_append(*dst, list_new(0, src->string, 1));
 147       if (!src->next) break;
 148       if (strcmp(src->string, src->next->string) > 0) dst = (dst==&first)?&second:&first;
 149       src = src->next;
 150     }
 151     if (merged != l) list_free(merged);
 152     merged = 0;
 153     if (second == 0) { result = first; break; }
 154     /* merge lists 'first' and 'second' into 'merged' and free 'first'/'second' */
 155     {
 156       LIST *f = first, *s = second;
 157       while (f && s) {
 158         if (strcmp(f->string, s->string) < 0) {
 159           merged = list_append(merged, list_new(0, f->string, 1));
 160           f = f->next;
 161         } else {
 162           merged = list_append(merged, list_new(0, s->string, 1));
 163           s = s->next;
 164         }
 165       }
 166       merged = list_copy(merged, f);
 167       merged = list_copy(merged, s);
 168       list_free(first);
 169       list_free(second);
 170       first = second = 0;
 171     }
 172   }
 173   return result;
 174 }
 175
 176
 177 /*
 178  * list_free() - free a list of strings
 179  */
 180 void list_free (LIST *head) {
 181   /* Just tack onto freelist. */
 182   if (head) {
 183     head->tail->next = freelist;
 184     freelist = head;
 185   }
 186 }
 187
 188
 189 /*
 190  * list_print() - print a list of strings to stdout
 191  */
 192 void list_print_ex (FILE *fo, const LIST *l, int flags) {
 193   int spc = (l == NULL);
 194   for (; l; l = list_next(l)) {
 195     if (spc && (flags&LPFLAG_NO_SPACES) == 0) fputc(' ', fo);
 196     fputs(l->string, fo);
 197     spc = 1;
 198   }
 199   if (spc && (flags&LPFLAG_NO_TRSPACE) == 0) fputc(' ', fo);
 200 }
 201
 202
 203 #if 0
 204 /* FIXME! */
 205 /*
 206  * list_printq() - print a list of safely quoted strings to a file
 207  */
 208 void list_printq (FILE *out, LIST *l) {
 209   /* dump each word, enclosed in "s */
 210   /* suitable for Jambase use. */
 211   for (; l; l = list_next(l)) {
 212     const char *p = l->string;
 213     const char *ep = p+strlen(p);
 214     const char *op = p;
 215     fputc('\n', out);
 216     fputc('\t', out);
 217     fputc('"', out);
 218     /* any embedded "'s?  Escape them */
 219     while ((p = (char *)memchr(op, '"', ep-op))) {
 220       fwrite(op, p-op, 1, out);
 221       fputc('\\', out);
 222       fputc('"', out);
 223       op = p+1;
 224     }
 225     /* Write remainder */
 226     fwrite(op, ep-op, 1, out);
 227     fputc('"', out);
 228     fputc(' ', out);
 229   }
 230 }
 231 #endif
 232
 233
 234 /*
 235  * list_length() - return the number of items in the list
 236  */
 237 JAMFA_PURE int list_length (const LIST *l) {
 238   int n;
 239   for (n = 0; l; l = list_next(l), ++n) ;
 240   return n;
 241 }
 242
 243
 244 /*
 245  * lol_init() - initialize a LOL (list of lists)
 246  */
 247 void lol_init (LOL *lol) {
 248   lol->count = 0;
 249 }
 250
 251
 252 /*
 253  * lol_add() - append a LIST onto an LOL
 254  */
 255 void lol_add (LOL *lol, LIST *l) {
 256   if (lol->count < LOL_MAX) lol->list[lol->count++] = l;
 257 }
 258
 259
 260 /*
 261  * lol_free() - free the LOL and its LISTs
 262  */
 263 void lol_free (LOL *lol) {
 264   for (int i = 0; i < lol->count; ++i) list_free(lol->list[i]);
 265   lol->count = 0;
 266 }
 267
 268
 269 /*
 270  * lol_get() - return one of the LISTs in the LOL
 271  */
 272 JAMFA_PURE LIST *lol_get (LOL *lol, int i) {
 273   return (i >= 0 && i < lol->count ? lol->list[i] : NULL);
 274 }
 275
 276
 277 /*
 278  * lol_print() - debug print LISTS separated by ":"
 279  */
 280 void lol_print (const LOL *lol) {
 281   for (int i = 0; i < lol->count; ++i) {
 282     if (i) printf(":");
 283     list_print(lol->list[i]);
 284   }
 285 }