Add index lookup table for large PLIST_ARRAY nodes

3 files changed, 113 insertions, 22 deletions

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 @@ void plist_free_data(plist_data_t data)
         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 @@ static void plist_copy_node(node_t *node, void *parent_node_ptr)
         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 uint32_t plist_array_get_size(plist_t node)
 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 @@ PLIST_API uint32_t plist_array_get_item_index(plist_t node)
     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 @@ PLIST_API void plist_array_append_item(plist_t node, plist_t item)
     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_API void plist_dict_set_item(plist_t node, const char* key, plist_t item)
         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 @@ void ptr_array_free(ptrarray_t *pa)
 	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