list.c revision 6ae2c069 
1/*
2  Copyright (c) 2002-2003 by Juliusz Chroboczek
3
4  Permission is hereby granted, free of charge, to any person obtaining a copy
5  of this software and associated documentation files (the "Software"), to deal
6  in the Software without restriction, including without limitation the rights
7  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8  copies of the Software, and to permit persons to whom the Software is
9  furnished to do so, subject to the following conditions:
10
11  The above copyright notice and this permission notice shall be included in
12  all copies or substantial portions of the Software.
13
14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
17  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20  THE SOFTWARE.
21*/
22
23#ifdef HAVE_CONFIG_H
24#include "config.h"
25#endif
26
27#include <stdlib.h>
28#include <stdio.h>
29#include <stdarg.h>
30#include <string.h>
31#include "list.h"
32
33int
34listMember(const char *elt, ListPtr list)
35{
36    while (list != NULL) {
37        if (strcmp(elt, list->value) == 0)
38            return 1;
39        list = list->next;
40    }
41    return 0;
42}
43
44ListPtr
45listCons(char *car, ListPtr cdr)
46{
47    ListPtr lcar = malloc(sizeof(ListRec));
48
49    if (!lcar)
50        return NULL;
51    lcar->value = car;
52    lcar->next = cdr;
53    return lcar;
54}
55
56ListPtr
57listAdjoin(char *car, ListPtr cdr)
58{
59    if (listMember(car, cdr)) {
60        free(car);
61        return cdr;
62    }
63    return listCons(car, cdr);
64}
65
66char *
67dsprintf(const char *f, ...)
68{
69    va_list args;
70    char *string;
71
72#ifdef HAVE_VASPRINTF
73    va_start(args, f);
74    if (vasprintf(&string, f, args) == -1)
75        string = NULL;
76    va_end(args);
77    return string;
78#else
79    {
80        int n, size = 20;
81
82        while (1) {
83            if (size > 4096)
84                return NULL;
85            string = malloc(size);
86            if (!string)
87                return NULL;
88            va_start(args, f);
89            n = vsnprintf(string, size, f, args);
90            va_end(args);
91            if (n >= 0 && n < size)
92                return string;
93            else if (n >= size)
94                size = n + 1;
95            else
96                size = size * 3 / 2 + 1;
97            free(string);
98        }
99    }
100#endif
101}
102
103ListPtr
104listConsF(ListPtr cdr, const char *f, ...)
105{
106    va_list args;
107    char *string;
108
109    {
110        int n, size = 20;
111
112        while (1) {
113            if (size > 4096)
114                return NULL;
115            string = malloc(size);
116            if (!string)
117                return NULL;
118            va_start(args, f);
119            n = vsnprintf(string, size, f, args);
120            va_end(args);
121            if (n >= 0 && n < size)
122                return listCons(string, cdr);
123            else if (n >= size)
124                size = n + 1;
125            else
126                size = size * 3 / 2 + 1;
127            free(string);
128        }
129    }
130}
131
132ListPtr
133listAdjoinF(ListPtr cdr, const char *f, ...)
134{
135    va_list args;
136    char *string;
137
138    {
139        int n, size = 20;
140
141        while (1) {
142            if (size > 4096)
143                return NULL;
144            string = malloc(size);
145            if (!string)
146                return NULL;
147            va_start(args, f);
148            n = vsnprintf(string, size, f, args);
149            va_end(args);
150            if (n >= 0 && n < size)
151                return listAdjoin(string, cdr);
152            else if (n >= size)
153                size = n + 1;
154            else
155                size = size * 3 / 2 + 1;
156            free(string);
157        }
158    }
159}
160
161int
162listLength(ListPtr list)
163{
164    int n = 0;
165
166    while (list) {
167        n++;
168        list = list->next;
169    }
170    return n;
171}
172
173ListPtr
174appendList(ListPtr first, ListPtr second)
175{
176    ListPtr current;
177
178    if (second == NULL)
179        return first;
180
181    if (first == NULL)
182        return second;
183
184    for (current = first; current->next; current = current->next);
185
186    current->next = second;
187    return first;
188}
189
190ListPtr
191makeList(char **a, int n, ListPtr old, int begin)
192{
193    ListPtr first, current, next;
194    int i;
195
196    if (n == 0)
197        return old;
198
199    first = malloc(sizeof(ListRec));
200    if (!first)
201        return NULL;
202
203    first->value = a[0];
204    first->next = NULL;
205
206    current = first;
207    for (i = 1; i < n; i++) {
208        next = malloc(sizeof(ListRec));
209        if (!next) {
210            destroyList(first);
211            return NULL;
212        }
213        next->value = a[i];
214        next->next = NULL;
215
216        current->next = next;
217        current = next;
218    }
219    if (begin) {
220        current->next = old;
221        return first;
222    }
223    else {
224        return appendList(old, first);
225    }
226}
227
228ListPtr
229reverseList(ListPtr old)
230{
231    ListPtr new = NULL, current;
232
233    while (old) {
234        current = old;
235        old = old->next;
236        current->next = new;
237        new = current;
238    }
239    return new;
240}
241
242/* qsort helper for sorting list entries */
243static int
244compareListEntries(const void *a, const void *b)
245{
246    const ListPtr lista = *(const ListPtr *) a;
247    const ListPtr listb = *(const ListPtr *) b;
248
249    return strcmp(lista->value, listb->value);
250}
251
252ListPtr
253sortList(ListPtr old)
254{
255    int i;
256    int l = listLength(old);
257    ListPtr n;
258    ListPtr *sorted;
259
260    if (l <= 0)
261        return old;
262
263    sorted = malloc(l * sizeof(ListPtr));
264
265    if (sorted == NULL)
266        return old;
267
268    for (n = old, i = 0; n != NULL; n = n->next) {
269        sorted[i++] = n;
270    }
271    qsort(sorted, i, sizeof(ListPtr), compareListEntries);
272    n = sorted[0];
273    for (i = 0; i < (l - 1); i++) {
274        sorted[i]->next = sorted[i + 1];
275    }
276    sorted[i]->next = NULL;
277    free(sorted);
278    return n;
279}
280
281void
282destroyList(ListPtr old)
283{
284    ListPtr next;
285
286    if (!old)
287        return;
288    while (old) {
289        next = old->next;
290        free(old);
291        old = next;
292    }
293}
294
295void
296deepDestroyList(ListPtr old)
297{
298    ListPtr next;
299
300    if (!old)
301        return;
302    while (old) {
303        next = old->next;
304        free(old->value);
305        free(old);
306        old = next;
307    }
308}
309