2 * Copyright 1993, 1995 Christopher Seiwald.
3 * This file is part of Jam - see jam.c for Copyright information.
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.
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.
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/>.
18 * lists.c - maintain lists of strings
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.
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.
35 static LIST
*freelist
= NULL
; /* junkpile for list_free() */
39 * list_append() - append a list onto another one, returning total
41 LIST
*list_append (LIST
*l
, LIST
*nl
) {
47 /* graft two non-empty lists */
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;
62 * list_removeall() - remove all occurences of `nl` items from `l`
64 LIST
*list_removeall (LIST
*l
, LIST
*nl
) {
66 LIST
*p
= NULL
, *h
= NULL
;
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
;
77 if (h
== NULL
) h
= l
; // save list head
79 if (n
== NULL
&& h
!= NULL
) h
->tail
= l
;
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) {
96 freelist
= freelist
->next
;
98 l
= malloc(sizeof(*l
));
105 * list_new() - tack a string onto the end of a list of strings
107 /* copy!=0: copystr; else newstr */
108 LIST
*list_new (LIST
*head
, const char *string
, int copy
) {
110 if (DEBUG_LISTS
) printf("list > %s <\n", string
);
111 /* copy/newstr as needed */
112 string
= (copy
? copystr(string
) : newstr(string
));
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
;
126 * list_copy() - copy a whole list of strings (nl) onto end of another (l)
128 LIST
*list_copy (LIST
*l
, LIST
*nl
) {
129 for (; nl
; nl
= list_next(nl
)) l
= list_new(l
, nl
->string
, 1);
135 * list_sublist() - copy a subset of a list of strings
137 LIST
*list_sublist (LIST
*l
, int start
, int count
) {
139 for (; l
&& start
--; l
= list_next(l
)) ;
140 for (; l
&& count
--; l
= list_next(l
)) nl
= list_new(nl
, l
->string
, 1);
145 /* backported from boost-jam; TEST IT!!! */
147 * list_sort() - sort list
149 LIST
*list_sort (LIST
*l
) {
150 LIST
*first
= NULL
, *second
= NULL
, *merged
= l
, *result
;
153 /* split the list in two */
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
;
162 if (merged
!= l
) list_free(merged
);
164 if (second
== 0) { result
= first
; break; }
165 /* merge lists 'first' and 'second' into 'merged' and free 'first'/'second' */
167 LIST
*f
= first
, *s
= second
;
169 if (strcmp(f
->string
, s
->string
) < 0) {
170 merged
= list_append(merged
, list_new(0, f
->string
, 1));
173 merged
= list_append(merged
, list_new(0, s
->string
, 1));
177 merged
= list_copy(merged
, f
);
178 merged
= list_copy(merged
, s
);
188 /* returns new list */
189 LIST
*list_reverse (const LIST
*l
) {
190 LIST
*res
= L0
, *last
= L0
;
192 res
= last
= alloc_item();
193 last
->string
= copystr(l
->string
);
198 for (; l
!= NULL
; l
= l
->next
) {
199 LIST
*i
= alloc_item();
200 i
->string
= copystr(l
->string
);
204 if (res
!= L0
) res
->tail
= last
;
211 * list_free() - free a list of strings
213 void list_free (LIST
*head
) {
214 /* Just tack onto freelist. */
216 head
->tail
->next
= freelist
;
223 * list_print() - print a list of strings to stdout
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
);
232 if (spc
&& (flags
&LPFLAG_NO_TRSPACE
) == 0) fputc(' ', fo
);
239 * list_printq() - print a list of safely quoted strings to a file
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
);
251 /* any embedded "'s? Escape them */
252 while ((p
= (char *)memchr(op
, '"', ep
-op
))) {
253 fwrite(op
, p
-op
, 1, out
);
258 /* Write remainder */
259 fwrite(op
, ep
-op
, 1, out
);
268 * list_length() - return the number of items in the list
270 JAMFA_PURE
int list_length (const LIST
*l
) {
272 for (n
= 0; l
; l
= list_next(l
), ++n
) ;
278 * lol_init() - initialize a LOL (list of lists)
280 void lol_init (LOL
*lol
) {
286 * lol_add() - append a LIST onto an LOL
288 void lol_add (LOL
*lol
, LIST
*l
) {
289 if (lol
->count
< LOL_MAX
) lol
->list
[lol
->count
++] = l
;
294 * lol_free() - free the LOL and its LISTs
296 void lol_free (LOL
*lol
) {
297 for (int i
= 0; i
< lol
->count
; ++i
) list_free(lol
->list
[i
]);
303 * lol_get() - return one of the LISTs in the LOL
305 JAMFA_PURE LIST
*lol_get (LOL
*lol
, int i
) {
306 return (i
>= 0 && i
< lol
->count
? lol
->list
[i
] : NULL
);
311 * lol_print() - debug print LISTS separated by ":"
313 void lol_print (const LOL
*lol
) {
314 for (int i
= 0; i
< lol
->count
; ++i
) {
316 list_print(lol
->list
[i
]);