From 6957519054ad15b46c32c0ff1ec071d453fcefaf Mon Sep 17 00:00:00 2001 From: Curtis McEnroe Date: Wed, 21 Nov 2018 16:11:28 -0500 Subject: Track hot slice in tables --- bin/edi/edi.h | 3 ++- bin/edi/table.c | 82 ++++++++++++++++++++++++++++++++++++++++++--------------- 2 files changed, 63 insertions(+), 22 deletions(-) diff --git a/bin/edi/edi.h b/bin/edi/edi.h index 4e127b94..412e6d19 100644 --- a/bin/edi/edi.h +++ b/bin/edi/edi.h @@ -49,9 +49,10 @@ wchar_t *bufferDest(struct Buffer *buf, size_t len); struct Table { size_t len; + size_t hot; struct Slice *slices; }; -static const struct Table TableEmpty = { 0, NULL }; +static const struct Table TableEmpty = { 0, 0, NULL }; struct Table tableInsert(struct Table prev, size_t at, struct Slice ins); struct Table tableDelete(struct Table prev, struct Span del); diff --git a/bin/edi/table.c b/bin/edi/table.c index bb84c38e..c4d6ab24 100644 --- a/bin/edi/table.c +++ b/bin/edi/table.c @@ -24,13 +24,13 @@ static struct Table alloc(size_t cap) { struct Slice *slices = malloc(sizeof(*slices) * cap); if (!slices) err(EX_OSERR, "malloc"); - return (struct Table) { 0, slices }; + return (struct Table) { 0, 0, slices }; } struct Table tableInsert(struct Table prev, size_t at, struct Slice ins) { if (!prev.len) { struct Table next = alloc(1); - next.slices[next.len++] = ins; + next.slices[next.hot = next.len++] = ins; return next; } @@ -39,14 +39,14 @@ struct Table tableInsert(struct Table prev, size_t at, struct Slice ins) { for (size_t i = 0; i < prev.len; ++i) { span = spanNext(span, prev.slices[i].len); if (span.at == at) { - next.slices[next.len++] = ins; + next.slices[next.hot = next.len++] = ins; next.slices[next.len++] = prev.slices[i]; } else if (span.at < at && span.to > at) { next.slices[next.len++] = (struct Slice) { prev.slices[i].ptr, at - span.at, }; - next.slices[next.len++] = ins; + next.slices[next.hot = next.len++] = ins; next.slices[next.len++] = (struct Slice) { &prev.slices[i].ptr[at - span.at], prev.slices[i].len - (at - span.at), @@ -56,7 +56,7 @@ struct Table tableInsert(struct Table prev, size_t at, struct Slice ins) { } } if (span.to == at) { - next.slices[next.len++] = ins; + next.slices[next.hot = next.len++] = ins; } return next; } @@ -69,12 +69,13 @@ struct Table tableDelete(struct Table prev, struct Span del) { span = spanNext(span, prev.slices[i].len); if (span.at >= del.at && span.to <= del.to) { (void)prev.slices[i]; + next.hot = next.len; } else if (span.at < del.at && span.to > del.to) { next.slices[next.len++] = (struct Slice) { prev.slices[i].ptr, del.at - span.at, }; - next.slices[next.len++] = (struct Slice) { + next.slices[next.hot = next.len++] = (struct Slice) { &prev.slices[i].ptr[del.to - span.at], prev.slices[i].len - (del.to - span.at), }; @@ -83,8 +84,9 @@ struct Table tableDelete(struct Table prev, struct Span del) { prev.slices[i].ptr, del.at - span.at, }; + next.hot = next.len; } else if (span.at < del.to && span.to > del.to) { - next.slices[next.len++] = (struct Slice) { + next.slices[next.hot = next.len++] = (struct Slice) { &prev.slices[i].ptr[del.to - span.at], prev.slices[i].len - (del.to - span.at), }; @@ -98,36 +100,74 @@ struct Table tableDelete(struct Table prev, struct Span del) { #ifdef TEST #include -static struct Span span(size_t at, size_t to) { - return (struct Span) { at, to }; -} - static struct Slice slice(const wchar_t *str) { return (struct Slice) { str, wcslen(str) }; } -static int eq(struct Table table, const wchar_t *str) { +static struct Span span(size_t at, size_t to) { + return (struct Span) { at, to }; +} + +static int eq(const wchar_t *str, struct Table table) { for (size_t i = 0; i < table.len; ++i) { if (wcsncmp(str, table.slices[i].ptr, table.slices[i].len)) { return 0; } str = &str[table.slices[i].len]; } - return 1; + return !str[0]; +} + +static int hot(wint_t ch, struct Table table) { + if (table.hot == table.len) { + return ch == WEOF; + } else { + return ch == table.slices[table.hot].ptr[0]; + } } int main() { struct Table abc = tableInsert(TableEmpty, 0, slice(L"ABC")); - assert(eq(abc, L"ABC")); + assert(eq(L"ABC", abc)); + assert(hot(L'A', abc)); + + struct Table dabc = tableInsert(abc, 0, slice(L"D")); + struct Table abcd = tableInsert(abc, 3, slice(L"D")); + struct Table adbc = tableInsert(abc, 1, slice(L"D")); + + assert(eq(L"DABC", dabc)); + assert(eq(L"ABCD", abcd)); + assert(eq(L"ADBC", adbc)); + + assert(hot(L'D', dabc)); + assert(hot(L'D', abcd)); + assert(hot(L'D', adbc)); + + free(dabc.slices); + free(abcd.slices); + free(adbc.slices); + + struct Table bc = tableDelete(abc, span(0, 1)); + struct Table ab = tableDelete(abc, span(2, 3)); + struct Table ac = tableDelete(abc, span(1, 2)); + struct Table __ = tableDelete(abc, span(0, 3)); + + assert(eq(L"BC", bc)); + assert(eq(L"AB", ab)); + assert(eq(L"AC", ac)); + assert(eq(L"", __)); + + assert(hot(L'B', bc)); + assert(hot(WEOF, ab)); + assert(hot(L'C', ac)); + assert(hot(WEOF, __)); - assert(eq(tableInsert(abc, 0, slice(L"D")), L"DABC")); - assert(eq(tableInsert(abc, 3, slice(L"D")), L"ABCD")); - assert(eq(tableInsert(abc, 1, slice(L"D")), L"ADBC")); + free(bc.slices); + free(ab.slices); + free(ac.slices); + free(__.slices); - assert(eq(tableDelete(abc, span(0, 1)), L"BC")); - assert(eq(tableDelete(abc, span(2, 3)), L"AB")); - assert(eq(tableDelete(abc, span(1, 2)), L"AC")); - assert(eq(tableDelete(abc, span(0, 3)), L"")); + free(abc.slices); } #endif -- cgit 1.4.1 class='logmsg'> 2022-04-17Add HenchJune McEnroe There are some truly horrifying and gruesome bits though. 2022-04-14Publish "Agency"June McEnroe 2022-04-13Swap dates so the difference is always positiveJune McEnroe 2022-04-04Update "Care"June McEnroe 2022-04-03Publish "Care"June McEnroe 2022-03-31Publish "Compassion"June McEnroe 2022-03-24Skip matches with ident chars on either sideJune McEnroe This fixes, for example, where the link gets placed on static regex_t regex(const char *pattern, int flags) in title.c. 2022-03-24Add The Invisible Life of Addie LaRueJune McEnroe So good, but so long. Reminded me of The Ten Thousand Doors of January at the beginning, and more of that N. K. Jemisin series about gods later. I like this interacting with gods and becoming something like one sort of thing. God, it took me a whole month (more?) to read and this is only my third book of the year :( I need some more novellas to read, but the other books I have from the library currently are also thick. 2022-03-22Source ~/.profile.local if it existsJune McEnroe 2022-03-18Publish "Addendum 2021"June McEnroe 2022-03-16Remove wcwidth portJune McEnroe DYLD_FORCE_FLAT_NAMESPACE no longer exists in macOS 12 so this approach doesn't work anymore. Moved to <https://git.causal.agency/jorts/tree/wcwidth> and compiled into <https://git.causal.agency/jorts/tree/ncurses>. 2022-03-16Remove -j4 from ./PlanJune McEnroe Plan learned to set this automatically! 2022-03-15Rewrite Linux install.sh for DebianJune McEnroe 2022-03-15Remove dashJune McEnroe