From 0974a299f5bfd54bb35409aa50e6cedd6dc9f646 Mon Sep 17 00:00:00 2001 From: Nicholas Nethercote Date: Mon, 17 Sep 2007 05:30:48 +0000 Subject: [PATCH] Split the OSet interface into two parts: "OSetGen_", which is the existing interface and provides full power; and "OSetWord_", which is an easier-to-use interface for if you just want to store words. git-svn-id: svn://svn.valgrind.org/valgrind/trunk@6841 --- cachegrind/cg_main.c | 53 +- coregrind/m_debuginfo/readelf.c | 18 +- coregrind/m_oset.c | 105 ++- coregrind/m_redir.c | 46 +- include/pub_tool_oset.h | 182 +++-- memcheck/mc_main.c | 54 +- memcheck/tests/oset_test.c | 272 ++++++-- memcheck/tests/oset_test.stdout.exp | 1003 ++++++++++++++++++++++++++- 8 files changed, 1494 insertions(+), 239 deletions(-) diff --git a/cachegrind/cg_main.c b/cachegrind/cg_main.c index bd9016b748..e2b8661cb4 100644 --- a/cachegrind/cg_main.c +++ b/cachegrind/cg_main.c @@ -190,13 +190,13 @@ static Word stringCmp( void* key, void* elem ) // been encountered before, or dup it and put it into the string table. static Char* get_perm_string(Char* s) { - Char** s_ptr = VG_(OSet_Lookup)(stringTable, &s); + Char** s_ptr = VG_(OSetGen_Lookup)(stringTable, &s); if (s_ptr) { return *s_ptr; } else { - Char** s_node = VG_(OSet_AllocNode)(stringTable, sizeof(Char*)); + Char** s_node = VG_(OSetGen_AllocNode)(stringTable, sizeof(Char*)); *s_node = VG_(strdup)(s); - VG_(OSet_Insert)(stringTable, s_node); + VG_(OSetGen_Insert)(stringTable, s_node); return *s_node; } } @@ -258,10 +258,10 @@ static LineCC* get_lineCC(Addr origAddr) loc.fn = fn; loc.line = line; - lineCC = VG_(OSet_Lookup)(CC_table, &loc); + lineCC = VG_(OSetGen_Lookup)(CC_table, &loc); if (!lineCC) { // Allocate and zero a new node. - lineCC = VG_(OSet_AllocNode)(CC_table, sizeof(LineCC)); + lineCC = VG_(OSetGen_AllocNode)(CC_table, sizeof(LineCC)); lineCC->loc.file = get_perm_string(loc.file); lineCC->loc.fn = get_perm_string(loc.fn); lineCC->loc.line = loc.line; @@ -278,7 +278,7 @@ static LineCC* get_lineCC(Addr origAddr) lineCC->Bc.mp = 0; lineCC->Bi.b = 0; lineCC->Bi.mp = 0; - VG_(OSet_Insert)(CC_table, lineCC); + VG_(OSetGen_Insert)(CC_table, lineCC); } return lineCC; @@ -560,16 +560,16 @@ SB_info* get_SB_info(IRSB* sbIn, Addr origAddr) // If this assertion fails, there has been some screwup: some // translations must have been discarded but Cachegrind hasn't discarded // the corresponding entries in the instr-info table. - sbInfo = VG_(OSet_Lookup)(instrInfoTable, &origAddr); + sbInfo = VG_(OSetGen_Lookup)(instrInfoTable, &origAddr); tl_assert(NULL == sbInfo); // BB never translated before (at this address, at least; could have // been unloaded and then reloaded elsewhere in memory) - sbInfo = VG_(OSet_AllocNode)(instrInfoTable, + sbInfo = VG_(OSetGen_AllocNode)(instrInfoTable, sizeof(SB_info) + n_instrs*sizeof(InstrInfo)); sbInfo->SB_addr = origAddr; sbInfo->n_instrs = n_instrs; - VG_(OSet_Insert)( instrInfoTable, sbInfo ); + VG_(OSetGen_Insert)( instrInfoTable, sbInfo ); distinct_instrs++; return sbInfo; @@ -1330,8 +1330,8 @@ static void fprint_CC_table_and_calc_totals(void) VG_(write)(fd, (void*)buf, VG_(strlen)(buf)); // Traverse every lineCC - VG_(OSet_ResetIter)(CC_table); - while ( (lineCC = VG_(OSet_Next)(CC_table)) ) { + VG_(OSetGen_ResetIter)(CC_table); + while ( (lineCC = VG_(OSetGen_Next)(CC_table)) ) { Bool just_hit_a_new_file = False; // If we've hit a new file, print a "fl=" line. Note that because // each string is stored exactly once in the string table, we can use @@ -1610,11 +1610,11 @@ static void cg_fini(Int exitcode) buf4, no_debugs); VG_(message)(Vg_DebugMsg, "cachegrind: string table size: %u", - VG_(OSet_Size)(stringTable)); + VG_(OSetGen_Size)(stringTable)); VG_(message)(Vg_DebugMsg, "cachegrind: CC table size: %u", - VG_(OSet_Size)(CC_table)); + VG_(OSetGen_Size)(CC_table)); VG_(message)(Vg_DebugMsg, "cachegrind: InstrInfo table size: %u", - VG_(OSet_Size)(instrInfoTable)); + VG_(OSetGen_Size)(instrInfoTable)); } } @@ -1640,9 +1640,9 @@ void cg_discard_superblock_info ( Addr64 orig_addr64, VexGuestExtents vge ) // Get BB info, remove from table, free BB info. Simple! Note that we // use orig_addr, not the first instruction address in vge. - sbInfo = VG_(OSet_Remove)(instrInfoTable, &orig_addr); + sbInfo = VG_(OSetGen_Remove)(instrInfoTable, &orig_addr); tl_assert(NULL != sbInfo); - VG_(OSet_FreeNode)(instrInfoTable, sbInfo); + VG_(OSetGen_FreeNode)(instrInfoTable, sbInfo); } /*--------------------------------------------------------------------*/ @@ -1800,15 +1800,18 @@ static void cg_post_clo_init(void) tl_assert( cachegrind_out_file[filename_szB-1] == 0 ); - CC_table = VG_(OSet_Create)(offsetof(LineCC, loc), - cmp_CodeLoc_LineCC, - VG_(malloc), VG_(free)); - instrInfoTable = VG_(OSet_Create)(/*keyOff*/0, - NULL, - VG_(malloc), VG_(free)); - stringTable = VG_(OSet_Create)(/*keyOff*/0, - stringCmp, - VG_(malloc), VG_(free)); + CC_table = + VG_(OSetGen_Create)(offsetof(LineCC, loc), + cmp_CodeLoc_LineCC, + VG_(malloc), VG_(free)); + instrInfoTable = + VG_(OSetGen_Create)(/*keyOff*/0, + NULL, + VG_(malloc), VG_(free)); + stringTable = + VG_(OSetGen_Create)(/*keyOff*/0, + stringCmp, + VG_(malloc), VG_(free)); configure_caches(&I1c, &D1c, &L2c); diff --git a/coregrind/m_debuginfo/readelf.c b/coregrind/m_debuginfo/readelf.c index 39075db9a2..dfe9cf90e4 100644 --- a/coregrind/m_debuginfo/readelf.c +++ b/coregrind/m_debuginfo/readelf.c @@ -516,9 +516,9 @@ void read_elf_symtab__ppc64_linux( TRACE_SYMTAB("\nReading (ELF, ppc64-linux) %s (%d entries)\n", tab_name, o_symtab_sz/sizeof(ElfXX_Sym) ); - oset = VG_(OSet_Create)( offsetof(TempSym,key), - (OSetCmp_t)cmp_TempSymKey, - oset_malloc, oset_free ); + oset = VG_(OSetGen_Create)( offsetof(TempSym,key), + (OSetCmp_t)cmp_TempSymKey, + oset_malloc, oset_free ); vg_assert(oset); /* Perhaps should start at i = 1; ELF docs suggest that entry @@ -542,7 +542,7 @@ void read_elf_symtab__ppc64_linux( /* Check if we've seen this (name,addr) key before. */ key.addr = sym_addr_really; key.name = sym_name_really; - prev = VG_(OSet_Lookup)( oset, &key ); + prev = VG_(OSetGen_Lookup)( oset, &key ); if (prev) { @@ -604,13 +604,13 @@ void read_elf_symtab__ppc64_linux( } else { /* A new (name,addr) key. Add and continue. */ - elem = VG_(OSet_AllocNode)(oset, sizeof(TempSym)); + elem = VG_(OSetGen_AllocNode)(oset, sizeof(TempSym)); vg_assert(elem); elem->key = key; elem->tocptr = sym_tocptr; elem->size = sym_size; elem->from_opd = from_opd; - VG_(OSet_Insert)(oset, elem); + VG_(OSetGen_Insert)(oset, elem); if (si->trace_symtab) { VG_(printf)(" to-oset [%4d]: " " val %010p, toc %010p, sz %4d %s\n", @@ -629,9 +629,9 @@ void read_elf_symtab__ppc64_linux( build a "standard" symbol table, and nuke the oset. */ i = 0; - VG_(OSet_ResetIter)( oset ); + VG_(OSetGen_ResetIter)( oset ); - while ( (elem = VG_(OSet_Next)(oset)) ) { + while ( (elem = VG_(OSetGen_Next)(oset)) ) { risym.addr = elem->key.addr; risym.size = elem->size; risym.name = ML_(addStr) ( si, elem->key.name, -1 ); @@ -651,7 +651,7 @@ void read_elf_symtab__ppc64_linux( i++; } - VG_(OSet_Destroy)( oset, NULL ); + VG_(OSetGen_Destroy)( oset ); } diff --git a/coregrind/m_oset.c b/coregrind/m_oset.c index 63cd25b2ef..b61820f984 100644 --- a/coregrind/m_oset.c +++ b/coregrind/m_oset.c @@ -56,7 +56,7 @@ // keyOff -> | key | elemSize // +---------------+ v // -// Users have to allocate AvlNodes with OSet_AllocNode(), which allocates +// Users have to allocate AvlNodes with OSetGen_AllocNode(), which allocates // space for the metadata. // // The terminology used throughout this file: @@ -70,7 +70,7 @@ // an AvlNode. // // Each tree also has an iterator. Note that we cannot use the iterator -// internally within this file (eg. we could implement OSet_Size() by +// internally within this file (eg. we could implement OSetGen_Size() by // stepping through with the iterator and counting nodes) because it's // non-reentrant -- the user might be using it themselves, and the // concurrent uses would screw things up. @@ -85,6 +85,8 @@ /*--- Types and constants ---*/ /*--------------------------------------------------------------------*/ +typedef struct _OSetNode OSetNode; + // Internal names for the OSet types. typedef OSet AvlTree; typedef OSetNode AvlNode; @@ -133,7 +135,7 @@ AvlNode* node_of_elem(const void *elem) vg_assert2(n->magic == OSET_MAGIC, "bad magic on node %p = %x (expected %x)\n" "possible causes:\n" - " - node not allocated with VG_(OSet_AllocNode)()?\n" + " - node not allocated with VG_(OSetGen_AllocNode)()?\n" " - node metadata corrupted by underwriting start of element?\n", n, n->magic, OSET_MAGIC); return n; @@ -268,8 +270,8 @@ static inline Bool stackPop(AvlTree* t, AvlNode** n, Int* i) /*--------------------------------------------------------------------*/ // The underscores avoid GCC complaints about overshadowing global names. -AvlTree* VG_(OSet_Create)(OffT _keyOff, OSetCmp_t _cmp, - OSetAlloc_t _alloc, OSetFree_t _free) +AvlTree* VG_(OSetGen_Create)(OffT _keyOff, OSetCmp_t _cmp, + OSetAlloc_t _alloc, OSetFree_t _free) { AvlTree* t; @@ -293,8 +295,13 @@ AvlTree* VG_(OSet_Create)(OffT _keyOff, OSetCmp_t _cmp, return t; } +AvlTree* VG_(OSetWord_Create)(OSetAlloc_t _alloc, OSetFree_t _free) +{ + return VG_(OSetGen_Create)(/*keyOff*/0, /*cmp*/NULL, _alloc, _free); +} + // Destructor, frees up all memory held by remaining nodes. -void VG_(OSet_Destroy)(AvlTree* t, OSetNodeDestroy_t destroyNode) +void VG_(OSetGen_Destroy)(AvlTree* t) { AvlNode* n = NULL; Int i = 0, sz = 0; @@ -304,8 +311,8 @@ void VG_(OSet_Destroy)(AvlTree* t, OSetNodeDestroy_t destroyNode) if (t->root) stackPush(t, t->root, 1); - // Free all the AvlNodes. This is a post-order traversal, because we - // must free all children of a node before the node itself. + /* Free all the AvlNodes. This is a post-order traversal, because we */ + /* must free all children of a node before the node itself. */ while (stackPop(t, &n, &i)) { switch (i) { case 1: @@ -317,7 +324,6 @@ void VG_(OSet_Destroy)(AvlTree* t, OSetNodeDestroy_t destroyNode) if (n->right) stackPush(t, n->right, 1); break; case 3: - if (destroyNode) destroyNode(n); t->free(n); sz++; break; @@ -325,12 +331,17 @@ void VG_(OSet_Destroy)(AvlTree* t, OSetNodeDestroy_t destroyNode) } vg_assert(sz == t->nElems); - // Free the AvlTree itself. + /* Free the AvlTree itself. */ t->free(t); } +void VG_(OSetWord_Destroy)(AvlTree* t) +{ + VG_(OSetGen_Destroy)(t); +} + // Allocate and initialise a new node. -void* VG_(OSet_AllocNode)(AvlTree* t, SizeT elemSize) +void* VG_(OSetGen_AllocNode)(AvlTree* t, SizeT elemSize) { Int nodeSize = sizeof(AvlNode) + elemSize; AvlNode* n = t->alloc( nodeSize ); @@ -340,7 +351,7 @@ void* VG_(OSet_AllocNode)(AvlTree* t, SizeT elemSize) return elem_of_node(n); } -void VG_(OSet_FreeNode)(AvlTree* t, void* e) +void VG_(OSetGen_FreeNode)(AvlTree* t, void* e) { t->free( node_of_elem(e) ); } @@ -427,19 +438,19 @@ static Bool avl_insert(AvlTree* t, AvlNode* n) } } else { - vg_assert2(0, "OSet_Insert: duplicate element added"); + vg_assert2(0, "OSet{Word,Gen}_Insert: duplicate element added"); } } // Insert element e into the AVL tree t. This is just a wrapper for // avl_insert() which doesn't return a Bool. -void VG_(OSet_Insert)(AvlTree* t, void* e) +void VG_(OSetGen_Insert)(AvlTree* t, void* e) { AvlNode* n; vg_assert(t); - // Initialise. Even though OSet_AllocNode zeroes these fields, we should + // Initialise. Even though OSetGen_AllocNode zeroes these fields, we should // do it again in case a node is removed and then re-added to the tree. n = node_of_elem(e); n->left = 0; @@ -457,6 +468,13 @@ void VG_(OSet_Insert)(AvlTree* t, void* e) t->stackTop = 0; // So the iterator can't get out of sync } +void VG_(OSetWord_Insert)(AvlTree* t, Word val) +{ + Word* node = VG_(OSetGen_AllocNode)(t, sizeof(Word)); + *node = val; + VG_(OSetGen_Insert)(t, node); +} + /*--------------------------------------------------------------------*/ /*--- Lookup ---*/ /*--------------------------------------------------------------------*/ @@ -493,7 +511,7 @@ static AvlNode* avl_lookup(AvlTree* t, void* k) } // Find the *element* in t matching k, or NULL if not found. -void* VG_(OSet_Lookup)(AvlTree* t, void* k) +void* VG_(OSetGen_Lookup)(AvlTree* t, void* k) { AvlNode* n; vg_assert(t); @@ -503,7 +521,7 @@ void* VG_(OSet_Lookup)(AvlTree* t, void* k) // Find the *element* in t matching k, or NULL if not found; use the given // comparison function rather than the standard one. -void* VG_(OSet_LookupWithCmp)(AvlTree* t, void* k, OSetCmp_t cmp) +void* VG_(OSetGen_LookupWithCmp)(AvlTree* t, void* k, OSetCmp_t cmp) { // Save the normal one to the side, then restore once we're done. void* e; @@ -511,15 +529,20 @@ void* VG_(OSet_LookupWithCmp)(AvlTree* t, void* k, OSetCmp_t cmp) vg_assert(t); tmpcmp = t->cmp; t->cmp = cmp; - e = VG_(OSet_Lookup)(t, k); + e = VG_(OSetGen_Lookup)(t, k); t->cmp = tmpcmp; return e; } // Is there an element matching k? -Bool VG_(OSet_Contains)(AvlTree* t, void* k) +Bool VG_(OSetGen_Contains)(AvlTree* t, void* k) { - return (NULL != VG_(OSet_Lookup)(t, k)); + return (NULL != VG_(OSetGen_Lookup)(t, k)); +} + +Bool VG_(OSetWord_Contains)(AvlTree* t, Word val) +{ + return (NULL != VG_(OSetGen_Lookup)(t, &val)); } /*--------------------------------------------------------------------*/ @@ -650,7 +673,7 @@ static Bool avl_removeroot(AvlTree* t) } // Remove and return the element matching the key 'k', or NULL if not present. -void* VG_(OSet_Remove)(AvlTree* t, void* k) +void* VG_(OSetGen_Remove)(AvlTree* t, void* k) { // Have to find the node first, then remove it. AvlNode* n = avl_lookup(t, k); @@ -664,15 +687,26 @@ void* VG_(OSet_Remove)(AvlTree* t, void* k) } } +Bool VG_(OSetWord_Remove)(AvlTree* t, Word val) +{ + void* n = VG_(OSetGen_Remove)(t, &val); + if (n) { + VG_(OSetGen_FreeNode)(t, n); + return True; + } else { + return False; + } +} + /*--------------------------------------------------------------------*/ /*--- Iterator ---*/ /*--------------------------------------------------------------------*/ // The iterator is implemented using in-order traversal with an explicit // stack, which lets us do the traversal one step at a time and remember -// where we are between each call to OSet_Next(). +// where we are between each call to OSetGen_Next(). -void VG_(OSet_ResetIter)(AvlTree* t) +void VG_(OSetGen_ResetIter)(AvlTree* t) { vg_assert(t); stackClear(t); @@ -680,7 +714,12 @@ void VG_(OSet_ResetIter)(AvlTree* t) stackPush(t, t->root, 1); } -void* VG_(OSet_Next)(AvlTree* t) +void VG_(OSetWord_ResetIter)(AvlTree* t) +{ + VG_(OSetGen_ResetIter)(t); +} + +void* VG_(OSetGen_Next)(AvlTree* t) { Int i = 0; OSetNode* n = NULL; @@ -710,16 +749,32 @@ void* VG_(OSet_Next)(AvlTree* t) return NULL; } +Bool VG_(OSetWord_Next)(AvlTree* t, Word* val) +{ + Word* n = VG_(OSetGen_Next)(t); + if (n) { + *val = *n; + return True; + } else { + return False; + } +} + /*--------------------------------------------------------------------*/ /*--- Miscellaneous operations ---*/ /*--------------------------------------------------------------------*/ -Int VG_(OSet_Size)(AvlTree* t) +Int VG_(OSetGen_Size)(AvlTree* t) { vg_assert(t); return t->nElems; } +Int VG_(OSetWord_Size)(AvlTree* t) +{ + return VG_(OSetGen_Size)(t); +} + static void OSet_Print2( AvlTree* t, AvlNode* n, Char*(*strElem)(void *), Int p ) { diff --git a/coregrind/m_redir.c b/coregrind/m_redir.c index 057924dbbe..5a3a44123c 100644 --- a/coregrind/m_redir.c +++ b/coregrind/m_redir.c @@ -544,7 +544,7 @@ static void maybe_add_active ( Active act ) goto bad; } - old = VG_(OSet_Lookup)( activeSet, &act.from_addr ); + old = VG_(OSetGen_Lookup)( activeSet, &act.from_addr ); if (old) { /* Dodgy. Conflicting binding. */ vg_assert(old->from_addr == act.from_addr); @@ -559,10 +559,10 @@ static void maybe_add_active ( Active act ) /* XXXXXXXXXXX COMPLAIN if new and old parents differ */ } } else { - Active* a = VG_(OSet_AllocNode)(activeSet, sizeof(Active)); + Active* a = VG_(OSetGen_AllocNode)(activeSet, sizeof(Active)); vg_assert(a); *a = act; - VG_(OSet_Insert)(activeSet, a); + VG_(OSetGen_Insert)(activeSet, a); /* Now that a new from->to redirection is in force, we need to get rid of any translations intersecting 'from' in order that they get redirected to 'to'. So discard them. Just for @@ -597,7 +597,7 @@ void VG_(redir_notify_delete_SegInfo)( SegInfo* delsi ) OSet* tmpSet; Active* act; Bool delMe; - Addr* addrP; + Addr addr; vg_assert(delsi); @@ -617,13 +617,12 @@ void VG_(redir_notify_delete_SegInfo)( SegInfo* delsi ) /* Traverse the actives, copying the addresses of those we intend to delete into tmpSet. */ - tmpSet = VG_(OSet_Create)( 0/*keyOff*/, NULL/*fastCmp*/, - symtab_alloc, symtab_free); + tmpSet = VG_(OSetWord_Create)(symtab_alloc, symtab_free); ts->mark = True; - VG_(OSet_ResetIter)( activeSet ); - while ( (act = VG_(OSet_Next)(activeSet)) ) { + VG_(OSetGen_ResetIter)( activeSet ); + while ( (act = VG_(OSetGen_Next)(activeSet)) ) { delMe = act->parent_spec != NULL && act->parent_sym != NULL && act->parent_spec->seginfo != NULL @@ -644,9 +643,7 @@ void VG_(redir_notify_delete_SegInfo)( SegInfo* delsi ) } if (delMe) { - addrP = VG_(OSet_AllocNode)( tmpSet, sizeof(Addr) ); - *addrP = act->from_addr; - VG_(OSet_Insert)( tmpSet, addrP ); + VG_(OSetWord_Insert)( tmpSet, act->from_addr ); /* While we have our hands on both the 'from' and 'to' of this Active, do paranoid stuff with tt/tc. */ VG_(discard_translations)( (Addr64)act->from_addr, 1, @@ -656,16 +653,15 @@ void VG_(redir_notify_delete_SegInfo)( SegInfo* delsi ) } } - /* Now traverse tmpSet, deleting corresponding elements in - activeSet. */ - VG_(OSet_ResetIter)( tmpSet ); - while ( (addrP = VG_(OSet_Next)(tmpSet)) ) { - act = VG_(OSet_Remove)( activeSet, addrP ); + /* Now traverse tmpSet, deleting corresponding elements in activeSet. */ + VG_(OSetWord_ResetIter)( tmpSet ); + while ( VG_(OSetWord_Next)(tmpSet, &addr) ) { + act = VG_(OSetGen_Remove)( activeSet, &addr ); vg_assert(act); - VG_(OSet_FreeNode)( activeSet, act ); + VG_(OSetGen_FreeNode)( activeSet, act ); } - VG_(OSet_Destroy)( tmpSet, NULL ); + VG_(OSetWord_Destroy)( tmpSet ); /* The Actives set is now cleaned up. Free up this TopSpec and everything hanging off it. */ @@ -698,7 +694,7 @@ void VG_(redir_notify_delete_SegInfo)( SegInfo* delsi ) just before translating a basic block. */ Addr VG_(redir_do_lookup) ( Addr orig, Bool* isWrap ) { - Active* r = VG_(OSet_Lookup)(activeSet, &orig); + Active* r = VG_(OSetGen_Lookup)(activeSet, &orig); if (r == NULL) return orig; @@ -776,10 +772,10 @@ void VG_(redir_initialise) ( void ) vg_assert( VG_(next_seginfo)(NULL) == NULL ); // Initialise active mapping. - activeSet = VG_(OSet_Create)(offsetof(Active, from_addr), - NULL, // Use fast comparison - symtab_alloc, - symtab_free); + activeSet = VG_(OSetGen_Create)(offsetof(Active, from_addr), + NULL, // Use fast comparison + symtab_alloc, + symtab_free); // The rest of this function just adds initial Specs. @@ -1003,8 +999,8 @@ static void show_redir_state ( HChar* who ) show_spec(" ", sp); } VG_(message)(Vg_DebugMsg, " ------ ACTIVE ------"); - VG_(OSet_ResetIter)( activeSet ); - while ( (act = VG_(OSet_Next)(activeSet)) ) { + VG_(OSetGen_ResetIter)( activeSet ); + while ( (act = VG_(OSetGen_Next)(activeSet)) ) { show_active(" ", act); } diff --git a/include/pub_tool_oset.h b/include/pub_tool_oset.h index e49f4d51e3..860a277183 100644 --- a/include/pub_tool_oset.h +++ b/include/pub_tool_oset.h @@ -36,23 +36,31 @@ // elements. It does not allow duplicates, and will assert if you insert a // duplicate to an OSet. // -// The structure is totally generic. The user provides the allocation and -// deallocation functions. Also, each element has a key, which the lookup -// is done with. The key may be the whole element (eg. in an OSet of -// integers, each integer serves both as an element and a key), or it may be -// only part of it (eg. if the key is a single field in a struct). The user -// can provide a function that compares an element with a key; this is very -// flexible, and with the right comparison function even a (non-overlapping) -// interval list can be created. But the cost of calling a function for -// every comparison can be high during lookup. If no comparison function is -// provided, we assume that keys are (signed or unsigned) words, and that -// the key is the first word in each element. This fast comparison is -// suitable for an OSet of Words, or an OSet containing structs where the -// first element is an Addr, for example. -// -// Each OSet also has an iterator, which makes it simple to traverse all the -// nodes in order. Note that the iterator maintains state and so is -// non-reentrant. +// It has two interfaces. +// +// - The "OSetWord_" interface provides an easier-to-use interface for the +// case where you just want to store Word-sized values. The user provides +// the allocation and deallocation functions, and possibly a comparison +// function. +// +// - The "OSetGen_" interface provides a totally generic interface, which +// allows any kind of structure to be put into the set. The user provides +// the allocation and deallocation functions. Also, each element has a +// key, which the lookup is done with. The key may be the whole element +// (eg. in an OSet of integers, each integer serves both as an element and +// a key), or it may be only part of it (eg. if the key is a single field +// in a struct). The user can provide a function that compares an element +// with a key; this is very flexible, and with the right comparison +// function even a (non-overlapping) interval list can be created. But +// the cost of calling a function for every comparison can be high during +// lookup. If no comparison function is provided, we assume that keys are +// (signed or unsigned) words, and that the key is the first word in each +// element. This fast comparison is suitable for an OSet containing +// structs where the first element is an Addr, for example. +// +// Each OSet interface also has an iterator, which makes it simple to +// traverse all the nodes in order. Note that the iterator maintains state +// and so is non-reentrant. // // Note that once you insert an element into an OSet, if you modify any part // of it looked at by your cmp() function, this may cause incorrect @@ -63,15 +71,86 @@ /*--------------------------------------------------------------------*/ typedef struct _OSet OSet; -typedef struct _OSetNode OSetNode; + +// - Cmp: returns -1, 0 or 1 if key is <=, == or >= elem. +// - Alloc: allocates a chunk of memory. +// - Free: frees a chunk of memory allocated with Alloc. typedef Word (*OSetCmp_t) ( void* key, void* elem ); typedef void* (*OSetAlloc_t) ( SizeT szB ); typedef void (*OSetFree_t) ( void* p ); -typedef void (*OSetNodeDestroy_t) ( void* elem ); /*--------------------------------------------------------------------*/ -/*--- Creating and destroying OSets and OSet members ---*/ +/*--- Creating and destroying OSets (Word) ---*/ +/*--------------------------------------------------------------------*/ + +// * Create: allocates and initialises the OSet. Arguments: +// - alloc The allocation function used internally for allocating the +// OSet and all its nodes. +// - free The deallocation function used internally for freeing nodes +// called by VG_(OSetWord_Destroy)(). +// +// * CreateWithCmp: like Create, but you specify your own comparison +// function. +// +// * Destroy: frees all nodes in the table, plus the memory used by +// the table itself. The passed-in function is called on each node first +// to allow the destruction of any attached resources; if NULL it is not +// called. + +extern OSet* VG_(OSetWord_Create) ( OSetAlloc_t alloc, OSetFree_t free ); +extern void VG_(OSetWord_Destroy) ( OSet* os ); + +/*--------------------------------------------------------------------*/ +/*--- Operations on OSets (Word) ---*/ +/*--------------------------------------------------------------------*/ + +// In everything that follows, the parameter 'key' is always the *address* +// of the key, and 'elem' is *address* of the elem, as are the return values +// of the functions that return elems. +// +// * Size: The number of elements in the set. +// +// * Contains: Determines if the value is in the set. +// +// * Insert: Inserts a new element into the set. Duplicates are forbidden, +// and will cause assertion failures. +// +// * Remove: Removes the value from the set, if present. Returns a Bool +// indicating if the value was removed. +// +// * ResetIter: Each OSet has an iterator. This resets it to point to the +// first element in the OSet. +// +// * Next: Copies the next value according to the OSet's iterator into &val, +// advances the iterator by one, and returns True; the elements are +// visited in order. Or, returns False if the iterator has reached the +// set's end. +// +// You can thus iterate in order through a set like this: +// +// Word val; +// VG_(OSetWord_ResetIter)(oset); +// while ( VG_(OSetWord_Next)(oset, &val) ) { +// ... do stuff with 'val' ... +// } +// +// Note that iterators are cleared any time an element is inserted or +// removed from the OSet, to avoid possible mayhem caused by the iterator +// getting out of sync with the OSet's contents. "Cleared" means that +// they will return False if VG_(OSetWord_Next)() is called without an +// intervening call to VG_(OSetWord_ResetIter)(). + +extern Int VG_(OSetWord_Size) ( OSet* os ); +extern void VG_(OSetWord_Insert) ( OSet* os, Word val ); +extern Bool VG_(OSetWord_Contains) ( OSet* os, Word val ); +extern Bool VG_(OSetWord_Remove) ( OSet* os, Word val ); +extern void VG_(OSetWord_ResetIter) ( OSet* os ); +extern Bool VG_(OSetWord_Next) ( OSet* os, Word* val ); + + +/*--------------------------------------------------------------------*/ +/*--- Creating and destroying OSets and OSet members (Gen) ---*/ /*--------------------------------------------------------------------*/ // * Create: allocates and initialises the OSet. Arguments: @@ -79,9 +158,10 @@ typedef void (*OSetNodeDestroy_t) ( void* elem ); // - cmp The comparison function between keys and elements, or NULL // if the OSet should use fast comparisons. // - alloc The allocation function used for allocating the OSet itself; -// it's also called for each invocation of VG_(OSet_AllocNode)(). -// - free The deallocation function used by VG_(OSet_FreeNode)() and -// VG_(OSet_Destroy)(). +// it's also called for each invocation of +// VG_(OSetGen_AllocNode)(). +// - free The deallocation function used by VG_(OSetGen_FreeNode)() and +// VG_(OSetGen_Destroy)(). // // If cmp is NULL, keyOff must be zero. This is checked. // @@ -91,25 +171,25 @@ typedef void (*OSetNodeDestroy_t) ( void* elem ); // called. // // * AllocNode: Allocate and zero memory for a node to go into the OSet. -// Uses the alloc function given to VG_(OSet_Create)() to allocated a node -// which is big enough for both an element and the OSet metadata. +// Uses the alloc function given to VG_(OSetGen_Create)() to allocated a +// node which is big enough for both an element and the OSet metadata. // Not all elements in one OSet have to be the same size. // // Note that the element allocated will be at most word-aligned, which may // be less aligned than the element type would normally be. // -// * FreeNode: Deallocate a node allocated with OSet_AllocNode(). Using +// * FreeNode: Deallocate a node allocated with OSetGen_AllocNode(). Using // a deallocation function (such as VG_(free)()) directly will likely // lead to assertions in Valgrind's allocator. -extern OSet* VG_(OSet_Create) ( OffT keyOff, OSetCmp_t cmp, - OSetAlloc_t alloc, OSetFree_t free ); -extern void VG_(OSet_Destroy) ( OSet* os, OSetNodeDestroy_t destroyNode ); -extern void* VG_(OSet_AllocNode) ( OSet* os, SizeT elemSize ); -extern void VG_(OSet_FreeNode) ( OSet* os, void* elem ); +extern OSet* VG_(OSetGen_Create) ( OffT keyOff, OSetCmp_t cmp, + OSetAlloc_t alloc, OSetFree_t free ); +extern void VG_(OSetGen_Destroy) ( OSet* os ); +extern void* VG_(OSetGen_AllocNode) ( OSet* os, SizeT elemSize ); +extern void VG_(OSetGen_FreeNode) ( OSet* os, void* elem ); /*--------------------------------------------------------------------*/ -/*--- Operations on OSets ---*/ +/*--- Operations on OSets (Gen) ---*/ /*--------------------------------------------------------------------*/ // In everything that follows, the parameter 'key' is always the *address* @@ -118,6 +198,11 @@ extern void VG_(OSet_FreeNode) ( OSet* os, void* elem ); // // * Size: The number of elements in the set. // +// * Insert: Inserts a new element into the set. Note that 'elem' must +// have been allocated using VG_(OSetGen_AllocNode)(), otherwise you will +// get assertion failures about "bad magic". Duplicates are forbidden, +// and will also cause assertion failures. +// // * Contains: Determines if any element in the OSet matches the key. // // * Lookup: Returns a pointer to the element matching the key, if there is @@ -126,11 +211,6 @@ extern void VG_(OSet_FreeNode) ( OSet* os, void* elem ); // * LookupWithCmp: Like Lookup, but you specify the comparison function, // which overrides the OSet's normal one. // -// * Insert: Inserts a new element into the list. Note that 'elem' must -// have been allocated using VG_(OSet_AllocNode)(), otherwise you will get -// assertion failures about "bad magic". Duplicates are forbidden, and -// will also cause assertion failures. -// // * Remove: Removes the element matching the key, if there is one. Returns // NULL if no element matches the key. // @@ -141,27 +221,27 @@ extern void VG_(OSet_FreeNode) ( OSet* os, void* elem ); // iterator, and advances the iterator by one; the elements are visited // in order. Or, returns NULL if the iterator has reached the OSet's end. // -// You can thus iterate in order through an OSet like this: +// You can thus iterate in order through a set like this: // -// VG_(OSet_ResetIter)(oset); -// while ( (elem = VG_(OSet_Next)(oset)) ) { +// VG_(OSetGen_ResetIter)(oset); +// while ( (elem = VG_(OSetGen_Next)(oset)) ) { // ... do stuff with 'elem' ... // } // // Note that iterators are cleared any time an element is inserted or // removed from the OSet, to avoid possible mayhem caused by the iterator // getting out of sync with the OSet's contents. "Cleared" means that -// they will return NULL if VG_(OSet_Next)() is called without an -// intervening call to VG_(OSet_ResetIter)(). - -extern Int VG_(OSet_Size) ( OSet* os ); -extern void VG_(OSet_Insert) ( OSet* os, void* elem ); -extern Bool VG_(OSet_Contains) ( OSet* os, void* key ); -extern void* VG_(OSet_Lookup) ( OSet* os, void* key ); -extern void* VG_(OSet_LookupWithCmp)( OSet* os, void* key, OSetCmp_t cmp ); -extern void* VG_(OSet_Remove) ( OSet* os, void* key ); -extern void VG_(OSet_ResetIter) ( OSet* os ); -extern void* VG_(OSet_Next) ( OSet* os ); +// they will return NULL if VG_(OSetGen_Next)() is called without an +// intervening call to VG_(OSetGen_ResetIter)(). + +extern Int VG_(OSetGen_Size) ( OSet* os ); +extern void VG_(OSetGen_Insert) ( OSet* os, void* elem ); +extern Bool VG_(OSetGen_Contains) ( OSet* os, void* key ); +extern void* VG_(OSetGen_Lookup) ( OSet* os, void* key ); +extern void* VG_(OSetGen_LookupWithCmp)( OSet* os, void* key, OSetCmp_t cmp ); +extern void* VG_(OSetGen_Remove) ( OSet* os, void* key ); +extern void VG_(OSetGen_ResetIter) ( OSet* os ); +extern void* VG_(OSetGen_Next) ( OSet* os ); #endif // __PUB_TOOL_OSET_H diff --git a/memcheck/mc_main.c b/memcheck/mc_main.c index a553f92e5e..5a39efed1b 100644 --- a/memcheck/mc_main.c +++ b/memcheck/mc_main.c @@ -387,9 +387,9 @@ static void init_auxmap_L1_L2 ( void ) tl_assert(0 == offsetof(AuxMapEnt,base)); tl_assert(sizeof(Addr) == sizeof(void*)); - auxmap_L2 = VG_(OSet_Create)( /*keyOff*/ offsetof(AuxMapEnt,base), - /*fastCmp*/ NULL, - VG_(malloc), VG_(free) ); + auxmap_L2 = VG_(OSetGen_Create)( /*keyOff*/ offsetof(AuxMapEnt,base), + /*fastCmp*/ NULL, + VG_(malloc), VG_(free) ); } /* Check representation invariants; if OK return NULL; else a @@ -418,7 +418,7 @@ static HChar* check_auxmap_L1_L2_sanity ( Word* n_secmaps_found ) *n_secmaps_found = 0; if (sizeof(void*) == 4) { /* 32-bit platform */ - if (VG_(OSet_Size)(auxmap_L2) != 0) + if (VG_(OSetGen_Size)(auxmap_L2) != 0) return "32-bit: auxmap_L2 is non-empty"; for (i = 0; i < N_AUXMAP_L1; i++) if (auxmap_L1[i].base != 0 || auxmap_L1[i].ent != NULL) @@ -429,8 +429,8 @@ static HChar* check_auxmap_L1_L2_sanity ( Word* n_secmaps_found ) AuxMapEnt *elem, *res; AuxMapEnt key; /* L2 table */ - VG_(OSet_ResetIter)(auxmap_L2); - while ( (elem = VG_(OSet_Next)(auxmap_L2)) ) { + VG_(OSetGen_ResetIter)(auxmap_L2); + while ( (elem = VG_(OSetGen_Next)(auxmap_L2)) ) { elems_seen++; if (0 != (elem->base & (Addr)0xFFFF)) return "64-bit: nonzero .base & 0xFFFF in auxmap_L2"; @@ -458,7 +458,7 @@ static HChar* check_auxmap_L1_L2_sanity ( Word* n_secmaps_found ) /* Look it up in auxmap_L2. */ key.base = auxmap_L1[i].base; key.sm = 0; - res = VG_(OSet_Lookup)(auxmap_L2, &key); + res = VG_(OSetGen_Lookup)(auxmap_L2, &key); if (res == NULL) return "64-bit: _L1 .base not found in _L2"; if (res != auxmap_L1[i].ent) @@ -544,7 +544,7 @@ static INLINE AuxMapEnt* maybe_find_in_auxmap ( Addr a ) key.base = a; key.sm = 0; - res = VG_(OSet_Lookup)(auxmap_L2, &key); + res = VG_(OSetGen_Lookup)(auxmap_L2, &key); if (res) insert_into_auxmap_L1_at( AUXMAP_L1_INSERT_IX, res ); return res; @@ -563,11 +563,11 @@ static AuxMapEnt* find_or_alloc_in_auxmap ( Addr a ) to allocate one. */ a &= ~(Addr)0xFFFF; - nyu = (AuxMapEnt*) VG_(OSet_AllocNode)( auxmap_L2, sizeof(AuxMapEnt) ); + nyu = (AuxMapEnt*) VG_(OSetGen_AllocNode)( auxmap_L2, sizeof(AuxMapEnt) ); tl_assert(nyu); nyu->base = a; nyu->sm = &sm_distinguished[SM_DIST_NOACCESS]; - VG_(OSet_Insert)( auxmap_L2, nyu ); + VG_(OSetGen_Insert)( auxmap_L2, nyu ); insert_into_auxmap_L1_at( AUXMAP_L1_INSERT_IX, nyu ); n_auxmap_L2_nodes++; return nyu; @@ -879,9 +879,9 @@ typedef static OSet* createSecVBitTable(void) { - return VG_(OSet_Create)( offsetof(SecVBitNode, a), - NULL, // use fast comparisons - VG_(malloc), VG_(free) ); + return VG_(OSetGen_Create)( offsetof(SecVBitNode, a), + NULL, // use fast comparisons + VG_(malloc), VG_(free) ); } static void gcSecVBitTable(void) @@ -896,8 +896,8 @@ static void gcSecVBitTable(void) secVBitTable2 = createSecVBitTable(); // Traverse the table, moving fresh nodes into the new table. - VG_(OSet_ResetIter)(secVBitTable); - while ( (n = VG_(OSet_Next)(secVBitTable)) ) { + VG_(OSetGen_ResetIter)(secVBitTable); + while ( (n = VG_(OSetGen_Next)(secVBitTable)) ) { Bool keep = False; if ( (GCs_done - n->last_touched) <= MAX_STALE_AGE ) { // Keep node if it's been touched recently enough (regardless of @@ -918,18 +918,18 @@ static void gcSecVBitTable(void) if ( keep ) { // Insert a copy of the node into the new table. SecVBitNode* n2 = - VG_(OSet_AllocNode)(secVBitTable2, sizeof(SecVBitNode)); + VG_(OSetGen_AllocNode)(secVBitTable2, sizeof(SecVBitNode)); *n2 = *n; - VG_(OSet_Insert)(secVBitTable2, n2); + VG_(OSetGen_Insert)(secVBitTable2, n2); } } // Get the before and after sizes. - n_nodes = VG_(OSet_Size)(secVBitTable); - n_survivors = VG_(OSet_Size)(secVBitTable2); + n_nodes = VG_(OSetGen_Size)(secVBitTable); + n_survivors = VG_(OSetGen_Size)(secVBitTable2); // Destroy the old table, and put the new one in its place. - VG_(OSet_Destroy)(secVBitTable, NULL); + VG_(OSetGen_Destroy)(secVBitTable); secVBitTable = secVBitTable2; if (VG_(clo_verbosity) > 1) { @@ -952,7 +952,7 @@ static UWord get_sec_vbits8(Addr a) { Addr aAligned = VG_ROUNDDN(a, BYTES_PER_SEC_VBIT_NODE); Int amod = a % BYTES_PER_SEC_VBIT_NODE; - SecVBitNode* n = VG_(OSet_Lookup)(secVBitTable, &aAligned); + SecVBitNode* n = VG_(OSetGen_Lookup)(secVBitTable, &aAligned); UChar vbits8; tl_assert2(n, "get_sec_vbits8: no node for address %p (%p)\n", aAligned, a); // Shouldn't be fully defined or fully undefined -- those cases shouldn't @@ -966,7 +966,7 @@ static void set_sec_vbits8(Addr a, UWord vbits8) { Addr aAligned = VG_ROUNDDN(a, BYTES_PER_SEC_VBIT_NODE); Int i, amod = a % BYTES_PER_SEC_VBIT_NODE; - SecVBitNode* n = VG_(OSet_Lookup)(secVBitTable, &aAligned); + SecVBitNode* n = VG_(OSetGen_Lookup)(secVBitTable, &aAligned); // Shouldn't be fully defined or fully undefined -- those cases shouldn't // make it to the secondary V bits table. tl_assert(V_BITS8_DEFINED != vbits8 && V_BITS8_UNDEFINED != vbits8); @@ -977,7 +977,7 @@ static void set_sec_vbits8(Addr a, UWord vbits8) } else { // New node: assign the specific byte, make the rest invalid (they // should never be read as-is, but be cautious). - n = VG_(OSet_AllocNode)(secVBitTable, sizeof(SecVBitNode)); + n = VG_(OSetGen_AllocNode)(secVBitTable, sizeof(SecVBitNode)); n->a = aAligned; for (i = 0; i < BYTES_PER_SEC_VBIT_NODE; i++) { n->vbits8[i] = V_BITS8_UNDEFINED; @@ -987,15 +987,15 @@ static void set_sec_vbits8(Addr a, UWord vbits8) // Do a table GC if necessary. Nb: do this before inserting the new // node, to avoid erroneously GC'ing the new node. - if (secVBitLimit == VG_(OSet_Size)(secVBitTable)) { + if (secVBitLimit == VG_(OSetGen_Size)(secVBitTable)) { gcSecVBitTable(); } // Insert the new node. - VG_(OSet_Insert)(secVBitTable, n); + VG_(OSetGen_Insert)(secVBitTable, n); sec_vbits_new_nodes++; - n_secVBit_nodes = VG_(OSet_Size)(secVBitTable); + n_secVBit_nodes = VG_(OSetGen_Size)(secVBitTable); if (n_secVBit_nodes > max_secVBit_nodes) max_secVBit_nodes = n_secVBit_nodes; } @@ -4316,7 +4316,7 @@ static Bool mc_expensive_sanity_check ( void ) /* If we're not checking for undefined value errors, the secondary V bit * table should be empty. */ if (!MC_(clo_undef_value_errors)) { - if (0 != VG_(OSet_Size)(secVBitTable)) + if (0 != VG_(OSetGen_Size)(secVBitTable)) return False; } diff --git a/memcheck/tests/oset_test.c b/memcheck/tests/oset_test.c index 50ecdb146c..b2b95794d4 100644 --- a/memcheck/tests/oset_test.c +++ b/memcheck/tests/oset_test.c @@ -77,23 +77,24 @@ void example1(void) // Create a static OSet of Ints. This one uses fast (built-in) // comparisons. - OSet* oset1 = VG_(OSet_Create)(0, + OSet* oset = VG_(OSetGen_Create)(0, NULL, (void*)malloc, free); // Try some operations on an empty OSet to ensure they don't screw up. - vg_assert( ! VG_(OSet_Contains)(oset1, &v) ); - vg_assert( ! VG_(OSet_Lookup)(oset1, &v) ); - vg_assert( ! VG_(OSet_Remove)(oset1, &v) ); - vg_assert( ! VG_(OSet_Next)(oset1) ); - vg_assert( 0 == VG_(OSet_Size)(oset1) ); + vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); + vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); + vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); + vg_assert( ! VG_(OSetGen_Next)(oset) ); + vg_assert( 0 == VG_(OSetGen_Size)(oset) ); // Create some elements, with gaps (they're all even) but no dups, // and shuffle them randomly. for (i = 0; i < NN; i++) { - vs[i] = VG_(OSet_AllocNode)(oset1, sizeof(Word)); + vs[i] = VG_(OSetGen_AllocNode)(oset, sizeof(Word)); *(vs[i]) = 2*i; } + seed = 0; for (i = 0; i < NN; i++) { Word r1 = myrandom() % NN; Word r2 = myrandom() % NN; @@ -104,32 +105,32 @@ void example1(void) // Insert the elements for (i = 0; i < NN; i++) { - VG_(OSet_Insert)(oset1, vs[i]); + VG_(OSetGen_Insert)(oset, vs[i]); } // Check the size - vg_assert( NN == VG_(OSet_Size)(oset1) ); + vg_assert( NN == VG_(OSetGen_Size)(oset) ); // Check we can find all the elements we inserted for (i = 0; i < NN; i++) { - assert( VG_(OSet_Contains)(oset1, vs[i]) ); + assert( VG_(OSetGen_Contains)(oset, vs[i]) ); } // Check we cannot find elements we did not insert, below, within (odd // numbers), and above the inserted elements. v = -1; - assert( ! VG_(OSet_Contains)(oset1, &v) ); + assert( ! VG_(OSetGen_Contains)(oset, &v) ); for (i = 0; i < NN; i++) { v = *(vs[i]) + 1; - assert( ! VG_(OSet_Contains)(oset1, &v) ); + assert( ! VG_(OSetGen_Contains)(oset, &v) ); } v = NN*2; - assert( ! VG_(OSet_Contains)(oset1, &v) ); + assert( ! VG_(OSetGen_Contains)(oset, &v) ); // Check we can find all the elements we inserted, and the right values // are returned. for (i = 0; i < NN; i++) { - assert( vs[i] == VG_(OSet_Lookup)(oset1, vs[i]) ); + assert( vs[i] == VG_(OSetGen_Lookup)(oset, vs[i]) ); } // Check that we can iterate over the OSet elements in sorted order, and @@ -137,67 +138,186 @@ void example1(void) n = 0; pv = NULL; prev = -1; - VG_(OSet_ResetIter)(oset1); - while ( (pv = VG_(OSet_Next)(oset1)) ) { + VG_(OSetGen_ResetIter)(oset); + while ( (pv = VG_(OSetGen_Next)(oset)) ) { Word curr = *pv; assert(prev < curr); prev = curr; n++; } assert(NN == n); - vg_assert( ! VG_(OSet_Next)(oset1) ); - vg_assert( ! VG_(OSet_Next)(oset1) ); + vg_assert( ! VG_(OSetGen_Next)(oset) ); + vg_assert( ! VG_(OSetGen_Next)(oset) ); // Check that we can remove half of the elements, and that their values // are as expected. for (i = 0; i < NN; i += 2) { - assert( pv = VG_(OSet_Remove)(oset1, vs[i]) ); + assert( pv = VG_(OSetGen_Remove)(oset, vs[i]) ); assert( pv == vs[i] ); } // Check the size - vg_assert( NN/2 == VG_(OSet_Size)(oset1) ); + vg_assert( NN/2 == VG_(OSetGen_Size)(oset) ); // Check we can find the remaining elements (with the right values). for (i = 1; i < NN; i += 2) { - assert( pv = VG_(OSet_LookupWithCmp)(oset1, vs[i], NULL) ); + assert( pv = VG_(OSetGen_LookupWithCmp)(oset, vs[i], NULL) ); assert( pv == vs[i] ); } // Check we cannot find any of the elements we removed. for (i = 0; i < NN; i += 2) { - assert( ! VG_(OSet_Contains)(oset1, vs[i]) ); + assert( ! VG_(OSetGen_Contains)(oset, vs[i]) ); } // Check that we can remove the remaining half of the elements, and that // their values are as expected. for (i = 1; i < NN; i += 2) { - assert( pv = VG_(OSet_Remove)(oset1, vs[i]) ); + assert( pv = VG_(OSetGen_Remove)(oset, vs[i]) ); assert( pv == vs[i] ); } // Try some more operations on the empty OSet to ensure they don't screw up. - vg_assert( ! VG_(OSet_Contains)(oset1, &v) ); - vg_assert( ! VG_(OSet_Lookup)(oset1, &v) ); - vg_assert( ! VG_(OSet_Remove)(oset1, &v) ); - vg_assert( ! VG_(OSet_Next)(oset1) ); - vg_assert( 0 == VG_(OSet_Size)(oset1) ); + vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); + vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); + vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); + vg_assert( ! VG_(OSetGen_Next)(oset) ); + vg_assert( 0 == VG_(OSetGen_Size)(oset) ); // Free a few elements - VG_(OSet_FreeNode)(oset1, vs[0]); - VG_(OSet_FreeNode)(oset1, vs[1]); - VG_(OSet_FreeNode)(oset1, vs[2]); + VG_(OSetGen_FreeNode)(oset, vs[0]); + VG_(OSetGen_FreeNode)(oset, vs[1]); + VG_(OSetGen_FreeNode)(oset, vs[2]); - // Re-insert remaining elements, to give OSet_Destroy something to work with. + // Re-insert remaining elements, to give OSetGen_Destroy something to + // work with. for (i = 3; i < NN; i++) { - VG_(OSet_Insert)(oset1, vs[i]); + VG_(OSetGen_Insert)(oset, vs[i]); } // Print the list - OSet_Print(oset1, "foo", wordToStr); + OSet_Print(oset, "oset1", wordToStr); // Destroy the OSet - VG_(OSet_Destroy)(oset1, NULL); + VG_(OSetGen_Destroy)(oset); +} + + +void example1b(void) +{ + Int i, n; + Word v = 0, prev; + Word vs[NN]; + Word *pv; + + // Create a static OSet of Ints. This one uses fast (built-in) + // comparisons. + OSet* oset = VG_(OSetWord_Create)( (void*)malloc, free); + + // Try some operations on an empty OSet to ensure they don't screw up. + vg_assert( ! VG_(OSetWord_Contains)(oset, v) ); + vg_assert( ! VG_(OSetWord_Remove)(oset, v) ); + vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); + vg_assert( 0 == VG_(OSetWord_Size)(oset) ); + + // Create some elements, with gaps (they're all even) but no dups, + // and shuffle them randomly. + for (i = 0; i < NN; i++) { + vs[i] = 2*i; + } + seed = 0; + for (i = 0; i < NN; i++) { + Word r1 = myrandom() % NN; + Word r2 = myrandom() % NN; + Word tmp = vs[r1]; + vs[r1] = vs[r2]; + vs[r2] = tmp; + } + + // Insert the elements + for (i = 0; i < NN; i++) { + VG_(OSetWord_Insert)(oset, vs[i]); + } + + // Check the size + vg_assert( NN == VG_(OSetWord_Size)(oset) ); + + // Check we can find all the elements we inserted + for (i = 0; i < NN; i++) { + assert( VG_(OSetWord_Contains)(oset, vs[i]) ); + } + + // Check we cannot find elements we did not insert, below, within (odd + // numbers), and above the inserted elements. + v = -1; + assert( ! VG_(OSetWord_Contains)(oset, v) ); + for (i = 0; i < NN; i++) { + v = vs[i] + 1; + assert( ! VG_(OSetWord_Contains)(oset, v) ); + } + v = NN*2; + assert( ! VG_(OSetWord_Contains)(oset, v) ); + + // Check we can find all the elements we inserted. + for (i = 0; i < NN; i++) { + assert( VG_(OSetWord_Contains)(oset, vs[i]) ); + } + + // Check that we can iterate over the OSet elements in sorted order, and + // there is the right number of them. + n = 0; + prev = -1; + VG_(OSetWord_ResetIter)(oset); + while ( VG_(OSetWord_Next)(oset, &v) ) { + Word curr = v; + assert(prev < curr); + prev = curr; + n++; + } + assert(NN == n); + vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); + vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); + + // Check that we can remove half of the elements. + for (i = 0; i < NN; i += 2) { + assert( VG_(OSetWord_Remove)(oset, vs[i]) ); + } + + // Check the size + vg_assert( NN/2 == VG_(OSetWord_Size)(oset) ); + + // Check we can find the remaining elements (with the right values). + for (i = 1; i < NN; i += 2) { + assert( VG_(OSetWord_Contains)(oset, vs[i]) ); + } + + // Check we cannot find any of the elements we removed. + for (i = 0; i < NN; i += 2) { + assert( ! VG_(OSetWord_Contains)(oset, vs[i]) ); + } + + // Check that we can remove the remaining half of the elements. + for (i = 1; i < NN; i += 2) { + assert( VG_(OSetWord_Remove)(oset, vs[i]) ); + } + + // Try some more operations on the empty OSet to ensure they don't screw up. + vg_assert( ! VG_(OSetWord_Contains)(oset, v) ); + vg_assert( ! VG_(OSetWord_Remove)(oset, v) ); + vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); + vg_assert( 0 == VG_(OSetWord_Size)(oset) ); + + // Re-insert remaining elements, to give OSetWord_Destroy something to + // work with. + for (i = 3; i < NN; i++) { + VG_(OSetWord_Insert)(oset, vs[i]); + } + + // Print the list + OSet_Print(oset, "oset1b", wordToStr); + + // Destroy the OSet + VG_(OSetWord_Destroy)(oset); } @@ -248,26 +368,27 @@ void example2(void) // Create a dynamic OSet of Blocks. This one uses slow (custom) // comparisons. - OSet* oset2 = VG_(OSet_Create)(offsetof(Block, first), + OSet* oset = VG_(OSetGen_Create)(offsetof(Block, first), blockCmp, (void*)malloc, free); // Try some operations on an empty OSet to ensure they don't screw up. - vg_assert( ! VG_(OSet_Contains)(oset2, &v) ); - vg_assert( ! VG_(OSet_Lookup)(oset2, &v) ); - vg_assert( ! VG_(OSet_Remove)(oset2, &v) ); - vg_assert( ! VG_(OSet_Next)(oset2) ); - vg_assert( 0 == VG_(OSet_Size)(oset2) ); + vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); + vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); + vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); + vg_assert( ! VG_(OSetGen_Next)(oset) ); + vg_assert( 0 == VG_(OSetGen_Size)(oset) ); // Create some inputs, with gaps -- intervals are 1..3, 11..13, ... -- but // no dups, and shuffle them randomly. for (i = 0; i < NN; i++) { - vs[i] = VG_(OSet_AllocNode)(oset2, sizeof(Block)); + vs[i] = VG_(OSetGen_AllocNode)(oset, sizeof(Block)); vs[i]->b1 = i; vs[i]->first = i*10 + 1; vs[i]->last = vs[i]->first + 2; vs[i]->b2 = i+1; } + seed = 0; for (i = 0; i < NN; i++) { Int r1 = myrandom() % NN; Int r2 = myrandom() % NN; @@ -278,36 +399,36 @@ void example2(void) // Insert the elements for (i = 0; i < NN; i++) { - VG_(OSet_Insert)(oset2, vs[i]); + VG_(OSetGen_Insert)(oset, vs[i]); } // Check the size - vg_assert( NN == VG_(OSet_Size)(oset2) ); + vg_assert( NN == VG_(OSetGen_Size)(oset) ); // Check we can find all the elements we inserted, within the full range // of each Block. for (i = 0; i < NN; i++) { - a = vs[i]->first + 0; assert( VG_(OSet_Contains)(oset2, &a) ); - a = vs[i]->first + 1; assert( VG_(OSet_Contains)(oset2, &a) ); - a = vs[i]->first + 2; assert( VG_(OSet_Contains)(oset2, &a) ); + a = vs[i]->first + 0; assert( VG_(OSetGen_Contains)(oset, &a) ); + a = vs[i]->first + 1; assert( VG_(OSetGen_Contains)(oset, &a) ); + a = vs[i]->first + 2; assert( VG_(OSetGen_Contains)(oset, &a) ); } // Check we cannot find elements we did not insert, below and above the // ranges of the inserted elements. a = 0; - assert( ! VG_(OSet_Contains)(oset2, &a) ); + assert( ! VG_(OSetGen_Contains)(oset, &a) ); for (i = 0; i < NN; i++) { - a = vs[i]->first - 1; assert( ! VG_(OSet_Contains)(oset2, &a) ); - a = vs[i]->first + 3; assert( ! VG_(OSet_Contains)(oset2, &a) ); + a = vs[i]->first - 1; assert( ! VG_(OSetGen_Contains)(oset, &a) ); + a = vs[i]->first + 3; assert( ! VG_(OSetGen_Contains)(oset, &a) ); } // Check we can find all the elements we inserted, and the right values // are returned. for (i = 0; i < NN; i++) { - a = vs[i]->first + 0; assert( vs[i] == VG_(OSet_Lookup)(oset2, &a) ); - a = vs[i]->first + 1; assert( vs[i] == VG_(OSet_Lookup)(oset2, &a) ); - a = vs[i]->first + 2; assert( vs[i] == VG_(OSet_Lookup)(oset2, &a) ); - assert( vs[i] == VG_(OSet_LookupWithCmp)(oset2, &a, blockCmp) ); + a = vs[i]->first + 0; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); + a = vs[i]->first + 1; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); + a = vs[i]->first + 2; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); + assert( vs[i] == VG_(OSetGen_LookupWithCmp)(oset, &a, blockCmp) ); } // Check that we can iterate over the OSet elements in sorted order, and @@ -315,60 +436,60 @@ void example2(void) n = 0; pv = NULL; prev.last = 0; - VG_(OSet_ResetIter)(oset2); - while ( (pv = VG_(OSet_Next)(oset2)) ) { + VG_(OSetGen_ResetIter)(oset); + while ( (pv = VG_(OSetGen_Next)(oset)) ) { Block curr = *pv; assert(prev.last < curr.first); prev = curr; n++; } assert(NN == n); - vg_assert( ! VG_(OSet_Next)(oset2) ); - vg_assert( ! VG_(OSet_Next)(oset2) ); + vg_assert( ! VG_(OSetGen_Next)(oset) ); + vg_assert( ! VG_(OSetGen_Next)(oset) ); // Check that we can remove half of the elements, and that their values // are as expected. for (i = 0; i < NN; i += 2) { - a = vs[i]->first; assert( vs[i] == VG_(OSet_Remove)(oset2, &a) ); + a = vs[i]->first; assert( vs[i] == VG_(OSetGen_Remove)(oset, &a) ); } // Check the size - vg_assert( NN/2 == VG_(OSet_Size)(oset2) ); + vg_assert( NN/2 == VG_(OSetGen_Size)(oset) ); // Check we can find the remaining elements (with the right values). for (i = 1; i < NN; i += 2) { - a = vs[i]->first + 0; assert( vs[i] == VG_(OSet_Lookup)(oset2, &a) ); - a = vs[i]->first + 1; assert( vs[i] == VG_(OSet_Lookup)(oset2, &a) ); - a = vs[i]->first + 2; assert( vs[i] == VG_(OSet_Lookup)(oset2, &a) ); + a = vs[i]->first + 0; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); + a = vs[i]->first + 1; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); + a = vs[i]->first + 2; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); } // Check we cannot find any of the elements we removed. for (i = 0; i < NN; i += 2) { - a = vs[i]->first + 0; assert( ! VG_(OSet_Contains)(oset2, &a) ); - a = vs[i]->first + 1; assert( ! VG_(OSet_Contains)(oset2, &a) ); - a = vs[i]->first + 2; assert( ! VG_(OSet_Contains)(oset2, &a) ); + a = vs[i]->first + 0; assert( ! VG_(OSetGen_Contains)(oset, &a) ); + a = vs[i]->first + 1; assert( ! VG_(OSetGen_Contains)(oset, &a) ); + a = vs[i]->first + 2; assert( ! VG_(OSetGen_Contains)(oset, &a) ); } // Check that we can remove the remaining half of the elements, and that // their values are as expected. for (i = 1; i < NN; i += 2) { - a = vs[i]->first; assert( vs[i] == VG_(OSet_Remove)(oset2, &a) ); + a = vs[i]->first; assert( vs[i] == VG_(OSetGen_Remove)(oset, &a) ); } // Try some more operations on the empty OSet to ensure they don't screw up. - vg_assert( ! VG_(OSet_Contains)(oset2, &v) ); - vg_assert( ! VG_(OSet_Lookup)(oset2, &v) ); - vg_assert( ! VG_(OSet_Remove)(oset2, &v) ); - vg_assert( ! VG_(OSet_Next)(oset2) ); - vg_assert( 0 == VG_(OSet_Size)(oset2) ); + vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); + vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); + vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); + vg_assert( ! VG_(OSetGen_Next)(oset) ); + vg_assert( 0 == VG_(OSetGen_Size)(oset) ); - // Re-insert all elements, to give OSet_Destroy something to work with. + // Re-insert all elements, to give OSetGen_Destroy something to work with. for (i = 0; i < NN; i++) { - VG_(OSet_Insert)(oset2, vs[i]); + VG_(OSetGen_Insert)(oset, vs[i]); } // Destroy the OSet - VG_(OSet_Destroy)(oset2, NULL); + VG_(OSetGen_Destroy)(oset); } //----------------------------------------------------------------------- @@ -378,6 +499,7 @@ void example2(void) int main(void) { example1(); + example1b(); example2(); return 0; } diff --git a/memcheck/tests/oset_test.stdout.exp b/memcheck/tests/oset_test.stdout.exp index fcb93427c8..81251ccd6d 100644 --- a/memcheck/tests/oset_test.stdout.exp +++ b/memcheck/tests/oset_test.stdout.exp @@ -1,4 +1,4 @@ --- start foo ---------------- +-- start oset1 ---------------- .. .. .. .. .. .. .. .. .. 1998 .. .. .. .. .. .. .. .. 1996 .. .. .. .. .. .. .. .. .. .. 1994 @@ -996,4 +996,1003 @@ .. .. .. .. .. .. .. .. .. 4 .. .. .. .. .. .. .. .. 2 .. .. .. .. .. .. .. .. .. 0 --- end foo ---------------- +-- end oset1 ---------------- +-- start oset1b ---------------- +.. .. .. .. .. .. .. .. .. 1998 +.. .. .. .. .. .. .. .. 1996 +.. .. .. .. .. .. .. .. .. .. 1994 +.. .. .. .. .. .. .. .. .. 1992 +.. .. .. .. .. .. .. .. .. .. 1990 +.. .. .. .. .. .. .. 1988 +.. .. .. .. .. .. .. .. .. 1986 +.. .. .. .. .. .. .. .. .. .. 1984 +.. .. .. .. .. .. .. .. 1982 +.. .. .. .. .. .. .. .. .. .. 1980 +.. .. .. .. .. .. .. .. .. 1978 +.. .. .. .. .. .. .. .. .. .. 1976 +.. .. .. .. .. .. 1974 +.. .. .. .. .. .. .. .. .. .. 1972 +.. .. .. .. .. .. .. .. .. 1970 +.. .. .. .. .. .. .. .. .. .. 1968 +.. .. .. .. .. .. .. .. 1966 +.. .. .. .. .. .. .. .. .. .. 1964 +.. .. .. .. .. .. .. .. .. 1962 +.. .. .. .. .. .. .. 1960 +.. .. .. .. .. .. .. .. .. .. 1958 +.. .. .. .. .. .. .. .. .. 1956 +.. .. .. .. .. .. .. .. 1954 +.. .. .. .. .. .. .. .. .. .. 1952 +.. .. .. .. .. .. .. .. .. 1950 +.. .. .. .. .. .. .. .. .. .. 1948 +.. .. .. .. .. 1946 +.. .. .. .. .. .. .. .. .. 1944 +.. .. .. .. .. .. .. .. 1942 +.. .. .. .. .. .. .. 1940 +.. .. .. .. .. .. .. .. .. .. 1938 +.. .. .. .. .. .. .. .. .. 1936 +.. .. .. .. .. .. .. .. 1934 +.. .. .. .. .. .. .. .. .. 1932 +.. .. .. .. .. .. 1930 +.. .. .. .. .. .. .. .. .. 1928 +.. .. .. .. .. .. .. .. .. .. 1926 +.. .. .. .. .. .. .. .. 1924 +.. .. .. .. .. .. .. .. .. .. 1922 +.. .. .. .. .. .. .. .. .. 1920 +.. .. .. .. .. .. .. .. .. .. 1918 +.. .. .. .. .. .. .. 1916 +.. .. .. .. .. .. .. .. .. 1914 +.. .. .. .. .. .. .. .. 1912 +.. .. .. .. .. .. .. .. .. .. 1910 +.. .. .. .. .. .. .. .. .. 1908 +.. .. .. .. .. .. .. .. .. .. 1906 +.. .. .. .. 1904 +.. .. .. .. .. .. .. .. .. 1902 +.. .. .. .. .. .. .. .. 1900 +.. .. .. .. .. .. .. 1898 +.. .. .. .. .. .. .. .. .. 1896 +.. .. .. .. .. .. .. .. 1894 +.. .. .. .. .. .. .. .. .. 1892 +.. .. .. .. .. .. 1890 +.. .. .. .. .. .. .. .. .. .. 1888 +.. .. .. .. .. .. .. .. .. 1886 +.. .. .. .. .. .. .. .. .. .. 1884 +.. .. .. .. .. .. .. .. 1882 +.. .. .. .. .. .. .. .. .. 1880 +.. .. .. .. .. .. .. 1878 +.. .. .. .. .. .. .. .. 1876 +.. .. .. .. .. .. .. .. .. 1874 +.. .. .. .. .. 1872 +.. .. .. .. .. .. .. .. .. .. 1870 +.. .. .. .. .. .. .. .. .. 1868 +.. .. .. .. .. .. .. .. .. .. 1866 +.. .. .. .. .. .. .. .. 1864 +.. .. .. .. .. .. .. .. .. 1862 +.. .. .. .. .. .. .. .. .. .. 1860 +.. .. .. .. .. .. .. 1858 +.. .. .. .. .. .. .. .. .. 1856 +.. .. .. .. .. .. .. .. 1854 +.. .. .. .. .. .. .. .. .. 1852 +.. .. .. .. .. .. 1848 +.. .. .. .. .. .. .. .. .. 1846 +.. .. .. .. .. .. .. .. 1844 +.. .. .. .. .. .. .. .. .. .. 1842 +.. .. .. .. .. .. .. .. .. 1840 +.. .. .. .. .. .. .. 1838 +.. .. .. .. .. .. .. .. .. .. 1836 +.. .. .. .. .. .. .. .. .. 1834 +.. .. .. .. .. .. .. .. .. .. 1832 +.. .. .. .. .. .. .. .. 1830 +.. .. .. .. .. .. .. .. .. .. 1828 +.. .. .. .. .. .. .. .. .. 1826 +.. .. .. .. .. .. .. .. .. .. 1824 +.. .. .. 1822 +.. .. .. .. .. .. .. .. 1820 +.. .. .. .. .. .. .. .. .. 1818 +.. .. .. .. .. .. .. 1816 +.. .. .. .. .. .. .. .. 1814 +.. .. .. .. .. .. 1812 +.. .. .. .. .. .. .. .. 1810 +.. .. .. .. .. .. .. .. .. 1808 +.. .. .. .. .. .. .. 1806 +.. .. .. .. .. .. .. .. 1804 +.. .. .. .. .. 1802 +.. .. .. .. .. .. .. .. 1800 +.. .. .. .. .. .. .. .. .. 1798 +.. .. .. .. .. .. .. 1796 +.. .. .. .. .. .. .. .. 1794 +.. .. .. .. .. .. 1792 +.. .. .. .. .. .. .. .. 1790 +.. .. .. .. .. .. .. .. .. 1788 +.. .. .. .. .. .. .. 1786 +.. .. .. .. .. .. .. .. .. 1784 +.. .. .. .. .. .. .. .. 1782 +.. .. .. .. .. .. .. .. .. 1780 +.. .. .. .. 1778 +.. .. .. .. .. .. .. .. .. 1776 +.. .. .. .. .. .. .. .. 1774 +.. .. .. .. .. .. .. 1772 +.. .. .. .. .. .. .. .. 1770 +.. .. .. .. .. .. 1768 +.. .. .. .. .. .. .. .. .. 1766 +.. .. .. .. .. .. .. .. 1764 +.. .. .. .. .. .. .. .. .. 1762 +.. .. .. .. .. .. .. 1760 +.. .. .. .. .. .. .. .. .. 1758 +.. .. .. .. .. .. .. .. 1756 +.. .. .. .. .. 1754 +.. .. .. .. .. .. .. .. 1752 +.. .. .. .. .. .. .. 1750 +.. .. .. .. .. .. .. .. .. 1748 +.. .. .. .. .. .. .. .. 1746 +.. .. .. .. .. .. 1744 +.. .. .. .. .. .. .. .. .. 1742 +.. .. .. .. .. .. .. .. 1740 +.. .. .. .. .. .. .. .. .. 1738 +.. .. .. .. .. .. .. 1736 +.. .. .. .. .. .. .. .. .. 1734 +.. .. .. .. .. .. .. .. .. .. 1732 +.. .. .. .. .. .. .. .. 1730 +.. .. .. .. .. .. .. .. .. 1728 +.. .. 1726 +.. .. .. .. .. .. .. .. .. 1724 +.. .. .. .. .. .. .. .. 1722 +.. .. .. .. .. .. .. .. .. 1720 +.. .. .. .. .. .. .. .. .. .. 1718 +.. .. .. .. .. .. .. 1716 +.. .. .. .. .. .. .. .. .. 1714 +.. .. .. .. .. .. .. .. 1712 +.. .. .. .. .. .. 1710 +.. .. .. .. .. .. .. .. .. 1708 +.. .. .. .. .. .. .. .. 1706 +.. .. .. .. .. .. .. 1704 +.. .. .. .. .. .. .. .. .. 1702 +.. .. .. .. .. .. .. .. .. .. 1700 +.. .. .. .. .. .. .. .. 1698 +.. .. .. .. .. .. .. .. .. 1696 +.. .. .. .. .. 1694 +.. .. .. .. .. .. .. .. 1692 +.. .. .. .. .. .. .. .. .. 1690 +.. .. .. .. .. .. .. 1688 +.. .. .. .. .. .. .. .. .. 1686 +.. .. .. .. .. .. .. .. 1684 +.. .. .. .. .. .. .. .. .. 1682 +.. .. .. .. .. .. 1680 +.. .. .. .. .. .. .. .. 1678 +.. .. .. .. .. .. .. 1676 +.. .. .. .. 1674 +.. .. .. .. .. .. .. .. 1672 +.. .. .. .. .. .. .. 1670 +.. .. .. .. .. .. .. .. 1668 +.. .. .. .. .. .. 1666 +.. .. .. .. .. .. .. .. .. 1664 +.. .. .. .. .. .. .. .. 1662 +.. .. .. .. .. .. .. 1660 +.. .. .. .. .. .. .. .. 1658 +.. .. .. .. .. 1656 +.. .. .. .. .. .. .. .. .. 1654 +.. .. .. .. .. .. .. .. 1652 +.. .. .. .. .. .. .. 1650 +.. .. .. .. .. .. .. .. .. 1648 +.. .. .. .. .. .. .. .. 1646 +.. .. .. .. .. .. .. .. .. 1644 +.. .. .. .. .. .. 1642 +.. .. .. .. .. .. .. .. 1640 +.. .. .. .. .. .. .. .. .. 1638 +.. .. .. .. .. .. .. 1636 +.. .. .. .. .. .. .. .. .. 1634 +.. .. .. .. .. .. .. .. 1632 +.. .. .. .. .. .. .. .. .. 1630 +.. .. .. 1628 +.. .. .. .. .. .. .. .. 1626 +.. .. .. .. .. .. .. 1624 +.. .. .. .. .. .. 1622 +.. .. .. .. .. .. .. .. 1620 +.. .. .. .. .. .. .. 1618 +.. .. .. .. .. .. .. .. .. 1616 +.. .. .. .. .. .. .. .. 1614 +.. .. .. .. .. 1612 +.. .. .. .. .. .. .. .. .. 1610 +.. .. .. .. .. .. .. .. 1608 +.. .. .. .. .. .. .. 1606 +.. .. .. .. .. .. .. .. .. 1604 +.. .. .. .. .. .. .. .. 1602 +.. .. .. .. .. .. .. .. .. 1600 +.. .. .. .. .. .. 1598 +.. .. .. .. .. .. .. .. 1596 +.. .. .. .. .. .. .. .. .. 1594 +.. .. .. .. .. .. .. 1592 +.. .. .. .. .. .. .. .. 1590 +.. .. .. .. 1588 +.. .. .. .. .. .. .. .. 1586 +.. .. .. .. .. .. .. 1584 +.. .. .. .. .. .. .. .. .. 1582 +.. .. .. .. .. .. .. .. 1580 +.. .. .. .. .. .. 1578 +.. .. .. .. .. .. .. .. 1576 +.. .. .. .. .. .. .. 1574 +.. .. .. .. .. .. .. .. 1572 +.. .. .. .. .. .. .. .. .. 1570 +.. .. .. .. .. 1568 +.. .. .. .. .. .. .. .. 1566 +.. .. .. .. .. .. .. 1564 +.. .. .. .. .. .. .. .. .. 1562 +.. .. .. .. .. .. .. .. 1560 +.. .. .. .. .. .. .. .. .. 1558 +.. .. .. .. .. .. 1556 +.. .. .. .. .. .. .. .. 1554 +.. .. .. .. .. .. .. 1552 +.. .. .. .. .. .. .. .. 1550 +.. 1548 +.. .. .. .. .. .. .. .. 1546 +.. .. .. .. .. .. .. 1544 +.. .. .. .. .. .. .. .. 1542 +.. .. .. .. .. .. 1540 +.. .. .. .. .. .. .. .. .. 1538 +.. .. .. .. .. .. .. .. 1536 +.. .. .. .. .. .. .. 1534 +.. .. .. .. .. .. .. .. 1532 +.. .. .. .. .. 1530 +.. .. .. .. .. .. .. .. .. 1528 +.. .. .. .. .. .. .. .. 1526 +.. .. .. .. .. .. .. 1524 +.. .. .. .. .. .. .. .. 1522 +.. .. .. .. .. .. .. .. .. 1520 +.. .. .. .. .. .. 1518 +.. .. .. .. .. .. .. .. 1516 +.. .. .. .. .. .. .. 1514 +.. .. .. .. .. .. .. .. .. 1512 +.. .. .. .. .. .. .. .. 1510 +.. .. .. .. 1508 +.. .. .. .. .. .. .. .. 1506 +.. .. .. .. .. .. .. 1504 +.. .. .. .. .. .. .. .. 1502 +.. .. .. .. .. .. 1500 +.. .. .. .. .. .. .. 1498 +.. .. .. .. .. .. .. .. 1496 +.. .. .. .. .. 1494 +.. .. .. .. .. .. .. 1492 +.. .. .. .. .. .. .. .. 1490 +.. .. .. .. .. .. 1488 +.. .. .. .. .. .. .. .. .. 1486 +.. .. .. .. .. .. .. .. 1484 +.. .. .. .. .. .. .. .. .. 1482 +.. .. .. .. .. .. .. 1480 +.. .. .. .. .. .. .. .. .. 1478 +.. .. .. .. .. .. .. .. 1476 +.. .. .. .. .. .. .. .. .. 1474 +.. .. .. 1472 +.. .. .. .. .. .. .. .. .. .. 1470 +.. .. .. .. .. .. .. .. .. 1468 +.. .. .. .. .. .. .. .. .. .. 1466 +.. .. .. .. .. .. .. .. 1464 +.. .. .. .. .. .. .. .. .. 1462 +.. .. .. .. .. .. .. 1460 +.. .. .. .. .. .. .. .. .. .. 1458 +.. .. .. .. .. .. .. .. .. 1456 +.. .. .. .. .. .. .. .. .. .. 1454 +.. .. .. .. .. .. .. .. 1452 +.. .. .. .. .. .. .. .. .. 1450 +.. .. .. .. .. .. .. .. .. .. 1448 +.. .. .. .. .. .. 1446 +.. .. .. .. .. .. .. .. .. 1444 +.. .. .. .. .. .. .. .. 1442 +.. .. .. .. .. .. .. .. .. 1440 +.. .. .. .. .. .. .. 1438 +.. .. .. .. .. .. .. .. 1436 +.. .. .. .. .. 1434 +.. .. .. .. .. .. .. .. .. 1432 +.. .. .. .. .. .. .. .. 1430 +.. .. .. .. .. .. .. .. .. 1428 +.. .. .. .. .. .. .. 1426 +.. .. .. .. .. .. .. .. .. .. 1424 +.. .. .. .. .. .. .. .. .. 1422 +.. .. .. .. .. .. .. .. .. .. 1420 +.. .. .. .. .. .. .. .. 1418 +.. .. .. .. .. .. .. .. .. .. 1416 +.. .. .. .. .. .. .. .. .. 1414 +.. .. .. .. .. .. 1412 +.. .. .. .. .. .. .. .. .. 1410 +.. .. .. .. .. .. .. .. 1408 +.. .. .. .. .. .. .. .. .. 1406 +.. .. .. .. .. .. .. .. .. .. 1404 +.. .. .. .. .. .. .. 1402 +.. .. .. .. .. .. .. .. .. .. 1400 +.. .. .. .. .. .. .. .. .. 1398 +.. .. .. .. .. .. .. .. .. .. 1396 +.. .. .. .. .. .. .. .. 1394 +.. .. .. .. .. .. .. .. .. .. 1392 +.. .. .. .. .. .. .. .. .. 1390 +.. .. .. .. 1388 +.. .. .. .. .. .. .. .. .. .. 1386 +.. .. .. .. .. .. .. .. .. 1384 +.. .. .. .. .. .. .. .. 1382 +.. .. .. .. .. .. .. .. .. .. 1380 +.. .. .. .. .. .. .. .. .. 1378 +.. .. .. .. .. .. .. .. .. .. 1376 +.. .. .. .. .. .. .. 1374 +.. .. .. .. .. .. .. .. 1372 +.. .. .. .. .. .. .. .. .. 1370 +.. .. .. .. .. .. 1368 +.. .. .. .. .. .. .. .. .. .. 1366 +.. .. .. .. .. .. .. .. .. 1364 +.. .. .. .. .. .. .. .. .. .. 1362 +.. .. .. .. .. .. .. .. 1360 +.. .. .. .. .. .. .. .. .. 1358 +.. .. .. .. .. .. .. 1356 +.. .. .. .. .. .. .. .. .. 1354 +.. .. .. .. .. .. .. .. .. .. 1352 +.. .. .. .. .. .. .. .. 1350 +.. .. .. .. .. .. .. .. .. .. 1348 +.. .. .. .. .. .. .. .. .. 1346 +.. .. .. .. .. .. .. .. .. .. 1344 +.. .. .. .. .. 1342 +.. .. .. .. .. .. .. .. .. .. 1340 +.. .. .. .. .. .. .. .. .. 1338 +.. .. .. .. .. .. .. .. 1336 +.. .. .. .. .. .. .. .. .. .. 1334 +.. .. .. .. .. .. .. .. .. 1332 +.. .. .. .. .. .. .. .. .. .. 1330 +.. .. .. .. .. .. .. 1328 +.. .. .. .. .. .. .. .. .. .. 1326 +.. .. .. .. .. .. .. .. .. 1324 +.. .. .. .. .. .. .. .. .. .. 1322 +.. .. .. .. .. .. .. .. 1320 +.. .. .. .. .. .. .. .. .. 1318 +.. .. .. .. .. .. .. .. .. .. 1316 +.. .. .. .. .. .. 1314 +.. .. .. .. .. .. .. .. 1312 +.. .. .. .. .. .. .. .. .. 1310 +.. .. .. .. .. .. .. 1308 +.. .. .. .. .. .. .. .. .. .. 1306 +.. .. .. .. .. .. .. .. .. 1304 +.. .. .. .. .. .. .. .. .. .. 1302 +.. .. .. .. .. .. .. .. 1300 +.. .. .. .. .. .. .. .. .. 1298 +.. .. .. .. .. .. .. .. .. .. 1296 +.. .. 1294 +.. .. .. .. .. .. .. .. .. 1292 +.. .. .. .. .. .. .. .. 1290 +.. .. .. .. .. .. .. 1288 +.. .. .. .. .. .. .. .. .. 1286 +.. .. .. .. .. .. .. .. 1284 +.. .. .. .. .. .. .. .. .. 1282 +.. .. .. .. .. .. 1280 +.. .. .. .. .. .. .. .. 1278 +.. .. .. .. .. .. .. 1276 +.. .. .. .. .. 1274 +.. .. .. .. .. .. .. .. 1272 +.. .. .. .. .. .. .. .. .. 1270 +.. .. .. .. .. .. .. 1268 +.. .. .. .. .. .. .. .. .. 1266 +.. .. .. .. .. .. .. .. 1264 +.. .. .. .. .. .. .. .. .. 1262 +.. .. .. .. .. .. 1260 +.. .. .. .. .. .. .. .. .. 1258 +.. .. .. .. .. .. .. .. 1256 +.. .. .. .. .. .. .. 1254 +.. .. .. .. .. .. .. .. .. .. 1252 +.. .. .. .. .. .. .. .. .. 1250 +.. .. .. .. .. .. .. .. 1248 +.. .. .. .. .. .. .. .. .. 1246 +.. .. .. .. .. .. .. .. .. .. 1244 +.. .. .. .. 1242 +.. .. .. .. .. .. .. .. .. 1240 +.. .. .. .. .. .. .. .. 1238 +.. .. .. .. .. .. .. .. .. 1236 +.. .. .. .. .. .. .. 1234 +.. .. .. .. .. .. .. .. 1232 +.. .. .. .. .. .. 1230 +.. .. .. .. .. .. .. .. .. 1228 +.. .. .. .. .. .. .. .. 1226 +.. .. .. .. .. .. .. 1224 +.. .. .. .. .. .. .. .. .. 1222 +.. .. .. .. .. .. .. .. 1220 +.. .. .. .. .. .. .. .. .. 1218 +.. .. .. .. .. 1216 +.. .. .. .. .. .. .. .. .. 1214 +.. .. .. .. .. .. .. .. 1212 +.. .. .. .. .. .. .. .. .. 1210 +.. .. .. .. .. .. .. 1208 +.. .. .. .. .. .. .. .. 1206 +.. .. .. .. .. .. 1204 +.. .. .. .. .. .. .. .. .. 1202 +.. .. .. .. .. .. .. .. .. .. 1200 +.. .. .. .. .. .. .. .. 1198 +.. .. .. .. .. .. .. .. .. 1196 +.. .. .. .. .. .. .. 1194 +.. .. .. .. .. .. .. .. .. 1192 +.. .. .. .. .. .. .. .. 1190 +.. .. .. .. .. .. .. .. .. 1188 +.. .. .. 1186 +.. .. .. .. .. .. .. .. .. 1184 +.. .. .. .. .. .. .. .. .. .. 1182 +.. .. .. .. .. .. .. .. 1180 +.. .. .. .. .. .. .. .. .. 1178 +.. .. .. .. .. .. .. 1176 +.. .. .. .. .. .. .. .. .. 1174 +.. .. .. .. .. .. .. .. .. .. 1172 +.. .. .. .. .. .. .. .. 1170 +.. .. .. .. .. .. .. .. .. 1168 +.. .. .. .. .. .. 1166 +.. .. .. .. .. .. .. .. .. .. 1164 +.. .. .. .. .. .. .. .. .. 1162 +.. .. .. .. .. .. .. .. 1160 +.. .. .. .. .. .. .. .. .. 1158 +.. .. .. .. .. .. .. .. .. .. 1156 +.. .. .. .. .. .. .. 1152 +.. .. .. .. .. .. .. .. .. 1150 +.. .. .. .. .. .. .. .. .. .. 1148 +.. .. .. .. .. .. .. .. 1146 +.. .. .. .. .. .. .. .. .. 1144 +.. .. .. .. .. 1142 +.. .. .. .. .. .. .. .. .. 1140 +.. .. .. .. .. .. .. .. 1138 +.. .. .. .. .. .. .. .. .. 1136 +.. .. .. .. .. .. .. 1134 +.. .. .. .. .. .. .. .. .. 1132 +.. .. .. .. .. .. .. .. 1130 +.. .. .. .. .. .. .. .. .. 1128 +.. .. .. .. .. .. .. .. .. .. 1126 +.. .. .. .. .. .. 1124 +.. .. .. .. .. .. .. .. .. 1122 +.. .. .. .. .. .. .. .. 1120 +.. .. .. .. .. .. .. .. .. 1118 +.. .. .. .. .. .. .. .. .. .. 1116 +.. .. .. .. .. .. .. 1114 +.. .. .. .. .. .. .. .. 1112 +.. .. .. .. .. .. .. .. .. 1110 +.. .. .. .. 1108 +.. .. .. .. .. .. .. .. .. 1106 +.. .. .. .. .. .. .. .. 1104 +.. .. .. .. .. .. .. .. .. 1102 +.. .. .. .. .. .. .. 1100 +.. .. .. .. .. .. .. .. .. 1098 +.. .. .. .. .. .. .. .. .. .. 1096 +.. .. .. .. .. .. .. .. 1094 +.. .. .. .. .. .. .. .. .. 1092 +.. .. .. .. .. .. 1090 +.. .. .. .. .. .. .. .. 1088 +.. .. .. .. .. .. .. .. .. 1086 +.. .. .. .. .. .. .. 1084 +.. .. .. .. .. .. .. .. 1082 +.. .. .. .. .. .. .. .. .. 1080 +.. .. .. .. .. 1078 +.. .. .. .. .. .. .. .. 1076 +.. .. .. .. .. .. .. 1074 +.. .. .. .. .. .. .. .. 1072 +.. .. .. .. .. .. .. .. .. 1070 +.. .. .. .. .. .. 1068 +.. .. .. .. .. .. .. 1066 +.. .. .. .. .. .. .. .. 1064 +1062 +.. .. .. .. .. .. .. .. .. 1060 +.. .. .. .. .. .. .. .. 1058 +.. .. .. .. .. .. .. .. .. 1056 +.. .. .. .. .. .. .. 1054 +.. .. .. .. .. .. .. .. .. 1052 +.. .. .. .. .. .. .. .. 1050 +.. .. .. .. .. .. .. .. .. .. 1048 +.. .. .. .. .. .. .. .. .. 1046 +.. .. .. .. .. .. 1044 +.. .. .. .. .. .. .. .. .. .. 1042 +.. .. .. .. .. .. .. .. .. .. .. 1040 +.. .. .. .. .. .. .. .. .. 1038 +.. .. .. .. .. .. .. .. .. .. .. 1036 +.. .. .. .. .. .. .. .. .. .. 1034 +.. .. .. .. .. .. .. .. .. .. .. 1032 +.. .. .. .. .. .. .. .. 1030 +.. .. .. .. .. .. .. .. .. .. 1028 +.. .. .. .. .. .. .. .. .. 1026 +.. .. .. .. .. .. .. .. .. .. 1024 +.. .. .. .. .. .. .. 1022 +.. .. .. .. .. .. .. .. .. .. 1020 +.. .. .. .. .. .. .. .. .. 1018 +.. .. .. .. .. .. .. .. .. .. 1016 +.. .. .. .. .. .. .. .. 1014 +.. .. .. .. .. .. .. .. .. .. 1012 +.. .. .. .. .. .. .. .. .. 1010 +.. .. .. .. .. .. .. .. .. .. 1008 +.. .. .. .. .. 1006 +.. .. .. .. .. .. .. .. .. 1004 +.. .. .. .. .. .. .. .. 1002 +.. .. .. .. .. .. .. .. .. 1000 +.. .. .. .. .. .. .. 998 +.. .. .. .. .. .. .. .. .. .. 996 +.. .. .. .. .. .. .. .. .. 994 +.. .. .. .. .. .. .. .. .. .. 992 +.. .. .. .. .. .. .. .. 990 +.. .. .. .. .. .. .. .. .. 988 +.. .. .. .. .. .. 986 +.. .. .. .. .. .. .. .. .. .. 984 +.. .. .. .. .. .. .. .. .. 982 +.. .. .. .. .. .. .. .. .. .. 980 +.. .. .. .. .. .. .. .. 978 +.. .. .. .. .. .. .. .. .. 976 +.. .. .. .. .. .. .. .. .. .. 974 +.. .. .. .. .. .. .. 972 +.. .. .. .. .. .. .. .. .. 970 +.. .. .. .. .. .. .. .. 968 +.. .. .. .. .. .. .. .. .. 966 +.. .. .. .. 964 +.. .. .. .. .. .. .. .. .. 962 +.. .. .. .. .. .. .. .. .. .. 960 +.. .. .. .. .. .. .. .. 958 +.. .. .. .. .. .. .. .. .. 956 +.. .. .. .. .. .. .. 954 +.. .. .. .. .. .. .. .. 952 +.. .. .. .. .. .. .. .. .. 950 +.. .. .. .. .. .. 948 +.. .. .. .. .. .. .. .. .. 946 +.. .. .. .. .. .. .. .. .. .. 944 +.. .. .. .. .. .. .. .. 942 +.. .. .. .. .. .. .. .. .. 940 +.. .. .. .. .. .. .. 938 +.. .. .. .. .. .. .. .. .. .. 936 +.. .. .. .. .. .. .. .. .. 934 +.. .. .. .. .. .. .. .. 932 +.. .. .. .. .. .. .. .. .. .. 930 +.. .. .. .. .. .. .. .. .. 928 +.. .. .. .. .. .. .. .. .. .. 926 +.. .. .. .. .. 924 +.. .. .. .. .. .. .. .. .. 922 +.. .. .. .. .. .. .. .. 920 +.. .. .. .. .. .. .. .. .. .. 918 +.. .. .. .. .. .. .. .. .. 916 +.. .. .. .. .. .. .. 914 +.. .. .. .. .. .. .. .. .. 912 +.. .. .. .. .. .. .. .. 910 +.. .. .. .. .. .. 908 +.. .. .. .. .. .. .. .. 906 +.. .. .. .. .. .. .. 904 +.. .. .. .. .. .. .. .. .. 900 +.. .. .. .. .. .. .. .. 898 +.. .. .. 896 +.. .. .. .. .. .. .. .. .. 894 +.. .. .. .. .. .. .. .. 892 +.. .. .. .. .. .. .. .. .. 890 +.. .. .. .. .. .. .. .. .. .. 888 +.. .. .. .. .. .. .. 886 +.. .. .. .. .. .. .. .. .. .. 884 +.. .. .. .. .. .. .. .. .. 882 +.. .. .. .. .. .. .. .. .. .. .. 880 +.. .. .. .. .. .. .. .. .. .. 878 +.. .. .. .. .. .. .. .. 876 +.. .. .. .. .. .. .. .. .. .. 874 +.. .. .. .. .. .. .. .. .. 872 +.. .. .. .. .. .. .. .. .. .. 870 +.. .. .. .. .. .. 868 +.. .. .. .. .. .. .. .. .. .. 866 +.. .. .. .. .. .. .. .. .. 864 +.. .. .. .. .. .. .. .. 862 +.. .. .. .. .. .. .. .. .. 860 +.. .. .. .. .. .. .. .. .. .. 858 +.. .. .. .. .. .. .. 856 +.. .. .. .. .. .. .. .. .. 854 +.. .. .. .. .. .. .. .. 852 +.. .. .. .. .. .. .. .. .. 850 +.. .. .. .. .. .. .. .. .. .. 848 +.. .. .. .. .. 846 +.. .. .. .. .. .. .. .. .. .. 844 +.. .. .. .. .. .. .. .. .. 842 +.. .. .. .. .. .. .. .. 840 +.. .. .. .. .. .. .. .. .. 838 +.. .. .. .. .. .. .. 836 +.. .. .. .. .. .. .. .. .. 834 +.. .. .. .. .. .. .. .. .. .. 832 +.. .. .. .. .. .. .. .. 830 +.. .. .. .. .. .. .. .. .. 828 +.. .. .. .. .. .. 826 +.. .. .. .. .. .. .. .. .. 824 +.. .. .. .. .. .. .. .. 822 +.. .. .. .. .. .. .. 820 +.. .. .. .. .. .. .. .. .. .. 818 +.. .. .. .. .. .. .. .. .. 816 +.. .. .. .. .. .. .. .. 814 +.. .. .. .. .. .. .. .. .. .. 812 +.. .. .. .. .. .. .. .. .. 810 +.. .. .. .. 808 +.. .. .. .. .. .. .. .. .. 806 +.. .. .. .. .. .. .. .. 804 +.. .. .. .. .. .. .. 802 +.. .. .. .. .. .. .. .. .. 800 +.. .. .. .. .. .. .. .. 798 +.. .. .. .. .. .. .. .. .. 796 +.. .. .. .. .. .. 794 +.. .. .. .. .. .. .. .. .. 792 +.. .. .. .. .. .. .. .. 790 +.. .. .. .. .. .. .. .. .. 788 +.. .. .. .. .. .. .. 786 +.. .. .. .. .. .. .. .. 784 +.. .. .. .. .. .. .. .. .. 782 +.. .. .. .. .. 780 +.. .. .. .. .. .. .. .. .. .. 778 +.. .. .. .. .. .. .. .. .. 776 +.. .. .. .. .. .. .. .. .. .. 774 +.. .. .. .. .. .. .. .. 772 +.. .. .. .. .. .. .. .. .. 770 +.. .. .. .. .. .. .. 768 +.. .. .. .. .. .. .. .. .. .. 766 +.. .. .. .. .. .. .. .. .. 764 +.. .. .. .. .. .. .. .. 762 +.. .. .. .. .. .. .. .. .. .. 760 +.. .. .. .. .. .. .. .. .. 758 +.. .. .. .. .. .. .. .. .. .. 756 +.. .. .. .. .. .. 754 +.. .. .. .. .. .. .. .. .. .. 752 +.. .. .. .. .. .. .. .. .. 750 +.. .. .. .. .. .. .. .. .. .. 748 +.. .. .. .. .. .. .. .. 746 +.. .. .. .. .. .. .. .. .. .. 744 +.. .. .. .. .. .. .. .. .. 742 +.. .. .. .. .. .. .. .. .. .. 740 +.. .. .. .. .. .. .. 738 +.. .. .. .. .. .. .. .. .. 736 +.. .. .. .. .. .. .. .. 734 +.. .. .. .. .. .. .. .. .. 732 +.. .. .. .. .. .. .. .. .. .. 730 +.. .. 728 +.. .. .. .. .. .. .. .. 726 +.. .. .. .. .. .. .. .. .. 724 +.. .. .. .. .. .. .. 722 +.. .. .. .. .. .. .. .. .. 720 +.. .. .. .. .. .. .. .. .. .. 718 +.. .. .. .. .. .. .. .. 716 +.. .. .. .. .. .. .. .. .. 714 +.. .. .. .. .. .. 712 +.. .. .. .. .. .. .. .. .. 710 +.. .. .. .. .. .. .. .. 708 +.. .. .. .. .. .. .. 706 +.. .. .. .. .. .. .. .. .. 704 +.. .. .. .. .. .. .. .. 702 +.. .. .. .. .. .. .. .. .. 700 +.. .. .. .. .. 698 +.. .. .. .. .. .. .. .. 696 +.. .. .. .. .. .. .. 694 +.. .. .. .. .. .. .. .. 692 +.. .. .. .. .. .. .. .. .. 690 +.. .. .. .. .. .. 688 +.. .. .. .. .. .. .. 686 +.. .. .. .. .. .. .. .. 684 +.. .. .. .. 682 +.. .. .. .. .. .. .. .. 680 +.. .. .. .. .. .. .. 678 +.. .. .. .. .. .. 676 +.. .. .. .. .. .. .. .. 674 +.. .. .. .. .. .. .. 672 +.. .. .. .. .. .. .. .. 670 +.. .. .. .. .. 668 +.. .. .. .. .. .. .. .. .. 666 +.. .. .. .. .. .. .. .. 664 +.. .. .. .. .. .. .. .. .. 662 +.. .. .. .. .. .. .. 660 +.. .. .. .. .. .. .. .. 658 +.. .. .. .. .. .. 656 +.. .. .. .. .. .. .. .. .. 654 +.. .. .. .. .. .. .. .. 652 +.. .. .. .. .. .. .. .. .. 650 +.. .. .. .. .. .. .. 648 +.. .. .. .. .. .. .. .. 646 +.. .. .. .. .. .. .. .. .. 644 +.. .. .. 642 +.. .. .. .. .. .. .. .. .. 640 +.. .. .. .. .. .. .. .. 638 +.. .. .. .. .. .. .. 636 +.. .. .. .. .. .. .. .. .. 634 +.. .. .. .. .. .. .. .. 632 +.. .. .. .. .. .. .. .. .. 630 +.. .. .. .. .. .. 628 +.. .. .. .. .. .. .. .. .. 626 +.. .. .. .. .. .. .. .. 624 +.. .. .. .. .. .. .. .. .. 622 +.. .. .. .. .. .. .. 620 +.. .. .. .. .. .. .. .. .. 618 +.. .. .. .. .. .. .. .. 616 +.. .. .. .. .. 614 +.. .. .. .. .. .. .. .. .. 612 +.. .. .. .. .. .. .. .. 610 +.. .. .. .. .. .. .. .. .. .. 608 +.. .. .. .. .. .. .. .. .. 606 +.. .. .. .. .. .. .. .. .. .. 604 +.. .. .. .. .. .. .. 602 +.. .. .. .. .. .. .. .. .. 600 +.. .. .. .. .. .. .. .. 598 +.. .. .. .. .. .. 596 +.. .. .. .. .. .. .. .. .. 594 +.. .. .. .. .. .. .. .. 592 +.. .. .. .. .. .. .. .. .. 590 +.. .. .. .. .. .. .. 588 +.. .. .. .. .. .. .. .. .. .. 586 +.. .. .. .. .. .. .. .. .. 584 +.. .. .. .. .. .. .. .. 582 +.. .. .. .. .. .. .. .. .. 580 +.. .. .. .. 578 +.. .. .. .. .. .. .. .. .. 576 +.. .. .. .. .. .. .. .. 574 +.. .. .. .. .. .. .. .. .. 572 +.. .. .. .. .. .. .. 570 +.. .. .. .. .. .. .. .. .. .. 568 +.. .. .. .. .. .. .. .. .. 566 +.. .. .. .. .. .. .. .. .. .. 564 +.. .. .. .. .. .. .. .. 562 +.. .. .. .. .. .. .. .. .. 560 +.. .. .. .. .. .. .. .. .. .. 558 +.. .. .. .. .. .. 556 +.. .. .. .. .. .. .. .. .. 554 +.. .. .. .. .. .. .. .. 552 +.. .. .. .. .. .. .. 550 +.. .. .. .. .. .. .. .. .. 548 +.. .. .. .. .. .. .. .. 546 +.. .. .. .. .. 544 +.. .. .. .. .. .. .. .. 542 +.. .. .. .. .. .. .. .. .. 540 +.. .. .. .. .. .. .. 538 +.. .. .. .. .. .. .. .. .. 536 +.. .. .. .. .. .. .. .. 534 +.. .. .. .. .. .. .. .. .. 532 +.. .. .. .. .. .. 530 +.. .. .. .. .. .. .. .. 528 +.. .. .. .. .. .. .. 526 +.. .. .. .. .. .. .. .. 524 +.. 522 +.. .. .. .. .. .. .. .. .. .. 520 +.. .. .. .. .. .. .. .. .. 518 +.. .. .. .. .. .. .. .. 516 +.. .. .. .. .. .. .. .. .. 514 +.. .. .. .. .. .. .. .. .. .. 512 +.. .. .. .. .. .. .. 510 +.. .. .. .. .. .. .. .. .. 508 +.. .. .. .. .. .. .. .. 506 +.. .. .. .. .. .. .. .. .. 504 +.. .. .. .. .. .. 502 +.. .. .. .. .. .. .. .. .. .. 500 +.. .. .. .. .. .. .. .. .. 498 +.. .. .. .. .. .. .. .. 496 +.. .. .. .. .. .. .. .. .. 494 +.. .. .. .. .. .. .. 492 +.. .. .. .. .. .. .. .. .. .. 490 +.. .. .. .. .. .. .. .. .. 488 +.. .. .. .. .. .. .. .. 486 +.. .. .. .. .. .. .. .. .. 484 +.. .. .. .. .. 482 +.. .. .. .. .. .. .. .. .. 480 +.. .. .. .. .. .. .. .. 478 +.. .. .. .. .. .. .. .. .. 476 +.. .. .. .. .. .. .. 474 +.. .. .. .. .. .. .. .. 472 +.. .. .. .. .. .. 470 +.. .. .. .. .. .. .. .. 468 +.. .. .. .. .. .. .. 466 +.. .. .. .. .. .. .. .. 464 +.. .. .. .. 462 +.. .. .. .. .. .. .. .. .. .. 460 +.. .. .. .. .. .. .. .. .. 458 +.. .. .. .. .. .. .. .. .. .. 456 +.. .. .. .. .. .. .. .. 454 +.. .. .. .. .. .. .. .. .. .. 452 +.. .. .. .. .. .. .. .. .. 450 +.. .. .. .. .. .. .. .. .. .. 448 +.. .. .. .. .. .. .. 446 +.. .. .. .. .. .. .. .. 444 +.. .. .. .. .. .. .. .. .. 442 +.. .. .. .. .. .. 440 +.. .. .. .. .. .. .. .. .. .. 438 +.. .. .. .. .. .. .. .. .. 436 +.. .. .. .. .. .. .. .. .. .. 434 +.. .. .. .. .. .. .. .. 432 +.. .. .. .. .. .. .. .. .. 430 +.. .. .. .. .. .. .. 428 +.. .. .. .. .. .. .. .. 426 +.. .. .. .. .. .. .. .. .. 424 +.. .. .. .. .. 422 +.. .. .. .. .. .. .. .. .. 420 +.. .. .. .. .. .. .. .. .. .. 418 +.. .. .. .. .. .. .. .. 416 +.. .. .. .. .. .. .. .. .. .. 414 +.. .. .. .. .. .. .. .. .. 412 +.. .. .. .. .. .. .. 410 +.. .. .. .. .. .. .. .. .. 408 +.. .. .. .. .. .. .. .. .. .. 406 +.. .. .. .. .. .. .. .. 404 +.. .. .. .. .. .. .. .. .. 402 +.. .. .. .. .. .. .. .. .. .. 400 +.. .. .. .. .. .. 398 +.. .. .. .. .. .. .. .. .. 396 +.. .. .. .. .. .. .. .. 394 +.. .. .. .. .. .. .. .. .. 392 +.. .. .. .. .. .. .. .. .. .. 390 +.. .. .. .. .. .. .. 388 +.. .. .. .. .. .. .. .. .. .. 386 +.. .. .. .. .. .. .. .. .. 384 +.. .. .. .. .. .. .. .. 382 +.. .. .. .. .. .. .. .. .. .. 380 +.. .. .. .. .. .. .. .. .. 378 +.. .. .. .. .. .. .. .. .. .. 376 +.. .. .. 374 +.. .. .. .. .. .. .. .. 372 +.. .. .. .. .. .. .. 370 +.. .. .. .. .. .. 368 +.. .. .. .. .. .. .. .. 366 +.. .. .. .. .. .. .. .. .. 364 +.. .. .. .. .. .. .. 362 +.. .. .. .. .. .. .. .. 360 +.. .. .. .. .. 358 +.. .. .. .. .. .. .. .. 356 +.. .. .. .. .. .. .. .. .. 354 +.. .. .. .. .. .. .. 352 +.. .. .. .. .. .. .. .. .. 350 +.. .. .. .. .. .. .. .. 348 +.. .. .. .. .. .. .. .. .. 346 +.. .. .. .. .. .. 344 +.. .. .. .. .. .. .. .. .. 342 +.. .. .. .. .. .. .. .. 340 +.. .. .. .. .. .. .. .. .. 338 +.. .. .. .. .. .. .. 336 +.. .. .. .. .. .. .. .. .. 334 +.. .. .. .. .. .. .. .. 332 +.. .. .. .. .. .. .. .. .. 330 +.. .. .. .. 328 +.. .. .. .. .. .. .. .. .. 326 +.. .. .. .. .. .. .. .. 324 +.. .. .. .. .. .. .. 322 +.. .. .. .. .. .. .. .. 320 +.. .. .. .. .. .. 318 +.. .. .. .. .. .. .. .. .. 316 +.. .. .. .. .. .. .. .. 314 +.. .. .. .. .. .. .. .. .. .. 312 +.. .. .. .. .. .. .. .. .. 310 +.. .. .. .. .. .. .. .. .. .. 308 +.. .. .. .. .. .. .. 306 +.. .. .. .. .. .. .. .. .. .. 304 +.. .. .. .. .. .. .. .. .. 302 +.. .. .. .. .. .. .. .. 300 +.. .. .. .. .. .. .. .. .. 298 +.. .. .. .. .. 296 +.. .. .. .. .. .. .. .. .. 294 +.. .. .. .. .. .. .. .. 292 +.. .. .. .. .. .. .. .. .. 290 +.. .. .. .. .. .. .. 288 +.. .. .. .. .. .. .. .. 286 +.. .. .. .. .. .. 284 +.. .. .. .. .. .. .. .. .. 282 +.. .. .. .. .. .. .. .. 280 +.. .. .. .. .. .. .. .. .. 278 +.. .. .. .. .. .. .. 276 +.. .. .. .. .. .. .. .. .. .. 274 +.. .. .. .. .. .. .. .. .. 272 +.. .. .. .. .. .. .. .. 270 +.. .. .. .. .. .. .. .. .. 268 +.. .. 266 +.. .. .. .. .. .. .. .. .. 264 +.. .. .. .. .. .. .. .. 262 +.. .. .. .. .. .. .. .. .. 260 +.. .. .. .. .. .. .. 258 +.. .. .. .. .. .. .. .. .. 256 +.. .. .. .. .. .. .. .. 254 +.. .. .. .. .. .. .. .. .. 252 +.. .. .. .. .. .. 250 +.. .. .. .. .. .. .. .. .. 248 +.. .. .. .. .. .. .. .. 246 +.. .. .. .. .. .. .. .. .. 244 +.. .. .. .. .. .. .. 242 +.. .. .. .. .. .. .. .. 240 +.. .. .. .. .. 238 +.. .. .. .. .. .. .. .. .. 236 +.. .. .. .. .. .. .. .. 234 +.. .. .. .. .. .. .. .. .. 232 +.. .. .. .. .. .. .. 230 +.. .. .. .. .. .. .. .. 228 +.. .. .. .. .. .. 226 +.. .. .. .. .. .. .. .. .. .. 224 +.. .. .. .. .. .. .. .. .. 222 +.. .. .. .. .. .. .. .. 220 +.. .. .. .. .. .. .. .. .. .. 218 +.. .. .. .. .. .. .. .. .. 216 +.. .. .. .. .. .. .. 214 +.. .. .. .. .. .. .. .. .. 212 +.. .. .. .. .. .. .. .. 210 +.. .. .. .. 208 +.. .. .. .. .. .. .. .. .. .. 206 +.. .. .. .. .. .. .. .. .. 204 +.. .. .. .. .. .. .. .. .. .. 202 +.. .. .. .. .. .. .. .. 200 +.. .. .. .. .. .. .. .. .. .. 198 +.. .. .. .. .. .. .. .. .. 196 +.. .. .. .. .. .. .. 194 +.. .. .. .. .. .. .. .. .. 192 +.. .. .. .. .. .. .. .. .. .. 190 +.. .. .. .. .. .. .. .. 188 +.. .. .. .. .. .. .. .. .. 186 +.. .. .. .. .. .. 184 +.. .. .. .. .. .. .. .. .. 182 +.. .. .. .. .. .. .. .. 180 +.. .. .. .. .. .. .. .. .. 178 +.. .. .. .. .. .. .. 176 +.. .. .. .. .. .. .. .. .. .. 174 +.. .. .. .. .. .. .. .. .. 172 +.. .. .. .. .. .. .. .. 170 +.. .. .. .. .. .. .. .. .. .. 168 +.. .. .. .. .. .. .. .. .. 166 +.. .. .. .. .. .. .. .. .. .. 164 +.. .. .. .. .. 162 +.. .. .. .. .. .. .. .. .. 160 +.. .. .. .. .. .. .. .. 158 +.. .. .. .. .. .. .. .. .. 156 +.. .. .. .. .. .. .. 154 +.. .. .. .. .. .. .. .. 152 +.. .. .. .. .. .. .. .. .. 150 +.. .. .. .. .. .. 148 +.. .. .. .. .. .. .. .. 146 +.. .. .. .. .. .. .. .. .. 144 +.. .. .. .. .. .. .. 142 +.. .. .. .. .. .. .. .. .. 140 +.. .. .. .. .. .. .. .. 138 +.. .. .. .. .. .. .. .. .. .. 136 +.. .. .. .. .. .. .. .. .. 134 +.. .. .. 132 +.. .. .. .. .. .. .. .. 130 +.. .. .. .. .. .. .. 128 +.. .. .. .. .. .. .. .. .. 126 +.. .. .. .. .. .. .. .. 124 +.. .. .. .. .. .. 122 +.. .. .. .. .. .. .. .. .. 120 +.. .. .. .. .. .. .. .. 118 +.. .. .. .. .. .. .. 116 +.. .. .. .. .. .. .. .. .. 114 +.. .. .. .. .. .. .. .. 112 +.. .. .. .. .. .. .. .. .. 110 +.. .. .. .. .. 108 +.. .. .. .. .. .. .. .. .. 106 +.. .. .. .. .. .. .. .. 104 +.. .. .. .. .. .. .. .. .. 102 +.. .. .. .. .. .. .. 100 +.. .. .. .. .. .. .. .. .. 98 +.. .. .. .. .. .. .. .. 96 +.. .. .. .. .. .. .. .. .. 94 +.. .. .. .. .. .. .. .. .. .. 92 +.. .. .. .. .. .. 90 +.. .. .. .. .. .. .. .. .. 88 +.. .. .. .. .. .. .. .. 86 +.. .. .. .. .. .. .. .. .. 84 +.. .. .. .. .. .. .. 82 +.. .. .. .. .. .. .. .. .. 80 +.. .. .. .. .. .. .. .. 78 +.. .. .. .. 76 +.. .. .. .. .. .. .. .. .. 74 +.. .. .. .. .. .. .. .. 72 +.. .. .. .. .. .. .. .. .. 70 +.. .. .. .. .. .. .. 68 +.. .. .. .. .. .. .. .. .. .. 66 +.. .. .. .. .. .. .. .. .. 64 +.. .. .. .. .. .. .. .. .. .. 62 +.. .. .. .. .. .. .. .. 60 +.. .. .. .. .. .. .. .. .. 58 +.. .. .. .. .. .. 56 +.. .. .. .. .. .. .. .. .. 54 +.. .. .. .. .. .. .. .. 52 +.. .. .. .. .. .. .. .. .. 50 +.. .. .. .. .. .. .. 48 +.. .. .. .. .. .. .. .. .. 46 +.. .. .. .. .. .. .. .. 44 +.. .. .. .. .. .. .. .. .. 42 +.. .. .. .. .. 40 +.. .. .. .. .. .. .. .. .. .. 38 +.. .. .. .. .. .. .. .. .. 36 +.. .. .. .. .. .. .. .. 34 +.. .. .. .. .. .. .. .. .. 32 +.. .. .. .. .. .. .. 30 +.. .. .. .. .. .. .. .. .. 28 +.. .. .. .. .. .. .. .. 26 +.. .. .. .. .. .. .. .. .. 24 +.. .. .. .. .. .. .. .. .. .. 22 +.. .. .. .. .. .. 20 +.. .. .. .. .. .. .. .. .. .. 18 +.. .. .. .. .. .. .. .. .. 16 +.. .. .. .. .. .. .. .. .. .. 14 +.. .. .. .. .. .. .. .. 12 +.. .. .. .. .. .. .. .. .. 10 +.. .. .. .. .. .. .. .. .. .. 8 +.. .. .. .. .. .. .. 6 +.. .. .. .. .. .. .. .. .. 4 +.. .. .. .. .. .. .. .. 2 +.. .. .. .. .. .. .. .. .. 0 +-- end oset1b ---------------- -- 2.47.2