From 9243700f938656936ac57a19c030fef1aaa0ebc0 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Wed, 13 Jan 2021 23:47:44 +0100 Subject: Simplify stack management by popping in bulk at higher levels Since all memory used by the reader is POD in the stack, there is no benefit to forcing code to explicitly pop everything pushed to the stack, since any function can record an offset and pop back down to it regardless of what its callers pushed if it knows that it does not need those items. --- src/n3.c | 93 ++++++++++++++++++++---------------------------------------- src/reader.c | 28 ++++++------------ src/reader.h | 5 +--- src/stack.h | 34 +++++++--------------- 4 files changed, 51 insertions(+), 109 deletions(-) (limited to 'src') diff --git a/src/n3.c b/src/n3.c index c33febeb..82012fc6 100644 --- a/src/n3.c +++ b/src/n3.c @@ -716,7 +716,6 @@ read_IRIREF(SerdReader* reader, SerdNode** dest) *dest = push_node(reader, SERD_URI, "", 0); if (!fancy_syntax(reader) && read_IRIREF_scheme(reader, *dest)) { - *dest = pop_node(reader, *dest); return r_err(reader, SERD_ERR_BAD_SYNTAX, "expected IRI scheme\n"); } @@ -727,25 +726,19 @@ read_IRIREF(SerdReader* reader, SerdNode** dest) switch (c) { case '"': case '<': - *dest = pop_node(reader, *dest); return r_err( reader, SERD_ERR_BAD_SYNTAX, "invalid IRI character `%c'\n", c); - case '>': return SERD_SUCCESS; - case '\\': if (read_UCHAR(reader, *dest, &code)) { - *dest = pop_node(reader, *dest); return r_err(reader, SERD_ERR_BAD_SYNTAX, "invalid IRI escape\n"); } - switch (code) { case 0: case ' ': case '<': case '>': - *dest = pop_node(reader, *dest); return r_err(reader, SERD_ERR_BAD_SYNTAX, "invalid escaped IRI character U+%04X\n", @@ -754,16 +747,13 @@ read_IRIREF(SerdReader* reader, SerdNode** dest) break; } break; - case '^': case '`': case '{': case '|': case '}': - *dest = pop_node(reader, *dest); return r_err( reader, SERD_ERR_BAD_SYNTAX, "invalid IRI character `%c'\n", c); - default: if (c <= 0x20) { r_err(reader, @@ -771,7 +761,6 @@ read_IRIREF(SerdReader* reader, SerdNode** dest) "invalid IRI character (escape %%%02X)\n", (unsigned)c); if (reader->strict) { - *dest = pop_node(reader, *dest); return SERD_ERR_BAD_SYNTAX; } st = SERD_FAILURE; @@ -780,14 +769,12 @@ read_IRIREF(SerdReader* reader, SerdNode** dest) push_byte(reader, *dest, c); } else if (read_utf8_character(reader, *dest, (uint8_t)c)) { if (reader->strict) { - *dest = pop_node(reader, *dest); return SERD_ERR_BAD_SYNTAX; } } } } - *dest = pop_node(reader, *dest); return st; } @@ -930,7 +917,7 @@ read_literal(SerdReader* reader, SerdStatus st = read_String(reader, *dest, flags); if (st) { - *dest = pop_node(reader, *dest); + *dest = NULL; return st; } @@ -939,9 +926,6 @@ read_literal(SerdReader* reader, eat_byte_safe(reader, '@'); *flags |= SERD_HAS_LANGUAGE; if ((st = read_LANGTAG(reader, lang))) { - *datatype = pop_node(reader, *datatype); - *lang = pop_node(reader, *lang); - *dest = pop_node(reader, *dest); return r_err(reader, st, "bad literal\n"); } break; @@ -950,9 +934,6 @@ read_literal(SerdReader* reader, eat_byte_check(reader, '^'); *flags |= SERD_HAS_DATATYPE; if ((st = read_iri(reader, datatype, ate_dot))) { - *datatype = pop_node(reader, *datatype); - *lang = pop_node(reader, *lang); - *dest = pop_node(reader, *dest); return r_err(reader, st, "bad literal\n"); } break; @@ -963,6 +944,7 @@ read_literal(SerdReader* reader, static SerdStatus read_verb(SerdReader* reader, SerdNode** dest) { + const size_t orig_stack_size = reader->stack.size; if (peek_byte(reader) == '<') { return read_IRIREF(reader, dest); } @@ -980,14 +962,14 @@ read_verb(SerdReader* reader, SerdNode** dest) const int next = peek_byte(reader); if (!st && node->n_bytes == 1 && serd_node_string(node)[0] == 'a' && next != ':' && !is_PN_CHARS_BASE((uint32_t)next)) { - pop_node(reader, *dest); + serd_stack_pop_to(&reader->stack, orig_stack_size); *dest = push_node(reader, SERD_URI, NS_RDF "type", 47); return SERD_SUCCESS; } if (st > SERD_FAILURE || read_PrefixedName(reader, *dest, false, &ate_dot) || ate_dot) { - *dest = pop_node(reader, *dest); + *dest = NULL; return r_err(reader, SERD_ERR_BAD_SYNTAX, "bad verb\n"); } @@ -1009,7 +991,6 @@ read_BLANK_NODE_LABEL(SerdReader* reader, SerdNode** dest, bool* ate_dot) if (is_digit(c) || c == '_') { push_byte(reader, n, eat_byte_safe(reader, c)); } else if (read_PN_CHARS(reader, n)) { - *dest = pop_node(reader, n); return r_err(reader, SERD_ERR_BAD_SYNTAX, "invalid name start\n"); } @@ -1035,7 +1016,6 @@ read_BLANK_NODE_LABEL(SerdReader* reader, SerdNode** dest, bool* ate_dot) buf[reader->bprefix_len] = 'B'; // Prevent clash reader->seen_genid = true; } else if (reader->seen_genid && buf[reader->bprefix_len] == 'B') { - *dest = pop_node(reader, n); return r_err(reader, SERD_ERR_ID_CLASH, "found both `b' and `B' blank IDs, prefix required\n"); @@ -1115,9 +1095,7 @@ read_object(SerdReader* reader, ReadContext* ctx, bool emit, bool* ate_dot) static const char* const XSD_BOOLEAN = NS_XSD "boolean"; static const size_t XSD_BOOLEAN_LEN = 40; -#ifndef NDEBUG const size_t orig_stack_size = reader->stack.size; -#endif SerdStatus ret = SERD_FAILURE; @@ -1197,7 +1175,6 @@ read_object(SerdReader* reader, ReadContext* ctx, bool emit, bool* ate_dot) } else { if ((ret = read_PrefixedName(reader, o, false, ate_dot))) { ret = ret > SERD_FAILURE ? ret : SERD_ERR_BAD_SYNTAX; - pop_node(reader, o); return r_err(reader, ret, "expected prefixed name\n"); } } @@ -1216,9 +1193,7 @@ read_object(SerdReader* reader, ReadContext* ctx, bool emit, bool* ate_dot) return SERD_SUCCESS; } - pop_node(reader, lang); - pop_node(reader, datatype); - pop_node(reader, o); + serd_stack_pop_to(&reader->stack, orig_stack_size); #ifndef NDEBUG assert(reader->stack.size == orig_stack_size); #endif @@ -1245,11 +1220,13 @@ read_objectList(SerdReader* reader, ReadContext ctx, bool* ate_dot) static SerdStatus read_predicateObjectList(SerdReader* reader, ReadContext ctx, bool* ate_dot) { + const size_t orig_stack_size = reader->stack.size; + SerdStatus st = SERD_SUCCESS; while (!(st = read_verb(reader, &ctx.predicate)) && read_ws_star(reader) && !(st = read_objectList(reader, ctx, ate_dot))) { - ctx.predicate = pop_node(reader, ctx.predicate); if (*ate_dot) { + serd_stack_pop_to(&reader->stack, orig_stack_size); return SERD_SUCCESS; } @@ -1259,10 +1236,12 @@ read_predicateObjectList(SerdReader* reader, ReadContext ctx, bool* ate_dot) read_ws_star(reader); switch (c = peek_byte(reader)) { case EOF: + serd_stack_pop_to(&reader->stack, orig_stack_size); return r_err(reader, SERD_ERR_BAD_SYNTAX, "unexpected end of file\n"); case '.': case ']': case '}': + serd_stack_pop_to(&reader->stack, orig_stack_size); return SERD_SUCCESS; case ';': eat_byte_safe(reader, c); @@ -1271,29 +1250,24 @@ read_predicateObjectList(SerdReader* reader, ReadContext ctx, bool* ate_dot) } while (c == ';'); if (!ate_semi) { + serd_stack_pop_to(&reader->stack, orig_stack_size); return r_err(reader, SERD_ERR_BAD_SYNTAX, "missing ';' or '.'\n"); } } - ctx.predicate = pop_node(reader, ctx.predicate); + serd_stack_pop_to(&reader->stack, orig_stack_size); + ctx.predicate = 0; return st; } static SerdStatus -end_collection(SerdReader* reader, - ReadContext ctx, - SerdNode* n1, - SerdNode* n2, - SerdStatus st) +end_collection(SerdReader* reader, ReadContext ctx, SerdStatus st) { - pop_node(reader, n2); - pop_node(reader, n1); *ctx.flags &= ~(unsigned)SERD_LIST_CONT; if (!st) { return (eat_byte_check(reader, ')') == ')') ? SERD_SUCCESS : SERD_ERR_BAD_SYNTAX; } - return st; } @@ -1314,14 +1288,13 @@ read_collection(SerdReader* reader, ReadContext ctx, SerdNode** dest) } if (end) { - return end_collection(reader, ctx, 0, 0, st); + return end_collection(reader, ctx, st); } /* The order of node allocation here is necessarily not in stack order, so we create two nodes and recycle them throughout. */ SerdNode* n1 = push_node_padded(reader, genid_size(reader), SERD_BLANK, "", 0); - SerdNode* n2 = 0; SerdNode* node = n1; SerdNode* rest = 0; @@ -1335,14 +1308,14 @@ read_collection(SerdReader* reader, ReadContext ctx, SerdNode** dest) ctx.predicate = reader->rdf_first; bool ate_dot = false; if ((st = read_object(reader, &ctx, true, &ate_dot)) || ate_dot) { - return end_collection(reader, ctx, n1, n2, st); + return end_collection(reader, ctx, st); } if (!(end = peek_delim(reader, ')'))) { /* Give rest a new ID. Done as late as possible to ensure it is used and > IDs generated by read_object above. */ if (!rest) { - rest = n2 = blank_id(reader); // First pass, push + rest = blank_id(reader); // First pass, push } else { set_blank_id(reader, rest, genid_size(reader)); } @@ -1358,7 +1331,7 @@ read_collection(SerdReader* reader, ReadContext ctx, SerdNode** dest) node = ctx.subject; // invariant } - return end_collection(reader, ctx, n1, n2, st); + return end_collection(reader, ctx, st); } static SerdStatus @@ -1381,7 +1354,6 @@ read_subject(SerdReader* reader, ReadContext ctx, SerdNode** dest, int* s_type) } if (ate_dot) { - pop_node(reader, *dest); return r_err(reader, SERD_ERR_BAD_SYNTAX, "subject ends with `.'\n"); } @@ -1445,7 +1417,6 @@ read_base(SerdReader* reader, bool sparql, bool token) SerdNode* uri = NULL; TRY(st, read_IRIREF(reader, &uri)); TRY(st, serd_sink_write_base(reader->sink, uri)); - pop_node(reader, uri); read_ws_star(reader); if (!sparql) { @@ -1478,7 +1449,6 @@ read_prefixID(SerdReader* reader, bool sparql, bool token) } if (eat_byte_check(reader, ':') != ':') { - pop_node(reader, name); return SERD_ERR_BAD_SYNTAX; } @@ -1488,8 +1458,6 @@ read_prefixID(SerdReader* reader, bool sparql, bool token) st = serd_sink_write_prefix(reader->sink, name, uri); - pop_node(reader, uri); - pop_node(reader, name); if (!sparql) { read_ws_star(reader); st = eat_byte_check(reader, '.') ? SERD_SUCCESS : SERD_ERR_BAD_SYNTAX; @@ -1533,8 +1501,10 @@ read_wrappedGraph(SerdReader* reader, ReadContext* ctx) read_ws_star(reader); while (peek_byte(reader) != '}') { - bool ate_dot = false; - int s_type = 0; + const size_t orig_stack_size = reader->stack.size; + bool ate_dot = false; + int s_type = 0; + ctx->subject = 0; SerdStatus st = read_subject(reader, *ctx, &ctx->subject, &s_type); if (st) { @@ -1546,7 +1516,7 @@ read_wrappedGraph(SerdReader* reader, ReadContext* ctx) reader, SERD_ERR_BAD_SYNTAX, "missing predicate object list\n"); } - pop_node(reader, ctx->subject); + serd_stack_pop_to(&reader->stack, orig_stack_size); read_ws_star(reader); if (peek_byte(reader) == '.') { eat_byte_safe(reader, '.'); @@ -1618,7 +1588,6 @@ read_n3_statement(SerdReader* reader) TRY(st, read_labelOrSubject(reader, &ctx.graph)); read_ws_star(reader); TRY(st, read_wrappedGraph(reader, &ctx)); - pop_node(reader, ctx.graph); ctx.graph = 0; read_ws_star(reader); } else if (read_ws_star(reader) && peek_byte(reader) == '{') { @@ -1626,9 +1595,8 @@ read_n3_statement(SerdReader* reader) return r_err(reader, SERD_ERR_BAD_SYNTAX, "invalid graph name\n"); } ctx.graph = ctx.subject; - ctx.subject = 0; + ctx.subject = NULL; TRY(st, read_wrappedGraph(reader, &ctx)); - pop_node(reader, ctx.graph); read_ws_star(reader); } else if ((st = read_triples(reader, ctx, &ate_dot))) { if (st == SERD_FAILURE && s_type == '[') { @@ -1663,15 +1631,17 @@ SerdStatus read_turtleTrigDoc(SerdReader* reader) { while (!reader->source.eof) { - const SerdStatus st = read_n3_statement(reader); + const size_t orig_stack_size = reader->stack.size; + const SerdStatus st = read_n3_statement(reader); if (st > SERD_FAILURE) { if (reader->strict) { + serd_stack_pop_to(&reader->stack, orig_stack_size); return st; } skip_until(reader, '\n'); } + serd_stack_pop_to(&reader->stack, orig_stack_size); } - return SERD_SUCCESS; } @@ -1680,6 +1650,8 @@ read_nquadsDoc(SerdReader* reader) { SerdStatus st = SERD_SUCCESS; while (!reader->source.eof) { + const size_t orig_stack_size = reader->stack.size; + SerdStatementFlags flags = 0; ReadContext ctx = {0, 0, 0, 0, 0, 0, &flags}; bool ate_dot = false; @@ -1724,10 +1696,7 @@ read_nquadsDoc(SerdReader* reader) TRY(st, emit_statement(reader, ctx, ctx.object)); - pop_node(reader, ctx.graph); - pop_node(reader, ctx.lang); - pop_node(reader, ctx.datatype); - pop_node(reader, ctx.object); + serd_stack_pop_to(&reader->stack, orig_stack_size); } return SERD_SUCCESS; } diff --git a/src/reader.c b/src/reader.c index 1693ef64..24240de8 100644 --- a/src/reader.c +++ b/src/reader.c @@ -75,6 +75,13 @@ push_node_padded(SerdReader* reader, const char* str, size_t n_bytes) { + // Push a null byte to ensure the previous node was null terminated + char* terminator = (char*)serd_stack_push(&reader->stack, 1); + if (!terminator) { + return NULL; + } + *terminator = 0; + void* mem = serd_stack_push_aligned( &reader->stack, sizeof(SerdNode) + maxlen + 1, sizeof(SerdNode)); @@ -93,8 +100,7 @@ push_node_padded(SerdReader* reader, #ifdef SERD_STACK_CHECK reader->allocs = (SerdNode**)realloc( reader->allocs, sizeof(reader->allocs) * (++reader->n_allocs)); - reader->allocs[reader->n_allocs - 1] = - (SerdNode*)((char*)mem - reader->stack.buf); + reader->allocs[reader->n_allocs - 1] = node; #endif return node; } @@ -108,21 +114,6 @@ push_node(SerdReader* reader, return push_node_padded(reader, n_bytes, type, str, n_bytes); } -SerdNode* -pop_node(SerdReader* reader, const SerdNode* node) -{ - if (node && node != reader->rdf_first && node != reader->rdf_rest && - node != reader->rdf_nil) { -#ifdef SERD_STACK_CHECK - SERD_STACK_ASSERT_TOP(reader, node); - --reader->n_allocs; -#endif - char* const top = reader->stack.buf + reader->stack.size; - serd_stack_pop_aligned(&reader->stack, (size_t)(top - (char*)node)); - } - return NULL; -} - SerdStatus emit_statement(SerdReader* reader, ReadContext ctx, SerdNode* o) { @@ -199,9 +190,6 @@ serd_reader_free(SerdReader* reader) return; } - pop_node(reader, reader->rdf_nil); - pop_node(reader, reader->rdf_rest); - pop_node(reader, reader->rdf_first); serd_reader_finish(reader); serd_node_free(reader->default_graph); diff --git a/src/reader.h b/src/reader.h index 162b5e04..0aebce81 100644 --- a/src/reader.h +++ b/src/reader.h @@ -101,9 +101,6 @@ blank_id(SerdReader* reader); void set_blank_id(SerdReader* reader, SerdNode* node, size_t buf_size); -SerdNode* -pop_node(SerdReader* reader, const SerdNode* node); - SerdStatus emit_statement(SerdReader* reader, ReadContext ctx, SerdNode* o); @@ -162,7 +159,7 @@ static inline SerdStatus push_byte(SerdReader* reader, SerdNode* node, const int c) { assert(c != EOF); - SERD_STACK_ASSERT_TOP(reader, ref); + SERD_STACK_ASSERT_TOP(reader, node); char* const s = (char*)serd_stack_push(&reader->stack, 1); if (!s) { diff --git a/src/stack.h b/src/stack.h index c2335b3a..4c53b4ae 100644 --- a/src/stack.h +++ b/src/stack.h @@ -20,8 +20,8 @@ #include #include #include -#include #include +#include /** An offset to start the stack at. Note 0 is reserved for NULL. */ #define SERD_STACK_BOTTOM sizeof(void*) @@ -81,40 +81,28 @@ serd_stack_pop(SerdStack* stack, size_t n_bytes) stack->size -= n_bytes; } +static inline void +serd_stack_pop_to(SerdStack* stack, size_t n_bytes) +{ + assert(stack->size >= n_bytes); + stack->size = n_bytes; +} + static inline void* serd_stack_push_aligned(SerdStack* stack, size_t n_bytes, size_t align) { - // Push one byte to ensure space for a pad count - if (!serd_stack_push(stack, 1)) { - return NULL; - } - // Push padding if necessary const size_t pad = align - stack->size % align; if (pad > 0) { - if (!serd_stack_push(stack, pad)) { + void* padding = serd_stack_push(stack, pad); + if (!padding) { return NULL; } + memset(padding, 0, pad); } - // Set top of stack to pad count so we can properly pop later - stack->buf[stack->size - 1] = (char)pad; - // Push requested space at aligned location return serd_stack_push(stack, n_bytes); } -static inline void -serd_stack_pop_aligned(SerdStack* stack, size_t n_bytes) -{ - // Pop requested space down to aligned location - serd_stack_pop(stack, n_bytes); - - // Get amount of padding from top of stack - const uint8_t pad = (uint8_t)stack->buf[stack->size - 1]; - - // Pop padding and pad count - serd_stack_pop(stack, pad + 1u); -} - #endif // SERD_STACK_H -- cgit v1.2.1