src/lists.c

   1 /*
   2  * Copyright 1993, 1995 Christopher Seiwald.
   3  * This file is part of Jam - see jam.c for Copyright information.
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18 /*
  19  * lists.c - maintain lists of strings
  20  *
  21  * This implementation essentially uses a singly linked list, but
  22  * guarantees that the head element of every list has a valid pointer
  23  * to the tail of the list, so the new elements can efficiently and
  24  * properly be appended to the end of a list.
  25  *
  26  * To avoid massive allocation, list_free() just tacks the whole freed
  27  * chain onto freelist and list_new() looks on freelist first for an
  28  * available list struct.  list_free() does not free the strings in the
  29  * chain: it lazily lets list_new() do so.
  30  */
  31 #include "jam.h"
  32 #include "newstr.h"
  33 #include "lists.h"
  34
  35
  36 static LIST *freelist = NULL;  /* junkpile for list_free() */
  37
  38
  39 /*
  40  * list_append() - append a list onto another one, returning total
  41  */
  42 LIST *list_append (LIST *l, LIST *nl) {
  43   if (!nl) {
  44     /* Just return l */
  45   } else if (!l) {
  46     l = nl;
  47   } else {
  48     /* graft two non-empty lists */
  49     l->tail->next = nl;
  50     l->tail = nl->tail;
  51   }
  52   return l;
  53 }
  54
  55
  56 static JAMFA_PURE int contains (LIST *l, const char *str) {
  57   for (; l != NULL; l = l->next) if (strcmp(l->string, str) == 0) return 1;
  58   return 0;
  59 }
  60
  61
  62 /*
  63  * list_removeall() - remove all occurences of `nl` items from `l`
  64  */
  65 LIST *list_removeall (LIST *l, LIST *nl) {
  66   if (nl && l) {
  67     LIST *p = NULL, *h = NULL;
  68     while (l != NULL) {
  69       LIST *n = l->next;
  70       if (contains(nl, l->string)) {
  71         // remove (i.e. move node to freelist)
  72         if (p != NULL) p->next = n;
  73         if (n == NULL && h != NULL) h->tail = p;
  74         l->next = freelist;
  75         freelist = l;
  76       } else {
  77         // skip
  78         if (h == NULL) h = l; // save list head
  79         p = l;
  80         if (n == NULL && h != NULL) h->tail = l;
  81       }
  82       l = n;
  83     }
  84     l = h;
  85   }
  86   return l;
  87 }
  88
  89
  90 /* get list struct from freelist, if one available, otherwise allocate */
  91 /* if from freelist, must free string first */
  92 static inline LIST *alloc_item (void) {
  93   LIST *l;
  94   if (freelist) {
  95     l = freelist;
  96     freestr(l->string);
  97     freelist = freelist->next;
  98   } else {
  99     l = malloc(sizeof(*l));
 100   }
 101   return l;
 102 }
 103
 104
 105 /*
 106  * list_new() - tack a string onto the end of a list of strings
 107  */
 108 /* copy!=0: copystr; else newstr */
 109 LIST *list_new (LIST *head, const char *string, int copy) {
 110   LIST *l;
 111   if (DEBUG_LISTS) printf("list > %s <\n", string);
 112   /* copy/newstr as needed */
 113   string = (copy ? copystr(string) : newstr(string));
 114   l = alloc_item();
 115   /* if first on chain, head points here */
 116   /* if adding to chain, tack us on */
 117   /* tail must point to this new, last element */
 118   if (!head) head = l; else head->tail->next = l;
 119   head->tail = l;
 120   l->next = 0;
 121   l->string = string;
 122   return head;
 123 }
 124
 125
 126 /*
 127  * list_copy() - copy a whole list of strings (nl) onto end of another (l)
 128  */
 129 LIST *list_copy (LIST *l, LIST *nl) {
 130   for (; nl; nl = list_next(nl)) l = list_new(l, nl->string, 1);
 131   return l;
 132 }
 133
 134
 135 /*
 136  * list_sublist() - copy a subset of a list of strings
 137  */
 138 LIST *list_sublist (LIST *l, int start, int count) {
 139   LIST *nl = NULL;
 140   for (; l && start--; l = list_next(l)) ;
 141   for (; l && count--; l = list_next(l)) nl = list_new(nl, l->string, 1);
 142   return nl;
 143 }
 144
 145
 146 /* backported from boost-jam; TEST IT!!! */
 147 /*
 148  * list_sort() - sort list
 149  */
 150 LIST *list_sort (LIST *l) {
 151   LIST *first = NULL, *second = NULL, *merged = l, *result;
 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, *s = second;
 169       while (f && s) {
 170         if (strcmp(f->string, s->string) < 0) {
 171           merged = list_append(merged, list_new(0, f->string, 1));
 172           f = f->next;
 173         } else {
 174           merged = list_append(merged, list_new(0, s->string, 1));
 175           s = s->next;
 176         }
 177       }
 178       merged = list_copy(merged, f);
 179       merged = list_copy(merged, s);
 180       list_free(first);
 181       list_free(second);
 182       first = second = 0;
 183     }
 184   }
 185   return result;
 186 }
 187
 188
 189 /* returns new list */
 190 LIST *list_reverse (const LIST *l) {
 191   LIST *res = L0, *last = L0;
 192   if (l != L0) {
 193     res = last = alloc_item();
 194     last->string = copystr(l->string);
 195     last->next = L0;
 196     last->tail = last;
 197     l = l->next;
 198   }
 199   for (; l != NULL; l = l->next) {
 200     LIST *i = alloc_item();
 201     i->string = copystr(l->string);
 202     i->next = res;
 203     res = i;
 204   }
 205   if (res != L0) res->tail = last;
 206   return res;
 207 }
 208
 209
 210
 211 /*
 212  * list_free() - free a list of strings
 213  */
 214 void list_free (LIST *head) {
 215   /* Just tack onto freelist. */
 216   if (head) {
 217     head->tail->next = freelist;
 218     freelist = head;
 219   }
 220 }
 221
 222
 223 /*
 224  * list_print() - print a list of strings to stdout
 225  */
 226 void list_print_ex (FILE *fo, const LIST *l, int flags) {
 227   int spc = (l == NULL);
 228   for (; l; l = list_next(l)) {
 229     if (spc && (flags&LPFLAG_NO_SPACES) == 0) fputc(' ', fo);
 230     fputs(l->string, fo);
 231     spc = 1;
 232   }
 233   if (spc && (flags&LPFLAG_NO_TRSPACE) == 0) fputc(' ', fo);
 234 }
 235
 236
 237 #if 0
 238 /* FIXME! */
 239 /*
 240  * list_printq() - print a list of safely quoted strings to a file
 241  */
 242 void list_printq (FILE *out, LIST *l) {
 243   /* dump each word, enclosed in "s */
 244   /* suitable for Jambase use. */
 245   for (; l; l = list_next(l)) {
 246     const char *p = l->string;
 247     const char *ep = p+strlen(p);
 248     const char *op = p;
 249     fputc('\n', out);
 250     fputc('\t', out);
 251     fputc('"', out);
 252     /* any embedded "'s?  Escape them */
 253     while ((p = (char *)memchr(op, '"', ep-op))) {
 254       fwrite(op, p-op, 1, out);
 255       fputc('\\', out);
 256       fputc('"', out);
 257       op = p+1;
 258     }
 259     /* Write remainder */
 260     fwrite(op, ep-op, 1, out);
 261     fputc('"', out);
 262     fputc(' ', out);
 263   }
 264 }
 265 #endif
 266
 267
 268 /*
 269  * list_length() - return the number of items in the list
 270  */
 271 JAMFA_PURE int list_length (const LIST *l) {
 272   int n;
 273   for (n = 0; l; l = list_next(l), ++n) ;
 274   return n;
 275 }
 276
 277
 278 /*
 279  * lol_init() - initialize a LOL (list of lists)
 280  */
 281 void lol_init (LOL *lol) {
 282   lol->count = 0;
 283 }
 284
 285
 286 /*
 287  * lol_add() - append a LIST onto an LOL
 288  */
 289 void lol_add (LOL *lol, LIST *l) {
 290   if (lol->count < LOL_MAX) lol->list[lol->count++] = l;
 291 }
 292
 293
 294 /*
 295  * lol_free() - free the LOL and its LISTs
 296  */
 297 void lol_free (LOL *lol) {
 298   for (int i = 0; i < lol->count; ++i) list_free(lol->list[i]);
 299   lol->count = 0;
 300 }
 301
 302
 303 /*
 304  * lol_get() - return one of the LISTs in the LOL
 305  */
 306 JAMFA_PURE LIST *lol_get (LOL *lol, int i) {
 307   return (i >= 0 && i < lol->count ? lol->list[i] : NULL);
 308 }
 309
 310
 311 /*
 312  * lol_print() - debug print LISTS separated by ":"
 313  */
 314 void lol_print (const LOL *lol) {
 315   for (int i = 0; i < lol->count; ++i) {
 316     if (i) printf(":");
 317     list_print(lol->list[i]);
 318   }
 319 }