2 * Copyright (c) 2000-2001
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 struct list_node *sameregion next;
41 #define scan_node(b,var) for (var = b; var; var = var->next)
47 list_node sameregion head;
50 struct list *new_list(region r)
56 result = ralloc(r,struct list);
64 int list_size(struct list *l)
69 struct list *list_cons(void *data, struct list *l)
71 list_node newnode = ralloc(l->r, struct list_node);
72 newnode->next = l->head;
81 struct list *list_reverse(struct list *l)
89 list_node temp,reversed = NULL;
95 l->head->next = reversed;
108 bool list_empty(struct list *l)
110 return (l->head == NULL);
113 static inline list_node tail(list_node n)
119 list_node temp = NULL,
125 assert(tail && tail->next == NULL);
131 struct list *list_append(struct list *a, struct list *b)
137 assert( ptr_eq(a->r,b->r) );
145 a->length = b->length;
151 a->length += b->length;
156 struct list *list_app(struct list *l,app_fn app)
170 void *list_find(struct list *l,eq_fn eq)
184 struct list *list_tail(struct list *l)
187 l->head = l->head->next;
191 void *list_head(struct list *l)
193 return l->head->data;
196 struct list *list_filter(region r,struct list *l,eq_fn eq)
202 result = new_list(r);
207 list_cons(n->data,result);
213 struct list *list_keep(struct list *l, eq_fn eq)
218 while (l->head && !eq(l->head->data))
220 l->head = l->head->next;
224 scan_node(l->head->next,n)
227 prev->next = n->next;
233 struct list *list_filter2(struct list *l,eq_fn eq)
235 return list_filter(l->r,l,eq);
238 struct list *list_copy(region r, struct list *l)
248 result = new_list(r);
252 list_cons(n->data,result);
253 assert(++count <= l->length);
256 return list_reverse(result);
258 /* A Linked-List Memory Sort
259 by Philip J. Erdelsky
261 http://www.alumni.caltech.edu/~pje/
266 static void *sort_linked_list(void *p, unsigned index,
267 int (*compare)(const void *,const void *, comparator_fn), long *pcount, comparator_fn data)
270 unsigned long block_size;
274 struct record *next[1];
275 /* other members not directly accessed by this function */
280 struct record *first, *last;
284 /* Distribute the records alternately to tape[0] and tape[1]. */
286 tape[0].count = tape[1].count = 0L;
287 tape[0].first = NULL;
291 struct record *next = ((struct record *)p)->next[index];
292 ((struct record *)p)->next[index] = tape[base].first;
293 tape[base].first = ((struct record *)p);
299 /* If the list is empty or contains only a single record, then */
300 /* tape[1].count == 0L and this part is vacuous. */
302 for (base = 0, block_size = 1L; tape[base+1].count != 0L;
303 base ^= 2, block_size <<= 1)
306 struct tape *tape0, *tape1;
308 tape1 = tape + base + 1;
310 tape[dest].count = tape[dest+1].count = 0;
311 for (; tape0->count != 0; dest ^= 1)
313 unsigned long n0, n1;
314 struct tape *output_tape = tape + dest;
315 n0 = n1 = block_size;
318 struct record *chosen_record;
319 struct tape *chosen_tape;
320 if (n0 == 0 || tape0->count == 0)
322 if (n1 == 0 || tape1->count == 0)
327 else if (n1 == 0 || tape1->count == 0)
332 else if ((*compare)(tape0->first, tape1->first, data) > 0)
342 chosen_tape->count--;
343 chosen_record = chosen_tape->first;
344 chosen_tape->first = chosen_record->next[index];
345 if (output_tape->count == 0)
346 output_tape->first = chosen_record;
348 output_tape->last->next[index] = chosen_record;
349 output_tape->last = chosen_record;
350 output_tape->count++;
355 if (tape[base].count > 1L)
356 tape[base].last->next[index] = NULL;
358 *pcount = tape[base].count;
359 return tape[base].first;
364 static int compare(const void *node1, const void *node2, comparator_fn data)
366 comparator_fn cmp = (comparator_fn) data;
367 return cmp(((struct list_node *)node1)->data,
368 ((struct list_node *)node2)->data);
371 struct list *list_sort(struct list *l, comparator_fn cmp)
374 l->head = sort_linked_list(l->head,1,compare,&pcount, cmp);
375 assert(pcount == l->length);
379 struct list *list_merge(struct list *a,struct list *b, comparator_fn cmp)
381 return list_sort( list_append(a,b),cmp);
384 void list_scan(struct list *a,struct list_scanner *scan)
390 bool list_next(struct list_scanner *scan, void **data)
397 *data = scan->cur->data;
398 scan->cur = scan->cur->next;
403 void list_clear(struct list *l)
409 bool list_member(struct list *l,void *data)
421 struct list *list_from_array(region r,void **data, int length)
423 struct list *result = new_list(r);
426 for (i = length -1; i >= 0; i--)
428 list_cons(data[i],result);