|
From: <sv...@va...> - 2008-11-13 13:17:13
|
Author: sewardj
Date: 2008-11-13 13:17:06 +0000 (Thu, 13 Nov 2008)
New Revision: 8765
Log:
Add performance comments to VG_(sizeFM), and add new method
VG_(isEmptyFM), currently commented out.
Modified:
trunk/coregrind/m_wordfm.c
trunk/include/pub_tool_wordfm.h
Modified: trunk/coregrind/m_wordfm.c
===================================================================
--- trunk/coregrind/m_wordfm.c 2008-11-13 13:14:00 UTC (rev 8764)
+++ trunk/coregrind/m_wordfm.c 2008-11-13 13:17:06 UTC (rev 8765)
@@ -683,12 +683,19 @@
key, fm->kCmp );
}
+// See comment in pub_tool_wordfm.h for performance warning
UWord VG_(sizeFM) ( WordFM* fm )
{
// Hmm, this is a bad way to do this
return fm->root ? size_avl_nonNull( fm->root ) : 0;
}
+// NB UNTESTED! TEST BEFORE USE!
+//Bool VG_(isEmptyFM)( WordFM* fm )
+//{
+// return fm->root ? False : True;
+//}
+
// set up FM for iteration
void VG_(initIterFM) ( WordFM* fm )
{
Modified: trunk/include/pub_tool_wordfm.h
===================================================================
--- trunk/include/pub_tool_wordfm.h 2008-11-13 13:14:00 UTC (rev 8764)
+++ trunk/include/pub_tool_wordfm.h 2008-11-13 13:17:06 UTC (rev 8765)
@@ -122,9 +122,16 @@
UWord maxKey, UWord maxVal,
UWord key );
-// How many elements are there in fm?
+// How many elements are there in fm? NOTE: dangerous in the
+// sense that this is not an O(1) operation but rather O(N),
+// since it involves walking the whole tree.
UWord VG_(sizeFM) ( WordFM* fm );
+// Is fm empty? This at least is an O(1) operation.
+// Code is present in m_wordfm.c but commented out due to no
+// current usage. Un-comment (and TEST IT) if required.
+//Bool VG_(isEmptyFM)( WordFM* fm );
+
// set up FM for iteration
void VG_(initIterFM) ( WordFM* fm );
|