fix list parse and construction

change lists to be represented by pointer arrays grown in 32 entry
blocks instead of linked list. This also ensures lists are constructed
in the correct order and makes enumeration and indexing much more
efficient.

3 files changed, 51 insertions, 55 deletions

diff --git a/src/cos_object.c b/src/cos_object.c
index b4de0f6..3dc5efa 100644
--- a/src/cos_object.c
+++ b/src/cos_object.c
@@ -23,7 +23,7 @@
 nspdferror cos_free_object(struct cos_object *cos_obj)
 {
     struct cos_dictionary_entry *dentry;
-    struct cos_array_entry *aentry;
+    unsigned int aentry;
 
     switch (cos_obj->type) {
     case COS_TYPE_NAME:
@@ -50,16 +50,13 @@ nspdferror cos_free_object(struct cos_object *cos_obj)
         break;
 
     case COS_TYPE_ARRAY:
-        aentry = cos_obj->u.array;
-        while (aentry != NULL) {
-            struct cos_array_entry *oaentry;
-
-            cos_free_object(aentry->value);
-
-            oaentry = aentry;
-            aentry = aentry->next;
-            free(oaentry);
+        if (cos_obj->u.array->alloc > 0) {
+            for (aentry = 0; aentry < cos_obj->u.array->length; aentry++) {
+                cos_free_object(*(cos_obj->u.array->values + aentry));
+            }
+            free(cos_obj->u.array->values);
         }
+        free(cos_obj->u.array);
         break;
 
     case COS_TYPE_STREAM:
@@ -381,25 +378,16 @@ cos_get_array_value(struct nspdf_doc *doc,
                     struct cos_object **value_out)
 {
     nspdferror res;
-    struct cos_array_entry *entry;
 
     res = nspdf__xref_get_referenced(doc, &array);
     if (res == NSPDFERROR_OK) {
         if (array->type != COS_TYPE_ARRAY) {
             res = NSPDFERROR_TYPE;
         } else {
-            unsigned int cur_index = 0;
-            res = NSPDFERROR_RANGE;
-
-            entry = array->u.array;
-            while (entry != NULL) {
-                if (cur_index == index) {
-                    *value_out = entry->value;
-                    res = NSPDFERROR_OK;
-                    break;
-                }
-                cur_index++;
-                entry = entry->next;
+            if (index >= array->u.array->length) {
+                res = NSPDFERROR_RANGE;
+            } else {
+                *value_out = *(array->u.array->values + index);
             }
         }
     }
@@ -428,21 +416,13 @@ cos_get_array_size(struct nspdf_doc *doc,
                    unsigned int *size_out)
 {
     nspdferror res;
-    unsigned int array_size = 0;
-    struct cos_array_entry *array_entry;
 
     res = nspdf__xref_get_referenced(doc, &cobj);
     if (res == NSPDFERROR_OK) {
         if (cobj->type != COS_TYPE_ARRAY) {
             res = NSPDFERROR_TYPE;
         } else {
-            /* walk array list to enumerate entries */
-            array_entry = cobj->u.array;
-            while (array_entry != NULL) {
-                array_size++;
-                array_entry = array_entry->next;
-            }
-            *size_out = array_size;
+            *size_out = cobj->u.array->length;
         }
     }
     return res;
diff --git a/src/cos_object.h b/src/cos_object.h
index b90ef15..2e763e2 100644
--- a/src/cos_object.h
+++ b/src/cos_object.h
@@ -45,12 +45,18 @@ struct cos_dictionary_entry {
     struct cos_object *value;
 };
 
-struct cos_array_entry {
-    /** next value in array */
-    struct cos_array_entry *next;
+/**
+ * array of COS objects
+ */
+struct cos_array {
+    /** number of values */
+    unsigned int length;
 
-    /** value */
-    struct cos_object *value;
+    /** number of allocated values */
+    unsigned int alloc;
+
+    /** array of object pointers */
+    struct cos_object **values;
 };
 
 struct cos_string {
@@ -96,7 +102,7 @@ struct cos_object {
         struct cos_dictionary_entry *dictionary;
 
         /* array */
-        struct cos_array_entry *array;
+        struct cos_array *array;
 
         /** reference */
         struct cos_reference *reference;
diff --git a/src/cos_parse.c b/src/cos_parse.c
index de85b0c..21ba0d7 100644
--- a/src/cos_parse.c
+++ b/src/cos_parse.c
@@ -380,16 +380,16 @@ cos_decode_dictionary(struct nspdf_doc *doc,
 }
 
 /**
- * decode a list
+ * parse a list
  */
 static nspdferror
-cos_decode_list(struct nspdf_doc *doc,
-                uint64_t *offset_out,
-                struct cos_object **cosobj_out)
+cos_parse_list(struct nspdf_doc *doc,
+               uint64_t *offset_out,
+               struct cos_object **cosobj_out)
 {
     uint64_t offset;
     struct cos_object *cosobj;
-    struct cos_array_entry *entry;
+    struct cos_array *array;
     struct cos_object *value;
     nspdferror res;
 
@@ -398,7 +398,7 @@ cos_decode_list(struct nspdf_doc *doc,
     /* sanity check first token is list open */
     if (DOC_BYTE(doc, offset) != '[') {
         printf("not a [\n");
-        return NSPDFERROR_SYNTAX; /* syntax error */
+        return NSPDFERROR_SYNTAX;
     }
     offset++;
 
@@ -409,13 +409,20 @@ cos_decode_list(struct nspdf_doc *doc,
     }
 
     //printf("found a list\n");
-
+    /* setup array object */
     cosobj = calloc(1, sizeof(struct cos_object));
     if (cosobj == NULL) {
         return NSPDFERROR_NOMEM;
     }
     cosobj->type = COS_TYPE_ARRAY;
 
+    array = calloc(1, sizeof(struct cos_array));
+    if (array == NULL) {
+        cos_free_object(cosobj);
+        return NSPDFERROR_NOMEM;
+    }
+    cosobj->u.array = array;
+
     while (DOC_BYTE(doc, offset) != ']') {
 
         res = cos_parse_object(doc, &offset, &value);
@@ -425,17 +432,20 @@ cos_decode_list(struct nspdf_doc *doc,
             return res;
         }
 
-        /* add entry to array */
-        entry = calloc(1, sizeof(struct cos_array_entry));
-        if (entry == NULL) {
-            cos_free_object(cosobj);
-            return NSPDFERROR_NOMEM;
+        if (array->alloc < (array->length + 1)) {
+            struct cos_object **nvalues;
+            nvalues = realloc(array->values,
+                            sizeof(struct cos_object *) * (array->alloc + 32));
+            if (nvalues == NULL) {
+                cos_free_object(cosobj);
+                return NSPDFERROR_NOMEM;
+            }
+            array->values = nvalues;
+            array->alloc += 32;
         }
 
-        entry->value = value;
-        entry->next = cosobj->u.array;
-
-        cosobj->u.array = entry;
+        *(array->values + array->length) = value;
+        array->length++;
     }
     offset++; /* skip closing ] */
 
@@ -996,7 +1006,7 @@ cos_parse_object(struct nspdf_doc *doc,
         break;
 
     case '[':
-        res = cos_decode_list(doc, &offset, &cosobj);
+        res = cos_parse_list(doc, &offset, &cosobj);
         break;
 
     case 't':