Add index lookup table for large PLIST_ARRAY nodes
diff --git a/src/plist.c b/src/plist.c
index 70386bc..f22a8a0 100644
--- a/src/plist.c
+++ b/src/plist.c
@@ -28,6 +28,7 @@
#include <stdio.h>
#include <math.h>
#include <assert.h>
+#include <limits.h>
#ifdef WIN32
#include <windows.h>
@@ -37,6 +38,7 @@
#include <node.h>
#include <hashtable.h>
+#include <ptrarray.h>
extern void plist_xml_init(void);
extern void plist_xml_deinit(void);
@@ -190,6 +192,9 @@
case PLIST_DATA:
free(data->buff);
break;
+ case PLIST_ARRAY:
+ ptr_array_free(data->hashtable);
+ break;
case PLIST_DICT:
hash_table_destroy(data->hashtable);
break;
@@ -338,6 +343,20 @@
case PLIST_STRING:
newdata->strval = strdup((char *) data->strval);
break;
+ case PLIST_ARRAY:
+ if (data->hashtable) {
+ ptrarray_t* pa = ptr_array_new(((ptrarray_t*)data->hashtable)->capacity);
+ assert(pa);
+ plist_t current = NULL;
+ for (current = (plist_t)node_first_child(node);
+ pa && current;
+ current = (plist_t)node_next_sibling(current))
+ {
+ ptr_array_add(pa, current);
+ }
+ newdata->hashtable = pa;
+ }
+ break;
case PLIST_DICT:
if (data->hashtable) {
hashtable_t* ht = hash_table_new(dict_key_hash, dict_key_compare, NULL);
@@ -392,9 +411,14 @@
PLIST_API plist_t plist_array_get_item(plist_t node, uint32_t n)
{
plist_t ret = NULL;
- if (node && PLIST_ARRAY == plist_get_node_type(node))
+ if (node && PLIST_ARRAY == plist_get_node_type(node) && n < INT_MAX)
{
- ret = (plist_t)node_nth_child(node, n);
+ ptrarray_t *pa = ((plist_data_t)((node_t*)node)->data)->hashtable;
+ if (pa) {
+ ret = (plist_t)ptr_array_index(pa, n);
+ } else {
+ ret = (plist_t)node_nth_child(node, n);
+ }
}
return ret;
}
@@ -409,19 +433,46 @@
return 0;
}
+static void _plist_array_post_insert(plist_t node, plist_t item, long n)
+{
+ ptrarray_t *pa = ((plist_data_t)((node_t*)node)->data)->hashtable;
+ if (pa) {
+ /* store pointer to item in array */
+ ptr_array_insert(pa, item, n);
+ } else {
+ if (((node_t*)node)->count > 100) {
+ /* make new lookup array */
+ pa = ptr_array_new(128);
+ plist_t current = NULL;
+ for (current = (plist_t)node_first_child(node);
+ pa && current;
+ current = (plist_t)node_next_sibling(current))
+ {
+ ptr_array_add(pa, current);
+ }
+ ((plist_data_t)((node_t*)node)->data)->hashtable = pa;
+ }
+ }
+}
+
PLIST_API void plist_array_set_item(plist_t node, plist_t item, uint32_t n)
{
- if (node && PLIST_ARRAY == plist_get_node_type(node))
+ if (node && PLIST_ARRAY == plist_get_node_type(node) && n < INT_MAX)
{
plist_t old_item = plist_array_get_item(node, n);
if (old_item)
{
int idx = plist_free_node(old_item);
- if (idx < 0) {
- node_attach(node, item);
- } else {
- node_insert(node, idx, item);
- }
+ assert(idx >= 0);
+ if (idx < 0) {
+ return;
+ } else {
+ node_insert(node, idx, item);
+ ptrarray_t* pa = ((plist_data_t)((node_t*)node)->data)->hashtable;
+ if (pa) {
+ ptr_array_set(pa, item, idx);
+ }
+ }
}
}
return;
@@ -432,26 +483,32 @@
if (node && PLIST_ARRAY == plist_get_node_type(node))
{
node_attach(node, item);
+ _plist_array_post_insert(node, item, -1);
}
return;
}
PLIST_API void plist_array_insert_item(plist_t node, plist_t item, uint32_t n)
{
- if (node && PLIST_ARRAY == plist_get_node_type(node))
+ if (node && PLIST_ARRAY == plist_get_node_type(node) && n < INT_MAX)
{
node_insert(node, n, item);
+ _plist_array_post_insert(node, item, (long)n);
}
return;
}
PLIST_API void plist_array_remove_item(plist_t node, uint32_t n)
{
- if (node && PLIST_ARRAY == plist_get_node_type(node))
+ if (node && PLIST_ARRAY == plist_get_node_type(node) && n < INT_MAX)
{
plist_t old_item = plist_array_get_item(node, n);
if (old_item)
{
+ ptrarray_t* pa = ((plist_data_t)((node_t*)node)->data)->hashtable;
+ if (pa) {
+ ptr_array_remove(pa, n);
+ }
plist_free(old_item);
}
}
@@ -586,8 +643,9 @@
plist_t key_node = NULL;
if (old_item) {
int idx = plist_free_node(old_item);
+ assert(idx >= 0);
if (idx < 0) {
- node_attach(node, item);
+ return;
} else {
node_insert(node, idx, item);
}
diff --git a/src/ptrarray.c b/src/ptrarray.c
index eb17d28..bcffb77 100644
--- a/src/ptrarray.c
+++ b/src/ptrarray.c
@@ -2,7 +2,7 @@
* ptrarray.c
* simple pointer array implementation
*
- * Copyright (c) 2011 Nikias Bassen, All Rights Reserved.
+ * Copyright (c) 2011-2019 Nikias Bassen, All Rights Reserved.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -19,6 +19,7 @@
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
#include "ptrarray.h"
+#include <string.h>
ptrarray_t *ptr_array_new(int capacity)
{
@@ -39,22 +40,51 @@
free(pa);
}
-void ptr_array_add(ptrarray_t *pa, void *data)
+void ptr_array_insert(ptrarray_t *pa, void *data, long array_index)
{
if (!pa || !pa->pdata || !data) return;
- size_t remaining = pa->capacity-pa->len;
+ long remaining = pa->capacity-pa->len;
if (remaining == 0) {
pa->pdata = realloc(pa->pdata, sizeof(void*) * (pa->capacity + pa->capacity_step));
pa->capacity += pa->capacity_step;
}
- pa->pdata[pa->len] = data;
+ if (array_index < 0 || array_index >= pa->len) {
+ pa->pdata[pa->len] = data;
+ } else {
+ memmove(&pa->pdata[array_index+1], &pa->pdata[array_index], (pa->len-array_index) * sizeof(void*));
+ pa->pdata[array_index] = data;
+ }
pa->len++;
}
-void* ptr_array_index(ptrarray_t *pa, size_t array_index)
+void ptr_array_add(ptrarray_t *pa, void *data)
+{
+ ptr_array_insert(pa, data, -1);
+}
+
+void ptr_array_remove(ptrarray_t *pa, long array_index)
+{
+ if (!pa || !pa->pdata || array_index < 0) return;
+ if (pa->len == 0 || array_index >= pa->len) return;
+ if (pa->len == 1) {
+ pa->pdata[0] = NULL;
+ } else {
+ memmove(&pa->pdata[array_index], &pa->pdata[array_index+1], (pa->len-array_index-1) * sizeof(void*));
+ }
+ pa->len--;
+}
+
+void ptr_array_set(ptrarray_t *pa, void *data, long array_index)
+{
+ if (!pa || !pa->pdata || array_index < 0) return;
+ if (pa->len == 0 || array_index >= pa->len) return;
+ pa->pdata[array_index] = data;
+}
+
+void* ptr_array_index(ptrarray_t *pa, long array_index)
{
if (!pa) return NULL;
- if (array_index >= pa->len) {
+ if (array_index < 0 || array_index >= pa->len) {
return NULL;
}
return pa->pdata[array_index];
diff --git a/src/ptrarray.h b/src/ptrarray.h
index e8a3c88..2c6136a 100644
--- a/src/ptrarray.h
+++ b/src/ptrarray.h
@@ -2,7 +2,7 @@
* ptrarray.h
* header file for simple pointer array implementation
*
- * Copyright (c) 2011 Nikias Bassen, All Rights Reserved.
+ * Copyright (c) 2011-2019 Nikias Bassen, All Rights Reserved.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -24,13 +24,16 @@
typedef struct ptrarray_t {
void **pdata;
- size_t len;
- size_t capacity;
- size_t capacity_step;
+ long len;
+ long capacity;
+ long capacity_step;
} ptrarray_t;
ptrarray_t *ptr_array_new(int capacity);
void ptr_array_free(ptrarray_t *pa);
void ptr_array_add(ptrarray_t *pa, void *data);
-void* ptr_array_index(ptrarray_t *pa, size_t index);
+void ptr_array_insert(ptrarray_t *pa, void *data, long index);
+void ptr_array_remove(ptrarray_t *pa, long index);
+void ptr_array_set(ptrarray_t *pa, void *data, long index);
+void* ptr_array_index(ptrarray_t *pa, long index);
#endif
