|
From: <sv...@va...> - 2008-03-23 13:18:13
|
Author: sewardj
Date: 2008-03-23 13:17:52 +0000 (Sun, 23 Mar 2008)
New Revision: 7760
Log:
Specialise implementation of the type "WordBag" so that no dynamic
memory allocation is required in the common case where there is only
one unique value in the bag. Unfortunately this has the side effect
of making the type non-abstract.
Modified:
branches/HGDEV/helgrind/hg_main.c
branches/HGDEV/helgrind/hg_wordfm.c
branches/HGDEV/helgrind/hg_wordfm.h
Modified: branches/HGDEV/helgrind/hg_main.c
===================================================================
--- branches/HGDEV/helgrind/hg_main.c 2008-03-23 08:03:27 UTC (rev 7759)
+++ branches/HGDEV/helgrind/hg_main.c 2008-03-23 13:17:52 UTC (rev 7760)
@@ -58,9 +58,6 @@
- Fix command line ordering assumptions for --ignore-i= vs --ignore-n=
- - Specialise the heldBy field in Locks for the case where the lock
- is only held by one thread.
-
STUFF I DON'T UNDERSTAND:
Make sense of ignore-n/ignore-i. What exactly does this do?
@@ -462,20 +459,22 @@
ExeContext* appeared_at;
/* If the lock is held, place where the lock most recently made
an unlocked->locked transition. Must be sync'd with .heldBy:
- either both NULL or both non-NULL. */
+ if acquired_at is NULL then .heldBy must be empty, and vice
+ versa. */
ExeContext* acquired_at;
/* USEFUL-STATIC */
Addr guestaddr; /* Guest address of lock */
LockKind kind; /* what kind of lock this is */
/* USEFUL-DYNAMIC */
- Bool heldW;
- WordBag* heldBy; /* bag of threads that hold this lock */
- /* .heldBy is NULL: lock is unheld, and .heldW is meaningless
- but arbitrarily set to False
- .heldBy is non-NULL:
- .heldW is True: lock is w-held by threads in heldBy
- .heldW is False: lock is r-held by threads in heldBy
- Either way, heldBy may not validly be an empty Bag.
+ Bool heldW;
+ WordBag heldBy; /* bag of threads that hold this lock */
+ /* HG_(isEmptyBag)(.heldBy) == True
+ means: lock is unheld, and heldW is meaningless
+ but arbitrarily set to False
+ HG_(isEmptyBag)(.heldBy) == False
+ means:
+ lock is w-held by threads in .heldBy if .heldW is True
+ lock is r-held by threads in .heldBy if .heldW is False
for LK_nonRec, r-holdings are not allowed, and w-holdings may
only have sizeTotal(heldBy) == 1
@@ -483,7 +482,8 @@
for LK_mbRec, r-holdings are not allowed, and w-holdings may
only have sizeUnique(heldBy) == 1
- for LK_rdwr, w-holdings may only have sizeTotal(heldBy) == 1 */
+ for LK_rdwr, w-holdings may only have sizeTotal(.heldBy) == 1
+ */
}
Lock;
@@ -847,7 +847,7 @@
lock->guestaddr = guestaddr;
lock->kind = kind;
lock->heldW = False;
- lock->heldBy = NULL;
+ HG_(initBag)(&lock->heldBy, hg_zalloc, hg_free);
tl_assert(is_sane_LockN(lock));
admin_locks = lock;
return lock;
@@ -894,7 +894,7 @@
case LK_mbRec: case LK_nonRec: case LK_rdwr: break;
default: return False;
}
- if (lock->heldBy == NULL) {
+ if (HG_(isEmptyBag)(&lock->heldBy)) {
if (lock->acquired_at != NULL) return False;
/* Unheld. We arbitrarily require heldW to be False. */
return !lock->heldW;
@@ -902,18 +902,13 @@
if (lock->acquired_at == NULL) return False;
}
- /* If heldBy is non-NULL, we require it to contain at least one
- thread. */
- if (HG_(isEmptyBag)(lock->heldBy))
- return False;
-
/* Lock is either r- or w-held. */
- if (!is_sane_Bag_of_Threads(lock->heldBy))
+ if (!is_sane_Bag_of_Threads(&lock->heldBy))
return False;
if (lock->heldW) {
/* Held in write-mode */
if ((lock->kind == LK_nonRec || lock->kind == LK_rdwr)
- && !HG_(isSingletonTotalBag)(lock->heldBy))
+ && !HG_(isSingletonTotalBag)(&lock->heldBy))
return False;
} else {
/* Held in read-mode */
@@ -937,14 +932,13 @@
/* Release storage for a Lock. Also release storage in .heldBy, if
any. */
-static void del_LockN ( Lock* lk )
-{
- tl_assert(is_sane_LockN(lk));
- if (lk->heldBy)
- HG_(deleteBag)( lk->heldBy );
- VG_(memset)(lk, 0xAA, sizeof(*lk));
- hg_free(lk);
-}
+//static void del_LockN ( Lock* lk )
+//{
+// tl_assert(is_sane_LockN(lk));
+// HG_(finiBag)( &lk->heldBy );
+// VG_(memset)(lk, 0xAA, sizeof(*lk));
+// hg_free(lk);
+//}
/* Update 'lk' to reflect that 'thr' now has a write-acquisition of
it. This is done strictly: only combinations resulting from
@@ -961,38 +955,39 @@
acquired, so as to produce better lock-order error messages. */
if (lk->acquired_at == NULL) {
ThreadId tid;
- tl_assert(lk->heldBy == NULL);
+ tl_assert(HG_(isEmptyBag)(&lk->heldBy));
tid = map_threads_maybe_reverse_lookup_SLOW(thr);
lk->acquired_at
= VG_(record_ExeContext(tid, 0/*first_ip_delta*/));
} else {
- tl_assert(lk->heldBy != NULL);
+ tl_assert(!HG_(isEmptyBag)(&lk->heldBy));
}
/* end EXPOSITION only */
switch (lk->kind) {
case LK_nonRec:
case_LK_nonRec:
- tl_assert(lk->heldBy == NULL); /* can't w-lock recursively */
+ /* can't w-lock recursively */
+ tl_assert(HG_(isEmptyBag)(&lk->heldBy));
tl_assert(!lk->heldW);
- lk->heldW = True;
- lk->heldBy = HG_(newBag)( hg_zalloc, hg_free );
- HG_(addToBag)( lk->heldBy, (Word)thr );
+ lk->heldW = True;
+ HG_(addToBag)( &lk->heldBy, (Word)thr );
break;
case LK_mbRec:
- if (lk->heldBy == NULL)
+ if (HG_(isEmptyBag)(&lk->heldBy))
goto case_LK_nonRec;
/* 2nd and subsequent locking of a lock by its owner */
tl_assert(lk->heldW);
/* assert: lk is only held by one thread .. */
- tl_assert(HG_(sizeUniqueBag(lk->heldBy)) == 1);
+ tl_assert(HG_(sizeUniqueBag(&lk->heldBy)) == 1);
/* assert: .. and that thread is 'thr'. */
- tl_assert(HG_(elemBag)(lk->heldBy, (Word)thr)
- == HG_(sizeTotalBag)(lk->heldBy));
- HG_(addToBag)(lk->heldBy, (Word)thr);
+ tl_assert(HG_(elemBag)(&lk->heldBy, (Word)thr)
+ == HG_(sizeTotalBag)(&lk->heldBy));
+ HG_(addToBag)(&lk->heldBy, (Word)thr);
break;
case LK_rdwr:
- tl_assert(lk->heldBy == NULL && !lk->heldW); /* must be unheld */
+ /* must be unheld */
+ tl_assert(HG_(isEmptyBag)(&lk->heldBy) && !lk->heldW);
goto case_LK_nonRec;
default:
tl_assert(0);
@@ -1007,8 +1002,8 @@
/* can only add reader to a reader-writer lock. */
tl_assert(lk->kind == LK_rdwr);
/* lk must be free or already r-held. */
- tl_assert(lk->heldBy == NULL
- || (lk->heldBy != NULL && !lk->heldW));
+ tl_assert(HG_(isEmptyBag)(&lk->heldBy)
+ || (!HG_(isEmptyBag)(&lk->heldBy) && !lk->heldW));
stats__lockN_acquires++;
@@ -1017,21 +1012,20 @@
acquired, so as to produce better lock-order error messages. */
if (lk->acquired_at == NULL) {
ThreadId tid;
- tl_assert(lk->heldBy == NULL);
+ tl_assert(HG_(isEmptyBag)(&lk->heldBy));
tid = map_threads_maybe_reverse_lookup_SLOW(thr);
lk->acquired_at
= VG_(record_ExeContext(tid, 0/*first_ip_delta*/));
} else {
- tl_assert(lk->heldBy != NULL);
+ tl_assert(!HG_(isEmptyBag)(&lk->heldBy));
}
/* end EXPOSITION only */
- if (lk->heldBy) {
- HG_(addToBag)(lk->heldBy, (Word)thr);
+ if (!HG_(isEmptyBag)(&lk->heldBy)) {
+ HG_(addToBag)(&lk->heldBy, (Word)thr);
} else {
- lk->heldW = False;
- lk->heldBy = HG_(newBag)( hg_zalloc, hg_free );
- HG_(addToBag)( lk->heldBy, (Word)thr );
+ lk->heldW = False;
+ HG_(addToBag)( &lk->heldBy, (Word)thr );
}
tl_assert(!lk->heldW);
tl_assert(is_sane_LockN(lk));
@@ -1047,17 +1041,15 @@
tl_assert(is_sane_LockN(lk));
tl_assert(is_sane_Thread(thr));
/* lock must be held by someone */
- tl_assert(lk->heldBy);
+ tl_assert(!HG_(isEmptyBag)(&lk->heldBy));
stats__lockN_releases++;
/* Remove it from the holder set */
- b = HG_(delFromBag)(lk->heldBy, (Word)thr);
+ b = HG_(delFromBag)(&lk->heldBy, (Word)thr);
/* thr must actually have been a holder of lk */
tl_assert(b);
/* normalise */
tl_assert(lk->acquired_at);
- if (HG_(isEmptyBag)(lk->heldBy)) {
- HG_(deleteBag)(lk->heldBy);
- lk->heldBy = NULL;
+ if (HG_(isEmptyBag)(&lk->heldBy)) {
lk->heldW = False;
lk->acquired_at = NULL;
}
@@ -1067,13 +1059,13 @@
static void remove_Lock_from_locksets_of_all_owning_Threads( Lock* lk )
{
Thread* thr;
- if (!lk->heldBy) {
+ if (HG_(isEmptyBag)(&lk->heldBy)) {
tl_assert(!lk->heldW);
return;
}
/* for each thread that holds this lock do ... */
- HG_(initIterBag)( lk->heldBy );
- while (HG_(nextIterBag)( lk->heldBy, (Word*)&thr, NULL )) {
+ HG_(initIterBag)( &lk->heldBy );
+ while (HG_(nextIterBag)( &lk->heldBy, (Word*)&thr, NULL )) {
tl_assert(is_sane_Thread(thr));
tl_assert(HG_(elemWS)( univ_lsets,
thr->locksetA, (Word)lk ));
@@ -1087,7 +1079,7 @@
= HG_(delFromWS)( univ_lsets, thr->locksetW, (Word)lk );
}
}
- HG_(doneIterBag)( lk->heldBy );
+ HG_(doneIterBag)( &lk->heldBy );
}
/* --------- xxxID functions --------- */
@@ -1358,15 +1350,15 @@
space(d+3); VG_(printf)("unique %llu\n", lk->unique);
space(d+3); VG_(printf)("kind %s\n", show_LockKind(lk->kind));
space(d+3); VG_(printf)("heldW %s\n", lk->heldW ? "yes" : "no");
- space(d+3); VG_(printf)("heldBy %p", lk->heldBy);
- if (lk->heldBy) {
+ //space(d+3); VG_(printf)("heldBy %p", lk->heldBy);
+ if (!HG_(isEmptyBag)(&lk->heldBy)) {
Thread* thr;
Word count;
VG_(printf)(" { ");
- HG_(initIterBag)( lk->heldBy );
- while (HG_(nextIterBag)( lk->heldBy, (Word*)&thr, &count ))
+ HG_(initIterBag)( &lk->heldBy );
+ while (HG_(nextIterBag)( &lk->heldBy, (Word*)&thr, &count ))
VG_(printf)("%lu:%p ", count, thr);
- HG_(doneIterBag)( lk->heldBy );
+ HG_(doneIterBag)( &lk->heldBy );
VG_(printf)("}");
}
VG_(printf)("\n");
@@ -2925,10 +2917,7 @@
/* Return True iff 'thr' holds 'lk' in some mode. */
static Bool thread_is_a_holder_of_Lock ( Thread* thr, Lock* lk )
{
- if (lk->heldBy)
- return HG_(elemBag)( lk->heldBy, (Word)thr ) > 0;
- else
- return False;
+ return HG_(elemBag)( &lk->heldBy, (Word)thr ) > 0;
}
/* Sanity check Threads, as far as possible */
@@ -3008,11 +2997,11 @@
//if (is_SHVAL_NoAccess(shadow_mem_get8(lk->guestaddr))) BAD("5");
// look at all threads mentioned as holders of this lock. Ensure
// this lock is mentioned in their locksets.
- if (lk->heldBy) {
+ if (!HG_(isEmptyBag)( &lk->heldBy )) {
Thread* thr;
Word count;
- HG_(initIterBag)( lk->heldBy );
- while (HG_(nextIterBag)( lk->heldBy,
+ HG_(initIterBag)( &lk->heldBy );
+ while (HG_(nextIterBag)( &lk->heldBy,
(Word*)&thr, &count )) {
// is_sane_LockN above ensures these
tl_assert(count >= 1);
@@ -3027,7 +3016,7 @@
&& HG_(elemWS)(univ_lsets, thr->locksetW, (Word)lk))
BAD("8");
}
- HG_(doneIterBag)( lk->heldBy );
+ HG_(doneIterBag)( &lk->heldBy );
} else {
/* lock not held by anybody */
if (lk->heldW) BAD("9"); /* should be False if !heldBy */
@@ -3585,7 +3574,7 @@
VG_(printf)("\n");
}
- if (__bus_lock_Lock->heldBy) {
+ if (!HG_(isEmptyBag)(&__bus_lock_Lock->heldBy)) {
VG_(printf)("BHL is held\n");
}
@@ -3637,8 +3626,8 @@
goto done;
}
- if (UNLIKELY(__bus_lock_Lock->heldBy)
- && (is_SHVAL_New(sv_old) || is_SHVAL_R(sv_old))) {
+ if (UNLIKELY(!HG_(isEmptyBag_UNCHECKED)(&__bus_lock_Lock->heldBy)
+ && (is_SHVAL_New(sv_old) || is_SHVAL_R(sv_old)))) {
stats__msm_BHL_hack++;
// BHL is held and we are in 'Read' or 'New' state.
// User is doing something very smart with LOCK prefix.
@@ -3772,8 +3761,8 @@
goto done;
}
- if (UNLIKELY(__bus_lock_Lock->heldBy)
- && (is_SHVAL_New(sv_old) || is_SHVAL_R(sv_old))) {
+ if (UNLIKELY(!HG_(isEmptyBag_UNCHECKED)(&__bus_lock_Lock->heldBy))
+ && (is_SHVAL_New(sv_old) || is_SHVAL_R(sv_old))) {
stats__msm_BHL_hack++;
// BHL is held and we are in 'Read' or 'New' state.
// User is doing something very smart with LOCK prefix.
@@ -5694,13 +5683,13 @@
one of the threads that holds it; really we should mention
them all, but that's too much hassle. So choose one
arbitrarily. */
- if (lk->heldBy) {
- tl_assert(!HG_(isEmptyBag)(lk->heldBy));
- record_error_FreeMemLock( (Thread*)HG_(anyElementOfBag)(lk->heldBy),
- lk );
+ if (!HG_(isEmptyBag)(&lk->heldBy)) {
+ record_error_FreeMemLock(
+ (Thread*)HG_(anyElementOfBag)(&lk->heldBy),
+ lk
+ );
/* remove lock from locksets of all owning threads */
remove_Lock_from_locksets_of_all_owning_Threads( lk );
- /* Leave lk->heldBy in place; del_Lock below will free it up. */
}
}
HG_(doneIterFM)( map_locks );
@@ -5832,7 +5821,7 @@
tl_assert( is_sane_LockN(lk) );
shmem__set_mbHasLocks( lock_ga, True );
- if (lk->heldBy == NULL) {
+ if (HG_(isEmptyBag)(&lk->heldBy)) {
/* the lock isn't held. Simple. */
tl_assert(!lk->heldW);
lockN_acquire_writer( lk, thr );
@@ -5841,7 +5830,6 @@
/* So the lock is already held. If held as a r-lock then
libpthread must be buggy. */
- tl_assert(lk->heldBy);
if (!lk->heldW) {
record_error_Misc( thr, "Bug in libpthread: write lock "
"granted on rwlock which is currently rd-held");
@@ -5850,9 +5838,9 @@
/* So the lock is held in w-mode. If it's held by some other
thread, then libpthread must be buggy. */
- tl_assert(HG_(sizeUniqueBag)(lk->heldBy) == 1); /* from precondition */
+ tl_assert(HG_(sizeUniqueBag)(&lk->heldBy) == 1); /* from precondition */
- if (thr != (Thread*)HG_(anyElementOfBag)(lk->heldBy)) {
+ if (thr != (Thread*)HG_(anyElementOfBag)(&lk->heldBy)) {
record_error_Misc( thr, "Bug in libpthread: write lock "
"granted on mutex/rwlock which is currently "
"wr-held by a different thread");
@@ -5929,7 +5917,7 @@
tl_assert( is_sane_LockN(lk) );
shmem__set_mbHasLocks( lock_ga, True );
- if (lk->heldBy == NULL) {
+ if (HG_(isEmptyBag)(&lk->heldBy)) {
/* the lock isn't held. Simple. */
tl_assert(!lk->heldW);
lockN_acquire_reader( lk, thr );
@@ -5938,7 +5926,6 @@
/* So the lock is already held. If held as a w-lock then
libpthread must be buggy. */
- tl_assert(lk->heldBy);
if (lk->heldW) {
record_error_Misc( thr, "Bug in libpthread: read lock "
"granted on rwlock which is "
@@ -6017,7 +6004,7 @@
"pthread_rwlock_t* argument " );
}
- if (!lock->heldBy) {
+ if (HG_(isEmptyBag)(&lock->heldBy)) {
/* The lock is not held. This indicates a serious bug in the
client. */
tl_assert(!lock->heldW);
@@ -6029,14 +6016,14 @@
/* The lock is held. Is this thread one of the holders? If not,
report a bug in the client. */
- n = HG_(elemBag)( lock->heldBy, (Word)thr );
+ n = HG_(elemBag)( &lock->heldBy, (Word)thr );
tl_assert(n >= 0);
if (n == 0) {
/* We are not a current holder of the lock. This is a bug in
the guest, and (per POSIX pthread rules) the unlock
attempt will fail. So just complain and do nothing
else. */
- Thread* realOwner = (Thread*)HG_(anyElementOfBag)( lock->heldBy );
+ Thread* realOwner = (Thread*)HG_(anyElementOfBag)( &lock->heldBy );
tl_assert(is_sane_Thread(realOwner));
tl_assert(realOwner != thr);
tl_assert(!HG_(elemWS)( univ_lsets, thr->locksetA, (Word)lock ));
@@ -6054,8 +6041,8 @@
tl_assert(n >= 0);
if (n > 0) {
- tl_assert(lock->heldBy);
- tl_assert(n == HG_(elemBag)( lock->heldBy, (Word)thr ));
+ tl_assert(!HG_(isEmptyBag)(&lock->heldBy));
+ tl_assert(n == HG_(elemBag)( &lock->heldBy, (Word)thr ));
/* We still hold the lock. So either it's a recursive lock
or a rwlock which is currently r-held. */
tl_assert(lock->kind == LK_mbRec
@@ -6067,9 +6054,8 @@
tl_assert(!HG_(elemWS)( univ_lsets, thr->locksetW, (Word)lock ));
} else {
/* We no longer hold the lock. */
- if (lock->heldBy) {
- tl_assert(0 == HG_(elemBag)( lock->heldBy, (Word)thr ));
- }
+ tl_assert(HG_(isEmptyBag)(&lock->heldBy));
+ tl_assert(0 == HG_(elemBag)( &lock->heldBy, (Word)thr ));
/* update this thread's lockset accordingly. */
thr->locksetA
= HG_(delFromWS)( univ_lsets, thr->locksetA, (Word)lock );
@@ -6591,17 +6577,16 @@
if (lk) {
tl_assert( is_sane_LockN(lk) );
tl_assert( lk->guestaddr == (Addr)mutex );
- if (lk->heldBy) {
+ if (!HG_(isEmptyBag)(&lk->heldBy)) {
/* Basically act like we unlocked the lock */
record_error_Misc( thr, "pthread_mutex_destroy of a locked mutex" );
/* remove lock from locksets of all owning threads */
remove_Lock_from_locksets_of_all_owning_Threads( lk );
- HG_(deleteBag)( lk->heldBy );
- lk->heldBy = NULL;
+ HG_(emptyOutBag)( &lk->heldBy );
lk->heldW = False;
lk->acquired_at = NULL;
}
- tl_assert( !lk->heldBy );
+ tl_assert( HG_(isEmptyBag)(&lk->heldBy) );
tl_assert( is_sane_LockN(lk) );
}
@@ -6634,9 +6619,9 @@
if ( lk
&& isTryLock == 0
&& (lk->kind == LK_nonRec || lk->kind == LK_rdwr)
- && lk->heldBy
+ && !HG_(isEmptyBag)(&lk->heldBy)
&& lk->heldW
- && HG_(elemBag)( lk->heldBy, (Word)thr ) > 0 ) {
+ && HG_(elemBag)( &lk->heldBy, (Word)thr ) > 0 ) {
/* uh, it's a non-recursive lock and we already w-hold it, and
this is a real lock operation (not a speculative "tryLock"
kind of thing). Duh. Deadlock coming up; but at least
@@ -6891,13 +6876,13 @@
thr, "pthread_cond_{timed}wait called with mutex "
"of type pthread_rwlock_t*" );
} else
- if (lk->heldBy == NULL) {
+ if (HG_(isEmptyBag)(&lk->heldBy)) {
lk_valid = False;
record_error_Misc(
thr, "pthread_cond_{timed}wait called with un-held mutex");
} else
- if (lk->heldBy != NULL
- && HG_(elemBag)( lk->heldBy, (Word)thr ) == 0) {
+ if (!HG_(isEmptyBag)(&lk->heldBy)
+ && HG_(elemBag)( &lk->heldBy, (Word)thr ) == 0) {
lk_valid = False;
record_error_Misc(
thr, "pthread_cond_{timed}wait called with mutex "
@@ -6972,17 +6957,16 @@
if (lk) {
tl_assert( is_sane_LockN(lk) );
tl_assert( lk->guestaddr == (Addr)rwl );
- if (lk->heldBy) {
+ if (!HG_(isEmptyBag)(&lk->heldBy)) {
/* Basically act like we unlocked the lock */
record_error_Misc( thr, "pthread_rwlock_destroy of a locked mutex" );
/* remove lock from locksets of all owning threads */
remove_Lock_from_locksets_of_all_owning_Threads( lk );
- HG_(deleteBag)( lk->heldBy );
- lk->heldBy = NULL;
+ HG_(emptyOutBag)( &lk->heldBy );
lk->heldW = False;
lk->acquired_at = NULL;
}
- tl_assert( !lk->heldBy );
+ tl_assert( HG_(isEmptyBag)(&lk->heldBy) );
tl_assert( is_sane_LockN(lk) );
}
@@ -8630,10 +8614,10 @@
lkp->admin = NULL;
lkp->magic = LockP_MAGIC;
/* Forget about the bag of lock holders - don't copy that.
- Also, acquired_at should be NULL whenever heldBy is, and vice
- versa. */
+ Also, acquired_at should be NULL whenever heldBy is empty,
+ and vice versa. */
lkp->heldW = False;
- lkp->heldBy = NULL;
+ VG_(memset)( &lkp->heldBy, 0, sizeof(lkp->heldBy) );
lkp->acquired_at = NULL;
HG_(addToFM)( yaWFM, (Word)lkp, (Word)lkp );
}
Modified: branches/HGDEV/helgrind/hg_wordfm.c
===================================================================
--- branches/HGDEV/helgrind/hg_wordfm.c 2008-03-23 08:03:27 UTC (rev 7759)
+++ branches/HGDEV/helgrind/hg_wordfm.c 2008-03-23 13:17:52 UTC (rev 7760)
@@ -531,7 +531,7 @@
void (*dealloc)(void*),
Word (*kCmp)(UWord,UWord) )
{
- fm->root = 0;
+ fm->root = NULL;
fm->kCmp = kCmp;
fm->alloc_nofail = alloc_nofail;
fm->dealloc = dealloc;
@@ -644,6 +644,23 @@
return fm->root ? size_avl_nonNull( fm->root ) : 0;
}
+Bool HG_(isEmptyFM)( WordFM* fm )
+{
+ return fm->root == NULL;
+}
+
+Bool HG_(anyElementOfFM) ( WordFM* fm,
+ /*OUT*/UWord* keyP, /*OUT*/UWord* valP )
+{
+ if (!fm->root)
+ return False;
+ if (keyP)
+ *keyP = fm->root->key;
+ if (valP)
+ *valP = fm->root->val;
+ return True;
+}
+
// set up FM for iteration
void HG_(initIterFM) ( WordFM* fm )
{
@@ -783,47 +800,139 @@
//--- Implementation ---//
//------------------------------------------------------------------//
-/* A WordBag is just a WordFM, but we typedef-void it for the
- interface, to make it opaque. */
+//struct _WordBag {
+// void* (*alloc_nofail)( SizeT );
+// void (*dealloc)(void*);
+// UWord firstWord;
+// UWord firstCount;
+// WordFM* rest;
+// /* When zero, the next call to HG_(nextIterBag) gives
+// (.firstWord, .firstCount). When nonzero, such calls traverse
+// .rest. */
+// UWord iterCount;
+//};
-WordBag* HG_(newBag) ( void* (*alloc_nofail)( SizeT ),
- void (*dealloc)(void*) )
+/* Representational invariants. Either:
+
+ * bag is empty
+ firstWord == firstCount == 0
+ rest == NULL
+
+ * bag contains just one unique element
+ firstCount > 0
+ rest == NULL
+
+ * bag contains more than one unique element
+ firstCount > 0
+ rest != NULL
+
+ If rest != NULL, then
+ (1) firstWord != any .key in rest, and
+ (2) all .val in rest > 0
+*/
+
+static inline Bool is_plausible_WordBag ( WordBag* bag ) {
+ if (bag->firstWord == 0 && bag->firstCount == 0 && bag->rest == NULL)
+ return True;
+ if (bag->firstCount > 0 && bag->rest == NULL)
+ return True;
+ if (bag->firstCount > 0 && bag->rest != NULL)
+ /* really should check (1) and (2) now, but that's
+ v. expensive */
+ return True;
+ return False;
+}
+
+void HG_(initBag) ( WordBag* bag,
+ void* (*alloc_nofail)( SizeT ),
+ void (*dealloc)(void*) )
{
- return HG_(newFM)( alloc_nofail, dealloc, NULL );
+ bag->alloc_nofail = alloc_nofail;
+ bag->dealloc = dealloc;
+ bag->firstWord = 0;
+ bag->firstCount = 0;
+ bag->rest = NULL;
+ bag->iterCount = 0;
}
-void HG_(deleteBag) ( WordBag* bag )
+void HG_(emptyOutBag) ( WordBag* bag )
{
- HG_(deleteFM)( bag, NULL, NULL );
+ if (bag->rest)
+ HG_(deleteFM)( bag->rest, NULL, NULL );
+ /* Don't zero out the alloc and dealloc function pointers, since we
+ want to be able to keep on using this bag later, without having
+ to call HG_(initBag) again. */
+ bag->firstWord = 0;
+ bag->firstCount = 0;
+ bag->rest = NULL;
+ bag->iterCount = 0;
}
void HG_(addToBag)( WordBag* bag, UWord w )
{
- UWord key, count;
- if (HG_(lookupFM)(bag, &key, &count, w)) {
- tl_assert(key == w);
- tl_assert(count >= 1);
- HG_(addToFM)(bag, w, count+1);
- } else {
- HG_(addToFM)(bag, w, 1);
+ tl_assert(is_plausible_WordBag(bag));
+ /* case where the bag is completely empty */
+ if (bag->firstCount == 0) {
+ tl_assert(bag->firstWord == 0 && bag->rest == NULL);
+ bag->firstWord = w;
+ bag->firstCount = 1;
+ return;
}
+ /* there must be at least one element in it */
+ tl_assert(bag->firstCount > 0);
+ if (bag->firstWord == w) {
+ bag->firstCount++;
+ return;
+ }
+ /* it's not the Distinguished Element. Try the rest */
+ { UWord key, count;
+ if (bag->rest == NULL) {
+ bag->rest = HG_(newFM)( bag->alloc_nofail, bag->dealloc,
+ NULL/*unboxed uword cmp*/ );
+ }
+ tl_assert(bag->rest);
+ if (HG_(lookupFM)(bag->rest, &key, &count, w)) {
+ tl_assert(key == w);
+ tl_assert(count >= 1);
+ HG_(addToFM)(bag->rest, w, count+1);
+ } else {
+ HG_(addToFM)(bag->rest, w, 1);
+ }
+ }
}
UWord HG_(elemBag) ( WordBag* bag, UWord w )
{
- UWord key, count;
- if (HG_(lookupFM)( bag, &key, &count, w)) {
- tl_assert(key == w);
- tl_assert(count >= 1);
- return count;
- } else {
+ tl_assert(is_plausible_WordBag(bag));
+ if (bag->firstCount == 0) {
return 0;
}
+ if (w == bag->firstWord) {
+ return bag->firstCount;
+ }
+ if (!bag->rest) {
+ return 0;
+ }
+ { UWord key, count;
+ if (HG_(lookupFM)( bag->rest, &key, &count, w)) {
+ tl_assert(key == w);
+ tl_assert(count >= 1);
+ return count;
+ } else {
+ return 0;
+ }
+ }
}
UWord HG_(sizeUniqueBag) ( WordBag* bag )
{
- return HG_(sizeFM)( bag );
+ tl_assert(is_plausible_WordBag(bag));
+ if (bag->firstCount == 0) {
+ tl_assert(bag->firstWord == 0);
+ tl_assert(bag->rest == NULL);
+ return 0;
+ }
+ return 1 + (bag->rest ? HG_(sizeFM)( bag->rest ) : 0);
}
static UWord sizeTotalBag_wrk ( AvlNode* nd )
@@ -839,72 +948,166 @@
}
UWord HG_(sizeTotalBag)( WordBag* bag )
{
- if (((WordFM*)bag)->root)
- return sizeTotalBag_wrk(((WordFM*)bag)->root);
- else
+ UWord res;
+ tl_assert(is_plausible_WordBag(bag));
+ if (bag->firstCount == 0) {
+ tl_assert(bag->firstWord == 0);
+ tl_assert(bag->rest == NULL);
return 0;
+ }
+ res = bag->firstCount;
+ if (bag->rest && bag->rest->root)
+ res += sizeTotalBag_wrk( bag->rest->root );
+ return res;
}
Bool HG_(delFromBag)( WordBag* bag, UWord w )
{
- UWord key, count;
- if (HG_(lookupFM)(bag, &key, &count, w)) {
- tl_assert(key == w);
- tl_assert(count >= 1);
- if (count > 1) {
- HG_(addToFM)(bag, w, count-1);
+ tl_assert(is_plausible_WordBag(bag));
+
+ /* Case: bag is empty */
+ if (bag->firstCount == 0) {
+ /* empty */
+ tl_assert(bag->firstWord == 0 && bag->rest == NULL);
+ return False;
+ }
+ tl_assert(bag->firstCount > 0);
+
+ /* Case: deleting from the distinguished (word,count) */
+ if (w == bag->firstWord) {
+ Bool b;
+ UWord tmpWord, tmpCount;
+ if (bag->firstCount > 1) {
+ /* Easy. */
+ bag->firstCount--;
+ return True;
+ }
+ tl_assert(bag->firstCount == 1);
+ /* Now it gets complex. Since the distinguished (word,count)
+ pair is about to disappear, we have to get a new one from
+ 'rest'. */
+ if (bag->rest == NULL) {
+ /* Resulting bag really is completely empty. */
+ bag->firstWord = 0;
+ bag->firstCount = 0;
+ return True;
+ }
+ /* Get a new distinguished element from 'rest'. This must be
+ possible if 'rest' is non-NULL. */
+ b = HG_(anyElementOfFM)( bag->rest, &bag->firstWord, &bag->firstCount );
+ tl_assert(b);
+ tl_assert(bag->firstCount > 0);
+ b = HG_(delFromFM)( bag->rest, &tmpWord, &tmpCount, bag->firstWord );
+ tl_assert(b);
+ tl_assert(tmpWord == bag->firstWord);
+ tl_assert(tmpCount == bag->firstCount);
+ if (HG_(isEmptyFM)( bag->rest )) {
+ HG_(deleteFM)( bag->rest, NULL, NULL );
+ bag->rest = NULL;
+ }
+ return True;
+ }
+
+ /* Case: deleting from 'rest' */
+ tl_assert(bag->firstCount > 0);
+ tl_assert(bag->firstWord != w);
+ if (bag->rest) {
+ UWord key, count;
+ if (HG_(lookupFM)(bag->rest, &key, &count, w)) {
+ tl_assert(key == w);
+ tl_assert(count >= 1);
+ if (count > 1) {
+ HG_(addToFM)(bag->rest, w, count-1);
+ } else {
+ tl_assert(count == 1);
+ HG_(delFromFM)(bag->rest, NULL, NULL, w);
+ if (HG_(isEmptyFM)( bag->rest )) {
+ HG_(deleteFM)( bag->rest, NULL, NULL );
+ bag->rest = NULL;
+ }
+ }
+ return True;
} else {
- tl_assert(count == 1);
- HG_(delFromFM)(bag, NULL, NULL, w);
+ return False;
}
- return True;
} else {
return False;
}
+ /*NOTREACHED*/
+ tl_assert(0);
}
Bool HG_(isEmptyBag)( WordBag* bag )
{
- return HG_(sizeFM)(bag) == 0;
+ tl_assert(is_plausible_WordBag(bag));
+ if (bag->firstCount == 0) {
+ tl_assert(bag->firstWord == 0);
+ tl_assert(bag->rest == NULL);
+ return True;
+ } else {
+ return False;
+ }
}
Bool HG_(isSingletonTotalBag)( WordBag* bag )
{
- AvlNode* nd;
- if (HG_(sizeFM)(bag) != 1)
- return False;
- nd = ((WordFM*)bag)->root;
- tl_assert(nd);
- tl_assert(!nd->child[0]);
- tl_assert(!nd->child[1]);
- return nd->val == 1;
+ tl_assert(is_plausible_WordBag(bag));
+ return bag->firstCount > 0 && bag->rest == NULL;
}
UWord HG_(anyElementOfBag)( WordBag* bag )
{
- /* Return an arbitrarily chosen element in the bag. We might as
- well return the one at the root of the underlying AVL tree. */
- AvlNode* nd = ((WordFM*)bag)->root;
- tl_assert(nd); /* if this fails, 'bag' is empty - caller is in error. */
- tl_assert(nd->val >= 1);
- return nd->key;
+ tl_assert(is_plausible_WordBag(bag));
+ if (bag->firstCount > 0) {
+ return bag->firstWord;
+ }
+ /* The bag is empty, so the caller is in error, and we should
+ assert. */
+ tl_assert(0);
}
void HG_(initIterBag)( WordBag* bag )
{
- HG_(initIterFM)(bag);
+ tl_assert(is_plausible_WordBag(bag));
+ bag->iterCount = 0;
}
Bool HG_(nextIterBag)( WordBag* bag, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount )
{
- return HG_(nextIterFM)( bag, pVal, pCount );
+ Bool b;
+ if (bag->iterCount == 0) {
+ /* Emitting (.firstWord, .firstCount) if we have it. */
+ if (bag->firstCount == 0) {
+ /* empty */
+ return False;
+ }
+ if (pVal) *pVal = bag->firstWord;
+ if (pCount) *pCount = bag->firstCount;
+ bag->iterCount = 1;
+ return True;
+ }
+
+ /* else emitting from .rest, if present */
+ if (!bag->rest)
+ return False;
+
+ if (bag->iterCount == 1)
+ HG_(initIterFM)( bag->rest );
+
+ b = HG_(nextIterFM)( bag->rest, pVal, pCount );
+ bag->iterCount++;
+
+ return b;
}
void HG_(doneIterBag)( WordBag* bag )
{
- HG_(doneIterFM)( bag );
+ bag->iterCount = 0;
+ if (bag->rest)
+ HG_(doneIterFM)( bag->rest );
}
+
//------------------------------------------------------------------//
//--- end WordBag (unboxed words only) ---//
//--- Implementation ---//
@@ -954,6 +1157,18 @@
return n_found;
}
+void showBag ( WordBag* bag )
+{
+ UWord val, count;
+ printf("Bag{");
+ HG_(initIterBag)( bag );
+ while (HG_(nextIterBag)( bag, &val, &count )) {
+ printf(" %lux%lu ", count, val );
+ }
+ HG_(doneIterBag)( bag );
+ printf("}"); fflush(stdout);
+}
+
int main(void)
{
long i, n = 10;
@@ -1018,6 +1233,82 @@
printf("Delete the map\n");
HG_(deleteFM)(map, NULL, NULL);
printf("Ok!\n");
+
+ printf("\nBEGIN testing WordBag\n");
+ WordBag bag;
+ Bool b;
+
+ HG_(initBag)( &bag, malloc, free );
+
+ printf("operations on an empty bag\n");
+ printf(" show: " ); showBag( &bag ); printf("\n");
+ printf(" elem: %lu\n", HG_(elemBag)( &bag, 42 ));
+ printf(" isEmpty: %lu\n", (UWord) HG_(isEmptyBag)( &bag ));
+ printf(" iSTB: %lu\n", (UWord) HG_(isSingletonTotalBag)( &bag ));
+ printf(" sizeUnique: %lu\n", HG_(sizeUniqueBag)( &bag ));
+ printf(" sizeTotal: %lu\n", HG_(sizeTotalBag)( &bag ));
+ printf(" delFrom: %lu\n", (UWord)HG_(delFromBag)( &bag, 42 ));
+
+ assert( HG_(isEmptyBag)( &bag ));
+ printf("\noperations on bag { 41 }\n");
+ HG_(addToBag)( &bag, 41 );
+ printf(" show: " ); showBag( &bag ); printf("\n");
+ printf(" elem: %lu\n", HG_(elemBag)( &bag, 42 ));
+ printf(" isEmpty: %lu\n", (UWord) HG_(isEmptyBag)( &bag ));
+ printf(" iSTB: %lu\n", (UWord) HG_(isSingletonTotalBag)( &bag ));
+ printf(" sizeUnique: %lu\n", HG_(sizeUniqueBag)( &bag ));
+ printf(" sizeTotal: %lu\n", HG_(sizeTotalBag)( &bag ));
+ printf(" delFrom: %lu\n", (UWord)HG_(delFromBag)( &bag, 42 ));
+
+ b = HG_(delFromBag)( &bag, 41 ); assert(b);
+
+ printf("\noperations on bag { 41,41 }\n");
+ HG_(addToBag)( &bag, 41 );
+ HG_(addToBag)( &bag, 41 );
+ printf(" show: " ); showBag( &bag ); printf("\n");
+ printf(" elem: %lu\n", HG_(elemBag)( &bag, 42 ));
+ printf(" isEmpty: %lu\n", (UWord) HG_(isEmptyBag)( &bag ));
+ printf(" iSTB: %lu\n", (UWord) HG_(isSingletonTotalBag)( &bag ));
+ printf(" sizeUnique: %lu\n", HG_(sizeUniqueBag)( &bag ));
+ printf(" sizeTotal: %lu\n", HG_(sizeTotalBag)( &bag ));
+ printf(" delFrom: %lu\n", (UWord)HG_(delFromBag)( &bag, 42 ));
+
+ printf("\noperations on bag { 41,41, 42, 43,43 }\n");
+ HG_(addToBag)( &bag, 42 );
+ HG_(addToBag)( &bag, 43 );
+ HG_(addToBag)( &bag, 43 );
+ printf(" show: " ); showBag( &bag ); printf("\n");
+ printf(" elem: %lu\n", HG_(elemBag)( &bag, 42 ));
+ printf(" isEmpty: %lu\n", (UWord) HG_(isEmptyBag)( &bag ));
+ printf(" iSTB: %lu\n", (UWord) HG_(isSingletonTotalBag)( &bag ));
+ printf(" sizeUnique: %lu\n", HG_(sizeUniqueBag)( &bag ));
+ printf(" sizeTotal: %lu\n", HG_(sizeTotalBag)( &bag ));
+ printf(" delFrom: %lu\n", (UWord)HG_(delFromBag)( &bag, 42 ));
+
+ b = HG_(delFromBag)( &bag, 41 ); assert(b);
+ printf(" after del of 41: " ); showBag( &bag ); printf("\n");
+ b = HG_(delFromBag)( &bag, 41 ); assert(b);
+ printf(" after del of 41: " ); showBag( &bag ); printf("\n");
+ b = HG_(delFromBag)( &bag, 43 ); assert(b);
+ printf(" after del of 43: " ); showBag( &bag ); printf("\n");
+ b = HG_(delFromBag)( &bag, 42 ); assert(!b); // already gone
+ printf(" after del of 42: " ); showBag( &bag ); printf("\n");
+ b = HG_(delFromBag)( &bag, 43 ); assert(b);
+ printf(" after del of 43: " ); showBag( &bag ); printf("\n");
+
+ HG_(emptyOutBag)( &bag );
+
+ printf("\noperations on now empty bag\n");
+ printf(" show: " ); showBag( &bag ); printf("\n");
+ printf(" elem: %lu\n", HG_(elemBag)( &bag, 42 ));
+ printf(" isEmpty: %lu\n", (UWord) HG_(isEmptyBag)( &bag ));
+ printf(" iSTB: %lu\n", (UWord) HG_(isSingletonTotalBag)( &bag ));
+ printf(" sizeUnique: %lu\n", HG_(sizeUniqueBag)( &bag ));
+ printf(" sizeTotal: %lu\n", HG_(sizeTotalBag)( &bag ));
+ printf(" delFrom: %lu\n", (UWord)HG_(delFromBag)( &bag, 42 ));
+
+ printf("\nEND testing WordBag\n");
+
return 0;
}
Modified: branches/HGDEV/helgrind/hg_wordfm.h
===================================================================
--- branches/HGDEV/helgrind/hg_wordfm.h 2008-03-23 08:03:27 UTC (rev 7759)
+++ branches/HGDEV/helgrind/hg_wordfm.h 2008-03-23 13:17:52 UTC (rev 7760)
@@ -97,9 +97,17 @@
Bool HG_(lookupFM) ( WordFM* fm,
/*OUT*/UWord* keyP, /*OUT*/UWord* valP, UWord key );
-// How many elements are there in fm?
+// How many elements are there in fm? Note; slow; O(# elems in the fm)
UWord HG_(sizeFM) ( WordFM* fm );
+// Is the fm empty? Fast (constant-time)
+Bool HG_(isEmptyFM)( WordFM* fm );
+
+// If fm is non-empty, return an arbitrarily chosen key/value pair
+// through *keyP/*valP, and return True. If empty return False.
+Bool HG_(anyElementOfFM) ( WordFM* fm,
+ /*OUT*/UWord* keyP, /*OUT*/UWord* valP );
+
// set up FM for iteration
void HG_(initIterFM) ( WordFM* fm );
@@ -136,15 +144,35 @@
//--- Public interface ---//
//------------------------------------------------------------------//
-typedef void WordBag; /* opaque */
+//typedef struct _WordBag WordBag; /* opaque */
-/* Allocate and initialise a WordBag */
-WordBag* HG_(newBag) ( void* (*alloc_nofail)( SizeT ),
- void (*dealloc)(void*) );
+// FIXME! find some way to turn this back into an abstract type.
+typedef
+ struct {
+ void* (*alloc_nofail)( SizeT );
+ void (*dealloc)(void*);
+ UWord firstWord;
+ UWord firstCount;
+ WordFM* rest;
+ /* When zero, the next call to HG_(nextIterBag) gives
+ (.firstWord, .firstCount). When nonzero, such calls traverse
+ .rest. */
+ UWord iterCount;
+ }
+ WordBag;
-/* Free up the Bag. */
-void HG_(deleteBag) ( WordBag* );
+/* Initialise a WordBag and make it empty. Only do this once for each
+ bag, at the start of its lifetime. */
+void HG_(initBag) ( WordBag* bag,
+ void* (*alloc_nofail)( SizeT ),
+ void (*dealloc)(void*) );
+
+/* Remove all elements from a bag, thereby making it empty, and free
+ all associated memory. This can be done as many times as required,
+ but only after the initial HG_(initBag) call. */
+void HG_(emptyOutBag) ( WordBag* bag );
+
/* Add a word. */
void HG_(addToBag)( WordBag*, UWord );
@@ -157,6 +185,11 @@
/* Is the bag empty? */
Bool HG_(isEmptyBag)( WordBag* );
+/* Is the bag empty, skipping all sanity checks? */
+static inline Bool HG_(isEmptyBag_UNCHECKED)( WordBag* bag ) {
+ return bag->firstCount == 0;
+}
+
/* Does the bag have exactly one element? */
Bool HG_(isSingletonTotalBag)( WordBag* );
@@ -164,8 +197,8 @@
UWord HG_(anyElementOfBag)( WordBag* );
/* How many different / total elements are in the bag? */
-UWord HG_(sizeUniqueBag)( WordBag* ); /* fast */
-UWord HG_(sizeTotalBag)( WordBag* ); /* warning: slow */
+UWord HG_(sizeUniqueBag)( WordBag* ); /* warning: slow */
+UWord HG_(sizeTotalBag)( WordBag* ); /* warning: very slow */
/* Iterating over the elements of a bag. */
void HG_(initIterBag)( WordBag* );
|