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
32 #include "jcollection.h"
38 static term_hash jcoll_hash;
45 get_stamp_fn_ptr get_stamp
;
55 /* generic jcoll type */
73 gen_e_list sameregion entries
;
80 jcoll_list sameregion joins
;
81 gen_e_list sameregion cache
;
84 typedef struct jcoll_single
*jcoll_single
;
85 typedef struct jcoll_chain
*jcoll_chain
;
86 typedef struct jcoll_join
*jcoll_join
;
88 DEFINE_LIST(jcoll_list
,jcoll
)
92 jcoll
jcoll_new(jcoll_dict d
, gen_e e
)
94 jcoll_single result
= ralloc(d
->r
, struct jcoll_single
);
95 result
->type
= j_single
;
96 result
->st
= stamp_fresh();
101 jcoll
jcoll_jjoin(jcoll_dict d
,jcoll_list list
)
104 if (jcoll_list_empty(list
))
106 else if (jcoll_list_length(list
) == 1)
107 return jcoll_list_head(list
);
112 length
= jcoll_list_length(list
) + 1;
116 jcoll_list_scanner scan
;
121 jcoll_list_scan(list
,&scan
);
122 while (jcoll_list_next(&scan
,&temp
))
124 stamp st
= temp
? temp
->st
: 0;
127 qsort(&sts
[1],length
-1,sizeof(int),ptr_cmp
);
129 if ( NULL
== (result
= (jcoll_join
)term_hash_find(d
->hash
,sts
,length
)) )
131 result
= ralloc(d
->r
,struct jcoll_join
);
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
);
139 return (jcoll
)result
;
147 jcoll
jcoll_create_chain(jcoll_dict d
, gen_e_list elems
)
150 length
= gen_e_list_length(elems
) + 1;
152 gen_e_list_scanner scan
;
158 gen_e_list_scan(elems
,&scan
);
159 while (gen_e_list_next(&scan
,&temp
))
161 sts
[i
++] = d
->get_stamp(temp
);
163 qsort(&sts
[1],length
-1,sizeof(int),ptr_cmp
); /* FIX, first pos should always be chain */
165 if ( NULL
== (result
= (jcoll_chain
)term_hash_find(d
->hash
,sts
,length
)) )
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
,
174 return (jcoll
)result
;
177 typedef void (*japp_fn_ptr
) (void *, void *);
179 static void app_aux(hash_set h
, get_stamp_fn_ptr get_stamp
, japp_fn_ptr app
,
189 jcoll_single single
= (jcoll_single
) j
;
191 if (! hs_member(h
,get_stamp(single
->entry
)) )
192 app(single
->entry
, data
);
197 jcoll_chain chain
= (jcoll_chain
) j
;
199 if (! hs_member(h
,chain
->st
) )
201 gen_e_list_scanner scan
;
204 gen_e_list_scan(chain
->entries
, &scan
);
205 while (gen_e_list_next(&scan
, &entry
))
207 if (! hs_member(h
, get_stamp(entry
)) )
217 jcoll_join join
= (jcoll_join
) j
;
219 if (! hs_member(h
, join
->st
))
221 if (! gen_e_list_empty(join
->cache
))
223 gen_e_list_scanner scan
;
226 gen_e_list_scan(join
->cache
, &scan
);
227 while (gen_e_list_next(&scan
, &entry
))
229 if (! hs_member(h
, get_stamp(entry
)) )
235 jcoll_list_scanner scan
;
238 jcoll_list_scan(join
->joins
, &scan
);
239 while (jcoll_list_next(&scan
,&temp
))
241 app_aux(h
,get_stamp
,app
,temp
, data
);
253 static void jcoll_app(jcoll_dict d
, japp_fn_ptr app
, jcoll j
, void *data
) deletes
255 region scratch_rgn
= newregion();
256 hash_set hash
= hs_create(scratch_rgn
);
257 app_aux(hash
,d
->get_stamp
, app
, j
, data
);
259 deleteregion(scratch_rgn
);
261 static void jcoll_accum(void *e
, void *accum
)
263 gen_e_list_cons((gen_e
) e
, (gen_e_list
) accum
);
266 gen_e_list
jcoll_flatten(jcoll_dict d
, jcoll j
) deletes
269 gen_e_list accum
= NULL
;
273 return new_gen_e_list(d
->r
);
279 jcoll_single single
= (jcoll_single
)j
;
281 accum
= new_gen_e_list(d
->r
);
282 gen_e_list_cons(single
->entry
,accum
);
287 jcoll_chain chain
= (jcoll_chain
)j
;
288 /* accum = gen_e_list_copy(r,chain->entries); */
289 accum
= chain
->entries
;
294 jcoll_join join
= (jcoll_join
)j
;
296 if (! gen_e_list_empty(join
->cache
))
300 accum
= new_gen_e_list(d
->r
);
301 jcoll_app(d
, jcoll_accum
,j
, accum
);
303 gen_e_list_append(join
->cache
,accum
/* gen_e_list_copy(r,accum)*/);
312 jcoll_dict
jcoll_create_dict(region r
,get_stamp_fn_ptr get_stamp
)
314 jcoll_dict result
= ralloc(r
,struct jcoll_dict
);
317 result
->hash
= make_term_hash(r
);
318 result
->get_stamp
= get_stamp
;
323 void jcoll_delete_dict(jcoll_dict d
)
325 term_hash_delete(d
->hash
);