From 08c6143b870167ad29f9c20a298e0f75c986d0ea Mon Sep 17 00:00:00 2001 From: Nikias Bassen Date: Sun, 19 May 2019 00:20:51 +0200 Subject: Add index lookup table for large PLIST_ARRAY nodes --- src/plist.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++-------- src/ptrarray.c | 42 +++++++++++++++++++++++++----- src/ptrarray.h | 13 ++++++---- 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 #include #include +#include #ifdef WIN32 #include @@ -37,6 +38,7 @@ #include #include +#include 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 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 -- cgit v1.1-32-gdbae