libbanshee/engine/list.c

   1 /*
   2  * Copyright (c) 2000-2001
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   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.
  16  *
  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
  27  * SUCH DAMAGE.
  28  *
  29  */
  30
  31 #include <assert.h>
  32 #include "list.h"
  33 #include "util.h"
  34
  35 struct list_node
  36 {
  37   void *data;
  38   struct list_node *sameregion next;
  39 };
  40
  41 #define scan_node(b,var) for (var = b; var; var = var->next)
  42
  43 struct list
  44 {
  45   region sameregion r;
  46   int length;
  47   list_node sameregion head;
  48 };
  49
  50 struct list *new_list(region r)
  51 {
  52   struct list *result;
  53
  54   assert(r);
  55
  56   result = ralloc(r,struct list);
  57   result->r = r;
  58   result->length = 0;
  59   result->head = NULL;
  60
  61   return result;
  62 }
  63
  64 int list_size(struct list *l)
  65 {
  66   return l->length;
  67 }
  68
  69 struct list *list_cons(void *data, struct list *l)
  70 {
  71   list_node newnode = ralloc(l->r, struct list_node);
  72   newnode->next = l->head;
  73   newnode->data = data;
  74
  75   l->head = newnode;
  76   l->length++;
  77
  78   return l;
  79 }
  80
  81 struct list *list_reverse(struct list *l)
  82 {
  83
  84   if (list_empty(l))
  85     return l;
  86
  87   else
  88     {
  89       list_node temp,reversed = NULL;
  90
  91       while (l->head)
  92         {
  93           temp = l->head->next;
  94
  95           l->head->next = reversed;
  96
  97           reversed = l->head;
  98
  99           l->head = temp;
 100         }
 101
 102       l->head = reversed;
 103       return l;
 104     }
 105
 106 }
 107
 108 bool list_empty(struct list *l)
 109 {
 110   return (l->head == NULL);
 111 }
 112
 113 static inline list_node tail(list_node n)
 114 {
 115   if (n == NULL)
 116     return NULL;
 117   else
 118     {
 119       list_node temp = NULL,
 120         tail = NULL;
 121
 122       scan_node(n,temp)
 123         tail = temp;
 124
 125       assert(tail && tail->next == NULL);
 126
 127       return tail;
 128     }
 129 }
 130
 131 struct list *list_append(struct list *a, struct list *b)
 132 {
 133   list_node tl;
 134
 135   assert( a && b );
 136   assert( a != b);
 137   assert( ptr_eq(a->r,b->r) );
 138
 139   tl = tail(a->head);
 140
 141
 142   if (! tl)
 143     {
 144       a->head = b->head;
 145       a->length = b->length;
 146     }
 147
 148   else
 149     {
 150       tl->next = b->head;
 151       a->length += b->length;
 152     }
 153   return a;
 154 }
 155
 156 struct list *list_app(struct list *l,app_fn app)
 157 {
 158   list_node n = NULL;
 159
 160
 161   assert(l);
 162
 163   scan_node(l->head,n)
 164     {
 165       app(n->data);
 166     }
 167   return l;
 168 }
 169
 170 void *list_find(struct list *l,eq_fn eq)
 171 {
 172   list_node n = NULL;
 173   assert(l);
 174
 175   scan_node(l->head,n)
 176     {
 177       if (eq(n->data))
 178         return n;
 179     }
 180
 181   return NULL;
 182 }
 183
 184 struct list *list_tail(struct list *l)
 185 {
 186   l->length--;
 187   l->head = l->head->next;
 188   return l;
 189 }
 190
 191 void *list_head(struct list *l)
 192 {
 193   return l->head->data;
 194 }
 195
 196 struct list *list_filter(region r,struct list *l,eq_fn eq)
 197 {
 198   struct list *result;
 199   list_node n = NULL;
 200   assert(l);
 201
 202   result = new_list(r);
 203
 204   scan_node(l->head,n)
 205     {
 206       if (eq(n->data))
 207         list_cons(n->data,result);
 208     }
 209
 210   return result;
 211 }
 212
 213 struct list *list_keep(struct list *l, eq_fn eq)
 214 {
 215   list_node prev, n;
 216   assert(l);
 217
 218   while (l->head && !eq(l->head->data))
 219     {
 220       l->head = l->head->next;
 221     }
 222
 223   prev = l->head;
 224   scan_node(l->head->next,n)
 225     {
 226       if (!eq(n->data))
 227           prev->next = n->next;
 228       else prev = n;
 229     }
 230   return l;
 231 }
 232
 233 struct list *list_filter2(struct list *l,eq_fn eq)
 234 {
 235   return list_filter(l->r,l,eq);
 236 }
 237
 238 struct list *list_copy(region r, struct list *l)
 239 {
 240
 241   struct list *result;
 242   list_node n = NULL;
 243 #ifndef NDEBUG
 244   int count = 0;
 245 #endif
 246   assert(l);
 247
 248   result = new_list(r);
 249
 250   scan_node(l->head,n)
 251     {
 252       list_cons(n->data,result);
 253       assert(++count <= l->length);
 254     }
 255
 256   return list_reverse(result);
 257 }
 258 /* A Linked-List Memory Sort
 259    by Philip J. Erdelsky
 260    pje@acm.org
 261    http://www.alumni.caltech.edu/~pje/
 262 */
 263
 264 #include <stdio.h>
 265
 266 static void *sort_linked_list(void *p, unsigned index,
 267   int (*compare)(const void *,const void *, comparator_fn), long *pcount, comparator_fn data)
 268 {
 269   unsigned base;
 270   unsigned long block_size;
 271
 272   struct record
 273   {
 274     struct record *next[1];
 275     /* other members not directly accessed by this function */
 276   };
 277
 278   struct tape
 279   {
 280     struct record *first, *last;
 281     unsigned long count;
 282   } tape[4];
 283
 284   /* Distribute the records alternately to tape[0] and tape[1]. */
 285
 286   tape[0].count = tape[1].count = 0L;
 287   tape[0].first = NULL;
 288   base = 0;
 289   while (p != NULL)
 290   {
 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);
 294     tape[base].count++;
 295     p = next;
 296     base ^= 1;
 297   }
 298
 299   /* If the list is empty or contains only a single record, then */
 300   /* tape[1].count == 0L and this part is vacuous.               */
 301
 302   for (base = 0, block_size = 1L; tape[base+1].count != 0L;
 303     base ^= 2, block_size <<= 1)
 304   {
 305     int dest;
 306     struct tape *tape0, *tape1;
 307     tape0 = tape + base;
 308     tape1 = tape + base + 1;
 309     dest = base ^ 2;
 310     tape[dest].count = tape[dest+1].count = 0;
 311     for (; tape0->count != 0; dest ^= 1)
 312     {
 313       unsigned long n0, n1;
 314       struct tape *output_tape = tape + dest;
 315       n0 = n1 = block_size;
 316       while (1)
 317       {
 318         struct record *chosen_record;
 319         struct tape *chosen_tape;
 320         if (n0 == 0 || tape0->count == 0)
 321         {
 322           if (n1 == 0 || tape1->count == 0)
 323             break;
 324           chosen_tape = tape1;
 325           n1--;
 326         }
 327         else if (n1 == 0 || tape1->count == 0)
 328         {
 329           chosen_tape = tape0;
 330           n0--;
 331         }
 332         else if ((*compare)(tape0->first, tape1->first, data) > 0)
 333         {
 334           chosen_tape = tape1;
 335           n1--;
 336         }
 337         else
 338         {
 339           chosen_tape = tape0;
 340           n0--;
 341         }
 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;
 347         else
 348           output_tape->last->next[index] = chosen_record;
 349         output_tape->last = chosen_record;
 350         output_tape->count++;
 351       }
 352     }
 353   }
 354
 355   if (tape[base].count > 1L)
 356     tape[base].last->next[index] = NULL;
 357   if (pcount != NULL)
 358     *pcount = tape[base].count;
 359   return tape[base].first;
 360 }
 361
 362
 363
 364 static int compare(const void *node1, const void *node2, comparator_fn data)
 365 {
 366    comparator_fn cmp = (comparator_fn) data;
 367    return cmp(((struct list_node *)node1)->data,
 368               ((struct list_node *)node2)->data);
 369 }
 370
 371 struct list *list_sort(struct list *l, comparator_fn cmp)
 372 {
 373   long pcount;
 374   l->head = sort_linked_list(l->head,1,compare,&pcount, cmp);
 375   assert(pcount == l->length);
 376   return l;
 377 }
 378
 379 struct list *list_merge(struct list *a,struct list *b, comparator_fn cmp)
 380 {
 381   return list_sort( list_append(a,b),cmp);
 382 }
 383
 384 void list_scan(struct list *a,struct list_scanner *scan)
 385 {
 386   scan->l = a;
 387   scan->cur = a->head;
 388 }
 389
 390 bool list_next(struct list_scanner *scan, void **data)
 391 {
 392   if (!scan->cur)
 393     return FALSE;
 394   else
 395     {
 396       if (data)
 397         *data = scan->cur->data;
 398       scan->cur = scan->cur->next;
 399       return TRUE;
 400     }
 401 }
 402
 403 void list_clear(struct list *l)
 404 {
 405   l->head = NULL;
 406   l->length = 0;
 407 }
 408
 409 bool list_member(struct list *l,void *data)
 410 {
 411   list_node n = NULL;
 412   scan_node(l->head,n)
 413     {
 414       if (n->data == data)
 415         return TRUE;
 416     }
 417   return FALSE;
 418 }
 419
 420
 421 struct list *list_from_array(region r,void **data, int length)
 422 {
 423   struct list *result = new_list(r);
 424   int i;
 425
 426   for (i = length -1; i >= 0; i--)
 427     {
 428       list_cons(data[i],result);
 429     }
 430   return result;
 431 }
 432
 433
 434
 435
 436
 437
 438