|
From: <sv...@va...> - 2005-05-12 04:37:31
|
Author: njn Date: 2005-05-12 05:37:27 +0100 (Thu, 12 May 2005) New Revision: 3671 Added: trunk/coregrind/m_skiplist.c trunk/coregrind/pub_core_skiplist.h trunk/include/pub_tool_skiplist.h Removed: trunk/coregrind/vg_skiplist.c Modified: trunk/coregrind/Makefile.am trunk/coregrind/vg_redir.c trunk/include/Makefile.am trunk/include/tool.h Log: Modularised vg_skiplist.c as m_skiplist.c. 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-05-12 03:51:15 UTC (rev 3670) +++ trunk/coregrind/Makefile.am 2005-05-12 04:37:27 UTC (rev 3671) @@ -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 Copied: trunk/coregrind/m_skiplist.c (from rev 3670, trunk/coregrind/vg_s= kiplist.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/vg_skiplist.c 2005-05-12 03:51:15 UTC (rev 3670) +++ trunk/coregrind/m_skiplist.c 2005-05-12 04:37:27 UTC (rev 3671) @@ -0,0 +1,509 @@ + +/*--------------------------------------------------------------------*/ +/*--- 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 "core.h" +#include "pub_core_skiplist.h" + +#include <stdlib.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) && (random() & 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 ---*/ +/*--------------------------------------------------------------------*/ + Added: 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-05-12 03:51:15 UTC (rev 3670= ) +++ trunk/coregrind/pub_core_skiplist.h 2005-05-12 04:37:27 UTC (rev 3671= ) @@ -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 + 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/coregrind/vg_redir.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/vg_redir.c 2005-05-12 03:51:15 UTC (rev 3670) +++ trunk/coregrind/vg_redir.c 2005-05-12 04:37:27 UTC (rev 3671) @@ -33,6 +33,7 @@ #include "vg_symtab2.h" =20 #include "pub_core_aspacemgr.h" +#include "pub_core_skiplist.h" =20 /*------------------------------------------------------------*/ /*--- General purpose redirection. ---*/ Deleted: trunk/coregrind/vg_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/vg_skiplist.c 2005-05-12 03:51:15 UTC (rev 3670) +++ trunk/coregrind/vg_skiplist.c 2005-05-12 04:37:27 UTC (rev 3671) @@ -1,501 +0,0 @@ - -/* - 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 "core.h" - -#include <stdlib.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) && (random() & 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); -} - - 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-05-12 03:51:15 UTC (rev 3670) +++ trunk/include/Makefile.am 2005-05-12 04:37:27 UTC (rev 3671) @@ -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 Added: 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-05-12 03:51:15 UTC (rev 3670) +++ trunk/include/pub_tool_skiplist.h 2005-05-12 04:37:27 UTC (rev 3671) @@ -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 + 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. The arguments are p= retty 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) p= ointers 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 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 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); // or SkipList_Find + 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 ---*/ +/*--------------------------------------------------------------------*/ Modified: trunk/include/tool.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/tool.h 2005-05-12 03:51:15 UTC (rev 3670) +++ trunk/include/tool.h 2005-05-12 04:37:27 UTC (rev 3671) @@ -635,92 +635,6 @@ =20 =20 /*=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=3D*/ -/*=3D=3D=3D A generic skiplist = =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=3D=3D=3D=3D*/ - -/*=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 (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 p= retty 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) p= ointers 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 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 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); // or SkipList_Find - 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); - - -/*=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=3D*/ /*=3D=3D=3D Functions for shadow registers = =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=3D=3D=3D=3D*/ =20 |