summaryrefslogtreecommitdiff
path: root/yajl/yajl_tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'yajl/yajl_tree.c')
-rw-r--r--yajl/yajl_tree.c558
1 files changed, 558 insertions, 0 deletions
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 <ff at octo.it>
+ *
+ * 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 <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <errno.h>
+#include <assert.h>
+
+#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);
+ }
+}