Modularised vg_skiplist.c as m_skiplist.c.

git-svn-id: svn://svn.valgrind.org/valgrind/trunk@3671 a5019735-40e9-0310-863c-91ae7b9d1cf9

3 files changed, 121 insertions, 86 deletions

diff --git a/include/Makefile.am b/include/Makefile.am
index c346bbfee..622e8fb4f 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -16,6 +16,7 @@ incinc_HEADERS = \
 	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 000000000..d597fb004
--- /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 9ba5644aa..17634f98b 100644
--- a/include/tool.h
+++ b/include/tool.h
@@ -635,92 +635,6 @@ extern void VG_(HT_destruct) ( VgHashTable t );
 
 
 /*====================================================================*/
-/*=== 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                               ===*/
 /*====================================================================*/