From 6a2acd23f9ac478d13dd1d204959c6dd7e766303 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Fri, 10 Aug 2018 06:57:05 +0100 Subject: [PATCH] Gathered various buffers used for TDFA state mapping in a struct. --- re2c/src/dfa/closure.h | 3 + re2c/src/dfa/find_state.cc | 211 +++++++++++++++++++------------------ re2c/src/dfa/find_state.h | 37 ++++--- re2c/src/dfa/tagpool.h | 4 +- 4 files changed, 133 insertions(+), 122 deletions(-) diff --git a/re2c/src/dfa/closure.h b/re2c/src/dfa/closure.h index 914a867b..f04295e9 100644 --- a/re2c/src/dfa/closure.h +++ b/re2c/src/dfa/closure.h @@ -9,6 +9,7 @@ #include "src/dfa/tagtree.h" #include "src/nfa/nfa.h" #include "src/re/tag.h" +#include "src/util/slab_allocator.h" namespace re2c { @@ -17,6 +18,8 @@ struct Tagpool; struct dfa_t; struct tcmd_t; +typedef slab_allocator_t<> allocator_t; + struct clos_t { nfa_state_t *state; diff --git a/re2c/src/dfa/find_state.cc b/re2c/src/dfa/find_state.cc index e0cab003..6a63aac1 100644 --- a/re2c/src/dfa/find_state.cc +++ b/re2c/src/dfa/find_state.cc @@ -25,43 +25,110 @@ struct kernel_eq_t }; -kernel_t *kernel_t::make_init(size_t size, Tagpool &tagpool) +static void reserve_buffers(kernel_buffers_t &, allocator_t &, tagver_t, size_t); +static kernel_t *make_new_kernel(size_t, allocator_t &); +static kernel_t *make_kernel_copy(const kernel_t *, allocator_t &); + + +kernel_buffers_t::kernel_buffers_t(allocator_t &alc) + : maxsize(0) // usually ranges from one to some twenty + , kernel(make_new_kernel(maxsize, alc)) + , cap(0) + , max(0) + , memory(NULL) + , x2y(NULL) + , y2x(NULL) + , x2t(NULL) + , indegree(NULL) + , actnext(NULL) + , actlhs(NULL) +{} + + +kernels_t::kernels_t(Tagpool &tagp, tcpool_t &tcp, const std::vector &ts) + : lookup() + , tagpool(tagp) + , tcpool(tcp) + , tags(ts) + , buffers(tagp.alc) + , pacts(NULL) +{} + + +kernel_t *make_new_kernel(size_t size, allocator_t &alc) { - kernel_t *kcopy = tagpool.alc.alloct(1); - kcopy->size = size; - kcopy->prectbl = NULL; - kcopy->state = tagpool.alc.alloct(size); - kcopy->tvers = tagpool.alc.alloct(size); - kcopy->tlook = tagpool.alc.alloct(size); - return kcopy; + kernel_t *k = alc.alloct(1); + k->size = size; + k->prectbl = NULL; + k->state = alc.alloct(size); + k->tvers = alc.alloct(size); + k->tlook = alc.alloct(size); + return k; } -kernel_t *kernel_t::make_copy(const kernel_t &k, Tagpool &tagpool) + +kernel_t *make_kernel_copy(const kernel_t *kernel, allocator_t &alc) { - kernel_t *kcopy = tagpool.alc.alloct(1); + const size_t n = kernel->size; + + kernel_t *k = make_new_kernel(n, alc); - const size_t size = k.size; - kcopy->size = size; + memcpy(k->state, kernel->state, n * sizeof(void*)); + memcpy(k->tvers, kernel->tvers, n * sizeof(size_t)); + memcpy(k->tlook, kernel->tlook, n * sizeof(hidx_t)); - prectable_t *prectbl = NULL; - if (k.prectbl) { - prectbl = tagpool.alc.alloct(size * size); - memcpy(prectbl, k.prectbl, size * size * sizeof(prectable_t)); + prectable_t *ptbl = NULL; + if (kernel->prectbl) { + ptbl = alc.alloct(n * n); + memcpy(ptbl, kernel->prectbl, n * n * sizeof(prectable_t)); } - kcopy->prectbl = prectbl; + k->prectbl = ptbl; - kcopy->state = tagpool.alc.alloct(size); - memcpy(kcopy->state, k.state, size * sizeof(void*)); + return k; +} - kcopy->tvers = tagpool.alc.alloct(size); - memcpy(kcopy->tvers, k.tvers, size * sizeof(size_t)); - kcopy->tlook = tagpool.alc.alloct(size); - memcpy(kcopy->tlook, k.tlook, size * sizeof(hidx_t)); +void reserve_buffers(kernel_buffers_t &kbufs, allocator_t &alc, + tagver_t maxver, size_t maxkern) +{ + if (kbufs.maxsize < maxkern) { + kbufs.maxsize = maxkern * 2; // in advance + kbufs.kernel = make_new_kernel(kbufs.maxsize, alc); + } - return kcopy; + // +1 to ensure max tag version is not forgotten in loops + kbufs.max = maxver + 1; + if (kbufs.cap < kbufs.max) { + kbufs.cap = kbufs.max * 2; // in advance + + const size_t + n = static_cast(kbufs.cap), + m = 2 * n + 1, + sz_x2y = 2 * m * sizeof(tagver_t), + sz_x2t = m * sizeof(size_t), + sz_actnext = n * sizeof(tcmd_t*), + sz_actlhs = n * sizeof(tagver_t), + sz_indeg = n * sizeof(uint32_t); + + char *p = alc.alloct(sz_x2y + sz_x2t + sz_actnext + sz_actlhs + sz_indeg); + kbufs.memory = p; + + // point to the center (zero index) of each buffer + // indexes in range [-N .. N] must be valid, where N is capacity + kbufs.x2y = reinterpret_cast(p) + n; + kbufs.y2x = kbufs.x2y + m; + p += sz_x2y; + kbufs.x2t = reinterpret_cast(p) + n; + p += sz_x2t; + kbufs.actnext = reinterpret_cast(p); + p += sz_actnext; + kbufs.actlhs = reinterpret_cast(p); + p += sz_actlhs; + kbufs.indegree = reinterpret_cast(p); + } } + static bool equal_lookahead_tags(const kernel_t *x, const kernel_t *y, Tagpool &tagpool, const std::vector &tags) { @@ -146,6 +213,9 @@ bool kernels_t::operator()(const kernel_t *x, const kernel_t *y) && equal_lookahead_tags(x, y, tagpool, tags); if (!compatible) return false; + tagver_t *x2y = buffers.x2y, *y2x = buffers.y2x, max = buffers.max; + size_t *x2t = buffers.x2t; + // map tag versions of one kernel to that of another // and check that lookahead versions (if any) coincide const size_t ntag = tagpool.ntags; @@ -176,7 +246,8 @@ bool kernels_t::operator()(const kernel_t *x, const kernel_t *y) } // we have bijective mapping; now try to create list of commands - tcmd_t *a, **pa, *copy = NULL; + tcmd_t **actnext = buffers.actnext, *a, **pa, *copy = NULL; + tagver_t *actlhs = buffers.actlhs; // backup 'save' commands: if topsort finds cycles, this mapping // will be rejected and we'll have to revert all changes @@ -212,7 +283,7 @@ bool kernels_t::operator()(const kernel_t *x, const kernel_t *y) *pacts = copy; // see note [topological ordering of copy commands] - const bool nontrivial_cycles = tcmd_t::topsort(pacts, indeg); + const bool nontrivial_cycles = tcmd_t::topsort(pacts, buffers.indegree); // in case of cycles restore 'save' commands and fail if (nontrivial_cycles) { @@ -228,71 +299,6 @@ bool kernels_t::operator()(const kernel_t *x, const kernel_t *y) return !nontrivial_cycles; } -kernels_t::kernels_t(Tagpool &tagp, tcpool_t &tcp, const std::vector &ts) - : lookup() - , tagpool(tagp) - , tcpool(tcp) - , tags(ts) - - , maxsize(0) // usually ranges from one to some twenty - , buffer(kernel_t::make_init(maxsize, tagp)) - - , cap(0) - , max(0) - , mem(NULL) - , x2y(NULL) - , y2x(NULL) - , x2t(NULL) - , indeg(NULL) - - , pacts(NULL) - , actnext(NULL) - , actlhs(NULL) -{} - -void kernels_t::init(tagver_t v, size_t nkern) -{ - if (maxsize < nkern) { - maxsize = nkern * 2; // in advance - buffer = kernel_t::make_init(maxsize, tagpool); - } - - // +1 to ensure max tag version is not forgotten in loops - max = v + 1; - if (cap < max) { - cap = max * 2; // in advance - - const size_t - n = static_cast(cap), - m = 2 * n + 1, - sz_x2y = 2 * m * sizeof(tagver_t), - sz_x2t = m * sizeof(size_t), - sz_actnext = n * sizeof(tcmd_t*), - sz_actlhs = n * sizeof(tagver_t), - sz_indeg = n * sizeof(uint32_t); - mem = tagpool.alc.alloct(sz_x2y + sz_x2t + sz_actnext + sz_actlhs + sz_indeg); - - // point to the center (zero index) of each buffer - // indexes in range [-N .. N] must be valid, where N is capacity - x2y = reinterpret_cast(mem) + cap; - y2x = x2y + m; - x2t = reinterpret_cast(mem + sz_x2y) + cap; - actnext = reinterpret_cast(mem + sz_x2y + sz_x2t); - actlhs = reinterpret_cast(mem + sz_x2y + sz_x2t + sz_actnext); - indeg = reinterpret_cast(mem + sz_x2y + sz_x2t + sz_actnext + sz_actlhs); - } -} - -size_t kernels_t::size() const -{ - return lookup.size(); -} - -const kernel_t *kernels_t::operator[](size_t idx) const -{ - return lookup[idx]; -} - /* note [bijective mappings] * * Suppose we have just constructed a new DFA state Y and want to map it @@ -323,38 +329,39 @@ kernels_t::result_t kernels_t::insert(const closure_t &clos, if (nkern == 0) return result_t(x, NULL, false); // resize buffer if closure is too large - init(maxver, nkern); + reserve_buffers(buffers, tagpool.alc, maxver, nkern); // copy closure to buffer kernel and find its normal form - buffer->size = nkern; - buffer->prectbl = prectbl; + kernel_t *k = buffers.kernel; + k->size = nkern; + k->prectbl = prectbl; for (size_t i = 0; i < nkern; ++i) { const clos_t &c = clos[i]; - buffer->state[i] = c.state; - buffer->tvers[i] = c.tvers; - buffer->tlook[i] = c.tlook; + k->state[i] = c.state; + k->tvers[i] = c.tvers; + k->tlook[i] = c.tlook; } // get kernel hash uint32_t hash = static_cast(nkern); // seed - hash = hash32(hash, buffer->state, nkern * sizeof(void*)); + hash = hash32(hash, k->state, nkern * sizeof(void*)); if (prectbl) { - hash = hash32(hash, buffer->prectbl, nkern * nkern * sizeof(prectable_t)); + hash = hash32(hash, k->prectbl, nkern * nkern * sizeof(prectable_t)); } // try to find identical kernel kernel_eq_t cmp_eq = {tagpool, tags}; - x = lookup.find_with(hash, buffer, cmp_eq); + x = lookup.find_with(hash, k, cmp_eq); if (x != index_t::NIL) return result_t(x, acts, false); // else try to find mappable kernel // see note [bijective mappings] this->pacts = &acts; - x = lookup.find_with(hash, buffer, *this); + x = lookup.find_with(hash, k, *this); if (x != index_t::NIL) return result_t(x, acts, false); // otherwise add new kernel - x = lookup.push(hash, kernel_t::make_copy(*buffer, tagpool)); + x = lookup.push(hash, make_kernel_copy(k, tagpool.alc)); return result_t(x, acts, true); } diff --git a/re2c/src/dfa/find_state.h b/re2c/src/dfa/find_state.h index f65dba92..bb0144fd 100644 --- a/re2c/src/dfa/find_state.h +++ b/re2c/src/dfa/find_state.h @@ -30,11 +30,26 @@ struct kernel_t size_t *tvers; // tag versions hidx_t *tlook; // lookahead tags - static kernel_t *make_init(size_t size, Tagpool &tagpool); - static kernel_t *make_copy(const kernel_t &k, Tagpool &tagpool); FORBID_COPY(kernel_t); }; +struct kernel_buffers_t +{ + size_t maxsize; + kernel_t *kernel; + tagver_t cap; // capacity (greater or equal to max) + tagver_t max; // maximal tag version + char *memory; + tagver_t *x2y; + tagver_t *y2x; + size_t *x2t; + uint32_t *indegree; + tcmd_t **actnext; + tagver_t *actlhs; + + explicit kernel_buffers_t(allocator_t &alc); +}; + struct kernels_t { struct result_t @@ -60,26 +75,14 @@ public: const std::vector &tags; private: - size_t maxsize; - kernel_t *buffer; - - tagver_t cap; // capacity (greater or equal to max) - tagver_t max; // maximal tag version - char *mem; - tagver_t *x2y; - tagver_t *y2x; - size_t *x2t; - uint32_t *indeg; + kernel_buffers_t buffers; tcmd_t **pacts; - tcmd_t **actnext; - tagver_t *actlhs; public: kernels_t(Tagpool &tagp, tcpool_t &tcp, const std::vector &ts); - void init(tagver_t v, size_t nkern); - size_t size() const; - const kernel_t* operator[](size_t idx) const; + inline size_t size() const { return lookup.size(); } + inline const kernel_t* operator[](size_t idx) const { return lookup[idx]; } result_t insert(const closure_t &clos, tcmd_t *acts, tagver_t maxver, const prectable_t *prectbl); bool operator()(const kernel_t *k1, const kernel_t *k2); FORBID_COPY(kernels_t); diff --git a/re2c/src/dfa/tagpool.h b/re2c/src/dfa/tagpool.h index 38ac840b..7ff72e25 100644 --- a/re2c/src/dfa/tagpool.h +++ b/re2c/src/dfa/tagpool.h @@ -9,7 +9,6 @@ #include "src/re/tag.h" #include "src/util/forbid_copy.h" #include "src/util/lookup.h" -#include "src/util/slab_allocator.h" namespace re2c { @@ -30,8 +29,7 @@ public: const size_t ntags; tagver_t *buffer; - typedef slab_allocator_t<> alc_t; - alc_t alc; + allocator_t alc; tagtree_t history; std::stack astack; -- 2.40.0