njn | 641d5cc | 2005-05-12 04:37:27 +0000 | [diff] [blame^] | 1 | |
| 2 | /*--------------------------------------------------------------------*/ |
| 3 | /*--- SkipList: a skiplist implementaiton. pub_tool_skiplist.h ---*/ |
| 4 | /*--------------------------------------------------------------------*/ |
| 5 | |
| 6 | /* |
| 7 | This file is part of Valgrind, a dynamic binary instrumentation |
| 8 | framework. |
| 9 | |
| 10 | Copyright (C) 2000-2005 Julian Seward |
| 11 | jseward@acm.org |
| 12 | |
| 13 | This program is free software; you can redistribute it and/or |
| 14 | modify it under the terms of the GNU General Public License as |
| 15 | published by the Free Software Foundation; either version 2 of the |
| 16 | License, or (at your option) any later version. |
| 17 | |
| 18 | This program is distributed in the hope that it will be useful, but |
| 19 | WITHOUT ANY WARRANTY; without even the implied warranty of |
| 20 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 21 | General Public License for more details. |
| 22 | |
| 23 | You should have received a copy of the GNU General Public License |
| 24 | along with this program; if not, write to the Free Software |
| 25 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 26 | 02111-1307, USA. |
| 27 | |
| 28 | The GNU General Public License is contained in the file COPYING. |
| 29 | */ |
| 30 | |
| 31 | #ifndef __PUB_TOOL_SKIPLIST_H |
| 32 | #define __PUB_TOOL_SKIPLIST_H |
| 33 | |
| 34 | /* |
| 35 | The idea here is that the skiplist puts its per-element data at the |
| 36 | end of the structure. When you initialize the skiplist, you tell |
| 37 | it what structure your list elements are going to be. Then you |
| 38 | should allocate them with VG_(SkipNode_Alloc), which will allocate |
| 39 | enough memory for the extra bits. |
| 40 | */ |
| 41 | |
| 42 | typedef struct _SkipList SkipList; |
| 43 | typedef struct _SkipNode SkipNode; |
| 44 | |
| 45 | typedef Int (*SkipCmp_t)(const void *key1, const void *key2); |
| 46 | |
| 47 | struct _SkipList { |
| 48 | const Short arena; // allocation arena |
| 49 | const UShort size; // structure size (excluding SkipNode) |
| 50 | const UShort keyoff; // key offset |
| 51 | const SkipCmp_t cmp; // compare two keys |
| 52 | Char * (*strkey)(void *); // stringify a key (for debugging) |
| 53 | SkipNode *head; // list head |
| 54 | }; |
| 55 | |
| 56 | /* Use this macro to initialize your skiplist head. The arguments are pretty self explanitory: |
| 57 | _type is the type of your element structure |
| 58 | _key is the field within that type which you want to use as the key |
| 59 | _cmp is the comparison function for keys - it gets two typeof(_key) pointers as args |
| 60 | _strkey is a function which can return a string of your key - it's only used for debugging |
| 61 | _arena is the arena to use for allocation - -1 is the default |
| 62 | */ |
| 63 | #define VG_SKIPLIST_INIT(_type, _key, _cmp, _strkey, _arena) \ |
| 64 | { \ |
| 65 | .arena = _arena, \ |
| 66 | .size = sizeof(_type), \ |
| 67 | .keyoff = offsetof(_type, _key), \ |
| 68 | .cmp = _cmp, \ |
| 69 | .strkey = _strkey, \ |
| 70 | .head = NULL, \ |
| 71 | } |
| 72 | |
| 73 | /* List operations: |
| 74 | SkipList_Find_* search a list. The 3 variants are: |
| 75 | Before: returns a node which is <= key, or NULL if none |
| 76 | Exact: returns a node which is == key, or NULL if none |
| 77 | After: returns a node which is >= key, or NULL if none |
| 78 | SkipList_Insert inserts a new element into the list. Duplicates are |
| 79 | forbidden. The element must have been created with SkipList_Alloc! |
| 80 | SkipList_Remove removes an element from the list and returns it. It |
| 81 | doesn't free the memory. |
| 82 | */ |
| 83 | extern void *VG_(SkipList_Find_Before) (const SkipList *l, void *key); |
| 84 | extern void *VG_(SkipList_Find_Exact) (const SkipList *l, void *key); |
| 85 | extern void *VG_(SkipList_Find_After) (const SkipList *l, void *key); |
| 86 | extern void VG_(SkipList_Insert) ( SkipList *l, void *data); |
| 87 | extern void *VG_(SkipList_Remove) ( SkipList *l, void *key); |
| 88 | |
| 89 | /* Some useful standard comparisons */ |
| 90 | extern Int VG_(cmp_Addr) (const void *a, const void *b); |
| 91 | extern Int VG_(cmp_Int) (const void *a, const void *b); |
| 92 | extern Int VG_(cmp_UInt) (const void *a, const void *b); |
| 93 | extern Int VG_(cmp_string)(const void *a, const void *b); |
| 94 | |
| 95 | /* Node (element) operations: |
| 96 | SkipNode_Alloc: allocate memory for a new element on the list. Must be |
| 97 | used before an element can be inserted! Returns NULL if not enough |
| 98 | memory. |
| 99 | SkipNode_Free: free memory allocated above |
| 100 | SkipNode_First: return the first element on the list |
| 101 | SkipNode_Next: return the next element after "data" on the list - |
| 102 | NULL for none |
| 103 | |
| 104 | You can iterate through a SkipList like this: |
| 105 | |
| 106 | for(x = VG_(SkipNode_First)(&list); // or SkipList_Find |
| 107 | x != NULL; |
| 108 | x = VG_(SkipNode_Next)(&list, x)) { ... } |
| 109 | */ |
| 110 | extern void *VG_(SkipNode_Alloc) (const SkipList *l); |
| 111 | extern void VG_(SkipNode_Free) (const SkipList *l, void *p); |
| 112 | extern void *VG_(SkipNode_First) (const SkipList *l); |
| 113 | extern void *VG_(SkipNode_Next) (const SkipList *l, void *data); |
| 114 | |
| 115 | |
| 116 | #endif // __PUB_TOOL_SKIPLIST_H |
| 117 | |
| 118 | /*--------------------------------------------------------------------*/ |
| 119 | /*--- end ---*/ |
| 120 | /*--------------------------------------------------------------------*/ |