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