Lines Matching refs:wsu
47 // define to 1 to have (a lot of) debugging of add/re-use/die WSU entries.
186 static WordVec* new_WV_of_size ( WordSetU* wsu, UWord sz )
190 wv = wsu->alloc( wsu->cc, sizeof(WordVec) );
191 wv->owner = wsu;
195 wv->words = wsu->alloc( wsu->cc, (SizeT)sz * sizeof(UWord) );
239 static void ensure_ix2vec_space ( WordSetU* wsu )
243 tl_assert(wsu->ix2vec_used <= wsu->ix2vec_size);
244 if (wsu->ix2vec_used < wsu->ix2vec_size)
246 new_sz = 2 * wsu->ix2vec_size;
248 new_vec = wsu->alloc( wsu->cc, new_sz * sizeof(WordVec*) );
250 for (i = 0; i < wsu->ix2vec_size; i++)
251 new_vec[i] = wsu->ix2vec[i];
252 if (wsu->ix2vec)
253 wsu->dealloc(wsu->ix2vec);
254 wsu->ix2vec = new_vec;
255 wsu->ix2vec_size = new_sz;
260 static inline Bool is_dead ( WordSetU* wsu, WordVec* wv )
265 return (WordVec**)wv >= &(wsu->ix2vec[1])
266 && (WordVec**)wv < &(wsu->ix2vec[wsu->ix2vec_size]);
272 static WordVec* do_ix2vec ( WordSetU* wsu, WordSet ws )
275 tl_assert(wsu->ix2vec_used <= wsu->ix2vec_size);
276 if (wsu->ix2vec_used > 0)
277 tl_assert(wsu->ix2vec);
279 that does not come from the 'wsu' universe. */
280 tl_assert(ws < wsu->ix2vec_used); /* XXX */
281 wv = wsu->ix2vec[ws];
282 /* Make absolutely sure that 'ws' is a non dead member of 'wsu'. */
284 tl_assert(!is_dead(wsu,wv));
285 tl_assert(wv->owner == wsu); /* YYY */
290 static WordVec* do_ix2vec_with_dead ( WordSetU* wsu, WordSet ws )
293 tl_assert(wsu->ix2vec_used <= wsu->ix2vec_size);
294 if (wsu->ix2vec_used > 0)
295 tl_assert(wsu->ix2vec);
297 that does not come from the 'wsu' universe. */
298 tl_assert(ws < wsu->ix2vec_used); /* XXX */
299 wv = wsu->ix2vec[ws];
300 /* Make absolutely sure that 'ws' is either dead or a member of 'wsu'. */
301 if (is_dead(wsu,wv))
304 tl_assert(wv->owner == wsu); /* YYY */
308 /* See if wv is contained within wsu. If so, deallocate wv and return
312 static WordSet add_or_dealloc_WordVec( WordSetU* wsu, WordVec* wv_new )
320 tl_assert(wv_new->owner == wsu);
321 have = VG_(lookupFM)( wsu->vec2ix,
327 tl_assert(wv_old->owner == wsu);
328 tl_assert(ix_old < wsu->ix2vec_used);
329 tl_assert(wsu->ix2vec[ix_old] == wv_old);
332 } else if (wsu->ix2vec_free) {
334 tl_assert(is_dead(wsu,(WordVec*)wsu->ix2vec_free));
335 ws = wsu->ix2vec_free - &(wsu->ix2vec[0]);
336 tl_assert(wsu->ix2vec[ws] == NULL || is_dead(wsu,wsu->ix2vec[ws]));
337 wsu->ix2vec_free = (WordVec **) wsu->ix2vec[ws];
338 wsu->ix2vec[ws] = wv_new;
339 VG_(addToFM)( wsu->vec2ix, (Word)wv_new, ws );
340 if (HG_DEBUG) VG_(printf)("aodW %s re-use free %d %p\n", wsu->cc, (Int)ws, wv_new );
343 ensure_ix2vec_space( wsu );
344 tl_assert(wsu->ix2vec);
345 tl_assert(wsu->ix2vec_used < wsu->ix2vec_size);
346 wsu->ix2vec[wsu->ix2vec_used] = wv_new;
347 VG_(addToFM)( wsu->vec2ix, (Word)wv_new, (Word)wsu->ix2vec_used );
348 if (HG_DEBUG) VG_(printf)("aodW %s %d %p\n", wsu->cc, (Int)wsu->ix2vec_used, wv_new );
349 wsu->ix2vec_used++;
350 tl_assert(wsu->ix2vec_used <= wsu->ix2vec_size);
351 return (WordSet)(wsu->ix2vec_used - 1);
361 WordSetU* wsu;
364 wsu = alloc_nofail( cc, sizeof(WordSetU) );
365 VG_(memset)( wsu, 0, sizeof(WordSetU) );
366 wsu->alloc = alloc_nofail;
367 wsu->cc = cc;
368 wsu->dealloc = dealloc;
369 wsu->vec2ix = VG_(newFM)( alloc_nofail, cc,
371 wsu->ix2vec_used = 0;
372 wsu->ix2vec_size = 0;
373 wsu->ix2vec = NULL;
374 wsu->ix2vec_free = NULL;
375 WCache_INIT(wsu->cache_addTo, cacheSize);
376 WCache_INIT(wsu->cache_delFrom, cacheSize);
377 WCache_INIT(wsu->cache_intersect, cacheSize);
378 WCache_INIT(wsu->cache_minus, cacheSize);
379 empty = new_WV_of_size( wsu, 0 );
380 wsu->empty = add_or_dealloc_WordVec( wsu, empty );
382 return wsu;
385 void HG_(deleteWordSetU) ( WordSetU* wsu )
387 void (*dealloc)(void*) = wsu->dealloc;
388 tl_assert(wsu->vec2ix);
389 VG_(deleteFM)( wsu->vec2ix, delete_WV_for_FM, NULL/*val-finalizer*/ );
390 if (wsu->ix2vec)
391 dealloc(wsu->ix2vec);
392 dealloc(wsu);
395 WordSet HG_(emptyWS) ( WordSetU* wsu )
397 return wsu->empty;
400 Bool HG_(isEmptyWS) ( WordSetU* wsu, WordSet ws )
402 WordVec* wv = do_ix2vec( wsu, ws );
403 wsu->n_isEmpty++;
405 tl_assert(ws == wsu->empty);
408 tl_assert(ws != wsu->empty);
413 Bool HG_(isSingletonWS) ( WordSetU* wsu, WordSet ws, UWord w )
416 tl_assert(wsu);
417 wsu->n_isSingleton++;
418 wv = do_ix2vec( wsu, ws );
422 UWord HG_(cardinalityWS) ( WordSetU* wsu, WordSet ws )
425 tl_assert(wsu);
426 wv = do_ix2vec( wsu, ws );
431 UWord HG_(anyElementOfWS) ( WordSetU* wsu, WordSet ws )
434 tl_assert(wsu);
435 wsu->n_anyElementOf++;
436 wv = do_ix2vec( wsu, ws );
441 UWord HG_(cardinalityWSU) ( WordSetU* wsu )
443 tl_assert(wsu);
444 return wsu->ix2vec_used;
448 WordSetU* wsu, WordSet ws )
451 if (HG_DEBUG) VG_(printf)("getPayloadWS %s %d\n", wsu->cc, (Int)ws);
452 tl_assert(wsu);
453 wv = do_ix2vec( wsu, ws );
459 void HG_(dieWS) ( WordSetU* wsu, WordSet ws )
461 WordVec* wv = do_ix2vec_with_dead( wsu, ws );
465 if (HG_DEBUG) VG_(printf)("dieWS %s %d %p\n", wsu
473 wsu->n_die++;
476 wsu->ix2vec[ws] = (WordVec*) wsu->ix2vec_free;
477 wsu->ix2vec_free = &wsu->ix2vec[ws];
479 VG_(delFromFM) ( wsu->vec2ix,
489 wsu->cache_addTo.inUse = 0;
490 wsu->cache_delFrom.inUse = 0;
491 wsu->cache_intersect.inUse = 0;
492 wsu->cache_minus.inUse = 0;
495 Bool HG_(plausibleWS) ( WordSetU* wsu, WordSet ws )
497 if (wsu == NULL) return False;
498 if (ws < 0 || ws >= wsu->ix2vec_used)
503 Bool HG_(saneWS_SLOW) ( WordSetU* wsu, WordSet ws )
507 if (wsu == NULL) return False;
508 if (ws < 0 || ws >= wsu->ix2vec_used)
510 wv = do_ix2vec( wsu, ws );
512 if (wv->owner != wsu) return False;
523 Bool HG_(elemWS) ( WordSetU* wsu, WordSet ws, UWord w )
526 WordVec* wv = do_ix2vec( wsu, ws );
527 wsu->n_elem++;
535 WordSet HG_(doubletonWS) ( WordSetU* wsu, UWord w1, UWord w2 )
538 wsu->n_doubleton++;
540 wv = new_WV_of_size(wsu, 1);
544 wv = new_WV_of_size(wsu, 2);
550 wv = new_WV_of_size(wsu, 2);
554 return add_or_dealloc_WordVec( wsu, wv );
557 WordSet HG_(singletonWS) ( WordSetU* wsu, UWord w )
559 return HG_(doubletonWS)( wsu, w, w );
562 WordSet HG_(isSubsetOf) ( WordSetU* wsu, WordSet small, WordSet big )
564 wsu->n_isSubsetOf++;
565 return small == HG_(intersectWS)( wsu, small, big );
568 void HG_(ppWS) ( WordSetU* wsu, WordSet ws )
572 tl_assert(wsu);
573 wv = do_ix2vec( wsu, ws );
583 void HG_(ppWSUstats) ( WordSetU* wsu, HChar* name )
587 wsu->n_add, wsu->n_add_uncached);
589 wsu->n_del, wsu->n_del_uncached);
590 VG_(printf)(" union %10lu\n", wsu->n_union);
593 wsu->n_intersect, wsu->n_intersect_uncached);
595 wsu->n_minus, wsu->n_minus_uncached);
596 VG_(printf)(" elem %10lu\n", wsu->n_elem);
597 VG_(printf)(" doubleton %10lu\n", wsu->n_doubleton);
598 VG_(printf)(" isEmpty %10lu\n", wsu->n_isEmpty);
599 VG_(printf)(" isSingleton %10lu\n", wsu->n_isSingleton);
600 VG_(printf)(" anyElementOf %10lu\n", wsu->n_anyElementOf);
601 VG_(printf)(" isSubsetOf %10lu\n", wsu->n_isSubsetOf);
602 VG_(printf)(" dieWS %10lu\n", wsu->n_die);
605 WordSet HG_(addToWS) ( WordSetU* wsu, WordSet ws, UWord w )
612 wsu->n_add++;
613 WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_addTo, ws, w);
614 wsu->n_add_uncached++;
617 wv = do_ix2vec( wsu, ws );
625 wv_new = new_WV_of_size( wsu, wv->size + 1 );
638 result = add_or_dealloc_WordVec( wsu, wv_new );
642 WCache_UPDATE(wsu->cache_addTo, ws, w, result);
646 WordSet HG_(delFromWS) ( WordSetU* wsu, WordSet ws, UWord w )
651 WordVec* wv = do_ix2vec( wsu, ws );
653 wsu->n_del++;
657 tl_assert(ws == wsu->empty);
661 WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_delFrom, ws, w);
662 wsu->n_del_uncached++;
678 wv_new = new_WV_of_size( wsu, wv->size - 1 );
687 result = add_or_dealloc_WordVec( wsu, wv_new );
689 tl_assert(result == wsu->empty);
693 WCache_UPDATE(wsu->cache_delFrom, ws, w, result);
697 WordSet HG_(unionWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 )
701 WordVec* wv1 = do_ix2vec( wsu, ws1 );
702 WordVec* wv2 = do_ix2vec( wsu, ws2 );
703 wsu->n_union++;
730 wv_new = new_WV_of_size( wsu, sz );
764 return add_or_dealloc_WordVec( wsu, wv_new );
767 WordSet HG_(intersectWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 )
775 wsu->n_intersect++;
788 WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_intersect, ws1, ws2);
789 wsu->n_intersect_uncached++;
791 wv1 = do_ix2vec( wsu, ws1 );
792 wv2 = do_ix2vec( wsu, ws2 );
813 wv_new = new_WV_of_size( wsu, sz );
837 ws_new = add_or_dealloc_WordVec( wsu, wv_new );
839 tl_assert(ws_new == wsu->empty);
843 WCache_UPDATE(wsu->cache_intersect, ws1, ws2, ws_new);
848 WordSet HG_(minusWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 )
856 wsu->n_minus++;
857 WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_minus, ws1, ws2);
858 wsu->n_minus_uncached++;
860 wv1 = do_ix2vec( wsu, ws1 );
861 wv2 = do_ix2vec( wsu, ws2 );
885 wv_new = new_WV_of_size( wsu, sz );
913 ws_new = add_or_dealloc_WordVec( wsu, wv_new );
915 tl_assert(ws_new == wsu->empty);
919 WCache_UPDATE(wsu->cache_minus, ws1, ws2, ws_new);
925 void show_WS ( WordSetU* wsu, WordSet ws )
928 WordVec* wv = do_ix2vec( wsu, ws );
