lvm2-commits September 2018

lvm2-commits@lists.fedorahosted.org

4 participants
37 discussions

master - metadata: clarify comments about max size
by David Teigland 24 Sep '18

24 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=a49f494c4d9a3551fe63c… Commit: a49f494c4d9a3551fe63c702a9e8c3495fe066d0 Parent: 6be1efd13d212967e8518a46e5bce4ba81ab3b94 Author: David Teigland <teigland(a)redhat.com> AuthorDate: Mon Sep 24 15:27:03 2018 -0500 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Mon Sep 24 15:27:03 2018 -0500 metadata: clarify comments about max size Since there is now a direct limit of half the space. --- lib/format_text/format-text.c | 28 +++++++++++++--------------- 1 files changed, 13 insertions(+), 15 deletions(-) diff --git a/lib/format_text/format-text.c b/lib/format_text/format-text.c index c388a72..9634e47 100644 --- a/lib/format_text/format-text.c +++ b/lib/format_text/format-text.c @@ -1441,22 +1441,21 @@ int read_metadata_location_summary(const struct format_type *fmt, uint32_t wrap = 0; unsigned int len = 0; char buf[NAME_LEN + 1] __attribute__((aligned(8))); - - /* - * For the case where the metadata area is unused, we say that half of - * it is available, based on the fact that we keep two consecutive - * copies of the metadata in the area, so each copy can be as large as - * half the area. (Technically, one of those could be less than half - * and another could be more than half.) - */ - if (mda_free_sectors) - *mda_free_sectors = ((dev_area->size - MDA_HEADER_SIZE) / 2) >> SECTOR_SHIFT; + uint64_t max_size; if (!mdah) { log_error(INTERNAL_ERROR "read_metadata_location_summary called with NULL pointer for mda_header"); return 0; } + /* + * For the case where the metadata area is unused, half is available. + */ + if (mda_free_sectors) { + max_size = ((mdah->size - MDA_HEADER_SIZE) / 2) - 512; + *mda_free_sectors = max_size >> SECTOR_SHIFT; + } + rlocn = mdah->raw_locns; /* slot0, committed metadata */ /* @@ -1567,12 +1566,11 @@ int read_metadata_location_summary(const struct format_type *fmt, if (mda_free_sectors) { /* - * Report remaining space on the assumption that a single copy - * of metadata can be as large as half the total metadata - * space, minus 512 because each copy is rounded to begin - * on a sector boundary. + * Report remaining space given that a single copy of metadata + * can be as large as half the total metadata space, minus 512 + * because each copy is rounded to begin on a sector boundary. */ - uint64_t max_size = ((mdah->size - MDA_HEADER_SIZE) / 2) - 512; + max_size = ((mdah->size - MDA_HEADER_SIZE) / 2) - 512; if (rlocn->size >= max_size) *mda_free_sectors = UINT64_C(0);

1 0

master - metadata: add direct size limit
by David Teigland 24 Sep '18

24 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=6be1efd13d212967e8518… Commit: 6be1efd13d212967e8518a46e5bce4ba81ab3b94 Parent: 91c7e66f2b47f4ef814dcf85e1641d49e5123cc7 Author: David Teigland <teigland(a)redhat.com> AuthorDate: Mon Sep 24 14:41:58 2018 -0500 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Mon Sep 24 14:41:58 2018 -0500 metadata: add direct size limit Previously the size was limited by checking if the old and new copies of the metadata overlapped. This generally limited the size to about half of the total space, but it could be larger given the size differences between old and new. Now add a direct check to limit the size to half the space. --- lib/format_text/format-text.c | 40 ++++++++++++++++++++++++++++++++++------ 1 files changed, 34 insertions(+), 6 deletions(-) diff --git a/lib/format_text/format-text.c b/lib/format_text/format-text.c index de4be47..c388a72 100644 --- a/lib/format_text/format-text.c +++ b/lib/format_text/format-text.c @@ -682,6 +682,7 @@ static int _vg_write_raw(struct format_instance *fid, struct volume_group *vg, struct pv_list *pvl; uint64_t old_start = 0, old_last = 0, old_size = 0, old_wrap = 0; uint64_t new_start = 0, new_last = 0, new_size = 0, new_wrap = 0; + uint64_t max_size; char *new_buf = NULL; int overlap; int found = 0; @@ -722,6 +723,27 @@ static int _vg_write_raw(struct format_instance *fid, struct volume_group *vg, } /* + * The max size of a single copy of text metadata. + * + * The space available for all text metadata is the size of the + * metadata area (mdah->size) minus the sector used for the header. + * Two copies of the text metadata must fit in this space, so it is + * divided in two. This result is then reduced by 512 because any + * single copy of metadata is rounded to begin on a sector boundary. + */ + + max_size = ((mdah->size - MDA_HEADER_SIZE) / 2) - 512; + + if (new_size > max_size) { + log_error("VG %s metadata on %s (%llu bytes) exceeds maximum metadata size (%llu bytes)", + vg->name, + dev_name(mdac->area.dev), + (unsigned long long)new_size, + (unsigned long long)max_size); + goto out; + } + + /* * rlocn_old is the current, committed, raw_locn data in slot0 on disk. * * rlocn_new (mdac->rlocn) is the new, in-memory, raw_locn data for the @@ -816,6 +838,13 @@ static int _vg_write_raw(struct format_instance *fid, struct volume_group *vg, /* * If the new copy of the metadata would overlap the old copy of the * metadata, it means that the circular metadata buffer is full. + * + * Given the max_size restriction above, two copies of metadata should + * never overlap, so these overlap checks should not be technically + * necessary, and a failure should not occur here. It's left as a + * sanity check. For some unknown time, lvm did not enforce a + * max_size, but rather detected the too-large failure by checking for + * overlap between old and new. */ if (new_wrap && old_wrap) { @@ -1540,16 +1569,15 @@ int read_metadata_location_summary(const struct format_type *fmt, /* * Report remaining space on the assumption that a single copy * of metadata can be as large as half the total metadata - * space. Technically, it can be larger if the other copy is - * less. 511 is subtracted from max because the next copy can - * be rounded up by 511 bytes to start on a sector boundary. + * space, minus 512 because each copy is rounded to begin + * on a sector boundary. */ - uint64_t max = (mdah->size - MDA_HEADER_SIZE - 511) / 2; + uint64_t max_size = ((mdah->size - MDA_HEADER_SIZE) / 2) - 512; - if (rlocn->size >= max) + if (rlocn->size >= max_size) *mda_free_sectors = UINT64_C(0); else - *mda_free_sectors = (max - rlocn->size) >> SECTOR_SHIFT; + *mda_free_sectors = (max_size - rlocn->size) >> SECTOR_SHIFT; } return 1;

1 0

master - metadata: remove incorrect comment about alignment
by David Teigland 20 Sep '18

20 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=91c7e66f2b47f4ef814dc… Commit: 91c7e66f2b47f4ef814dcf85e1641d49e5123cc7 Parent: 09131e3922ffbea35733aecbc538cdbf415b43ac Author: David Teigland <teigland(a)redhat.com> AuthorDate: Thu Sep 20 15:37:06 2018 -0500 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Thu Sep 20 15:38:09 2018 -0500 metadata: remove incorrect comment about alignment --- lib/format_text/format-text.c | 5 ----- 1 files changed, 0 insertions(+), 5 deletions(-) diff --git a/lib/format_text/format-text.c b/lib/format_text/format-text.c index e987849..de4be47 100644 --- a/lib/format_text/format-text.c +++ b/lib/format_text/format-text.c @@ -487,11 +487,6 @@ static struct raw_locn *_read_metadata_location_vg(struct device_area *dev_area, /* * Determine offset for new metadata * - * Adjusting new offsets to begin on 512 boundaries is fairly new, and metadata - * previously begain immediately after the old, without rounding up. The - * rounding should have no practical benefit since it does not affect the - * actual disk io. - * * FIXME: The rounding can have a negative effect: when the current metadata * text size is just below the max, a command to remove something, that * *reduces* the text metadata size, can still be rejected for being too large,

1 0

master - metadata: add comment about negative impact of rounding
by David Teigland 20 Sep '18

20 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=09131e3922ffbea35733a… Commit: 09131e3922ffbea35733aecbc538cdbf415b43ac Parent: 30c94b0324f070ea3e8b746745572580fc8e0667 Author: David Teigland <teigland(a)redhat.com> AuthorDate: Thu Sep 20 14:15:49 2018 -0500 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Thu Sep 20 14:15:49 2018 -0500 metadata: add comment about negative impact of rounding --- lib/format_text/format-text.c | 13 +++++++++++++ 1 files changed, 13 insertions(+), 0 deletions(-) diff --git a/lib/format_text/format-text.c b/lib/format_text/format-text.c index 04a3a8d..e987849 100644 --- a/lib/format_text/format-text.c +++ b/lib/format_text/format-text.c @@ -486,7 +486,20 @@ static struct raw_locn *_read_metadata_location_vg(struct device_area *dev_area, /* * Determine offset for new metadata + * + * Adjusting new offsets to begin on 512 boundaries is fairly new, and metadata + * previously begain immediately after the old, without rounding up. The + * rounding should have no practical benefit since it does not affect the + * actual disk io. + * + * FIXME: The rounding can have a negative effect: when the current metadata + * text size is just below the max, a command to remove something, that + * *reduces* the text metadata size, can still be rejected for being too large, + * even though it's smaller than the current size. In this case, the user + * would need to find something in the VG to remove that uses more text space + * to compensate for the increase due to rounding. */ + static uint64_t _next_rlocn_offset(struct raw_locn *rlocn_old, uint64_t old_last, struct mda_header *mdah, uint64_t mdac_area_start, uint64_t alignment) { uint64_t next_start;

1 0

master - metadata: remove an unused and incorrect overflow check
by David Teigland 20 Sep '18

20 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=30c94b0324f070ea3e8b7… Commit: 30c94b0324f070ea3e8b746745572580fc8e0667 Parent: 8424655af9eed2f2422c904f8d3fa312fe61d00f Author: David Teigland <teigland(a)redhat.com> AuthorDate: Thu Sep 20 13:53:50 2018 -0500 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Thu Sep 20 13:53:50 2018 -0500 metadata: remove an unused and incorrect overflow check Remove another instance of an invalid check for metadata overflow during read. The previous instance was removed in commit 5fb15b193. This was checking for metadata that that overflowed the circular disk metadata buffer during read, but such metadata cannot be written, so it shouldn't be possible to find see. Also, the check was incorrect and could trigger when there was no overflow. --- lib/format_text/format-text.c | 8 -------- 1 files changed, 0 insertions(+), 8 deletions(-) diff --git a/lib/format_text/format-text.c b/lib/format_text/format-text.c index 7857091..04a3a8d 100644 --- a/lib/format_text/format-text.c +++ b/lib/format_text/format-text.c @@ -567,14 +567,6 @@ static struct volume_group *_vg_read_raw_area(struct format_instance *fid, if (rlocn->offset + rlocn->size > mdah->size) wrap = (uint32_t) ((rlocn->offset + rlocn->size) - mdah->size); - if (wrap > rlocn->offset) { - log_error("Metadata for VG %s on %s at %llu size %llu is too large for circular buffer.", - vgname, dev_name(area->dev), - (unsigned long long)(area->start + rlocn->offset), - (unsigned long long)rlocn->size); - goto out; - } - vg = text_read_metadata(fid, NULL, vg_fmtdata, use_previous_vg, area->dev, primary_mda, (off_t) (area->start + rlocn->offset), (uint32_t) (rlocn->size - wrap),

1 0

master - Merge branch '2018-09-13-radix-tree-bug'
by Joe Thornber 20 Sep '18

20 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=8424655af9eed2f2422c9… Commit: 8424655af9eed2f2422c904f8d3fa312fe61d00f Parent: 945d13541e50a25f859e471abea4d86f00ce0964 bda4f3a7ae5a3879105466d24fa274dd1a3e5c7b Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Thu Sep 20 14:43:51 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Sep 20 14:43:51 2018 +0100 Merge branch '2018-09-13-radix-tree-bug' base/Makefile | 2 +- base/data-struct/radix-tree-adaptive.c | 48 +- test/unit/Makefile | 2 + test/unit/radix_tree_t.c | 60 ++ test/unit/rt_case1.c | 1669 ++++++++++++++++++++++++++++++++ 5 files changed, 1769 insertions(+), 12 deletions(-) diff --cc base/Makefile index ff77815,7b21ca5..e30cb44 --- a/base/Makefile +++ b/base/Makefile @@@ -11,8 -11,7 +11,8 @@@ # Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA # Uncomment this to build the simple radix tree. You'll need to make clean too. +# Comment to build the advanced radix tree. - base/data-struct/radix-tree.o: CFLAGS += -DSIMPLE_RADIX_TREE + #base/data-struct/radix-tree.o: CFLAGS += -DSIMPLE_RADIX_TREE BASE_SOURCE=\ base/data-struct/radix-tree.c \

1 0

master - [unit-test/radix-tree] Add a huge test case
by Joe Thornber 20 Sep '18

20 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=ba6d8a319515b7c156999… Commit: ba6d8a319515b7c156999cc978c49d969a2b14a6 Parent: bb17302084192bd06facc5f6501206c3ab21b3a1 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Thu Sep 20 14:35:45 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Sep 20 14:38:34 2018 +0100 [unit-test/radix-tree] Add a huge test case Derived from the logs that dct gave me. --- test/unit/Makefile | 2 + test/unit/radix_tree_t.c | 60 ++ test/unit/rt_case1.c | 1669 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 1731 insertions(+), 0 deletions(-) diff --git a/test/unit/Makefile b/test/unit/Makefile index bf85354..0530fca 100644 --- a/test/unit/Makefile +++ b/test/unit/Makefile @@ -29,6 +29,8 @@ UNIT_SOURCE=\ test/unit/string_t.c \ test/unit/vdo_t.c +test/unit/radix_tree_t.o: test/unit/rt_case1.c + UNIT_DEPENDS=$(subst .c,.d,$(UNIT_SOURCE)) UNIT_OBJECTS=$(UNIT_SOURCE:%.c=%.o) CLEAN_TARGETS+=$(UNIT_DEPENDS) $(UNIT_OBJECTS) diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c index 0dde6b7..54bc406 100644 --- a/test/unit/radix_tree_t.c +++ b/test/unit/radix_tree_t.c @@ -750,6 +750,65 @@ static void test_bcache_scenario2(void *fixture) //---------------------------------------------------------------- +struct key_parts { + uint32_t fd; + uint64_t b; +} __attribute__ ((packed)); + +union key { + struct key_parts parts; + uint8_t bytes[12]; +}; + +static void __lookup_matches(struct radix_tree *rt, int fd, uint64_t b, uint64_t expected) +{ + union key k; + union radix_value v; + + k.parts.fd = fd; + k.parts.b = b; + T_ASSERT(radix_tree_lookup(rt, k.bytes, k.bytes + sizeof(k.bytes), &v)); + T_ASSERT(v.n == expected); +} + +static void __lookup_fails(struct radix_tree *rt, int fd, uint64_t b) +{ + union key k; + union radix_value v; + + k.parts.fd = fd; + k.parts.b = b; + T_ASSERT(!radix_tree_lookup(rt, k.bytes, k.bytes + sizeof(k.bytes), &v)); +} + +static void __insert(struct radix_tree *rt, int fd, uint64_t b, uint64_t n) +{ + union key k; + union radix_value v; + + k.parts.fd = fd; + k.parts.b = b; + v.n = n; + T_ASSERT(radix_tree_insert(rt, k.bytes, k.bytes + sizeof(k.bytes), v)); +} + +static void __invalidate(struct radix_tree *rt, int fd) +{ + union key k; + + k.parts.fd = fd; + radix_tree_remove_prefix(rt, k.bytes, k.bytes + sizeof(k.parts.fd)); + radix_tree_is_well_formed(rt); +} + +static void test_bcache_scenario3(void *fixture) +{ + struct radix_tree *rt = fixture; + + #include "test/unit/rt_case1.c" +} + +//---------------------------------------------------------------- #define T(path, desc, fn) register_test(ts, "/base/data-struct/radix-tree/" path, desc, fn) void radix_tree_tests(struct dm_list *all_tests) @@ -784,6 +843,7 @@ void radix_tree_tests(struct dm_list *all_tests) T("destroy-calls-dtr", "destroy should call the dtr for all values", test_destroy_calls_dtr); T("bcache-scenario", "A specific series of keys from a bcache scenario", test_bcache_scenario); T("bcache-scenario-2", "A second series of keys from a bcache scenario", test_bcache_scenario2); + T("bcache-scenario-3", "A third series of keys from a bcache scenario", test_bcache_scenario3); dm_list_add(all_tests, &ts->list); } diff --git a/test/unit/rt_case1.c b/test/unit/rt_case1.c new file mode 100644 index 0000000..c1677d1 --- /dev/null +++ b/test/unit/rt_case1.c @@ -0,0 +1,1669 @@ + __lookup_fails(rt, 6, 0); + __insert(rt, 6, 0, 0); + __lookup_fails(rt, 7, 0); + __insert(rt, 7, 0, 1); + __lookup_fails(rt, 8, 0); + __insert(rt, 8, 0, 2); + __lookup_fails(rt, 9, 0); + __insert(rt, 9, 0, 3); + __lookup_fails(rt, 10, 0); + __insert(rt, 10, 0, 4); + __lookup_fails(rt, 11, 0); + __insert(rt, 11, 0, 5); + __lookup_fails(rt, 12, 0); + __insert(rt, 12, 0, 6); + __lookup_fails(rt, 13, 0); + __insert(rt, 13, 0, 7); + __lookup_fails(rt, 14, 0); + __insert(rt, 14, 0, 8); + __lookup_fails(rt, 15, 0); + __insert(rt, 15, 0, 9); + __lookup_fails(rt, 16, 0); + __insert(rt, 16, 0, 10); + __lookup_fails(rt, 17, 0); + __insert(rt, 17, 0, 11); + __lookup_fails(rt, 18, 0); + __insert(rt, 18, 0, 12); + __lookup_fails(rt, 19, 0); + __insert(rt, 19, 0, 13); + __lookup_fails(rt, 20, 0); + __insert(rt, 20, 0, 14); + __lookup_fails(rt, 21, 0); + __insert(rt, 21, 0, 15); + __lookup_fails(rt, 22, 0); + __insert(rt, 22, 0, 16); + __lookup_fails(rt, 23, 0); + __insert(rt, 23, 0, 17); + __lookup_fails(rt, 24, 0); + __insert(rt, 24, 0, 18); + __lookup_fails(rt, 25, 0); + __insert(rt, 25, 0, 19); + __lookup_fails(rt, 26, 0); + __insert(rt, 26, 0, 20); + __lookup_fails(rt, 27, 0); + __insert(rt, 27, 0, 21); + __lookup_fails(rt, 28, 0); + __insert(rt, 28, 0, 22); + __lookup_fails(rt, 29, 0); + __insert(rt, 29, 0, 23); + __lookup_fails(rt, 30, 0); + __insert(rt, 30, 0, 24); + __lookup_fails(rt, 31, 0); + __insert(rt, 31, 0, 25); + __lookup_fails(rt, 32, 0); + __insert(rt, 32, 0, 26); + __lookup_fails(rt, 33, 0); + __insert(rt, 33, 0, 27); + __lookup_fails(rt, 34, 0); + __insert(rt, 34, 0, 28); + __lookup_fails(rt, 35, 0); + __insert(rt, 35, 0, 29); + __lookup_fails(rt, 36, 0); + __insert(rt, 36, 0, 30); + __lookup_fails(rt, 37, 0); + __insert(rt, 37, 0, 31); + __lookup_fails(rt, 38, 0); + __insert(rt, 38, 0, 32); + __lookup_fails(rt, 39, 0); + __insert(rt, 39, 0, 33); + __lookup_fails(rt, 40, 0); + __insert(rt, 40, 0, 34); + __lookup_fails(rt, 41, 0); + __insert(rt, 41, 0, 35); + __lookup_fails(rt, 42, 0); + __insert(rt, 42, 0, 36); + __lookup_fails(rt, 43, 0); + __insert(rt, 43, 0, 37); + __lookup_fails(rt, 44, 0); + __insert(rt, 44, 0, 38); + __lookup_fails(rt, 45, 0); + __insert(rt, 45, 0, 39); + __lookup_fails(rt, 46, 0); + __insert(rt, 46, 0, 40); + __lookup_fails(rt, 47, 0); + __insert(rt, 47, 0, 41); + __lookup_fails(rt, 48, 0); + __insert(rt, 48, 0, 42); + __lookup_fails(rt, 49, 0); + __insert(rt, 49, 0, 43); + __lookup_fails(rt, 50, 0); + __insert(rt, 50, 0, 44); + __lookup_fails(rt, 51, 0); + __insert(rt, 51, 0, 45); + __lookup_fails(rt, 52, 0); + __insert(rt, 52, 0, 46); + __lookup_fails(rt, 53, 0); + __insert(rt, 53, 0, 47); + __lookup_fails(rt, 54, 0); + __insert(rt, 54, 0, 48); + __lookup_fails(rt, 55, 0); + __insert(rt, 55, 0, 49); + __lookup_fails(rt, 56, 0); + __insert(rt, 56, 0, 50); + __lookup_fails(rt, 57, 0); + __insert(rt, 57, 0, 51); + __lookup_fails(rt, 58, 0); + __insert(rt, 58, 0, 52); + __lookup_fails(rt, 59, 0); + __insert(rt, 59, 0, 53); + __lookup_fails(rt, 60, 0); + __insert(rt, 60, 0, 54); + __lookup_fails(rt, 61, 0); + __insert(rt, 61, 0, 55); + __lookup_fails(rt, 62, 0); + __insert(rt, 62, 0, 56); + __lookup_fails(rt, 63, 0); + __insert(rt, 63, 0, 57); + __lookup_fails(rt, 64, 0); + __insert(rt, 64, 0, 58); + __lookup_fails(rt, 65, 0); + __insert(rt, 65, 0, 59); + __lookup_fails(rt, 66, 0); + __insert(rt, 66, 0, 60); + __lookup_fails(rt, 67, 0); + __insert(rt, 67, 0, 61); + __lookup_fails(rt, 68, 0); + __insert(rt, 68, 0, 62); + __lookup_fails(rt, 69, 0); + __insert(rt, 69, 0, 63); + __lookup_fails(rt, 70, 0); + __insert(rt, 70, 0, 64); + __lookup_fails(rt, 71, 0); + __insert(rt, 71, 0, 65); + __lookup_fails(rt, 72, 0); + __insert(rt, 72, 0, 66); + __lookup_fails(rt, 73, 0); + __insert(rt, 73, 0, 67); + __lookup_fails(rt, 74, 0); + __insert(rt, 74, 0, 68); + __lookup_fails(rt, 75, 0); + __insert(rt, 75, 0, 69); + __lookup_fails(rt, 76, 0); + __insert(rt, 76, 0, 70); + __lookup_fails(rt, 77, 0); + __insert(rt, 77, 0, 71); + __lookup_fails(rt, 78, 0); + __insert(rt, 78, 0, 72); + __lookup_fails(rt, 79, 0); + __insert(rt, 79, 0, 73); + __lookup_fails(rt, 80, 0); + __insert(rt, 80, 0, 74); + __lookup_fails(rt, 81, 0); + __insert(rt, 81, 0, 75); + __lookup_fails(rt, 82, 0); + __insert(rt, 82, 0, 76); + __lookup_fails(rt, 83, 0); + __insert(rt, 83, 0, 77); + __lookup_fails(rt, 84, 0); + __insert(rt, 84, 0, 78); + __lookup_fails(rt, 85, 0); + __insert(rt, 85, 0, 79); + __lookup_fails(rt, 86, 0); + __insert(rt, 86, 0, 80); + __lookup_fails(rt, 87, 0); + __insert(rt, 87, 0, 81); + __lookup_fails(rt, 88, 0); + __insert(rt, 88, 0, 82); + __lookup_fails(rt, 89, 0); + __insert(rt, 89, 0, 83); + __lookup_fails(rt, 90, 0); + __insert(rt, 90, 0, 84); + __lookup_fails(rt, 91, 0); + __insert(rt, 91, 0, 85); + __lookup_fails(rt, 92, 0); + __insert(rt, 92, 0, 86); + __lookup_fails(rt, 93, 0); + __insert(rt, 93, 0, 87); + __lookup_fails(rt, 94, 0); + __insert(rt, 94, 0, 88); + __lookup_fails(rt, 95, 0); + __insert(rt, 95, 0, 89); + __lookup_fails(rt, 96, 0); + __insert(rt, 96, 0, 90); + __lookup_fails(rt, 97, 0); + __insert(rt, 97, 0, 91); + __lookup_fails(rt, 98, 0); + __insert(rt, 98, 0, 92); + __lookup_fails(rt, 99, 0); + __insert(rt, 99, 0, 93); + __lookup_fails(rt, 100, 0); + __insert(rt, 100, 0, 94); + __lookup_fails(rt, 101, 0); + __insert(rt, 101, 0, 95); + __lookup_fails(rt, 102, 0); + __insert(rt, 102, 0, 96); + __lookup_fails(rt, 103, 0); + __insert(rt, 103, 0, 97); + __lookup_fails(rt, 104, 0); + __insert(rt, 104, 0, 98); + __lookup_fails(rt, 105, 0); + __insert(rt, 105, 0, 99); + __lookup_fails(rt, 106, 0); + __insert(rt, 106, 0, 100); + __lookup_fails(rt, 107, 0); + __insert(rt, 107, 0, 101); + __lookup_fails(rt, 108, 0); + __insert(rt, 108, 0, 102); + __lookup_fails(rt, 109, 0); + __insert(rt, 109, 0, 103); + __lookup_fails(rt, 110, 0); + __insert(rt, 110, 0, 104); + __lookup_fails(rt, 111, 0); + __insert(rt, 111, 0, 105); + __lookup_fails(rt, 112, 0); + __insert(rt, 112, 0, 106); + __lookup_fails(rt, 113, 0); + __insert(rt, 113, 0, 107); + __lookup_fails(rt, 114, 0); + __insert(rt, 114, 0, 108); + __lookup_fails(rt, 115, 0); + __insert(rt, 115, 0, 109); + __lookup_fails(rt, 116, 0); + __insert(rt, 116, 0, 110); + __lookup_fails(rt, 117, 0); + __insert(rt, 117, 0, 111); + __lookup_fails(rt, 118, 0); + __insert(rt, 118, 0, 112); + __lookup_fails(rt, 119, 0); + __insert(rt, 119, 0, 113); + __lookup_fails(rt, 120, 0); + __insert(rt, 120, 0, 114); + __lookup_fails(rt, 121, 0); + __insert(rt, 121, 0, 115); + __lookup_fails(rt, 122, 0); + __insert(rt, 122, 0, 116); + __lookup_fails(rt, 123, 0); + __insert(rt, 123, 0, 117); + __lookup_fails(rt, 124, 0); + __insert(rt, 124, 0, 118); + __lookup_fails(rt, 125, 0); + __insert(rt, 125, 0, 119); + __lookup_fails(rt, 126, 0); + __insert(rt, 126, 0, 120); + __lookup_fails(rt, 127, 0); + __insert(rt, 127, 0, 121); + __lookup_fails(rt, 128, 0); + __insert(rt, 128, 0, 122); + __lookup_fails(rt, 129, 0); + __insert(rt, 129, 0, 123); + __lookup_fails(rt, 130, 0); + __insert(rt, 130, 0, 124); + __lookup_fails(rt, 131, 0); + __insert(rt, 131, 0, 125); + __lookup_fails(rt, 132, 0); + __insert(rt, 132, 0, 126); + __lookup_fails(rt, 133, 0); + __insert(rt, 133, 0, 127); + __lookup_fails(rt, 134, 0); + __insert(rt, 134, 0, 128); + __lookup_fails(rt, 135, 0); + __insert(rt, 135, 0, 129); + __lookup_fails(rt, 136, 0); + __insert(rt, 136, 0, 130); + __lookup_fails(rt, 137, 0); + __insert(rt, 137, 0, 131); + __lookup_fails(rt, 138, 0); + __insert(rt, 138, 0, 132); + __lookup_fails(rt, 139, 0); + __insert(rt, 139, 0, 133); + __lookup_fails(rt, 140, 0); + __insert(rt, 140, 0, 134); + __lookup_fails(rt, 141, 0); + __insert(rt, 141, 0, 135); + __lookup_fails(rt, 142, 0); + __insert(rt, 142, 0, 136); + __lookup_fails(rt, 143, 0); + __insert(rt, 143, 0, 137); + __lookup_fails(rt, 144, 0); + __insert(rt, 144, 0, 138); + __lookup_fails(rt, 145, 0); + __insert(rt, 145, 0, 139); + __lookup_fails(rt, 146, 0); + __insert(rt, 146, 0, 140); + __lookup_fails(rt, 147, 0); + __insert(rt, 147, 0, 141); + __lookup_fails(rt, 148, 0); + __insert(rt, 148, 0, 142); + __lookup_fails(rt, 149, 0); + __insert(rt, 149, 0, 143); + __lookup_fails(rt, 150, 0); + __insert(rt, 150, 0, 144); + __lookup_fails(rt, 151, 0); + __insert(rt, 151, 0, 145); + __lookup_fails(rt, 152, 0); + __insert(rt, 152, 0, 146); + __lookup_fails(rt, 153, 0); + __insert(rt, 153, 0, 147); + __lookup_fails(rt, 154, 0); + __insert(rt, 154, 0, 148); + __lookup_fails(rt, 155, 0); + __insert(rt, 155, 0, 149); + __lookup_fails(rt, 156, 0); + __insert(rt, 156, 0, 150); + __lookup_fails(rt, 157, 0); + __insert(rt, 157, 0, 151); + __lookup_fails(rt, 158, 0); + __insert(rt, 158, 0, 152); + __lookup_fails(rt, 159, 0); + __insert(rt, 159, 0, 153); + __lookup_fails(rt, 160, 0); + __insert(rt, 160, 0, 154); + __lookup_fails(rt, 161, 0); + __insert(rt, 161, 0, 155); + __lookup_fails(rt, 162, 0); + __insert(rt, 162, 0, 156); + __lookup_fails(rt, 163, 0); + __insert(rt, 163, 0, 157); + __lookup_fails(rt, 164, 0); + __insert(rt, 164, 0, 158); + __lookup_fails(rt, 165, 0); + __insert(rt, 165, 0, 159); + __lookup_fails(rt, 166, 0); + __insert(rt, 166, 0, 160); + __lookup_fails(rt, 167, 0); + __insert(rt, 167, 0, 161); + __lookup_fails(rt, 168, 0); + __insert(rt, 168, 0, 162); + __lookup_fails(rt, 169, 0); + __insert(rt, 169, 0, 163); + __lookup_fails(rt, 170, 0); + __insert(rt, 170, 0, 164); + __lookup_fails(rt, 171, 0); + __insert(rt, 171, 0, 165); + __lookup_fails(rt, 172, 0); + __insert(rt, 172, 0, 166); + __lookup_fails(rt, 173, 0); + __insert(rt, 173, 0, 167); + __lookup_fails(rt, 174, 0); + __insert(rt, 174, 0, 168); + __lookup_fails(rt, 175, 0); + __insert(rt, 175, 0, 169); + __lookup_fails(rt, 176, 0); + __insert(rt, 176, 0, 170); + __lookup_fails(rt, 177, 0); + __insert(rt, 177, 0, 171); + __lookup_fails(rt, 178, 0); + __insert(rt, 178, 0, 172); + __lookup_fails(rt, 179, 0); + __insert(rt, 179, 0, 173); + __lookup_fails(rt, 180, 0); + __insert(rt, 180, 0, 174); + __lookup_fails(rt, 181, 0); + __insert(rt, 181, 0, 175); + __lookup_fails(rt, 182, 0); + __insert(rt, 182, 0, 176); + __lookup_fails(rt, 183, 0); + __insert(rt, 183, 0, 177); + __lookup_fails(rt, 184, 0); + __insert(rt, 184, 0, 178); + __lookup_fails(rt, 185, 0); + __insert(rt, 185, 0, 179); + __lookup_fails(rt, 186, 0); + __insert(rt, 186, 0, 180); + __lookup_fails(rt, 187, 0); + __insert(rt, 187, 0, 181); + __lookup_fails(rt, 188, 0); + __insert(rt, 188, 0, 182); + __lookup_fails(rt, 189, 0); + __insert(rt, 189, 0, 183); + __lookup_fails(rt, 190, 0); + __insert(rt, 190, 0, 184); + __lookup_fails(rt, 191, 0); + __insert(rt, 191, 0, 185); + __lookup_fails(rt, 192, 0); + __insert(rt, 192, 0, 186); + __lookup_fails(rt, 193, 0); + __insert(rt, 193, 0, 187); + __lookup_fails(rt, 194, 0); + __insert(rt, 194, 0, 188); + __lookup_fails(rt, 195, 0); + __insert(rt, 195, 0, 189); + __lookup_fails(rt, 196, 0); + __insert(rt, 196, 0, 190); + __lookup_fails(rt, 197, 0); + __insert(rt, 197, 0, 191); + __lookup_fails(rt, 198, 0); + __insert(rt, 198, 0, 192); + __lookup_fails(rt, 199, 0); + __insert(rt, 199, 0, 193); + __lookup_fails(rt, 200, 0); + __insert(rt, 200, 0, 194); + __lookup_fails(rt, 201, 0); + __insert(rt, 201, 0, 195); + __lookup_fails(rt, 202, 0); + __insert(rt, 202, 0, 196); + __lookup_fails(rt, 203, 0); + __insert(rt, 203, 0, 197); + __lookup_fails(rt, 204, 0); + __insert(rt, 204, 0, 198); + __lookup_fails(rt, 205, 0); + __insert(rt, 205, 0, 199); + __lookup_matches(rt, 6, 0, 0); + __invalidate(rt, 6); + __lookup_matches(rt, 7, 0, 1); + __invalidate(rt, 7); + __lookup_matches(rt, 8, 0, 2); + __invalidate(rt, 8); + __lookup_matches(rt, 9, 0, 3); + __invalidate(rt, 9); + __lookup_matches(rt, 10, 0, 4); + __invalidate(rt, 10); + __lookup_matches(rt, 11, 0, 5); + __invalidate(rt, 11); + __lookup_matches(rt, 12, 0, 6); + __lookup_matches(rt, 13, 0, 7); + __invalidate(rt, 13); + __lookup_matches(rt, 14, 0, 8); + __invalidate(rt, 14); + __lookup_matches(rt, 15, 0, 9); + __invalidate(rt, 15); + __lookup_matches(rt, 16, 0, 10); + __invalidate(rt, 16); + __lookup_matches(rt, 17, 0, 11); + __invalidate(rt, 17); + __lookup_matches(rt, 18, 0, 12); + __invalidate(rt, 18); + __lookup_matches(rt, 19, 0, 13); + __invalidate(rt, 19); + __lookup_matches(rt, 20, 0, 14); + __invalidate(rt, 20); + __lookup_matches(rt, 21, 0, 15); + __invalidate(rt, 21); + __lookup_matches(rt, 22, 0, 16); + __invalidate(rt, 22); + __lookup_matches(rt, 23, 0, 17); + __invalidate(rt, 23); + __lookup_matches(rt, 24, 0, 18); + __invalidate(rt, 24); + __lookup_matches(rt, 25, 0, 19); + __invalidate(rt, 25); + __lookup_matches(rt, 26, 0, 20); + __invalidate(rt, 26); + __lookup_matches(rt, 27, 0, 21); + __invalidate(rt, 27); + __lookup_matches(rt, 28, 0, 22); + __invalidate(rt, 28); + __lookup_matches(rt, 29, 0, 23); + __invalidate(rt, 29); + __lookup_matches(rt, 30, 0, 24); + __invalidate(rt, 30); + __lookup_matches(rt, 31, 0, 25); + __invalidate(rt, 31); + __lookup_matches(rt, 32, 0, 26); + __invalidate(rt, 32); + __lookup_matches(rt, 33, 0, 27); + __invalidate(rt, 33); + __lookup_matches(rt, 34, 0, 28); + __invalidate(rt, 34); + __lookup_matches(rt, 35, 0, 29); + __invalidate(rt, 35); + __lookup_matches(rt, 36, 0, 30); + __invalidate(rt, 36); + __lookup_matches(rt, 37, 0, 31); + __invalidate(rt, 37); + __lookup_matches(rt, 38, 0, 32); + __invalidate(rt, 38); + __lookup_matches(rt, 39, 0, 33); + __invalidate(rt, 39); + __lookup_matches(rt, 40, 0, 34); + __invalidate(rt, 40); + __lookup_matches(rt, 41, 0, 35); + __invalidate(rt, 41); + __lookup_matches(rt, 42, 0, 36); + __invalidate(rt, 42); + __lookup_matches(rt, 43, 0, 37); + __invalidate(rt, 43); + __lookup_matches(rt, 44, 0, 38); + __invalidate(rt, 44); + __lookup_matches(rt, 45, 0, 39); + __invalidate(rt, 45); + __lookup_matches(rt, 46, 0, 40); + __lookup_fails(rt, 46, 5); + __insert(rt, 46, 5, 200); + __lookup_matches(rt, 46, 5, 200); + __lookup_fails(rt, 46, 6); + __insert(rt, 46, 6, 201); + __lookup_fails(rt, 46, 7); + __insert(rt, 46, 7, 202); + __lookup_fails(rt, 46, 8); + __insert(rt, 46, 8, 203); + __lookup_matches(rt, 46, 5, 200); + __lookup_matches(rt, 46, 6, 201); + __lookup_matches(rt, 46, 7, 202); + __lookup_matches(rt, 46, 8, 203); + __lookup_matches(rt, 47, 0, 41); + __invalidate(rt, 47); + __lookup_matches(rt, 48, 0, 42); + __invalidate(rt, 48); + __lookup_matches(rt, 49, 0, 43); + __invalidate(rt, 49); + __lookup_matches(rt, 50, 0, 44); + __invalidate(rt, 50); + __lookup_matches(rt, 51, 0, 45); + __invalidate(rt, 51); + __lookup_matches(rt, 52, 0, 46); + __invalidate(rt, 52); + __lookup_matches(rt, 53, 0, 47); + __invalidate(rt, 53); + __lookup_matches(rt, 54, 0, 48); + __invalidate(rt, 54); + __lookup_matches(rt, 55, 0, 49); + __invalidate(rt, 55); + __lookup_matches(rt, 56, 0, 50); + __invalidate(rt, 56); + __lookup_matches(rt, 57, 0, 51); + __invalidate(rt, 57); + __lookup_matches(rt, 58, 0, 52); + __invalidate(rt, 58); + __lookup_matches(rt, 59, 0, 53); + __invalidate(rt, 59); + __lookup_matches(rt, 60, 0, 54); + __invalidate(rt, 60); + __lookup_matches(rt, 61, 0, 55); + __invalidate(rt, 61); + __lookup_matches(rt, 62, 0, 56); + __invalidate(rt, 62); + __lookup_matches(rt, 63, 0, 57); + __invalidate(rt, 63); + __lookup_matches(rt, 64, 0, 58); + __invalidate(rt, 64); + __lookup_matches(rt, 65, 0, 59); + __lookup_fails(rt, 65, 1); + __insert(rt, 65, 1, 204); + __lookup_fails(rt, 65, 2); + __insert(rt, 65, 2, 205); + __lookup_fails(rt, 65, 3); + __insert(rt, 65, 3, 206); + __lookup_fails(rt, 65, 4); + __insert(rt, 65, 4, 207); + __lookup_matches(rt, 65, 0, 59); + __lookup_matches(rt, 65, 1, 204); + __lookup_matches(rt, 65, 2, 205); + __lookup_matches(rt, 65, 3, 206); + __lookup_matches(rt, 65, 4, 207); + __lookup_matches(rt, 66, 0, 60); + __invalidate(rt, 66); + __lookup_matches(rt, 67, 0, 61); + __invalidate(rt, 67); + __lookup_matches(rt, 68, 0, 62); + __invalidate(rt, 68); + __lookup_matches(rt, 69, 0, 63); + __invalidate(rt, 69); + __lookup_matches(rt, 70, 0, 64); + __invalidate(rt, 70); + __lookup_matches(rt, 71, 0, 65); + __invalidate(rt, 71); + __lookup_matches(rt, 72, 0, 66); + __invalidate(rt, 72); + __lookup_matches(rt, 73, 0, 67); + __invalidate(rt, 73); + __lookup_matches(rt, 74, 0, 68); + __invalidate(rt, 74); + __lookup_matches(rt, 75, 0, 69); + __invalidate(rt, 75); + __lookup_matches(rt, 76, 0, 70); + __invalidate(rt, 76); + __lookup_matches(rt, 77, 0, 71); + __invalidate(rt, 77); + __lookup_matches(rt, 78, 0, 72); + __invalidate(rt, 78); + __lookup_matches(rt, 79, 0, 73); + __invalidate(rt, 79); + __lookup_matches(rt, 80, 0, 74); + __invalidate(rt, 80); + __lookup_matches(rt, 81, 0, 75); + __invalidate(rt, 81); + __lookup_matches(rt, 82, 0, 76); + __invalidate(rt, 82); + __lookup_matches(rt, 83, 0, 77); + __invalidate(rt, 83); + __lookup_matches(rt, 84, 0, 78); + __invalidate(rt, 84); + __lookup_matches(rt, 85, 0, 79); + __invalidate(rt, 85); + __lookup_matches(rt, 86, 0, 80); + __invalidate(rt, 86); + __lookup_matches(rt, 87, 0, 81); + __invalidate(rt, 87); + __lookup_matches(rt, 88, 0, 82); + __invalidate(rt, 88); + __lookup_matches(rt, 89, 0, 83); + __invalidate(rt, 89); + __lookup_matches(rt, 90, 0, 84); + __invalidate(rt, 90); + __lookup_matches(rt, 91, 0, 85); + __invalidate(rt, 91); + __lookup_matches(rt, 92, 0, 86); + __invalidate(rt, 92); + __lookup_matches(rt, 93, 0, 87); + __invalidate(rt, 93); + __lookup_matches(rt, 94, 0, 88); + __invalidate(rt, 94); + __lookup_matches(rt, 95, 0, 89); + __invalidate(rt, 95); + __lookup_matches(rt, 96, 0, 90); + __lookup_matches(rt, 97, 0, 91); + __invalidate(rt, 97); + __lookup_matches(rt, 98, 0, 92); + __invalidate(rt, 98); + __lookup_matches(rt, 99, 0, 93); + __invalidate(rt, 99); + __lookup_matches(rt, 100, 0, 94); + __invalidate(rt, 100); + __lookup_matches(rt, 101, 0, 95); + __invalidate(rt, 101); + __lookup_matches(rt, 102, 0, 96); + __invalidate(rt, 102); + __lookup_matches(rt, 103, 0, 97); + __invalidate(rt, 103); + __lookup_matches(rt, 104, 0, 98); + __invalidate(rt, 104); + __lookup_matches(rt, 105, 0, 99); + __invalidate(rt, 105); + __lookup_matches(rt, 106, 0, 100); + __invalidate(rt, 106); + __lookup_matches(rt, 107, 0, 101); + __invalidate(rt, 107); + __lookup_matches(rt, 108, 0, 102); + __invalidate(rt, 108); + __lookup_matches(rt, 109, 0, 103); + __invalidate(rt, 109); + __lookup_matches(rt, 110, 0, 104); + __invalidate(rt, 110); + __lookup_matches(rt, 111, 0, 105); + __invalidate(rt, 111); + __lookup_matches(rt, 112, 0, 106); + __invalidate(rt, 112); + __lookup_matches(rt, 113, 0, 107); + __invalidate(rt, 113); + __lookup_matches(rt, 114, 0, 108); + __invalidate(rt, 114); + __lookup_matches(rt, 115, 0, 109); + __invalidate(rt, 115); + __lookup_matches(rt, 116, 0, 110); + __invalidate(rt, 116); + __lookup_matches(rt, 117, 0, 111); + __invalidate(rt, 117); + __lookup_matches(rt, 118, 0, 112); + __invalidate(rt, 118); + __lookup_matches(rt, 119, 0, 113); + __invalidate(rt, 119); + __lookup_matches(rt, 120, 0, 114); + __invalidate(rt, 120); + __lookup_matches(rt, 121, 0, 115); + __invalidate(rt, 121); + __lookup_matches(rt, 122, 0, 116); + __invalidate(rt, 122); + __lookup_matches(rt, 123, 0, 117); + __invalidate(rt, 123); + __lookup_matches(rt, 124, 0, 118); + __invalidate(rt, 124); + __lookup_matches(rt, 125, 0, 119); + __invalidate(rt, 125); + __lookup_matches(rt, 126, 0, 120); + __invalidate(rt, 126); + __lookup_matches(rt, 127, 0, 121); + __invalidate(rt, 127); + __lookup_matches(rt, 128, 0, 122); + __invalidate(rt, 128); + __lookup_matches(rt, 129, 0, 123); + __invalidate(rt, 129); + __lookup_matches(rt, 130, 0, 124); + __invalidate(rt, 130); + __lookup_matches(rt, 131, 0, 125); + __invalidate(rt, 131); + __lookup_matches(rt, 132, 0, 126); + __invalidate(rt, 132); + __lookup_matches(rt, 133, 0, 127); + __invalidate(rt, 133); + __lookup_matches(rt, 134, 0, 128); + __invalidate(rt, 134); + __lookup_matches(rt, 135, 0, 129); + __invalidate(rt, 135); + __lookup_matches(rt, 136, 0, 130); + __invalidate(rt, 136); + __lookup_matches(rt, 137, 0, 131); + __invalidate(rt, 137); + __lookup_matches(rt, 138, 0, 132); + __invalidate(rt, 138); + __lookup_matches(rt, 139, 0, 133); + __invalidate(rt, 139); + __lookup_matches(rt, 140, 0, 134); + __invalidate(rt, 140); + __lookup_matches(rt, 141, 0, 135); + __invalidate(rt, 141); + __lookup_matches(rt, 142, 0, 136); + __invalidate(rt, 142); + __lookup_matches(rt, 143, 0, 137); + __invalidate(rt, 143); + __lookup_matches(rt, 144, 0, 138); + __invalidate(rt, 144); + __lookup_matches(rt, 145, 0, 139); + __invalidate(rt, 145); + __lookup_matches(rt, 146, 0, 140); + __invalidate(rt, 146); + __lookup_matches(rt, 147, 0, 141); + __invalidate(rt, 147); + __lookup_matches(rt, 148, 0, 142); + __invalidate(rt, 148); + __lookup_matches(rt, 149, 0, 143); + __invalidate(rt, 149); + __lookup_matches(rt, 150, 0, 144); + __invalidate(rt, 150); + __lookup_matches(rt, 151, 0, 145); + __invalidate(rt, 151); + __lookup_matches(rt, 152, 0, 146); + __invalidate(rt, 152); + __lookup_matches(rt, 153, 0, 147); + __invalidate(rt, 153); + __lookup_matches(rt, 154, 0, 148); + __invalidate(rt, 154); + __lookup_matches(rt, 155, 0, 149); + __invalidate(rt, 155); + __lookup_matches(rt, 156, 0, 150); + __invalidate(rt, 156); + __lookup_matches(rt, 157, 0, 151); + __invalidate(rt, 157); + __lookup_matches(rt, 158, 0, 152); + __invalidate(rt, 158); + __lookup_matches(rt, 159, 0, 153); + __invalidate(rt, 159); + __lookup_matches(rt, 160, 0, 154); + __invalidate(rt, 160); + __lookup_matches(rt, 161, 0, 155); + __invalidate(rt, 161); + __lookup_matches(rt, 162, 0, 156); + __invalidate(rt, 162); + __lookup_matches(rt, 163, 0, 157); + __lookup_matches(rt, 164, 0, 158); + __invalidate(rt, 164); + __lookup_matches(rt, 165, 0, 159); + __invalidate(rt, 165); + __lookup_matches(rt, 166, 0, 160); + __invalidate(rt, 166); + __lookup_matches(rt, 167, 0, 161); + __invalidate(rt, 167); + __lookup_matches(rt, 168, 0, 162); + __invalidate(rt, 168); + __lookup_matches(rt, 169, 0, 163); + __invalidate(rt, 169); + __lookup_matches(rt, 170, 0, 164); + __invalidate(rt, 170); + __lookup_matches(rt, 171, 0, 165); + __invalidate(rt, 171); + __lookup_matches(rt, 172, 0, 166); + __invalidate(rt, 172); + __lookup_matches(rt, 173, 0, 167); + __invalidate(rt, 173); + __lookup_matches(rt, 174, 0, 168); + __invalidate(rt, 174); + __lookup_matches(rt, 175, 0, 169); + __invalidate(rt, 175); + __lookup_matches(rt, 176, 0, 170); + __invalidate(rt, 176); + __lookup_matches(rt, 177, 0, 171); + __invalidate(rt, 177); + __lookup_matches(rt, 178, 0, 172); + __invalidate(rt, 178); + __lookup_matches(rt, 179, 0, 173); + __invalidate(rt, 179); + __lookup_matches(rt, 180, 0, 174); + __invalidate(rt, 180); + __lookup_matches(rt, 181, 0, 175); + __invalidate(rt, 181); + __lookup_matches(rt, 182, 0, 176); + __invalidate(rt, 182); + __lookup_matches(rt, 183, 0, 177); + __invalidate(rt, 183); + __lookup_matches(rt, 184, 0, 178); + __invalidate(rt, 184); + __lookup_matches(rt, 185, 0, 179); + __invalidate(rt, 185); + __lookup_matches(rt, 186, 0, 180); + __invalidate(rt, 186); + __lookup_matches(rt, 187, 0, 181); + __invalidate(rt, 187); + __lookup_matches(rt, 188, 0, 182); + __invalidate(rt, 188); + __lookup_matches(rt, 189, 0, 183); + __invalidate(rt, 189); + __lookup_matches(rt, 190, 0, 184); + __invalidate(rt, 190); + __lookup_matches(rt, 191, 0, 185); + __invalidate(rt, 191); + __lookup_matches(rt, 192, 0, 186); + __invalidate(rt, 192); + __lookup_matches(rt, 193, 0, 187); + __invalidate(rt, 193); + __lookup_matches(rt, 194, 0, 188); + __invalidate(rt, 194); + __lookup_matches(rt, 195, 0, 189); + __invalidate(rt, 195); + __lookup_matches(rt, 196, 0, 190); + __invalidate(rt, 196); + __lookup_matches(rt, 197, 0, 191); + __invalidate(rt, 197); + __lookup_matches(rt, 198, 0, 192); + __invalidate(rt, 198); + __lookup_matches(rt, 199, 0, 193); + __invalidate(rt, 199); + __lookup_matches(rt, 200, 0, 194); + __invalidate(rt, 200); + __lookup_matches(rt, 201, 0, 195); + __invalidate(rt, 201); + __lookup_matches(rt, 202, 0, 196); + __invalidate(rt, 202); + __lookup_matches(rt, 203, 0, 197); + __invalidate(rt, 203); + __lookup_matches(rt, 204, 0, 198); + __invalidate(rt, 204); + __lookup_matches(rt, 205, 0, 199); + __invalidate(rt, 205); + __lookup_fails(rt, 6, 0); + __insert(rt, 6, 0, 208); + __lookup_fails(rt, 7, 0); + __insert(rt, 7, 0, 209); + __lookup_fails(rt, 8, 0); + __insert(rt, 8, 0, 210); + __lookup_fails(rt, 9, 0); + __insert(rt, 9, 0, 211); + __lookup_fails(rt, 10, 0); + __insert(rt, 10, 0, 212); + __lookup_fails(rt, 11, 0); + __insert(rt, 11, 0, 213); + __lookup_fails(rt, 13, 0); + __insert(rt, 13, 0, 214); + __lookup_fails(rt, 14, 0); + __insert(rt, 14, 0, 215); + __lookup_fails(rt, 15, 0); + __insert(rt, 15, 0, 216); + __lookup_fails(rt, 16, 0); + __insert(rt, 16, 0, 217); + __lookup_fails(rt, 17, 0); + __insert(rt, 17, 0, 218); + __lookup_fails(rt, 18, 0); + __insert(rt, 18, 0, 219); + __lookup_fails(rt, 19, 0); + __insert(rt, 19, 0, 220); + __lookup_fails(rt, 20, 0); + __insert(rt, 20, 0, 221); + __lookup_fails(rt, 21, 0); + __insert(rt, 21, 0, 222); + __lookup_fails(rt, 22, 0); + __insert(rt, 22, 0, 223); + __lookup_fails(rt, 23, 0); + __insert(rt, 23, 0, 224); + __lookup_fails(rt, 24, 0); + __insert(rt, 24, 0, 225); + __lookup_fails(rt, 25, 0); + __insert(rt, 25, 0, 226); + __lookup_fails(rt, 26, 0); + __insert(rt, 26, 0, 227); + __lookup_fails(rt, 27, 0); + __insert(rt, 27, 0, 228); + __lookup_fails(rt, 28, 0); + __insert(rt, 28, 0, 229); + __lookup_fails(rt, 29, 0); + __insert(rt, 29, 0, 230); + __lookup_fails(rt, 30, 0); + __insert(rt, 30, 0, 231); + __lookup_fails(rt, 31, 0); + __insert(rt, 31, 0, 232); + __lookup_fails(rt, 32, 0); + __insert(rt, 32, 0, 233); + __lookup_fails(rt, 33, 0); + __insert(rt, 33, 0, 234); + __lookup_fails(rt, 34, 0); + __insert(rt, 34, 0, 235); + __lookup_fails(rt, 35, 0); + __insert(rt, 35, 0, 236); + __lookup_fails(rt, 36, 0); + __insert(rt, 36, 0, 237); + __lookup_fails(rt, 37, 0); + __insert(rt, 37, 0, 238); + __lookup_fails(rt, 38, 0); + __insert(rt, 38, 0, 239); + __lookup_fails(rt, 39, 0); + __insert(rt, 39, 0, 240); + __lookup_fails(rt, 40, 0); + __insert(rt, 40, 0, 241); + __lookup_fails(rt, 41, 0); + __insert(rt, 41, 0, 242); + __lookup_fails(rt, 42, 0); + __insert(rt, 42, 0, 243); + __lookup_fails(rt, 43, 0); + __insert(rt, 43, 0, 244); + __lookup_fails(rt, 44, 0); + __insert(rt, 44, 0, 245); + __lookup_fails(rt, 45, 0); + __insert(rt, 45, 0, 246); + __lookup_fails(rt, 47, 0); + __insert(rt, 47, 0, 247); + __lookup_fails(rt, 48, 0); + __insert(rt, 48, 0, 248); + __lookup_fails(rt, 49, 0); + __insert(rt, 49, 0, 249); + __lookup_fails(rt, 50, 0); + __insert(rt, 50, 0, 250); + __lookup_fails(rt, 51, 0); + __insert(rt, 51, 0, 251); + __lookup_fails(rt, 52, 0); + __insert(rt, 52, 0, 252); + __lookup_fails(rt, 53, 0); + __insert(rt, 53, 0, 253); + __lookup_fails(rt, 54, 0); + __insert(rt, 54, 0, 254); + __lookup_fails(rt, 55, 0); + __insert(rt, 55, 0, 255); + __lookup_fails(rt, 56, 0); + __insert(rt, 56, 0, 256); + __lookup_fails(rt, 57, 0); + __insert(rt, 57, 0, 257); + __lookup_fails(rt, 58, 0); + __insert(rt, 58, 0, 258); + __lookup_fails(rt, 59, 0); + __insert(rt, 59, 0, 259); + __lookup_fails(rt, 60, 0); + __insert(rt, 60, 0, 260); + __lookup_fails(rt, 61, 0); + __insert(rt, 61, 0, 261); + __lookup_fails(rt, 62, 0); + __insert(rt, 62, 0, 262); + __lookup_fails(rt, 63, 0); + __insert(rt, 63, 0, 263); + __lookup_fails(rt, 64, 0); + __insert(rt, 64, 0, 264); + __lookup_fails(rt, 66, 0); + __insert(rt, 66, 0, 265); + __lookup_fails(rt, 67, 0); + __insert(rt, 67, 0, 266); + __lookup_fails(rt, 68, 0); + __insert(rt, 68, 0, 267); + __lookup_fails(rt, 69, 0); + __insert(rt, 69, 0, 268); + __lookup_fails(rt, 70, 0); + __insert(rt, 70, 0, 269); + __lookup_fails(rt, 71, 0); + __insert(rt, 71, 0, 270); + __lookup_fails(rt, 72, 0); + __insert(rt, 72, 0, 271); + __lookup_fails(rt, 73, 0); + __insert(rt, 73, 0, 272); + __lookup_fails(rt, 74, 0); + __insert(rt, 74, 0, 273); + __lookup_fails(rt, 75, 0); + __insert(rt, 75, 0, 274); + __lookup_fails(rt, 76, 0); + __insert(rt, 76, 0, 275); + __lookup_fails(rt, 77, 0); + __insert(rt, 77, 0, 276); + __lookup_fails(rt, 78, 0); + __insert(rt, 78, 0, 277); + __lookup_fails(rt, 79, 0); + __insert(rt, 79, 0, 278); + __lookup_fails(rt, 80, 0); + __insert(rt, 80, 0, 279); + __lookup_fails(rt, 81, 0); + __insert(rt, 81, 0, 280); + __lookup_fails(rt, 82, 0); + __insert(rt, 82, 0, 281); + __lookup_fails(rt, 83, 0); + __insert(rt, 83, 0, 282); + __lookup_fails(rt, 84, 0); + __insert(rt, 84, 0, 283); + __lookup_fails(rt, 85, 0); + __insert(rt, 85, 0, 284); + __lookup_fails(rt, 86, 0); + __insert(rt, 86, 0, 285); + __lookup_fails(rt, 87, 0); + __insert(rt, 87, 0, 286); + __lookup_fails(rt, 88, 0); + __insert(rt, 88, 0, 287); + __lookup_fails(rt, 89, 0); + __insert(rt, 89, 0, 288); + __lookup_fails(rt, 90, 0); + __insert(rt, 90, 0, 289); + __lookup_fails(rt, 91, 0); + __insert(rt, 91, 0, 290); + __lookup_fails(rt, 92, 0); + __insert(rt, 92, 0, 291); + __lookup_fails(rt, 93, 0); + __insert(rt, 93, 0, 292); + __lookup_fails(rt, 94, 0); + __insert(rt, 94, 0, 293); + __lookup_fails(rt, 95, 0); + __insert(rt, 95, 0, 294); + __lookup_fails(rt, 97, 0); + __insert(rt, 97, 0, 295); + __lookup_fails(rt, 98, 0); + __insert(rt, 98, 0, 296); + __lookup_fails(rt, 99, 0); + __insert(rt, 99, 0, 297); + __lookup_fails(rt, 100, 0); + __insert(rt, 100, 0, 298); + __lookup_fails(rt, 101, 0); + __insert(rt, 101, 0, 299); + __lookup_fails(rt, 102, 0); + __insert(rt, 102, 0, 300); + __lookup_fails(rt, 103, 0); + __insert(rt, 103, 0, 301); + __lookup_fails(rt, 104, 0); + __insert(rt, 104, 0, 302); + __lookup_fails(rt, 105, 0); + __insert(rt, 105, 0, 303); + __lookup_fails(rt, 106, 0); + __insert(rt, 106, 0, 304); + __lookup_fails(rt, 107, 0); + __insert(rt, 107, 0, 305); + __lookup_fails(rt, 108, 0); + __insert(rt, 108, 0, 306); + __lookup_fails(rt, 109, 0); + __insert(rt, 109, 0, 307); + __lookup_fails(rt, 110, 0); + __insert(rt, 110, 0, 308); + __lookup_fails(rt, 111, 0); + __insert(rt, 111, 0, 309); + __lookup_fails(rt, 112, 0); + __insert(rt, 112, 0, 310); + __lookup_fails(rt, 113, 0); + __insert(rt, 113, 0, 311); + __lookup_fails(rt, 114, 0); + __insert(rt, 114, 0, 312); + __lookup_fails(rt, 115, 0); + __insert(rt, 115, 0, 313); + __lookup_fails(rt, 116, 0); + __insert(rt, 116, 0, 314); + __lookup_fails(rt, 117, 0); + __insert(rt, 117, 0, 315); + __lookup_fails(rt, 118, 0); + __insert(rt, 118, 0, 316); + __lookup_fails(rt, 119, 0); + __insert(rt, 119, 0, 317); + __lookup_fails(rt, 120, 0); + __insert(rt, 120, 0, 318); + __lookup_fails(rt, 121, 0); + __insert(rt, 121, 0, 319); + __lookup_fails(rt, 122, 0); + __insert(rt, 122, 0, 320); + __lookup_fails(rt, 123, 0); + __insert(rt, 123, 0, 321); + __lookup_fails(rt, 124, 0); + __insert(rt, 124, 0, 322); + __lookup_fails(rt, 125, 0); + __insert(rt, 125, 0, 323); + __lookup_fails(rt, 126, 0); + __insert(rt, 126, 0, 324); + __lookup_fails(rt, 127, 0); + __insert(rt, 127, 0, 325); + __lookup_fails(rt, 128, 0); + __insert(rt, 128, 0, 326); + __lookup_fails(rt, 129, 0); + __insert(rt, 129, 0, 327); + __lookup_fails(rt, 130, 0); + __insert(rt, 130, 0, 328); + __lookup_fails(rt, 131, 0); + __insert(rt, 131, 0, 329); + __lookup_fails(rt, 132, 0); + __insert(rt, 132, 0, 330); + __lookup_fails(rt, 133, 0); + __insert(rt, 133, 0, 331); + __lookup_fails(rt, 134, 0); + __insert(rt, 134, 0, 332); + __lookup_fails(rt, 135, 0); + __insert(rt, 135, 0, 333); + __lookup_fails(rt, 136, 0); + __insert(rt, 136, 0, 334); + __lookup_fails(rt, 137, 0); + __insert(rt, 137, 0, 335); + __lookup_fails(rt, 138, 0); + __insert(rt, 138, 0, 336); + __lookup_fails(rt, 139, 0); + __insert(rt, 139, 0, 337); + __lookup_fails(rt, 140, 0); + __insert(rt, 140, 0, 338); + __lookup_fails(rt, 141, 0); + __insert(rt, 141, 0, 339); + __lookup_fails(rt, 142, 0); + __insert(rt, 142, 0, 340); + __lookup_fails(rt, 143, 0); + __insert(rt, 143, 0, 341); + __lookup_fails(rt, 144, 0); + __insert(rt, 144, 0, 342); + __lookup_fails(rt, 145, 0); + __insert(rt, 145, 0, 343); + __lookup_fails(rt, 146, 0); + __insert(rt, 146, 0, 344); + __lookup_fails(rt, 147, 0); + __insert(rt, 147, 0, 345); + __lookup_fails(rt, 148, 0); + __insert(rt, 148, 0, 346); + __lookup_fails(rt, 149, 0); + __insert(rt, 149, 0, 347); + __lookup_fails(rt, 150, 0); + __insert(rt, 150, 0, 348); + __lookup_fails(rt, 151, 0); + __insert(rt, 151, 0, 349); + __lookup_fails(rt, 152, 0); + __insert(rt, 152, 0, 350); + __lookup_fails(rt, 153, 0); + __insert(rt, 153, 0, 351); + __lookup_fails(rt, 154, 0); + __insert(rt, 154, 0, 352); + __lookup_fails(rt, 155, 0); + __insert(rt, 155, 0, 353); + __lookup_fails(rt, 156, 0); + __insert(rt, 156, 0, 354); + __lookup_fails(rt, 157, 0); + __insert(rt, 157, 0, 355); + __lookup_fails(rt, 158, 0); + __insert(rt, 158, 0, 356); + __lookup_fails(rt, 159, 0); + __insert(rt, 159, 0, 357); + __lookup_fails(rt, 160, 0); + __insert(rt, 160, 0, 358); + __lookup_fails(rt, 161, 0); + __insert(rt, 161, 0, 359); + __lookup_fails(rt, 162, 0); + __insert(rt, 162, 0, 360); + __lookup_fails(rt, 164, 0); + __insert(rt, 164, 0, 361); + __lookup_fails(rt, 165, 0); + __insert(rt, 165, 0, 362); + __lookup_fails(rt, 166, 0); + __insert(rt, 166, 0, 363); + __lookup_fails(rt, 167, 0); + __insert(rt, 167, 0, 364); + __lookup_fails(rt, 168, 0); + __insert(rt, 168, 0, 365); + __lookup_fails(rt, 169, 0); + __insert(rt, 169, 0, 366); + __lookup_fails(rt, 170, 0); + __insert(rt, 170, 0, 367); + __lookup_fails(rt, 171, 0); + __insert(rt, 171, 0, 368); + __lookup_fails(rt, 172, 0); + __insert(rt, 172, 0, 369); + __lookup_fails(rt, 173, 0); + __insert(rt, 173, 0, 370); + __lookup_fails(rt, 174, 0); + __insert(rt, 174, 0, 371); + __lookup_fails(rt, 175, 0); + __insert(rt, 175, 0, 372); + __lookup_fails(rt, 176, 0); + __insert(rt, 176, 0, 373); + __lookup_fails(rt, 177, 0); + __insert(rt, 177, 0, 374); + __lookup_fails(rt, 178, 0); + __insert(rt, 178, 0, 375); + __lookup_fails(rt, 179, 0); + __insert(rt, 179, 0, 376); + __lookup_fails(rt, 180, 0); + __insert(rt, 180, 0, 377); + __lookup_fails(rt, 181, 0); + __insert(rt, 181, 0, 378); + __lookup_fails(rt, 182, 0); + __insert(rt, 182, 0, 379); + __lookup_fails(rt, 183, 0); + __insert(rt, 183, 0, 380); + __lookup_fails(rt, 184, 0); + __insert(rt, 184, 0, 381); + __lookup_fails(rt, 185, 0); + __insert(rt, 185, 0, 382); + __lookup_fails(rt, 186, 0); + __insert(rt, 186, 0, 383); + __lookup_fails(rt, 187, 0); + __insert(rt, 187, 0, 384); + __lookup_fails(rt, 188, 0); + __insert(rt, 188, 0, 385); + __lookup_fails(rt, 189, 0); + __insert(rt, 189, 0, 386); + __lookup_fails(rt, 190, 0); + __insert(rt, 190, 0, 387); + __lookup_fails(rt, 191, 0); + __insert(rt, 191, 0, 388); + __lookup_fails(rt, 192, 0); + __insert(rt, 192, 0, 389); + __lookup_fails(rt, 193, 0); + __insert(rt, 193, 0, 390); + __lookup_fails(rt, 194, 0); + __insert(rt, 194, 0, 391); + __lookup_fails(rt, 195, 0); + __insert(rt, 195, 0, 392); + __lookup_fails(rt, 196, 0); + __insert(rt, 196, 0, 393); + __lookup_fails(rt, 197, 0); + __insert(rt, 197, 0, 394); + __lookup_fails(rt, 198, 0); + __insert(rt, 198, 0, 395); + __lookup_fails(rt, 199, 0); + __insert(rt, 199, 0, 396); + __lookup_fails(rt, 200, 0); + __insert(rt, 200, 0, 397); + __lookup_fails(rt, 201, 0); + __insert(rt, 201, 0, 398); + __lookup_fails(rt, 202, 0); + __insert(rt, 202, 0, 399); + __lookup_fails(rt, 203, 0); + __insert(rt, 203, 0, 400); + __lookup_fails(rt, 204, 0); + __insert(rt, 204, 0, 401); + __lookup_fails(rt, 205, 0); + __insert(rt, 205, 0, 402); + __lookup_fails(rt, 206, 0); + __insert(rt, 206, 0, 403); + __lookup_fails(rt, 207, 0); + __insert(rt, 207, 0, 404); + __lookup_fails(rt, 208, 0); + __insert(rt, 208, 0, 405); + __lookup_fails(rt, 209, 0); + __insert(rt, 209, 0, 406); + __lookup_fails(rt, 210, 0); + __insert(rt, 210, 0, 407); + __lookup_matches(rt, 6, 0, 208); + __invalidate(rt, 6); + __lookup_matches(rt, 7, 0, 209); + __invalidate(rt, 7); + __lookup_matches(rt, 8, 0, 210); + __invalidate(rt, 8); + __lookup_matches(rt, 9, 0, 211); + __invalidate(rt, 9); + __lookup_matches(rt, 10, 0, 212); + __invalidate(rt, 10); + __lookup_matches(rt, 11, 0, 213); + __invalidate(rt, 11); + __lookup_matches(rt, 13, 0, 214); + __invalidate(rt, 13); + __lookup_matches(rt, 14, 0, 215); + __invalidate(rt, 14); + __lookup_matches(rt, 15, 0, 216); + __invalidate(rt, 15); + __lookup_matches(rt, 16, 0, 217); + __invalidate(rt, 16); + __lookup_matches(rt, 17, 0, 218); + __invalidate(rt, 17); + __lookup_matches(rt, 18, 0, 219); + __invalidate(rt, 18); + __lookup_matches(rt, 19, 0, 220); + __invalidate(rt, 19); + __lookup_matches(rt, 20, 0, 221); + __invalidate(rt, 20); + __lookup_matches(rt, 21, 0, 222); + __invalidate(rt, 21); + __lookup_matches(rt, 22, 0, 223); + __invalidate(rt, 22); + __lookup_matches(rt, 23, 0, 224); + __invalidate(rt, 23); + __lookup_matches(rt, 24, 0, 225); + __invalidate(rt, 24); + __lookup_matches(rt, 25, 0, 226); + __invalidate(rt, 25); + __lookup_matches(rt, 26, 0, 227); + __invalidate(rt, 26); + __lookup_matches(rt, 27, 0, 228); + __invalidate(rt, 27); + __lookup_matches(rt, 28, 0, 229); + __invalidate(rt, 28); + __lookup_matches(rt, 29, 0, 230); + __invalidate(rt, 29); + __lookup_matches(rt, 30, 0, 231); + __invalidate(rt, 30); + __lookup_matches(rt, 31, 0, 232); + __invalidate(rt, 31); + __lookup_matches(rt, 32, 0, 233); + __invalidate(rt, 32); + __lookup_matches(rt, 33, 0, 234); + __invalidate(rt, 33); + __lookup_matches(rt, 34, 0, 235); + __invalidate(rt, 34); + __lookup_matches(rt, 35, 0, 236); + __invalidate(rt, 35); + __lookup_matches(rt, 36, 0, 237); + __invalidate(rt, 36); + __lookup_matches(rt, 37, 0, 238); + __invalidate(rt, 37); + __lookup_matches(rt, 38, 0, 239); + __invalidate(rt, 38); + __lookup_matches(rt, 39, 0, 240); + __invalidate(rt, 39); + __lookup_matches(rt, 40, 0, 241); + __invalidate(rt, 40); + __lookup_matches(rt, 41, 0, 242); + __invalidate(rt, 41); + __lookup_matches(rt, 42, 0, 243); + __invalidate(rt, 42); + __lookup_matches(rt, 43, 0, 244); + __invalidate(rt, 43); + __lookup_matches(rt, 44, 0, 245); + __invalidate(rt, 44); + __lookup_matches(rt, 45, 0, 246); + __invalidate(rt, 45); + __lookup_matches(rt, 47, 0, 247); + __invalidate(rt, 47); + __lookup_matches(rt, 48, 0, 248); + __invalidate(rt, 48); + __lookup_matches(rt, 49, 0, 249); + __invalidate(rt, 49); + __lookup_matches(rt, 50, 0, 250); + __invalidate(rt, 50); + __lookup_matches(rt, 51, 0, 251); + __invalidate(rt, 51); + __lookup_matches(rt, 52, 0, 252); + __invalidate(rt, 52); + __lookup_matches(rt, 53, 0, 253); + __invalidate(rt, 53); + __lookup_matches(rt, 54, 0, 254); + __invalidate(rt, 54); + __lookup_matches(rt, 55, 0, 255); + __invalidate(rt, 55); + __lookup_matches(rt, 56, 0, 256); + __invalidate(rt, 56); + __lookup_matches(rt, 57, 0, 257); + __invalidate(rt, 57); + __lookup_matches(rt, 58, 0, 258); + __invalidate(rt, 58); + __lookup_matches(rt, 59, 0, 259); + __invalidate(rt, 59); + __lookup_matches(rt, 60, 0, 260); + __invalidate(rt, 60); + __lookup_matches(rt, 61, 0, 261); + __invalidate(rt, 61); + __lookup_matches(rt, 62, 0, 262); + __invalidate(rt, 62); + __lookup_matches(rt, 63, 0, 263); + __invalidate(rt, 63); + __lookup_matches(rt, 64, 0, 264); + __invalidate(rt, 64); + __lookup_matches(rt, 66, 0, 265); + __invalidate(rt, 66); + __lookup_matches(rt, 67, 0, 266); + __invalidate(rt, 67); + __lookup_matches(rt, 68, 0, 267); + __invalidate(rt, 68); + __lookup_matches(rt, 69, 0, 268); + __invalidate(rt, 69); + __lookup_matches(rt, 70, 0, 269); + __invalidate(rt, 70); + __lookup_matches(rt, 71, 0, 270); + __invalidate(rt, 71); + __lookup_matches(rt, 72, 0, 271); + __invalidate(rt, 72); + __lookup_matches(rt, 73, 0, 272); + __lookup_matches(rt, 74, 0, 273); + __invalidate(rt, 74); + __lookup_matches(rt, 75, 0, 274); + __invalidate(rt, 75); + __lookup_matches(rt, 76, 0, 275); + __invalidate(rt, 76); + __lookup_matches(rt, 77, 0, 276); + __invalidate(rt, 77); + __lookup_matches(rt, 78, 0, 277); + __invalidate(rt, 78); + __lookup_matches(rt, 79, 0, 278); + __invalidate(rt, 79); + __lookup_matches(rt, 80, 0, 279); + __invalidate(rt, 80); + __lookup_matches(rt, 81, 0, 280); + __invalidate(rt, 81); + __lookup_matches(rt, 82, 0, 281); + __invalidate(rt, 82); + __lookup_matches(rt, 83, 0, 282); + __invalidate(rt, 83); + __lookup_matches(rt, 84, 0, 283); + __invalidate(rt, 84); + __lookup_matches(rt, 85, 0, 284); + __invalidate(rt, 85); + __lookup_matches(rt, 86, 0, 285); + __invalidate(rt, 86); + __lookup_matches(rt, 87, 0, 286); + __invalidate(rt, 87); + __lookup_matches(rt, 88, 0, 287); + __invalidate(rt, 88); + __lookup_matches(rt, 89, 0, 288); + __invalidate(rt, 89); + __lookup_matches(rt, 90, 0, 289); + __invalidate(rt, 90); + __lookup_matches(rt, 91, 0, 290); + __invalidate(rt, 91); + __lookup_matches(rt, 92, 0, 291); + __invalidate(rt, 92); + __lookup_matches(rt, 93, 0, 292); + __invalidate(rt, 93); + __lookup_matches(rt, 94, 0, 293); + __invalidate(rt, 94); + __lookup_matches(rt, 95, 0, 294); + __invalidate(rt, 95); + __lookup_matches(rt, 97, 0, 295); + __invalidate(rt, 97); + __lookup_matches(rt, 98, 0, 296); + __invalidate(rt, 98); + __lookup_matches(rt, 99, 0, 297); + __invalidate(rt, 99); + __lookup_matches(rt, 100, 0, 298); + __invalidate(rt, 100); + __lookup_matches(rt, 101, 0, 299); + __invalidate(rt, 101); + __lookup_matches(rt, 102, 0, 300); + __invalidate(rt, 102); + __lookup_matches(rt, 103, 0, 301); + __invalidate(rt, 103); + __lookup_matches(rt, 104, 0, 302); + __invalidate(rt, 104); + __lookup_matches(rt, 105, 0, 303); + __invalidate(rt, 105); + __lookup_matches(rt, 106, 0, 304); + __invalidate(rt, 106); + __lookup_matches(rt, 107, 0, 305); + __invalidate(rt, 107); + __lookup_matches(rt, 108, 0, 306); + __invalidate(rt, 108); + __lookup_matches(rt, 109, 0, 307); + __invalidate(rt, 109); + __lookup_matches(rt, 110, 0, 308); + __invalidate(rt, 110); + __lookup_matches(rt, 111, 0, 309); + __invalidate(rt, 111); + __lookup_matches(rt, 112, 0, 310); + __invalidate(rt, 112); + __lookup_matches(rt, 113, 0, 311); + __invalidate(rt, 113); + __lookup_matches(rt, 114, 0, 312); + __invalidate(rt, 114); + __lookup_matches(rt, 115, 0, 313); + __invalidate(rt, 115); + __lookup_matches(rt, 116, 0, 314); + __invalidate(rt, 116); + __lookup_matches(rt, 117, 0, 315); + __invalidate(rt, 117); + __lookup_matches(rt, 118, 0, 316); + __invalidate(rt, 118); + __lookup_matches(rt, 119, 0, 317); + __invalidate(rt, 119); + __lookup_matches(rt, 120, 0, 318); + __invalidate(rt, 120); + __lookup_matches(rt, 121, 0, 319); + __invalidate(rt, 121); + __lookup_matches(rt, 122, 0, 320); + __invalidate(rt, 122); + __lookup_matches(rt, 123, 0, 321); + __invalidate(rt, 123); + __lookup_matches(rt, 124, 0, 322); + __invalidate(rt, 124); + __lookup_matches(rt, 125, 0, 323); + __invalidate(rt, 125); + __lookup_matches(rt, 126, 0, 324); + __invalidate(rt, 126); + __lookup_matches(rt, 127, 0, 325); + __invalidate(rt, 127); + __lookup_matches(rt, 128, 0, 326); + __invalidate(rt, 128); + __lookup_matches(rt, 129, 0, 327); + __invalidate(rt, 129); + __lookup_matches(rt, 130, 0, 328); + __invalidate(rt, 130); + __lookup_matches(rt, 131, 0, 329); + __invalidate(rt, 131); + __lookup_matches(rt, 132, 0, 330); + __invalidate(rt, 132); + __lookup_matches(rt, 133, 0, 331); + __invalidate(rt, 133); + __lookup_matches(rt, 134, 0, 332); + __invalidate(rt, 134); + __lookup_matches(rt, 135, 0, 333); + __invalidate(rt, 135); + __lookup_matches(rt, 136, 0, 334); + __invalidate(rt, 136); + __lookup_matches(rt, 137, 0, 335); + __invalidate(rt, 137); + __lookup_matches(rt, 138, 0, 336); + __invalidate(rt, 138); + __lookup_matches(rt, 139, 0, 337); + __invalidate(rt, 139); + __lookup_matches(rt, 140, 0, 338); + __invalidate(rt, 140); + __lookup_matches(rt, 141, 0, 339); + __invalidate(rt, 141); + __lookup_matches(rt, 142, 0, 340); + __invalidate(rt, 142); + __lookup_matches(rt, 143, 0, 341); + __invalidate(rt, 143); + __lookup_matches(rt, 144, 0, 342); + __invalidate(rt, 144); + __lookup_matches(rt, 145, 0, 343); + __invalidate(rt, 145); + __lookup_matches(rt, 146, 0, 344); + __invalidate(rt, 146); + __lookup_matches(rt, 147, 0, 345); + __invalidate(rt, 147); + __lookup_matches(rt, 148, 0, 346); + __invalidate(rt, 148); + __lookup_matches(rt, 149, 0, 347); + __invalidate(rt, 149); + __lookup_matches(rt, 150, 0, 348); + __invalidate(rt, 150); + __lookup_matches(rt, 151, 0, 349); + __invalidate(rt, 151); + __lookup_matches(rt, 152, 0, 350); + __invalidate(rt, 152); + __lookup_matches(rt, 153, 0, 351); + __invalidate(rt, 153); + __lookup_matches(rt, 154, 0, 352); + __invalidate(rt, 154); + __lookup_matches(rt, 155, 0, 353); + __invalidate(rt, 155); + __lookup_matches(rt, 156, 0, 354); + __invalidate(rt, 156); + __lookup_matches(rt, 157, 0, 355); + __invalidate(rt, 157); + __lookup_matches(rt, 158, 0, 356); + __invalidate(rt, 158); + __lookup_matches(rt, 159, 0, 357); + __invalidate(rt, 159); + __lookup_matches(rt, 160, 0, 358); + __invalidate(rt, 160); + __lookup_matches(rt, 161, 0, 359); + __invalidate(rt, 161); + __lookup_matches(rt, 162, 0, 360); + __invalidate(rt, 162); + __lookup_matches(rt, 164, 0, 361); + __invalidate(rt, 164); + __lookup_matches(rt, 165, 0, 362); + __invalidate(rt, 165); + __lookup_matches(rt, 166, 0, 363); + __invalidate(rt, 166); + __lookup_matches(rt, 167, 0, 364); + __invalidate(rt, 167); + __lookup_matches(rt, 168, 0, 365); + __invalidate(rt, 168); + __lookup_matches(rt, 169, 0, 366); + __invalidate(rt, 169); + __lookup_matches(rt, 170, 0, 367); + __invalidate(rt, 170); + __lookup_matches(rt, 171, 0, 368); + __invalidate(rt, 171); + __lookup_matches(rt, 172, 0, 369); + __invalidate(rt, 172); + __lookup_matches(rt, 173, 0, 370); + __invalidate(rt, 173); + __lookup_matches(rt, 174, 0, 371); + __invalidate(rt, 174); + __lookup_matches(rt, 175, 0, 372); + __invalidate(rt, 175); + __lookup_matches(rt, 176, 0, 373); + __invalidate(rt, 176); + __lookup_matches(rt, 177, 0, 374); + __invalidate(rt, 177); + __lookup_matches(rt, 178, 0, 375); + __invalidate(rt, 178); + __lookup_matches(rt, 179, 0, 376); + __invalidate(rt, 179); + __lookup_matches(rt, 180, 0, 377); + __invalidate(rt, 180); + __lookup_matches(rt, 181, 0, 378); + __invalidate(rt, 181); + __lookup_matches(rt, 182, 0, 379); + __invalidate(rt, 182); + __lookup_matches(rt, 183, 0, 380); + __invalidate(rt, 183); + __lookup_matches(rt, 184, 0, 381); + __invalidate(rt, 184); + __lookup_matches(rt, 185, 0, 382); + __invalidate(rt, 185); + __lookup_matches(rt, 186, 0, 383); + __invalidate(rt, 186); + __lookup_matches(rt, 187, 0, 384); + __invalidate(rt, 187); + __lookup_matches(rt, 188, 0, 385); + __invalidate(rt, 188); + __lookup_matches(rt, 189, 0, 386); + __invalidate(rt, 189); + __lookup_matches(rt, 190, 0, 387); + __invalidate(rt, 190); + __lookup_matches(rt, 191, 0, 388); + __invalidate(rt, 191); + __lookup_matches(rt, 192, 0, 389); + __invalidate(rt, 192); + __lookup_matches(rt, 193, 0, 390); + __invalidate(rt, 193); + __lookup_matches(rt, 194, 0, 391); + __invalidate(rt, 194); + __lookup_matches(rt, 195, 0, 392); + __invalidate(rt, 195); + __lookup_matches(rt, 196, 0, 393); + __invalidate(rt, 196); + __lookup_matches(rt, 197, 0, 394); + __invalidate(rt, 197); + __lookup_matches(rt, 198, 0, 395); + __invalidate(rt, 198); + __lookup_matches(rt, 199, 0, 396); + __invalidate(rt, 199); + __lookup_matches(rt, 200, 0, 397); + __invalidate(rt, 200); + __lookup_matches(rt, 201, 0, 398); + __invalidate(rt, 201); + __lookup_matches(rt, 202, 0, 399); + __invalidate(rt, 202); + __lookup_matches(rt, 203, 0, 400); + __invalidate(rt, 203); + __lookup_matches(rt, 204, 0, 401); + __invalidate(rt, 204); + __lookup_matches(rt, 205, 0, 402); + __invalidate(rt, 205); + __lookup_matches(rt, 206, 0, 403); + __invalidate(rt, 206); + __lookup_matches(rt, 207, 0, 404); + __invalidate(rt, 207); + __lookup_matches(rt, 208, 0, 405); + __invalidate(rt, 208); + __lookup_matches(rt, 209, 0, 406); + __invalidate(rt, 209); + __lookup_matches(rt, 210, 0, 407); + __invalidate(rt, 210); + __lookup_fails(rt, 6, 0); + __insert(rt, 6, 0, 408); + __lookup_fails(rt, 7, 0); + __insert(rt, 7, 0, 409); + __lookup_fails(rt, 8, 0); + __insert(rt, 8, 0, 410); + __lookup_fails(rt, 9, 0); + __insert(rt, 9, 0, 411); + __lookup_fails(rt, 10, 0); + __insert(rt, 10, 0, 412); + __lookup_fails(rt, 11, 0); + __insert(rt, 11, 0, 413); + __lookup_fails(rt, 13, 0); + __insert(rt, 13, 0, 414); + __lookup_fails(rt, 14, 0); + __insert(rt, 14, 0, 415); + __lookup_fails(rt, 15, 0); + __insert(rt, 15, 0, 416); + __lookup_fails(rt, 16, 0); + __insert(rt, 16, 0, 417); + __lookup_fails(rt, 17, 0); + __insert(rt, 17, 0, 418); + __lookup_fails(rt, 18, 0); + __insert(rt, 18, 0, 419); + __lookup_fails(rt, 19, 0); + __insert(rt, 19, 0, 420); + __lookup_fails(rt, 20, 0); + __insert(rt, 20, 0, 421); + __lookup_fails(rt, 21, 0); + __insert(rt, 21, 0, 422); + __lookup_fails(rt, 22, 0); + __insert(rt, 22, 0, 423); + __lookup_fails(rt, 23, 0); + __insert(rt, 23, 0, 424); + __lookup_matches(rt, 6, 0, 408); + __invalidate(rt, 6); + __lookup_matches(rt, 7, 0, 409); + __invalidate(rt, 7); + __lookup_matches(rt, 8, 0, 410); + __invalidate(rt, 8); + __lookup_matches(rt, 9, 0, 411); + __invalidate(rt, 9); + __lookup_matches(rt, 10, 0, 412); + __invalidate(rt, 10); + __lookup_matches(rt, 11, 0, 413); + __invalidate(rt, 11); + __lookup_matches(rt, 13, 0, 414); + __invalidate(rt, 13); + __lookup_matches(rt, 14, 0, 415);

1 0

master - [build] switch back to the adaptive radix tree
by Joe Thornber 20 Sep '18

20 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=bda4f3a7ae5a387910546… Commit: bda4f3a7ae5a3879105466d24fa274dd1a3e5c7b Parent: ba6d8a319515b7c156999cc978c49d969a2b14a6 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Thu Sep 20 14:40:28 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Sep 20 14:40:28 2018 +0100 [build] switch back to the adaptive radix tree --- base/Makefile | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/base/Makefile b/base/Makefile index 1823c9b..7b21ca5 100644 --- a/base/Makefile +++ b/base/Makefile @@ -11,7 +11,7 @@ # Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA # Uncomment this to build the simple radix tree. You'll need to make clean too. -# base/data-struct/radix-tree.o: CFLAGS += -DSIMPLE_RADIX_TREE +#base/data-struct/radix-tree.o: CFLAGS += -DSIMPLE_RADIX_TREE BASE_SOURCE=\ base/data-struct/radix-tree.c \

1 0

master - [radix-tree] tidy up _degrade_to_n48
by Joe Thornber 20 Sep '18

20 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=bb17302084192bd06facc… Commit: bb17302084192bd06facc5f6501206c3ab21b3a1 Parent: ebd2d7773f2531bd5dddb97c061ddb74af117844 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Thu Sep 20 14:28:47 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Sep 20 14:28:47 2018 +0100 [radix-tree] tidy up _degrade_to_n48 Shouldn't be any functional changes. --- base/data-struct/radix-tree-adaptive.c | 12 ++++++------ 1 files changed, 6 insertions(+), 6 deletions(-) diff --git a/base/data-struct/radix-tree-adaptive.c b/base/data-struct/radix-tree-adaptive.c index 23e69f8..cd53dd6 100644 --- a/base/data-struct/radix-tree-adaptive.c +++ b/base/data-struct/radix-tree-adaptive.c @@ -597,16 +597,16 @@ static void _degrade_to_n48(struct node256 *n256, struct value *result) unsigned i, count = 0; struct node48 *n48 = zalloc(sizeof(*n48)); - memset(n48->keys, 48, sizeof(n48->keys)); - n48->nr_entries = n256->nr_entries; for (i = 0; i < 256; i++) { if (n256->values[i].type == UNSET) - continue; + n48->keys[i] = 48; - n48->keys[i] = count; - n48->values[count] = n256->values[i]; - count++; + else { + n48->keys[i] = count; + n48->values[count] = n256->values[i]; + count++; + } } free(n256);

1 0

master - [radix-tree] Fix bug in _degrade_to_n16
by Joe Thornber 20 Sep '18

20 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=ebd2d7773f2531bd5dddb… Commit: ebd2d7773f2531bd5dddb97c061ddb74af117844 Parent: 0ac7913c6a43c5bcfbba735652041a0eae4180c6 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Thu Sep 20 14:20:16 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Sep 20 14:20:16 2018 +0100 [radix-tree] Fix bug in _degrade_to_n16 Values were getting shuffled --- base/data-struct/radix-tree-adaptive.c | 3 +-- 1 files changed, 1 insertions(+), 2 deletions(-) diff --git a/base/data-struct/radix-tree-adaptive.c b/base/data-struct/radix-tree-adaptive.c index a657b2b..23e69f8 100644 --- a/base/data-struct/radix-tree-adaptive.c +++ b/base/data-struct/radix-tree-adaptive.c @@ -581,12 +581,11 @@ static void _degrade_to_n16(struct node48 *n48, struct value *result) for (i = 0; i < 256; i++) { if (n48->keys[i] < 48) { n16->keys[count] = i; + n16->values[count] = n48->values[n48->keys[i]]; count++; } } - memcpy(n16->values, n48->values, n48->nr_entries * sizeof(*n16->values)); - free(n48); result->type = NODE16;

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

lvm2-commits September 2018