diff options
Diffstat (limited to 'src/iter.c')
| -rw-r--r-- | src/iter.c | 234 |
1 files changed, 234 insertions, 0 deletions
diff --git a/src/iter.c b/src/iter.c new file mode 100644 index 00000000..904f2562 --- /dev/null +++ b/src/iter.c @@ -0,0 +1,234 @@ +/* + Copyright 2011-2018 David Robillard <http://drobilla.net> + + Permission to use, copy, modify, and/or distribute this software for any + purpose with or without fee is hereby granted, provided that the above + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#include "iter.h" + +#include "log.h" +#include "model.h" +#include "statement.h" +#include "world.h" + +#include "serd/serd.h" +#include "zix/btree.h" + +#include <assert.h> +#include <stdlib.h> + +static inline bool +serd_iter_forward(SerdIter* iter) +{ + zix_btree_iter_increment(iter->cur); + return zix_btree_iter_is_end(iter->cur); +} + +/** + Seek forward as necessary until `iter` points at a match. + @return true iff iterator reached end of valid range. +*/ +static inline bool +serd_iter_seek_match(SerdIter* iter) +{ + for (iter->end = true; !zix_btree_iter_is_end(iter->cur); + serd_iter_forward(iter)) { + const SerdStatement* s = (const SerdStatement*)zix_btree_get(iter->cur); + if (serd_statement_matches_quad(s, iter->pat)) { + return (iter->end = false); + } + } + return true; +} + +/** + Seek forward as necessary until `iter` points at a match, or the prefix + no longer matches iter->pat. + @return true iff iterator reached end of valid range. +*/ +static inline bool +serd_iter_seek_match_range(SerdIter* iter) +{ + assert(!iter->end); + + do { + const SerdStatement* key = (const SerdStatement*)zix_btree_get(iter->cur); + + if (serd_statement_matches_quad(key, iter->pat)) { + return false; // Found match + } + + for (int i = 0; i < iter->n_prefix; ++i) { + const int idx = orderings[iter->order][i]; + if (!serd_node_pattern_match(key->nodes[idx], iter->pat[idx])) { + iter->end = true; // Reached end of valid range + return true; + } + } + } while (!serd_iter_forward(iter)); + + return (iter->end = true); // Reached end +} + +static bool +check_version(const SerdIter* const iter) +{ + if (iter->version != iter->model->version) { + serd_world_errorf(iter->model->world, + SERD_ERR_BAD_ITER, + "attempt to use invalidated iterator\n"); + return false; + } + return true; +} + +SerdIter* +serd_iter_new(const SerdModel* model, + ZixBTreeIter* cur, + const SerdQuad pat, + SerdOrder order, + SearchMode mode, + int n_prefix) +{ + SerdIter* iter = (SerdIter*)malloc(sizeof(SerdIter)); + iter->model = model; + iter->cur = cur; + iter->order = order; + iter->mode = mode; + iter->n_prefix = n_prefix; + iter->version = model->version; + iter->end = false; + for (int i = 0; i < TUP_LEN; ++i) { + iter->pat[i] = pat[i]; + } + + switch (iter->mode) { + case ALL: + case SINGLE: + case RANGE: + assert(serd_statement_matches_quad( + ((const SerdStatement*)zix_btree_get(iter->cur)), + iter->pat)); + break; + case FILTER_RANGE: serd_iter_seek_match_range(iter); break; + case FILTER_ALL: serd_iter_seek_match(iter); break; + } + +#ifdef SERD_DEBUG_ITER + const SerdStatement* statement = serd_iter_get(iter); + SERD_ITER_LOG("New %p pat=" TUP_FMT " cur=" TUP_FMT " end=%d\n", + (void*)iter, + TUP_FMT_ARGS(pat), + TUP_FMT_ARGS(statement->nodes), + iter->end); +#endif + + return iter; +} + +const SerdModel* +serd_iter_get_model(const SerdIter* iter) +{ + return iter->model; +} + +const SerdStatement* +serd_iter_get(const SerdIter* iter) +{ + return check_version(iter) ? (const SerdStatement*)zix_btree_get(iter->cur) + : NULL; +} + +bool +serd_iter_scan_next(SerdIter* iter) +{ + if (iter->end) { + return true; + } + + const SerdStatement* key = NULL; + if (!iter->end) { + switch (iter->mode) { + case ALL: + // At the end if the cursor is (assigned above) + break; + case SINGLE: + iter->end = true; + SERD_ITER_LOG("%p reached single end\n", (void*)iter); + break; + case RANGE: + SERD_ITER_LOG("%p range next\n", (void*)iter); + // At the end if the MSNs no longer match + key = (const SerdStatement*)zix_btree_get(iter->cur); + assert(key); + for (int i = 0; i < iter->n_prefix; ++i) { + const int idx = orderings[iter->order][i]; + if (!serd_node_pattern_match(key->nodes[idx], iter->pat[idx])) { + iter->end = true; + SERD_ITER_LOG("%p reached non-match end\n", (void*)iter); + break; + } + } + break; + case FILTER_RANGE: + // Seek forward to next match, stopping if prefix changes + serd_iter_seek_match_range(iter); + break; + case FILTER_ALL: + // Seek forward to next match + serd_iter_seek_match(iter); + break; + } + } else { + SERD_ITER_LOG("%p reached index end\n", (void*)iter); + } + + if (iter->end) { + SERD_ITER_LOG("%p Reached end\n", (void*)iter); + return true; + } else { +#ifdef SERD_DEBUG_ITER + SERD_ITER_LOG("%p Increment to " TUP_FMT "\n", + (void*)iter, + TUP_FMT_ARGS(serd_iter_get(iter)->nodes)); +#endif + return false; + } +} + +bool +serd_iter_next(SerdIter* iter) +{ + if (iter->end || !check_version(iter)) { + return true; + } + + iter->end = serd_iter_forward(iter); + return serd_iter_scan_next(iter); +} + +bool +serd_iter_end(const SerdIter* iter) +{ + return !iter || iter->end; +} + +void +serd_iter_free(SerdIter* iter) +{ + SERD_ITER_LOG("%p Free\n", (void*)iter); + if (iter) { + zix_btree_iter_free(iter->cur); + free(iter); + } +} |