decoding: improved tail cache in _asn1_append_sequence_set

We keep the head node in addition to the tail information
to allow easier deduction of the validity of the cache.

3 files changed, 27 insertions, 16 deletions

diff --git a/lib/decoding.c b/lib/decoding.c
index 69050fd..3f459f2 100644
--- a/lib/decoding.c
+++ b/lib/decoding.c
@@ -1015,7 +1015,7 @@ asn1_der_decoding2 (asn1_node *element, const void *ider, int *max_ider_len,
   asn1_node node, p, p2, p3;
   char temp[128];
   int counter, len2, len3, len4, move, ris, tlen;
-  asn1_node ptail = NULL;
+  struct node_tail_cache_st tcache = {NULL, NULL};
   unsigned char class;
   unsigned long tag;
   int tag_len;
@@ -1421,14 +1421,15 @@ asn1_der_decoding2 (asn1_node *element, const void *ider, int *max_ider_len,
 		    {		/* indefinite length method */
 		      if (!HAVE_TWO(ider_len) || ((der[counter]) || der[counter + 1]))
 			{
-			  _asn1_append_sequence_set (p, &ptail);
-			  p = ptail;
+			  _asn1_append_sequence_set (p, &tcache);
+			  p = tcache.tail;
 			  move = RIGHT;
 			  continue;
 			}
 
 		      p->tmp_ival = 0;
-		      ptail = NULL; /* finished decoding this structure */
+		      tcache.tail = NULL; /* finished decoding this structure */
+		      tcache.head = NULL;
 		      DECR_LEN(ider_len, 2);
 		      counter += 2;
 		    }
@@ -1436,14 +1437,15 @@ asn1_der_decoding2 (asn1_node *element, const void *ider, int *max_ider_len,
 		    {		/* definite length method */
 		      if (len2 > counter)
 			{
-			  _asn1_append_sequence_set (p, &ptail);
-			  p = ptail;
+			  _asn1_append_sequence_set (p, &tcache);
+			  p = tcache.tail;
 			  move = RIGHT;
 			  continue;
 			}
 
 		      p->tmp_ival = 0;
-		      ptail = NULL; /* finished decoding this structure */
+		      tcache.tail = NULL; /* finished decoding this structure */
+		      tcache.head = NULL;
 
 		      if (len2 != counter)
 			{
@@ -1481,7 +1483,7 @@ asn1_der_decoding2 (asn1_node *element, const void *ider, int *max_ider_len,
 			     || (type_field (p2->type) == ASN1_ETYPE_SIZE))
 			p2 = p2->right;
 		      if (p2->right == NULL)
-			_asn1_append_sequence_set (p, NULL);
+			_asn1_append_sequence_set (p, &tcache);
 		      p = p2;
 		    }
 		}
diff --git a/lib/element.c b/lib/element.c
index 7976285..dceb8ba 100644
--- a/lib/element.c
+++ b/lib/element.c
@@ -132,14 +132,14 @@ _asn1_convert_integer (const unsigned char *value, unsigned char *value_out,
  * node. The new element will have a name of '?number', where number
  * is a monotonically increased serial number.
  *
- * The last element in the list may be provided in @ptail, to avoid
+ * The last element in the list may be provided in @pcache, to avoid
  * traversing the list, an expensive operation in long lists.
  *
- * On success it returns in @ptail the added element (which is the 
+ * On success it returns in @pcache the added element (which is the 
  * tail in the list of added elements).
  */
 int
-_asn1_append_sequence_set (asn1_node node, asn1_node *ptail)
+_asn1_append_sequence_set (asn1_node node, struct node_tail_cache_st *pcache)
 {
   asn1_node p, p2;
   char temp[LTOSTR_MAX_SIZE];
@@ -154,7 +154,7 @@ _asn1_append_sequence_set (asn1_node node, asn1_node *ptail)
     p = p->right;
   p2 = _asn1_copy_structure3 (p);
 
-  if (ptail == NULL || *ptail == NULL)
+  if (pcache == NULL || pcache->tail == NULL || pcache->head != node)
     {
       while (p->right)
         {
@@ -163,12 +163,15 @@ _asn1_append_sequence_set (asn1_node node, asn1_node *ptail)
     }
   else
     {
-      p = *ptail;
+      p = pcache->tail;
     }
 
   _asn1_set_right (p, p2);
-  if (ptail)
-    *ptail = p2;
+  if (pcache)
+    {
+      pcache->head = node;
+      pcache->tail = p2;
+    }
 
   if (p->name[0] == 0)
     _asn1_str_cpy (temp, sizeof (temp), "?1");
diff --git a/lib/element.h b/lib/element.h
index 65a4845..4e45367 100644
--- a/lib/element.h
+++ b/lib/element.h
@@ -23,7 +23,13 @@
 #define _ELEMENT_H
 
 
-int _asn1_append_sequence_set (asn1_node node, asn1_node *pcached);
+struct node_tail_cache_st
+{
+	asn1_node head; /* the first element of the sequence */
+	asn1_node tail;
+};
+
+int _asn1_append_sequence_set (asn1_node node, struct node_tail_cache_st *pcached);
 
 int _asn1_convert_integer (const unsigned char *value,
 			   unsigned char *value_out,