|
From: <sv...@va...> - 2009-07-24 08:11:51
|
Author: sewardj
Date: 2009-07-24 09:11:39 +0100 (Fri, 24 Jul 2009)
New Revision: 10583
Log:
New methods in WordXA:
* lookupXA_UNSAFE -- binary search in array without being forced
to sortXA it first -- dangerous because if the array isn't in order
then the lookup can loop forever
* dropHeadXA -- drop the first N elements (kinda like dropTailXA, but
unfortunately O(N) not O(1)), so that xarrays can be used to
implement FIFOs, after a fashion.
Modified:
trunk/coregrind/m_xarray.c
Modified: trunk/coregrind/m_xarray.c
===================================================================
--- trunk/coregrind/m_xarray.c 2009-07-24 07:54:51 UTC (rev 10582)
+++ trunk/coregrind/m_xarray.c 2009-07-24 08:11:39 UTC (rev 10583)
@@ -225,14 +225,14 @@
xa->sorted = True;
}
-Bool VG_(lookupXA) ( XArray* xao, void* key, Word* first, Word* last )
+Bool VG_(lookupXA_UNSAFE) ( XArray* xao, void* key,
+ /*OUT*/Word* first, /*OUT*/Word* last,
+ Int(*cmpFn)(void*,void*) )
{
Word lo, mid, hi, cres;
void* midv;
struct _XArray* xa = (struct _XArray*)xao;
vg_assert(xa);
- vg_assert(xa->cmpFn);
- vg_assert(xa->sorted);
vg_assert(first);
vg_assert(last);
lo = 0;
@@ -242,23 +242,33 @@
if (lo > hi) return False; /* not found */
mid = (lo + hi) / 2;
midv = VG_(indexXA)( xa, mid );
- cres = xa->cmpFn( key, midv );
+ cres = cmpFn( key, midv );
if (cres < 0) { hi = mid-1; continue; }
if (cres > 0) { lo = mid+1; continue; }
/* Found it, at mid. See how far we can expand this. */
- vg_assert(xa->cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0);
- vg_assert(xa->cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0);
+ vg_assert(cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0);
+ vg_assert(cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0);
*first = *last = mid;
while (*first > 0
- && 0 == xa->cmpFn( key, VG_(indexXA)(xa, (*first)-1)))
+ && 0 == cmpFn( key, VG_(indexXA)(xa, (*first)-1)))
(*first)--;
while (*last < xa->usedsizeE-1
- && 0 == xa->cmpFn( key, VG_(indexXA)(xa, (*last)+1)))
+ && 0 == cmpFn( key, VG_(indexXA)(xa, (*last)+1)))
(*last)++;
return True;
}
}
+Bool VG_(lookupXA) ( XArray* xao, void* key,
+ /*OUT*/Word* first, /*OUT*/Word* last )
+{
+ struct _XArray* xa = (struct _XArray*)xao;
+ vg_assert(xa);
+ vg_assert(xa->cmpFn);
+ vg_assert(xa->sorted);
+ return VG_(lookupXA_UNSAFE)(xao, key, first, last, xa->cmpFn);
+}
+
Word VG_(sizeXA) ( XArray* xao )
{
struct _XArray* xa = (struct _XArray*)xao;
@@ -275,7 +285,28 @@
xa->usedsizeE -= n;
}
+void VG_(dropHeadXA) ( XArray* xao, Word n )
+{
+ struct _XArray* xa = (struct _XArray*)xao;
+ vg_assert(xa);
+ vg_assert(n >= 0);
+ vg_assert(n <= xa->usedsizeE);
+ if (n == 0) {
+ return;
+ }
+ if (n == xa->usedsizeE) {
+ xa->usedsizeE = 0;
+ return;
+ }
+ vg_assert(n > 0);
+ vg_assert(xa->usedsizeE - n > 0);
+ VG_(memcpy)( (char*)xa->arr,
+ ((char*)xa->arr) + n * xa->elemSzB,
+ (xa->usedsizeE - n) * xa->elemSzB );
+ xa->usedsizeE -= n;
+}
+
/*--------------------------------------------------------------------*/
/*--- end m_xarray.c ---*/
/*--------------------------------------------------------------------*/
|