2 * Copyright 1993, 1995 Christopher Seiwald.
4 * This file is part of Jam - see jam.c for Copyright information.
8 * lists.c - maintain lists of strings
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.
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.
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
31 static LIST
*freelist
= 0; /* junkpile for list_free() */
35 * list_append() - append a list onto another one, returning total
37 LIST
*list_append (LIST
*l
, LIST
*nl
) {
43 /* Graft two non-empty lists. */
51 static int contains (LIST
*l
, const char *str
) {
52 for (; l
!= NULL
; l
= l
->next
) if (strcmp(l
->string
, str
) == 0) return 1;
58 * list_removeall() - remove all occurences of `nl` items from `l`
60 LIST
*list_removeall (LIST
*l
, LIST
*nl
) {
62 LIST
*p
= NULL
, *h
= NULL
;
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
;
75 if (h
== NULL
) h
= l
; // save list head
77 if (n
== NULL
&& h
!= NULL
) h
->tail
= l
;
88 * list_new() - tack a string onto the end of a list of strings
90 /* copy!=0: copystr; else newstr */
91 LIST
*list_new (LIST
*head
, const char *string
, int copy
) {
94 if (DEBUG_LISTS
) printf("list > %s <\n", string
);
96 /* Copy/newstr as needed */
97 string
= copy
?copystr(string
):newstr(string
);
99 /* Get list struct from freelist, if one available. */
100 /* Otherwise allocate. */
101 /* If from freelist, must free string first */
105 freelist
= freelist
->next
;
107 l
= (LIST
*)malloc(sizeof(*l
));
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
;
122 * list_copy() - copy a whole list of strings (nl) onto end of another (l)
124 LIST
*list_copy (LIST
*l
, LIST
*nl
) {
125 for (; nl
; nl
= list_next(nl
)) l
= list_new(l
, nl
->string
, 1);
131 * list_sublist() - copy a subset of a list of strings
133 LIST
*list_sublist (LIST
*l
, int start
, int count
) {
136 for (; l
&& start
--; l
= list_next(l
)) ;
137 for (; l
&& count
--; l
= list_next(l
)) nl
= list_new(nl
, l
->string
, 1);
142 /* backported from boost-jam; TEST IT!!! */
144 * list_sort() - sort list
146 LIST
*list_sort (LIST
*l
) {
154 /* Split the list in two */
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
;
163 if (merged
!= l
) list_free(merged
);
165 if (second
== 0) { result
= first
; break; }
166 /* Merge lists 'first' and 'second' into 'merged' and free 'first'/'second'. */
171 if (strcmp(f
->string
, s
->string
) < 0) {
172 merged
= list_append(merged
, list_new(0, f
->string
, 1));
175 merged
= list_append(merged
, list_new(0, s
->string
, 1));
179 merged
= list_copy(merged
, f
);
180 merged
= list_copy(merged
, s
);
191 * list_free() - free a list of strings
193 void list_free (LIST
*head
) {
194 /* Just tack onto freelist. */
196 head
->tail
->next
= freelist
;
203 * list_print() - print a list of strings to stdout
205 void list_print (LIST
*l
) {
206 for (; l
; l
= list_next(l
)) printf("%s ", l
->string
);
212 * list_printq() - print a list of safely quoted strings to a file
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
);
225 /* Any embedded "'s? Escape them */
226 while ((p
= (char *)memchr(op
, '"', ep
-op
))) {
227 fwrite(op
, p
-op
, 1, out
);
232 /* Write remainder */
233 fwrite(op
, ep
-op
, 1, out
);
241 * list_length() - return the number of items in the list
243 int list_length (LIST
*l
) {
246 for (; l
; l
= list_next(l
), ++n
) ;
252 * lol_init() - initialize a LOL (list of lists)
254 void lol_init (LOL
*lol
) {
260 * lol_add() - append a LIST onto an LOL
262 void lol_add (LOL
*lol
, LIST
*l
) {
263 if (lol
->count
< LOL_MAX
) lol
->list
[lol
->count
++] = l
;
268 * lol_free() - free the LOL and its LISTs
270 void lol_free (LOL
*lol
) {
273 for (i
= 0; i
< lol
->count
; i
++) list_free(lol
->list
[i
]);
279 * lol_get() - return one of the LISTs in the LOL
281 LIST
*lol_get (LOL
*lol
, int i
) {
282 return i
<lol
->count
?lol
->list
[i
]:0;
287 * lol_print() - debug print LISTS separated by ":"
289 void lol_print (LOL
*lol
) {
292 for (i
= 0; i
< lol
->count
; i
++) {
293 if (i
) printf(" : ");
294 list_print(lol
->list
[i
]);