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     //
  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   /* copy/newstr as needed */
  96   string = copy?copystr(string):newstr(string);
  97   /* get list struct from freelist, if one available, otherwise allocate */
  98   /* if from freelist, must free string first */
  99   if (freelist) {
 100     l = freelist;
 101     freestr(l->string);
 102     freelist = freelist->next;
 103   } else {
 104     l = (LIST *)malloc(sizeof(*l));
 105   }
 106   /* if first on chain, head points here */
 107   /* if adding to chain, tack us on */
 108   /* tail must point to this new, last element */
 109   if (!head) head = l; else head->tail->next = l;
 110   head->tail = l;
 111   l->next = 0;
 112   l->string = string;
 113   return head;
 114 }
 115
 116
 117 /*
 118  * list_copy() - copy a whole list of strings (nl) onto end of another (l)
 119  */
 120 LIST *list_copy (LIST *l, LIST *nl) {
 121   for (; nl; nl = list_next(nl)) l = list_new(l, nl->string, 1);
 122   return l;
 123 }
 124
 125
 126 /*
 127  * list_sublist() - copy a subset of a list of strings
 128  */
 129 LIST *list_sublist (LIST *l, int start, int count) {
 130   LIST *nl = NULL;
 131   //
 132   for (; l && start--; l = list_next(l)) ;
 133   for (; l && count--; l = list_next(l)) nl = list_new(nl, l->string, 1);
 134   return nl;
 135 }
 136
 137
 138 /* backported from boost-jam; TEST IT!!! */
 139 /*
 140  * list_sort() - sort list
 141  */
 142 LIST *list_sort (LIST *l) {
 143   LIST *first = NULL, *second = NULL, *merged = l, *result;
 144   //
 145   if (!l) return L0;
 146   for (;;) {
 147     /* split the list in two */
 148     LIST **dst = &first;
 149     LIST *src = merged;
 150     for (;;) {
 151       *dst = list_append(*dst, list_new(0, src->string, 1));
 152       if (!src->next) break;
 153       if (strcmp(src->string, src->next->string) > 0) dst = (dst==&first)?&second:&first;
 154       src = src->next;
 155     }
 156     if (merged != l) list_free(merged);
 157     merged = 0;
 158     if (second == 0) { result = first; break; }
 159     /* merge lists 'first' and 'second' into 'merged' and free 'first'/'second' */
 160     {
 161       LIST *f = first, *s = second;
 162       //
 163       while (f && s) {
 164         if (strcmp(f->string, s->string) < 0) {
 165           merged = list_append(merged, list_new(0, f->string, 1));
 166           f = f->next;
 167         } else {
 168           merged = list_append(merged, list_new(0, s->string, 1));
 169           s = s->next;
 170         }
 171       }
 172       merged = list_copy(merged, f);
 173       merged = list_copy(merged, s);
 174       list_free(first);
 175       list_free(second);
 176       first = second = 0;
 177     }
 178   }
 179   return result;
 180 }
 181
 182
 183 /*
 184  * list_free() - free a list of strings
 185  */
 186 void list_free (LIST *head) {
 187   /* Just tack onto freelist. */
 188   if (head) {
 189     head->tail->next = freelist;
 190     freelist = head;
 191   }
 192 }
 193
 194
 195 /*
 196  * list_print() - print a list of strings to stdout
 197  */
 198 void list_print (LIST *l) {
 199   for (; l; l = list_next(l)) printf("%s ", l->string);
 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     //
 216     fputc('\n', out);
 217     fputc('\t', out);
 218     fputc('"', out);
 219     /* any embedded "'s?  Escape them */
 220     while ((p = (char *)memchr(op, '"', ep-op))) {
 221       fwrite(op, p-op, 1, out);
 222       fputc('\\', out);
 223       fputc('"', out);
 224       op = p+1;
 225     }
 226     /* Write remainder */
 227     fwrite(op, ep-op, 1, out);
 228     fputc('"', out);
 229     fputc(' ', out);
 230   }
 231 }
 232 #endif
 233
 234
 235 /*
 236  * list_length() - return the number of items in the list
 237  */
 238 int list_length (LIST *l) {
 239   int n;
 240   //
 241   for (n = 0; l; l = list_next(l), ++n) ;
 242   return n;
 243 }
 244
 245
 246 /*
 247  * lol_init() - initialize a LOL (list of lists)
 248  */
 249 void lol_init (LOL *lol) {
 250   lol->count = 0;
 251 }
 252
 253
 254 /*
 255  * lol_add() - append a LIST onto an LOL
 256  */
 257 void lol_add (LOL *lol, LIST *l) {
 258   if (lol->count < LOL_MAX) lol->list[lol->count++] = l;
 259 }
 260
 261
 262 /*
 263  * lol_free() - free the LOL and its LISTs
 264  */
 265 void lol_free (LOL *lol) {
 266   int i;
 267   //
 268   for (i = 0; i < lol->count; ++i) list_free(lol->list[i]);
 269   lol->count = 0;
 270 }
 271
 272
 273 /*
 274  * lol_get() - return one of the LISTs in the LOL
 275  */
 276 LIST *lol_get (LOL *lol, int i) {
 277   return i<lol->count?lol->list[i]:NULL;
 278 }
 279
 280
 281 /*
 282  * lol_print() - debug print LISTS separated by ":"
 283  */
 284 void lol_print (LOL *lol) {
 285   int i;
 286   //
 287   for (i = 0; i < lol->count; ++i) {
 288     if (i) printf(" : ");
 289     list_print(lol->list[i]);
 290   }
 291 }