diff options
| -rw-r--r-- | coregrind/Makefile.am | 3 | ||||
| -rw-r--r-- | coregrind/m_skiplist.c (renamed from coregrind/vg_skiplist.c) | 8 | ||||
| -rw-r--r-- | coregrind/pub_core_skiplist.h | 47 | ||||
| -rw-r--r-- | coregrind/vg_redir.c | 1 | ||||
| -rw-r--r-- | include/Makefile.am | 1 | ||||
| -rw-r--r-- | include/pub_tool_skiplist.h | 120 | ||||
| -rw-r--r-- | include/tool.h | 86 |
7 files changed, 179 insertions, 87 deletions
diff --git a/coregrind/Makefile.am b/coregrind/Makefile.am index f7dd59b02..c430bfa24 100644 --- a/coregrind/Makefile.am +++ b/coregrind/Makefile.am @@ -45,6 +45,7 @@ noinst_HEADERS = \ 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 @@ stage2_SOURCES = \ m_errormgr.c \ m_execontext.c \ m_mallocfree.c \ + m_skiplist.c \ m_stacktrace.c \ m_tooliface.c \ ume.c \ @@ -88,7 +90,6 @@ stage2_SOURCES = \ 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 index 02d345c48..281e937ab 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 @@ Int VG_(cmp_string)(const void *v1, const void *v2) 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 000000000..578731889 --- /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 af6c914b2..6794e841d 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 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 ===*/ /*====================================================================*/ |