|
From: <sv...@va...> - 2005-10-20 00:09:27
|
Author: sewardj Date: 2005-10-20 01:09:11 +0100 (Thu, 20 Oct 2005) New Revision: 4952 Log: rm the skiplist module, as it has been superseded by the AVL-tree based m_oset module. Removed: trunk/coregrind/m_skiplist.c trunk/coregrind/pub_core_skiplist.h trunk/include/pub_tool_skiplist.h Modified: trunk/coregrind/Makefile.am trunk/include/Makefile.am Modified: trunk/coregrind/Makefile.am =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- trunk/coregrind/Makefile.am 2005-10-19 23:49:45 UTC (rev 4951) +++ trunk/coregrind/Makefile.am 2005-10-20 00:09:11 UTC (rev 4952) @@ -59,7 +59,6 @@ pub_core_scheduler.h \ pub_core_sigframe.h \ pub_core_signals.h \ - pub_core_skiplist.h \ pub_core_stacks.h \ pub_core_stacktrace.h \ pub_core_syscall.h \ @@ -121,7 +120,6 @@ m_pthreadmodel.c \ m_redir.c \ m_signals.c \ - m_skiplist.c \ m_stacks.c \ m_stacktrace.c \ m_syscall.c \ Deleted: trunk/coregrind/m_skiplist.c =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- trunk/coregrind/m_skiplist.c 2005-10-19 23:49:45 UTC (rev 4951) +++ trunk/coregrind/m_skiplist.c 2005-10-20 00:09:11 UTC (rev 4952) @@ -1,511 +0,0 @@ - -/*--------------------------------------------------------------------*/ -/*--- A skiplist implementation. m_skiplist.c ---*/ -/*--------------------------------------------------------------------*/ - -/* - This file is part of Valgrind, a dynamic binary instrumentation - framework. - - Copyright (C) 2002-2005 Jeremy Fitzhardinge - je...@go... - - 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. -*/ - -/*=20 - This file implements a generic skip-list type. - - Skip-lists are described in William Pugh, Skip Lists: A - Probabilistic Alternative to Balanced Trees, CACM, 33(6):668-676, - June 1990.=20 - http://www.cs.unc.edu/~baruah/Teaching/2002f/HandOuts/skiplist-CACM.p= df - - Skip-lists are a randomized linked-list, where a node in the list - has at least one "next" pointer, but may have more. When - traversing the list, the "higher" next pointers allow you to skip - multiple list entries, allowing you to find the right place - quickly. =20 - - On average, 1/2 the entries have one next pointer, 1/4 have 2, 1/8 - have 3, etc. This means that the skiplist has the same search - complexity as a balanced binary tree, but there is no need to - rebalance or do any other structural changes. The randomness also - means that it is invulnerable to pathalogical workloads. - - Because the each node can be a different size, this implementation - puts the SkipNode structure at the end of the allocation, with the - node data starting at the beginning. - - low address ->+---------------+ ^ - | list data | | - key offset->: key : structure size - | | | - +---------------+ V - | struct | - | SkipNode | - +- - - - - - - -+ - | next pointers | - : : - - - When you declare the list with VG_SKIPLIST_INIT, you specify the - structure for each list node, structure member you want to use as a - key, and the function for comparing keys. - - Each node must be allocated with SkipNode_Alloc, which allocates - enough space for the client data, the SkipNode structure, and the - next pointers for this node. - - The helper functions data_of_node and node_of_data do the correct - pointer arithmetic to sort all this out. The SkipNode also has a - magic number which is checked after each operation to make sure - that we're really operating on a SkipNode. - - The first node of the list, the head node, is special. It contains - the maximum number of next pointers (SK_MAXHEIGHT). It has no data - associated with it, and it always compares less-than to all other - nodes. Because it has no data attached to it, it is always an - error to try and use data_of_node on it. To detect this problem, - it has a different magic number from all other SkipNodes so that it - won't be accidentally used. - */ - -#include "pub_core_basics.h" -#include "pub_core_libcbase.h" -#include "pub_core_libcassert.h" -#include "pub_core_libcprint.h" -#include "pub_core_mallocfree.h" -#include "pub_core_skiplist.h" - -#define SKIPLIST_DEBUG 0 - -#define SK_MAXHEIGHT 20 /* 2^20 elements */ -#define SKIPLIST_MAGIC 0x5b1ff872 -#define SKIPLIST_HEAD_MAGIC (~SKIPLIST_MAGIC) - - -#if SKIPLIST_DEBUG -#define inline -#endif /* SKIPLIST_DEBUG */ - -struct _SkipNode { - UInt magic; - UShort level; /* level is the max level (level =3D=3D 0 means 1 next= pointer) */ - SkipNode *next[0]; -}; - - -/*=20 - Compute the height of a new node. 1/2 will be 1, 1/4 2, 1/8 3, - etc. - */ -static inline Int get_height(void) -{ - UInt ret =3D 0; - - while((ret < SK_MAXHEIGHT - 1) && (VG_(random)(NULL) & 1)) - ret++; - - return ret; -} - -/*=20 - Given a pointer to the node's data, return a pointer to the key. - */ -static inline void *key_of_data(const SkipList *l, void *d) -{ - return (void *)((Char *)d + l->keyoff); -} - -/*=20 - Given a pointer to the node's data, return the pointer to the SkipNod= e - structure. If the node has a bad magic number, it will die with an - assertion failure. - */ -static inline SkipNode *node_of_data(const SkipList *l, const void *d) -{ - SkipNode *n =3D (SkipNode *)((Char *)d + l->size); - - if (SKIPLIST_DEBUG && n->magic !=3D SKIPLIST_MAGIC) - VG_(printf)("bad magic on node %p =3D %x (not %x)\n", - n, n->magic, SKIPLIST_MAGIC); - - vg_assert(n->magic =3D=3D SKIPLIST_MAGIC); - - return n;=20 -} - -/*=20 - Given a SkipNode structure, return the pointer to the node's data. - */ -static inline void *data_of_node(const SkipList *l, const SkipNode *n) -{ - if (SKIPLIST_DEBUG && n->magic !=3D SKIPLIST_MAGIC) - VG_(printf)("bad magic on node %p =3D %x (not %x)\n", - n, n->magic, SKIPLIST_MAGIC); - - vg_assert(n->magic =3D=3D SKIPLIST_MAGIC); - return (void *)((Char *)n - l->size); -} - -/*=20 - Given a SkipNode structure, return the pointer to the node's key. - */ -static inline void *key_of_node(const SkipList *l, const SkipNode *n) -{ - return key_of_data(l, data_of_node(l, n)); -} - -static inline void validate_skiplist(const SkipList *l, const Char *wher= e) -{ -#if SKIPLIST_DEBUG - const SkipNode *prev[SK_MAXHEIGHT]; - Int i; - const SkipNode *n, *next; - =20 - VG_(printf)("---------------- %s ----------------\n", where); - - if (l->head =3D=3D NULL) - return; - - for(i =3D 0; i <=3D l->head->level; i++) { - VG_(printf)("l->head->next[%d]=3D%p\n", - i, l->head->next[i]); - prev[i] =3D l->head->next[i]; - } - - for(n =3D l->head->next[0]; n !=3D NULL; n =3D next) { - next =3D n->next[0]; - - VG_(printf)("n=3D%p next=3D%p, n->level=3D%d k=3D%s\n", - n, next, n->level, (*l->strkey)(key_of_node(l, n))); - for(i =3D 0; i <=3D n->level; i++) { - VG_(printf)(" n->next[%d] =3D %p\n", - i, n->next[i]); - VG_(printf)(" prev[%d] =3D %p\n", - i, prev[i]); - } - =20 - vg_assert(l->head->level >=3D n->level); - - for(i =3D 0; i <=3D n->level; i++) - vg_assert(prev[i] =3D=3D n); - - for(i =3D 0; i <=3D n->level; i++) - prev[i] =3D n->next[i]; - - vg_assert(next =3D=3D NULL || (l->cmp)(key_of_node(l, n), key_of_n= ode(l, next)) < 0); - } -#endif /* SKIPLIST_DEBUG */ -} - -void *VG_(SkipNode_Alloc)(const SkipList *l) -{ - UInt size; - Int h; - SkipNode *n; - Char *ret; - - h =3D get_height(); - - size =3D l->size; - size +=3D sizeof(SkipNode) + (h+1)*sizeof(SkipNode *); - - if (l->arena =3D=3D -1) - *(Short *)&l->arena =3D VG_AR_TOOL; - - ret =3D VG_(arena_malloc)(l->arena, size); - - if (ret =3D=3D NULL) - return NULL; - - n =3D (SkipNode *)(ret + l->size); - n->level =3D h; - n->magic =3D SKIPLIST_MAGIC; - - VG_(memset)(n->next, 0, sizeof(n->next[0]) * (h+1)); - - return ret; -} - -void VG_(SkipNode_Free)(const SkipList *l, void *p) -{ - if (SKIPLIST_DEBUG) { - SkipNode *n =3D node_of_data(l, p); - - VG_(printf)("SkipNode_Free: freeing %p (node %p)\n", - p, n); - n->magic =3D 0x55ffaabb; - } - VG_(arena_free)(l->arena, p); -} - -void *VG_(SkipNode_First)(const SkipList *l) -{ - SkipNode *n =3D l->head ? l->head->next[0] : NULL; - - if (n =3D=3D NULL) - return NULL; - else - return data_of_node(l, n); -} - -void *VG_(SkipNode_Next)(const SkipList *l, void *data) -{ - SkipNode *n =3D node_of_data(l, data); - =20 - n =3D n->next[0]; - - if (n =3D=3D NULL) - return NULL; - - return data_of_node(l, n); -} - - - -static Int cmp(const SkipList *l, SkipNode *n, void *k2) -{ - void *k1 =3D key_of_node(l, n); - - if (k1 =3D=3D k2) - return 0; - - if (l->head =3D=3D n) - return -1; - - return (l->cmp)(k1, k2); -} - -/* Search the list for k; it either returns the k if it exists, or the - one before if not. */ -static SkipNode *SkipList__Find(const SkipList *l, void *k, SkipNode **p= revs) -{ - SkipNode *n; - Int lvl; - - if (SKIPLIST_DEBUG) - VG_(printf)("SkipList__Find: finding %s\n", (*l->strkey)(k)); - - validate_skiplist(l, "SkipList__Find"); - - if (l->head =3D=3D NULL) - return NULL; - - for(lvl =3D l->head->level, n =3D l->head; lvl >=3D 0; lvl--) { - while(n->next[lvl] !=3D NULL && cmp(l, n->next[lvl], k) < 0) { - if (SKIPLIST_DEBUG) - VG_(printf)("SkipList__Find: n=3D%p n->next[%d]=3D%p\n", - n, lvl, n->next[lvl]); - n =3D n->next[lvl]; - } - if (prevs) - prevs[lvl] =3D n; - } - - /* XXX Is there a cleaner way of getting this?=20 - =20 - If we get an exact match, return it. - If we get the head, return NULL. - Otherwise return the one before where the hit would be. - */ - if (n->next[0] !=3D NULL && cmp(l, n->next[0], k) =3D=3D 0) - n =3D n->next[0]; - if (n =3D=3D l->head) - n =3D NULL; - - if (SKIPLIST_DEBUG) { - - VG_(printf)("SkipList__Find returning node %p\n", n); - - if (n =3D=3D NULL) { - SkipNode *nn; - - for(nn =3D l->head->next[0]; nn !=3D NULL; nn =3D nn->next[0]) - vg_assert(cmp(l, nn, k) !=3D 0); - } else - vg_assert(cmp(l, n, k) <=3D 0); - } - - return n; -} - -/* Return list element which is <=3D k, or NULL if there is none. */ -void *VG_(SkipList_Find_Before)(const SkipList *l, void *k) -{ - SkipNode *n =3D SkipList__Find(l, k, NULL); - - if (n !=3D NULL) - return data_of_node(l, n); - return NULL; -} - -/* Return the list element which =3D=3D k, or NULL if none */ -void *VG_(SkipList_Find_Exact)(const SkipList *l, void *k) -{ - SkipNode *n =3D SkipList__Find(l, k, NULL); - - if (n !=3D NULL && (l->cmp)(key_of_node(l, n), k) =3D=3D 0) - return data_of_node(l, n); - return NULL; -} - -/* Return the list element which is >=3D k, or NULL if none */ -void *VG_(SkipList_Find_After)(const SkipList *l, void *k) -{ - SkipNode *n =3D SkipList__Find(l, k, NULL); - - if (n !=3D NULL && (l->cmp)(key_of_node(l, n), k) < 0) - n =3D n->next[0]; - - if (n !=3D NULL) - return data_of_node(l, n); - - return NULL; -} - -void VG_(SkipList_Insert)(SkipList *l, void *data) -{ - SkipNode *update[SK_MAXHEIGHT]; - SkipNode *n, *nn; - void *k =3D key_of_data(l, data); - Int i; - - if (SKIPLIST_DEBUG) - VG_(printf)("inserting node %p, key %s, height %d\n", - data, (*l->strkey)(key_of_data(l, data)), node_of_data(l, data)->lev= el); - - validate_skiplist(l, "SkipList_Insert before"); - - if (l->head =3D=3D NULL) { - Int size =3D sizeof(SkipNode) + sizeof(SkipNode *) * SK_MAXHEIGHT; - - if (l->arena =3D=3D -1) - *(Short *)&l->arena =3D VG_AR_TOOL; - =20 - l->head =3D VG_(arena_malloc)(l->arena, size); - VG_(memset)(l->head, 0, size); - - l->head->magic =3D SKIPLIST_HEAD_MAGIC; - l->head->level =3D 0; - } - - n =3D node_of_data(l, data); - - /* update size of head's next vector to fit this new node */ - vg_assert(l->head !=3D NULL); - if (l->head->level < n->level) { - for(i =3D l->head->level+1; i <=3D n->level; i++) - l->head->next[i] =3D NULL; - l->head->level =3D n->level; - } - - /* Look for the node, but we're mostly interested in setting - "update", which is the set of previous nodes with next pointers - we need to fix up. */ - nn =3D SkipList__Find(l, k, update); - =20 - /* check the new entry is unique */ - vg_assert(nn =3D=3D NULL || (l->cmp)(key_of_node(l, nn), k) !=3D 0); - - /* update the previous node's next pointers */ - for(i =3D 0; i <=3D n->level; i++) { - n->next[i] =3D update[i]->next[i]; - update[i]->next[i] =3D n; - } - - validate_skiplist(l, "SkipList_Insert after"); -} - -void *VG_(SkipList_Remove)(SkipList *l, void *k) -{ - SkipNode *update[SK_MAXHEIGHT]; - SkipNode *n; - Int i; - =20 - validate_skiplist(l, "SkipList_Remove before"); - - n =3D SkipList__Find(l, k, update); - if (n =3D=3D NULL) - return NULL; - - vg_assert((l->cmp)(k, key_of_node(l, n)) =3D=3D 0); - - for(i =3D 0; i <=3D n->level; i++) { - update[i]->next[i] =3D n->next[i]; - n->next[i] =3D NULL; - } - - validate_skiplist(l, "SkipList_Remove after"); - - return data_of_node(l, n); -} - - -/* -------------------------------------------------- - Comparison functions - -------------------------------------------------- */ -Int VG_(cmp_Int)(const void *v1, const void *v2) -{ - Int a =3D *(const Int *)v1; - Int b =3D *(const Int *)v2; - - if (a < b) - return -1; - if (a =3D=3D b) - return 0; - return 1; -} - -Int VG_(cmp_UInt)(const void *v1, const void *v2) -{ - UInt a =3D *(const UInt *)v1; - UInt b =3D *(const UInt *)v2; - - if (a < b) - return -1; - if (a =3D=3D b) - return 0; - return 1; -} - -Int VG_(cmp_Addr)(const void *v1, const void *v2) -{ - Addr a =3D *(const Addr *)v1; - Addr b =3D *(const Addr *)v2; - - if (a < b) - return -1; - if (a =3D=3D b) - return 0; - return 1; -} - -Int VG_(cmp_string)(const void *v1, const void *v2) -{ - const Char *a =3D *(const Char **)v1; - const Char *b =3D *(const Char **)v2; - - return VG_(strcmp)(a, b); -} - -/*--------------------------------------------------------------------*/ -/*--- end ---*/ -/*--------------------------------------------------------------------*/ - Deleted: trunk/coregrind/pub_core_skiplist.h =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- trunk/coregrind/pub_core_skiplist.h 2005-10-19 23:49:45 UTC (rev 4951= ) +++ trunk/coregrind/pub_core_skiplist.h 2005-10-20 00:09:11 UTC (rev 4952= ) @@ -1,47 +0,0 @@ - -/*--------------------------------------------------------------------*/ -/*--- 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 - js...@ac... - - 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 ---*/ -/*--------------------------------------------------------------------*/ Modified: trunk/include/Makefile.am =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- trunk/include/Makefile.am 2005-10-19 23:49:45 UTC (rev 4951) +++ trunk/include/Makefile.am 2005-10-20 00:09:11 UTC (rev 4952) @@ -25,7 +25,6 @@ pub_tool_redir.h \ pub_tool_replacemalloc.h \ pub_tool_signals.h \ - pub_tool_skiplist.h \ pub_tool_stacktrace.h \ pub_tool_threadstate.h \ pub_tool_tooliface.h \ Deleted: trunk/include/pub_tool_skiplist.h =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- trunk/include/pub_tool_skiplist.h 2005-10-19 23:49:45 UTC (rev 4951) +++ trunk/include/pub_tool_skiplist.h 2005-10-20 00:09:11 UTC (rev 4952) @@ -1,122 +0,0 @@ - -/*--------------------------------------------------------------------*/ -/*--- 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 - js...@ac... - - 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 - -/*=20 - 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 Skip= Node) - 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: - _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)=20 - pointers as args - _strkey is a function which can return a string of your key - it's on= ly - 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 =3D _arena, \ - .size =3D sizeof(_type), \ - .keyoff =3D offsetof(_type, _key), \ - .cmp =3D _cmp, \ - .strkey =3D _strkey, \ - .head =3D NULL, \ - } - -/* List operations: - SkipList_Find_* search a list. The 3 variants are: - Before: returns a node which is <=3D key, or NULL if none - Exact: returns a node which is =3D=3D key, or NULL if none - After: returns a node which is >=3D key, or NULL if none - SkipList_Insert inserts a new element into the list. Duplicates are - forbidden. The element must have been created with SkipNode_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 enoug= h - 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 -=20 - NULL for none - - You can iterate through a SkipList like this: - - for (x =3D VG_(SkipNode_First)(&list); - x !=3D NULL; - x =3D 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 ---*/ -/*--------------------------------------------------------------------*/ |