libbanshee/engine/jcollection.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 "jcollection.h"
  33 #include "hashset.h"
  34 #include "termhash.h"
  35
  36
  37 /*
  38    static term_hash jcoll_hash;
  39  */
  40
  41 struct jcoll_dict
  42 {
  43   region r;
  44   term_hash hash;
  45   get_stamp_fn_ptr get_stamp;
  46 };
  47
  48 enum jcoll_type
  49 {
  50   j_single,
  51   j_chain,
  52   j_join
  53 };
  54
  55 /* generic jcoll type */
  56 struct jcoll
  57 {
  58   enum jcoll_type type;
  59   stamp st;
  60 };
  61
  62 struct jcoll_single
  63 {
  64   enum jcoll_type type;
  65   stamp st;
  66   gen_e entry;
  67 };
  68
  69 struct jcoll_chain
  70 {
  71   enum jcoll_type type;
  72   stamp st;
  73   gen_e_list sameregion entries;
  74 };
  75
  76 struct jcoll_join
  77 {
  78   enum jcoll_type type;
  79   stamp st;
  80   jcoll_list sameregion joins;
  81   gen_e_list sameregion cache;
  82 };
  83
  84 typedef struct jcoll_single *jcoll_single;
  85 typedef struct jcoll_chain *jcoll_chain;
  86 typedef struct jcoll_join *jcoll_join;
  87
  88 DEFINE_LIST(jcoll_list,jcoll)
  89
  90
  91
  92 jcoll jcoll_new(jcoll_dict d, gen_e e)
  93 {
  94   jcoll_single result = ralloc(d->r, struct jcoll_single);
  95   result->type = j_single;
  96   result->st = stamp_fresh();
  97   result->entry = e;
  98   return (jcoll)result;
  99 }
 100
 101 jcoll jcoll_jjoin(jcoll_dict d,jcoll_list list)
 102 {
 103
 104   if (jcoll_list_empty(list))
 105     return NULL;
 106   else if (jcoll_list_length(list) == 1)
 107     return jcoll_list_head(list);
 108
 109   else
 110     {
 111       int i = 0,
 112         length = jcoll_list_length(list) + 1;
 113       stamp sts[length];
 114       jcoll_join result;
 115
 116       jcoll_list_scanner scan;
 117       jcoll temp;
 118
 119       sts[i++] = j_join;
 120
 121       jcoll_list_scan(list,&scan);
 122       while (jcoll_list_next(&scan,&temp))
 123         {
 124           stamp st = temp ? temp->st : 0;
 125           sts[i++] = st;
 126         }
 127       qsort(&sts[1],length-1,sizeof(int),ptr_cmp);
 128
 129       if ( NULL == (result = (jcoll_join)term_hash_find(d->hash,sts,length)) )
 130         {
 131           result = ralloc(d->r,struct jcoll_join);
 132
 133           result->type = j_join;
 134           result->st = stamp_fresh();
 135           result->joins = list;
 136           result->cache = new_gen_e_list(d->r);
 137           term_hash_insert(d->hash,(gen_e)result,sts,length);
 138         }
 139       return (jcoll)result;
 140     }
 141
 142 }
 143
 144 /*
 145   Hash chains
 146  */
 147 jcoll jcoll_create_chain(jcoll_dict d, gen_e_list elems)
 148 {
 149   int i = 0,
 150     length = gen_e_list_length(elems) + 1;
 151   stamp sts[length];
 152   gen_e_list_scanner scan;
 153   gen_e temp;
 154   jcoll_chain result;
 155
 156   sts[i++] = j_chain;
 157
 158   gen_e_list_scan(elems,&scan);
 159   while (gen_e_list_next(&scan,&temp))
 160     {
 161       sts[i++] = d->get_stamp(temp);
 162     }
 163   qsort(&sts[1],length-1,sizeof(int),ptr_cmp); /* FIX, first pos should always be chain */
 164
 165   if ( NULL == (result = (jcoll_chain)term_hash_find(d->hash,sts,length)) )
 166     {
 167       result = ralloc(d->r,struct jcoll_chain);
 168       result->type = j_chain;
 169       result->st = stamp_fresh();
 170       result->entries = elems;
 171       term_hash_insert(d->hash,(gen_e)result,sts,
 172                        length);
 173     }
 174   return (jcoll)result;
 175 }
 176
 177 typedef void (*japp_fn_ptr) (void *, void *);
 178
 179 static void app_aux(hash_set h, get_stamp_fn_ptr get_stamp, japp_fn_ptr app,
 180                     jcoll j, void *data)
 181 {
 182   if (! j)
 183     return;
 184
 185   switch(j->type)
 186     {
 187     case j_single:
 188       {
 189         jcoll_single single = (jcoll_single) j;
 190
 191         if (! hs_member(h,get_stamp(single->entry)) )
 192             app(single->entry, data);
 193       }
 194       break;
 195     case j_chain:
 196       {
 197         jcoll_chain chain = (jcoll_chain) j;
 198
 199         if (! hs_member(h,chain->st) )
 200           {
 201             gen_e_list_scanner scan;
 202             gen_e entry;
 203
 204             gen_e_list_scan(chain->entries, &scan);
 205             while (gen_e_list_next(&scan, &entry))
 206               {
 207                 if (! hs_member(h, get_stamp(entry)) )
 208                   app(entry, data);
 209               }
 210
 211           }
 212
 213       }
 214       break;
 215     case j_join:
 216       {
 217         jcoll_join join = (jcoll_join) j;
 218
 219         if (! hs_member(h, join->st))
 220           {
 221             if (! gen_e_list_empty(join->cache))
 222               {
 223                   gen_e_list_scanner scan;
 224                   gen_e entry;
 225
 226                   gen_e_list_scan(join->cache, &scan);
 227                   while (gen_e_list_next(&scan, &entry))
 228                     {
 229                       if (! hs_member(h, get_stamp(entry)) )
 230                         app(entry, data);
 231                     }
 232               }
 233             else
 234               {
 235                 jcoll_list_scanner scan;
 236                 jcoll temp;
 237
 238                 jcoll_list_scan(join->joins, &scan);
 239                 while (jcoll_list_next(&scan,&temp))
 240                   {
 241                     app_aux(h,get_stamp,app,temp, data);
 242                   }
 243
 244               }
 245           }
 246
 247       }
 248       break;
 249     }
 250
 251 }
 252
 253 static void jcoll_app(jcoll_dict d, japp_fn_ptr app, jcoll j, void *data) deletes
 254 {
 255   region scratch_rgn = newregion();
 256   hash_set hash = hs_create(scratch_rgn);
 257   app_aux(hash,d->get_stamp, app, j, data);
 258   hs_delete(hash);
 259   deleteregion(scratch_rgn);
 260 }
 261   static void jcoll_accum(void *e, void *accum)
 262     {
 263       gen_e_list_cons((gen_e) e, (gen_e_list) accum);
 264     }
 265
 266 gen_e_list jcoll_flatten(jcoll_dict d, jcoll j) deletes
 267 {
 268
 269   gen_e_list accum = NULL;
 270
 271
 272   if (j == NULL)
 273     return new_gen_e_list(d->r);
 274
 275   switch (j->type)
 276     {
 277     case j_single:
 278       {
 279         jcoll_single single = (jcoll_single)j;
 280
 281         accum = new_gen_e_list(d->r);
 282         gen_e_list_cons(single->entry,accum);
 283       }
 284       break;
 285     case j_chain:
 286       {
 287         jcoll_chain chain = (jcoll_chain)j;
 288         /* accum = gen_e_list_copy(r,chain->entries); */
 289         accum = chain->entries;
 290       }
 291       break;
 292     case j_join:
 293       {
 294         jcoll_join join = (jcoll_join)j;
 295
 296         if (! gen_e_list_empty(join->cache))
 297           return join->cache;
 298         else
 299           {
 300             accum = new_gen_e_list(d->r);
 301             jcoll_app(d, jcoll_accum,j, accum);
 302
 303             gen_e_list_append(join->cache,accum /* gen_e_list_copy(r,accum)*/);
 304           }
 305       }
 306       break;
 307     }
 308
 309   return accum;
 310 }
 311
 312 jcoll_dict jcoll_create_dict(region r,get_stamp_fn_ptr get_stamp)
 313 {
 314   jcoll_dict result = ralloc(r,struct jcoll_dict);
 315
 316   result->r = r;
 317   result->hash = make_term_hash(r);
 318   result->get_stamp = get_stamp;
 319   return result;
 320 }
 321
 322
 323 void jcoll_delete_dict(jcoll_dict d)
 324 {
 325   term_hash_delete(d->hash);
 326 }