From 094535c010320967639e8e86f974d878e80baa72 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=B6rg=20Frings-F=C3=BCrst?= Date: Fri, 1 May 2015 16:13:57 +0200 Subject: Imported Upstream version 1.7.0 --- yajl/yajl_tree.c | 558 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 558 insertions(+) create mode 100644 yajl/yajl_tree.c (limited to 'yajl/yajl_tree.c') diff --git a/yajl/yajl_tree.c b/yajl/yajl_tree.c new file mode 100644 index 0000000..8e4aca3 --- /dev/null +++ b/yajl/yajl_tree.c @@ -0,0 +1,558 @@ +/* + * Copyright (c) 2010-2011 Florian Forster + * + * 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. + * + * THE 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 +#include +#include +#include +#include + +#include "yajl_tree.h" +#include "yajl_parse.h" + +#include "yajl_parser.h" + +#if defined(_WIN32) || defined(WIN32) +# define snprintf _snprintf +#endif + +#define STATUS_CONTINUE 1 +#define STATUS_ABORT 0 + +struct stack_elem_s; +typedef struct stack_elem_s stack_elem_t; +struct stack_elem_s +{ + char * key; + yajl_val value; + stack_elem_t *next; +}; + +struct context_s +{ + stack_elem_t *stack; + yajl_val root; + char *errbuf; + size_t errbuf_size; +}; +typedef struct context_s context_t; + +#define RETURN_ERROR(ctx,retval,param) { \ + if ((ctx)->errbuf != NULL) \ + snprintf ((ctx)->errbuf, (ctx)->errbuf_size, param); \ + return (retval); \ + } + +#define RETURN_ERROR2(ctx,retval,param1, param2) { \ + if ((ctx)->errbuf != NULL) \ + snprintf ((ctx)->errbuf, (ctx)->errbuf_size, param1, param2); \ + return (retval); \ + } + +static yajl_val value_alloc (yajl_type type) +{ + yajl_val v; + + v = malloc (sizeof (*v)); + if (v == NULL) return (NULL); + memset (v, 0, sizeof (*v)); + v->type = type; + + return (v); +} + +static void yajl_object_free (yajl_val v) +{ + size_t i; + + if (!YAJL_IS_OBJECT(v)) return; + + for (i = 0; i < v->u.object.len; i++) + { + free((char *) v->u.object.keys[i]); + v->u.object.keys[i] = NULL; + yajl_tree_free (v->u.object.values[i]); + v->u.object.values[i] = NULL; + } + + free((void*) v->u.object.keys); + free(v->u.object.values); + free(v); +} + +static void yajl_array_free (yajl_val v) +{ + size_t i; + + if (!YAJL_IS_ARRAY(v)) return; + + for (i = 0; i < v->u.array.len; i++) + { + yajl_tree_free (v->u.array.values[i]); + v->u.array.values[i] = NULL; + } + + free(v->u.array.values); + free(v); +} + +/* + * Parsing nested objects and arrays is implemented using a stack. When a new + * object or array starts (a curly or a square opening bracket is read), an + * appropriate value is pushed on the stack. When the end of the object is + * reached (an appropriate closing bracket has been read), the value is popped + * off the stack and added to the enclosing object using "context_add_value". + */ +static int context_push(context_t *ctx, yajl_val v) +{ + stack_elem_t *stack; + + stack = malloc (sizeof (*stack)); + if (stack == NULL) + RETURN_ERROR (ctx, ENOMEM, "Out of memory"); + memset (stack, 0, sizeof (*stack)); + + assert ((ctx->stack == NULL) + || YAJL_IS_OBJECT (v) + || YAJL_IS_ARRAY (v)); + + stack->value = v; + stack->next = ctx->stack; + ctx->stack = stack; + + return (0); +} + +static yajl_val context_pop(context_t *ctx) +{ + stack_elem_t *stack; + yajl_val v; + + if (ctx->stack == NULL) + RETURN_ERROR (ctx, NULL, "context_pop: Bottom of stack reached prematurely"); + + stack = ctx->stack; + ctx->stack = stack->next; + + v = stack->value; + + free (stack); + + return (v); +} + +static int object_add_keyval(context_t *ctx, + yajl_val obj, char *key, yajl_val value) +{ + const char **tmpk; + yajl_val *tmpv; + + /* We're checking for NULL in "context_add_value" or its callers. */ + assert (ctx != NULL); + assert (obj != NULL); + assert (key != NULL); + assert (value != NULL); + + /* We're assuring that "obj" is an object in "context_add_value". */ + assert(YAJL_IS_OBJECT(obj)); + + tmpk = realloc((void *) obj->u.object.keys, sizeof(*(obj->u.object.keys)) * (obj->u.object.len + 1)); + if (tmpk == NULL) + RETURN_ERROR(ctx, ENOMEM, "Out of memory"); + obj->u.object.keys = tmpk; + + tmpv = realloc(obj->u.object.values, sizeof (*obj->u.object.values) * (obj->u.object.len + 1)); + if (tmpv == NULL) + RETURN_ERROR(ctx, ENOMEM, "Out of memory"); + obj->u.object.values = tmpv; + + obj->u.object.keys[obj->u.object.len] = key; + obj->u.object.values[obj->u.object.len] = value; + obj->u.object.len++; + + return (0); +} + +static int array_add_value (context_t *ctx, + yajl_val array, yajl_val value) +{ + yajl_val *tmp; + + /* We're checking for NULL pointers in "context_add_value" or its + * callers. */ + assert (ctx != NULL); + assert (array != NULL); + assert (value != NULL); + + /* "context_add_value" will only call us with array values. */ + assert(YAJL_IS_ARRAY(array)); + + tmp = realloc(array->u.array.values, + sizeof(*(array->u.array.values)) * (array->u.array.len + 1)); + if (tmp == NULL) + RETURN_ERROR(ctx, ENOMEM, "Out of memory"); + array->u.array.values = tmp; + array->u.array.values[array->u.array.len] = value; + array->u.array.len++; + + return 0; +} + +/* + * Add a value to the value on top of the stack or the "root" member in the + * context if the end of the parsing process is reached. + */ +static int context_add_value (context_t *ctx, yajl_val v) +{ + /* We're checking for NULL values in all the calling functions. */ + assert (ctx != NULL); + assert (v != NULL); + + /* + * There are three valid states in which this function may be called: + * - There is no value on the stack => This is the only value. This is the + * last step done when parsing a document. We assign the value to the + * "root" member and return. + * - The value on the stack is an object. In this case store the key on the + * stack or, if the key has already been read, add key and value to the + * object. + * - The value on the stack is an array. In this case simply add the value + * and return. + */ + if (ctx->stack == NULL) + { + assert (ctx->root == NULL); + ctx->root = v; + return (0); + } + else if (YAJL_IS_OBJECT (ctx->stack->value)) + { + if (ctx->stack->key == NULL) + { + if (!YAJL_IS_STRING (v)) + RETURN_ERROR2 (ctx, EINVAL, "context_add_value: Object key is not a string (%#04x)", + v->type); + + ctx->stack->key = v->u.string; + v->u.string = NULL; + free(v); + return (0); + } + else /* if (ctx->key != NULL) */ + { + char * key; + + key = ctx->stack->key; + ctx->stack->key = NULL; + return (object_add_keyval (ctx, ctx->stack->value, key, v)); + } + } + else if (YAJL_IS_ARRAY (ctx->stack->value)) + { + return (array_add_value (ctx, ctx->stack->value, v)); + } + else + { + RETURN_ERROR2 (ctx, EINVAL, "context_add_value: Cannot add value to " + "a value of type %#04x (not a composite type)", + ctx->stack->value->type); + } +} + +static int handle_string (void *ctx, + const unsigned char *string, size_t string_length) +{ + yajl_val v; + + v = value_alloc (yajl_t_string); + if (v == NULL) + RETURN_ERROR ((context_t *) ctx, STATUS_ABORT, "Out of memory"); + + v->u.string = malloc (string_length + 1); + if (v->u.string == NULL) + { + free (v); + RETURN_ERROR ((context_t *) ctx, STATUS_ABORT, "Out of memory"); + } + memcpy(v->u.string, string, string_length); + v->u.string[string_length] = 0; + + return ((context_add_value (ctx, v) == 0) ? STATUS_CONTINUE : STATUS_ABORT); +} + +static int handle_number (void *ctx, const char *string, size_t string_length) +{ + yajl_val v; + char *endptr; + + v = value_alloc(yajl_t_number); + if (v == NULL) + RETURN_ERROR((context_t *) ctx, STATUS_ABORT, "Out of memory"); + + v->u.number.r = malloc(string_length + 1); + if (v->u.number.r == NULL) + { + free(v); + RETURN_ERROR((context_t *) ctx, STATUS_ABORT, "Out of memory"); + } + memcpy(v->u.number.r, string, string_length); + v->u.number.r[string_length] = 0; + + v->u.number.flags = 0; + + errno = 0; + v->u.number.i = yajl_parse_integer((const unsigned char *) v->u.number.r, + strlen(v->u.number.r)); + if (errno == 0) + v->u.number.flags |= YAJL_NUMBER_INT_VALID; + + endptr = NULL; + errno = 0; + v->u.number.d = strtod(v->u.number.r, &endptr); + if ((errno == 0) && (endptr != NULL) && (*endptr == 0)) + v->u.number.flags |= YAJL_NUMBER_DOUBLE_VALID; + + return ((context_add_value(ctx, v) == 0) ? STATUS_CONTINUE : STATUS_ABORT); +} + +static int handle_start_map (void *ctx) +{ + yajl_val v; + + v = value_alloc(yajl_t_object); + if (v == NULL) + RETURN_ERROR ((context_t *) ctx, STATUS_ABORT, "Out of memory"); + + v->u.object.keys = NULL; + v->u.object.values = NULL; + v->u.object.len = 0; + + return ((context_push (ctx, v) == 0) ? STATUS_CONTINUE : STATUS_ABORT); +} + +static int handle_end_map (void *ctx) +{ + yajl_val v; + + v = context_pop (ctx); + if (v == NULL) + return (STATUS_ABORT); + + return ((context_add_value (ctx, v) == 0) ? STATUS_CONTINUE : STATUS_ABORT); +} + +static int handle_start_array (void *ctx) +{ + yajl_val v; + + v = value_alloc(yajl_t_array); + if (v == NULL) + RETURN_ERROR ((context_t *) ctx, STATUS_ABORT, "Out of memory"); + + v->u.array.values = NULL; + v->u.array.len = 0; + + return ((context_push (ctx, v) == 0) ? STATUS_CONTINUE : STATUS_ABORT); +} + +static int handle_end_array (void *ctx) +{ + yajl_val v; + + v = context_pop (ctx); + if (v == NULL) + return (STATUS_ABORT); + + return ((context_add_value (ctx, v) == 0) ? STATUS_CONTINUE : STATUS_ABORT); +} + +static int handle_boolean (void *ctx, int boolean_value) +{ + yajl_val v; + + v = value_alloc (boolean_value ? yajl_t_true : yajl_t_false); + if (v == NULL) + RETURN_ERROR ((context_t *) ctx, STATUS_ABORT, "Out of memory"); + + return ((context_add_value (ctx, v) == 0) ? STATUS_CONTINUE : STATUS_ABORT); +} + +static int handle_null (void *ctx) +{ + yajl_val v; + + v = value_alloc (yajl_t_null); + if (v == NULL) + RETURN_ERROR ((context_t *) ctx, STATUS_ABORT, "Out of memory"); + + return ((context_add_value (ctx, v) == 0) ? STATUS_CONTINUE : STATUS_ABORT); +} + +/* + * Public functions + */ +yajl_val yajl_tree_parse (const char *input, + char *error_buffer, size_t error_buffer_size) +{ + static const yajl_callbacks callbacks = + { + /* null = */ handle_null, + /* boolean = */ handle_boolean, + /* integer = */ NULL, + /* double = */ NULL, + /* number = */ handle_number, + /* string = */ handle_string, + /* C comment = */ NULL, + /* C++ comment = */ NULL, + /* start map = */ handle_start_map, + /* map key = */ handle_string, + /* end map = */ handle_end_map, + /* start array = */ handle_start_array, + /* end array = */ handle_end_array + }; + + yajl_handle handle; + yajl_status status; + char * internal_err_str; + context_t ctx = { NULL, NULL, NULL, 0 }; + + ctx.errbuf = error_buffer; + ctx.errbuf_size = error_buffer_size; + + if (error_buffer != NULL) + memset (error_buffer, 0, error_buffer_size); + + handle = yajl_alloc (&callbacks, NULL, &ctx); + yajl_config(handle, yajl_allow_comments, 1); + + status = yajl_parse(handle, + (unsigned char *) input, + strlen (input)); + status = yajl_complete_parse (handle); + if (status != yajl_status_ok) { + if (error_buffer != NULL && error_buffer_size > 0) { + internal_err_str = (char *) yajl_get_error(handle, 1, + (const unsigned char *) input, + strlen(input)); + snprintf(error_buffer, error_buffer_size, "%s", internal_err_str); + YA_FREE(&(handle->alloc), internal_err_str); + } + yajl_free (handle); + return NULL; + } + + yajl_free (handle); + return (ctx.root); +} + +/* (This is useless if what we want is within any arrays) */ +yajl_val yajl_tree_get(yajl_val n, const char ** path, yajl_type type) +{ + if (!path) return NULL; + while (n && *path) { + size_t i; + size_t len; + + if (n->type != yajl_t_object) + return NULL; + len = n->u.object.len; + for (i = 0; i < len; i++) { + if (!strcmp(*path, n->u.object.keys[i])) { + n = n->u.object.values[i]; + break; + } + } + if (i == len) + return NULL; + path++; + } + if (n && type != yajl_t_any && type != n->type) + n = NULL; + return n; +} + +/* Find the first key that matches the name and type in */ +/* a depth first search. (This will work within arrays) */ +/* (Note a breadth first search would be more useful, but slower) */ +/* Return NULL if not found */ +yajl_val yajl_tree_get_first(yajl_val n, const char *key, yajl_type type) +{ + size_t i; + size_t len; + yajl_val x; + + if (n->type == yajl_t_object) { + len = n->u.object.len; + for (i = 0; i < len; i++) { + x = n->u.object.values[i]; + + if (!strcmp(key, n->u.object.keys[i]) + && (type == yajl_t_any || type == x->type)) { + return x; /* Found it */ + } + if (yajl_t_object == x->type + || yajl_t_array == x->type) { + if ((x = yajl_tree_get_first(x, key, type)) != NULL) + return x; + } + } + return NULL; + + } else if (n->type == yajl_t_array) { + len = n->u.array.len; + for (i = 0; i < len; i++) { + x = n->u.array.values[i]; + if (yajl_t_object == x->type + || yajl_t_array == x->type) { + if ((x = yajl_tree_get_first(x, key, type)) != NULL) + return x; + } + } + return NULL; + + } else { + return NULL; + } + return n; +} + +void yajl_tree_free (yajl_val v) +{ + if (v == NULL) return; + + if (YAJL_IS_STRING(v)) + { + free(v->u.string); + free(v); + } + else if (YAJL_IS_NUMBER(v)) + { + free(v->u.number.r); + free(v); + } + else if (YAJL_GET_OBJECT(v)) + { + yajl_object_free(v); + } + else if (YAJL_GET_ARRAY(v)) + { + yajl_array_free(v); + } + else /* if (yajl_t_true or yajl_t_false or yajl_t_null) */ + { + free(v); + } +} -- cgit v1.2.3