Modularised vg_skiplist.c as m_skiplist.c.
git-svn-id: svn://svn.valgrind.org/valgrind/trunk@3671 a5019735-40e9-0310-863c-91ae7b9d1cf9
diff --git a/coregrind/Makefile.am b/coregrind/Makefile.am
index f7dd59b..c430bfa 100644
--- a/coregrind/Makefile.am
+++ b/coregrind/Makefile.am
@@ -45,6 +45,7 @@
pub_core_mallocfree.h \
pub_core_replacemalloc.h\
pub_core_sigframe.h \
+ pub_core_skiplist.h \
pub_core_stacktrace.h \
pub_core_syscalls.h \
pub_core_tooliface.h \
@@ -71,6 +72,7 @@
m_errormgr.c \
m_execontext.c \
m_mallocfree.c \
+ m_skiplist.c \
m_stacktrace.c \
m_tooliface.c \
ume.c \
@@ -88,7 +90,6 @@
vg_redir.c \
vg_dwarf.c \
vg_stabs.c \
- vg_skiplist.c \
vg_symtypes.c \
vg_translate.c \
vg_transtab.c
diff --git a/coregrind/vg_skiplist.c b/coregrind/m_skiplist.c
similarity index 96%
rename from coregrind/vg_skiplist.c
rename to coregrind/m_skiplist.c
index 02d345c..281e937 100644
--- a/coregrind/vg_skiplist.c
+++ b/coregrind/m_skiplist.c
@@ -1,4 +1,8 @@
+/*--------------------------------------------------------------------*/
+/*--- A skiplist implementation. m_skiplist.c ---*/
+/*--------------------------------------------------------------------*/
+
/*
This file is part of Valgrind, a dynamic binary instrumentation
framework.
@@ -83,6 +87,7 @@
*/
#include "core.h"
+#include "pub_core_skiplist.h"
#include <stdlib.h>
@@ -498,4 +503,7 @@
return VG_(strcmp)(a, b);
}
+/*--------------------------------------------------------------------*/
+/*--- end ---*/
+/*--------------------------------------------------------------------*/
diff --git a/coregrind/pub_core_skiplist.h b/coregrind/pub_core_skiplist.h
new file mode 100644
index 0000000..5787318
--- /dev/null
+++ b/coregrind/pub_core_skiplist.h
@@ -0,0 +1,47 @@
+
+/*--------------------------------------------------------------------*/
+/*--- A skip-list implemenation. pub_core_skiplist.h ---*/
+/*--------------------------------------------------------------------*/
+
+/*
+ This file is part of Valgrind, a dynamic binary instrumentation
+ framework.
+
+ Copyright (C) 2000-2005 Julian Seward
+ jseward@acm.org
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2 of the
+ License, or (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ The GNU General Public License is contained in the file COPYING.
+*/
+
+#ifndef __PUB_CORE_SKIPLIST_H
+#define __PUB_CORE_SKIPLIST_H
+
+//--------------------------------------------------------------------
+// PURPOSE: A generic data structure with amortised log(n) operations.
+//--------------------------------------------------------------------
+
+#include "pub_tool_skiplist.h"
+
+// No core-only exports; everything in this module is visible to both
+// the core and tools.
+
+#endif // __PUB_CORE_SKIPLIST_H
+
+/*--------------------------------------------------------------------*/
+/*--- end ---*/
+/*--------------------------------------------------------------------*/
diff --git a/coregrind/vg_redir.c b/coregrind/vg_redir.c
index af6c914..6794e84 100644
--- a/coregrind/vg_redir.c
+++ b/coregrind/vg_redir.c
@@ -33,6 +33,7 @@
#include "vg_symtab2.h"
#include "pub_core_aspacemgr.h"
+#include "pub_core_skiplist.h"
/*------------------------------------------------------------*/
/*--- General purpose redirection. ---*/
diff --git a/include/Makefile.am b/include/Makefile.am
index c346bbf..622e8fb 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -16,6 +16,7 @@
pub_tool_execontext.h \
pub_tool_mallocfree.h \
pub_tool_replacemalloc.h\
+ pub_tool_skiplist.h \
pub_tool_stacktrace.h \
pub_tool_tooliface.h \
valgrind.h
diff --git a/include/pub_tool_skiplist.h b/include/pub_tool_skiplist.h
new file mode 100644
index 0000000..d597fb0
--- /dev/null
+++ b/include/pub_tool_skiplist.h
@@ -0,0 +1,120 @@
+
+/*--------------------------------------------------------------------*/
+/*--- SkipList: a skiplist implementaiton. pub_tool_skiplist.h ---*/
+/*--------------------------------------------------------------------*/
+
+/*
+ This file is part of Valgrind, a dynamic binary instrumentation
+ framework.
+
+ Copyright (C) 2000-2005 Julian Seward
+ jseward@acm.org
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2 of the
+ License, or (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ The GNU General Public License is contained in the file COPYING.
+*/
+
+#ifndef __PUB_TOOL_SKIPLIST_H
+#define __PUB_TOOL_SKIPLIST_H
+
+/*
+ The idea here is that the skiplist puts its per-element data at the
+ end of the structure. When you initialize the skiplist, you tell
+ it what structure your list elements are going to be. Then you
+ should allocate them with VG_(SkipNode_Alloc), which will allocate
+ enough memory for the extra bits.
+ */
+
+typedef struct _SkipList SkipList;
+typedef struct _SkipNode SkipNode;
+
+typedef Int (*SkipCmp_t)(const void *key1, const void *key2);
+
+struct _SkipList {
+ const Short arena; // allocation arena
+ const UShort size; // structure size (excluding SkipNode)
+ const UShort keyoff; // key offset
+ const SkipCmp_t cmp; // compare two keys
+ Char * (*strkey)(void *); // stringify a key (for debugging)
+ SkipNode *head; // list head
+};
+
+/* Use this macro to initialize your skiplist head. The arguments are pretty self explanitory:
+ _type is the type of your element structure
+ _key is the field within that type which you want to use as the key
+ _cmp is the comparison function for keys - it gets two typeof(_key) pointers as args
+ _strkey is a function which can return a string of your key - it's only used for debugging
+ _arena is the arena to use for allocation - -1 is the default
+ */
+#define VG_SKIPLIST_INIT(_type, _key, _cmp, _strkey, _arena) \
+ { \
+ .arena = _arena, \
+ .size = sizeof(_type), \
+ .keyoff = offsetof(_type, _key), \
+ .cmp = _cmp, \
+ .strkey = _strkey, \
+ .head = NULL, \
+ }
+
+/* List operations:
+ SkipList_Find_* search a list. The 3 variants are:
+ Before: returns a node which is <= key, or NULL if none
+ Exact: returns a node which is == key, or NULL if none
+ After: returns a node which is >= key, or NULL if none
+ SkipList_Insert inserts a new element into the list. Duplicates are
+ forbidden. The element must have been created with SkipList_Alloc!
+ SkipList_Remove removes an element from the list and returns it. It
+ doesn't free the memory.
+*/
+extern void *VG_(SkipList_Find_Before) (const SkipList *l, void *key);
+extern void *VG_(SkipList_Find_Exact) (const SkipList *l, void *key);
+extern void *VG_(SkipList_Find_After) (const SkipList *l, void *key);
+extern void VG_(SkipList_Insert) ( SkipList *l, void *data);
+extern void *VG_(SkipList_Remove) ( SkipList *l, void *key);
+
+/* Some useful standard comparisons */
+extern Int VG_(cmp_Addr) (const void *a, const void *b);
+extern Int VG_(cmp_Int) (const void *a, const void *b);
+extern Int VG_(cmp_UInt) (const void *a, const void *b);
+extern Int VG_(cmp_string)(const void *a, const void *b);
+
+/* Node (element) operations:
+ SkipNode_Alloc: allocate memory for a new element on the list. Must be
+ used before an element can be inserted! Returns NULL if not enough
+ memory.
+ SkipNode_Free: free memory allocated above
+ SkipNode_First: return the first element on the list
+ SkipNode_Next: return the next element after "data" on the list -
+ NULL for none
+
+ You can iterate through a SkipList like this:
+
+ for(x = VG_(SkipNode_First)(&list); // or SkipList_Find
+ x != NULL;
+ x = VG_(SkipNode_Next)(&list, x)) { ... }
+*/
+extern void *VG_(SkipNode_Alloc) (const SkipList *l);
+extern void VG_(SkipNode_Free) (const SkipList *l, void *p);
+extern void *VG_(SkipNode_First) (const SkipList *l);
+extern void *VG_(SkipNode_Next) (const SkipList *l, void *data);
+
+
+#endif // __PUB_TOOL_SKIPLIST_H
+
+/*--------------------------------------------------------------------*/
+/*--- end ---*/
+/*--------------------------------------------------------------------*/
diff --git a/include/tool.h b/include/tool.h
index 9ba5644..17634f9 100644
--- a/include/tool.h
+++ b/include/tool.h
@@ -635,92 +635,6 @@
/*====================================================================*/
-/*=== A generic skiplist ===*/
-/*====================================================================*/
-
-/*
- The idea here is that the skiplist puts its per-element data at the
- end of the structure. When you initialize the skiplist, you tell
- it what structure your list elements are going to be. Then you
- should allocate them with VG_(SkipNode_Alloc), which will allocate
- enough memory for the extra bits.
- */
-
-typedef struct _SkipList SkipList;
-typedef struct _SkipNode SkipNode;
-
-typedef Int (*SkipCmp_t)(const void *key1, const void *key2);
-
-struct _SkipList {
- const Short arena; /* allocation arena */
- const UShort size; /* structure size (not including SkipNode) */
- const UShort keyoff; /* key offset */
- const SkipCmp_t cmp; /* compare two keys */
- Char * (*strkey)(void *); /* stringify a key (for debugging) */
- SkipNode *head; /* list head */
-};
-
-/* Use this macro to initialize your skiplist head. The arguments are pretty self explanitory:
- _type is the type of your element structure
- _key is the field within that type which you want to use as the key
- _cmp is the comparison function for keys - it gets two typeof(_key) pointers as args
- _strkey is a function which can return a string of your key - it's only used for debugging
- _arena is the arena to use for allocation - -1 is the default
- */
-#define VG_SKIPLIST_INIT(_type, _key, _cmp, _strkey, _arena) \
- { \
- .arena = _arena, \
- .size = sizeof(_type), \
- .keyoff = offsetof(_type, _key), \
- .cmp = _cmp, \
- .strkey = _strkey, \
- .head = NULL, \
- }
-
-/* List operations:
- SkipList_Find_* search a list. The 3 variants are:
- Before: returns a node which is <= key, or NULL if none
- Exact: returns a node which is == key, or NULL if none
- After: returns a node which is >= key, or NULL if none
- SkipList_Insert inserts a new element into the list. Duplicates are
- forbidden. The element must have been created with SkipList_Alloc!
- SkipList_Remove removes an element from the list and returns it. It
- doesn't free the memory.
-*/
-extern void *VG_(SkipList_Find_Before) (const SkipList *l, void *key);
-extern void *VG_(SkipList_Find_Exact) (const SkipList *l, void *key);
-extern void *VG_(SkipList_Find_After) (const SkipList *l, void *key);
-extern void VG_(SkipList_Insert) ( SkipList *l, void *data);
-extern void *VG_(SkipList_Remove) ( SkipList *l, void *key);
-
-/* Some useful standard comparisons */
-extern Int VG_(cmp_Addr) (const void *a, const void *b);
-extern Int VG_(cmp_Int) (const void *a, const void *b);
-extern Int VG_(cmp_UInt) (const void *a, const void *b);
-extern Int VG_(cmp_string)(const void *a, const void *b);
-
-/* Node (element) operations:
- SkipNode_Alloc: allocate memory for a new element on the list. Must be
- used before an element can be inserted! Returns NULL if not enough
- memory.
- SkipNode_Free: free memory allocated above
- SkipNode_First: return the first element on the list
- SkipNode_Next: return the next element after "data" on the list -
- NULL for none
-
- You can iterate through a SkipList like this:
-
- for(x = VG_(SkipNode_First)(&list); // or SkipList_Find
- x != NULL;
- x = VG_(SkipNode_Next)(&list, x)) { ... }
-*/
-extern void *VG_(SkipNode_Alloc) (const SkipList *l);
-extern void VG_(SkipNode_Free) (const SkipList *l, void *p);
-extern void *VG_(SkipNode_First) (const SkipList *l);
-extern void *VG_(SkipNode_Next) (const SkipList *l, void *data);
-
-
-/*====================================================================*/
/*=== Functions for shadow registers ===*/
/*====================================================================*/