hash: Fix deletion of entries during scan

Functions like xmlCleanSpecialAttr scan a hash table and possibly delete
entries in the callback. xmlHashScanFull must detect such deletions and
rescan the entry.

This regressed when rewriting the hash table code in 4a513d56.

Fixes #626.
diff --git a/hash.c b/hash.c
index f3ec639..38341d7 100644
--- a/hash.c
+++ b/hash.c
@@ -913,15 +913,42 @@
 void
 xmlHashScanFull(xmlHashTablePtr hash, xmlHashScannerFull scan, void *data) {
     const xmlHashEntry *entry, *end;
+    xmlHashEntry old;
+    unsigned i;
 
     if ((hash == NULL) || (hash->size == 0) || (scan == NULL))
         return;
 
+    /*
+     * We must handle the case that a scanned entry is removed when executing
+     * the callback (xmlCleanSpecialAttr and possibly other places).
+     *
+     * Find the start of a probe sequence to avoid scanning entries twice if
+     * a deletion happens.
+     */
+    entry = hash->table;
     end = &hash->table[hash->size];
+    while (entry->hashValue != 0) {
+        if (++entry >= end)
+            entry = hash->table;
+    }
 
-    for (entry = hash->table; entry < end; entry++) {
-        if ((entry->hashValue != 0) && (entry->payload != NULL))
-            scan(entry->payload, data, entry->key, entry->key2, entry->key3);
+    for (i = 0; i < hash->size; i++) {
+        if ((entry->hashValue != 0) && (entry->payload != NULL)) {
+            /*
+             * Make sure to rescan after a possible deletion.
+             */
+            do {
+                old = *entry;
+                scan(entry->payload, data, entry->key, entry->key2, entry->key3);
+            } while ((entry->hashValue != 0) &&
+                     (entry->payload != NULL) &&
+                     ((entry->key != old.key) ||
+                      (entry->key2 != old.key2) ||
+                      (entry->key3 != old.key3)));
+        }
+        if (++entry >= end)
+            entry = hash->table;
     }
 }
 
@@ -966,22 +993,47 @@
                  const xmlChar *key2, const xmlChar *key3,
                  xmlHashScannerFull scan, void *data) {
     const xmlHashEntry *entry, *end;
+    xmlHashEntry old;
+    unsigned i;
 
     if ((hash == NULL) || (hash->size == 0) || (scan == NULL))
         return;
 
+    /*
+     * We must handle the case that a scanned entry is removed when executing
+     * the callback (xmlCleanSpecialAttr and possibly other places).
+     *
+     * Find the start of a probe sequence to avoid scanning entries twice if
+     * a deletion happens.
+     */
+    entry = hash->table;
     end = &hash->table[hash->size];
+    while (entry->hashValue != 0) {
+        if (++entry >= end)
+            entry = hash->table;
+    }
 
-    for (entry = hash->table; entry < end; entry++) {
-        if (entry->hashValue == 0)
-            continue;
-        if (((key == NULL) ||
-             (strcmp((const char *) key, (const char *) entry->key) == 0)) &&
-            ((key2 == NULL) || (xmlFastStrEqual(key2, entry->key2))) &&
-            ((key3 == NULL) || (xmlFastStrEqual(key3, entry->key3))) &&
-            (entry->payload != NULL)) {
-            scan(entry->payload, data, entry->key, entry->key2, entry->key3);
+    for (i = 0; i < hash->size; i++) {
+        if ((entry->hashValue != 0) && (entry->payload != NULL)) {
+            /*
+             * Make sure to rescan after a possible deletion.
+             */
+            do {
+                if (((key != NULL) && (strcmp((const char *) key,
+                                              (const char *) entry->key) != 0)) ||
+                    ((key2 != NULL) && (!xmlFastStrEqual(key2, entry->key2))) ||
+                    ((key3 != NULL) && (!xmlFastStrEqual(key3, entry->key3))))
+                    break;
+                old = *entry;
+                scan(entry->payload, data, entry->key, entry->key2, entry->key3);
+            } while ((entry->hashValue != 0) &&
+                     (entry->payload != NULL) &&
+                     ((entry->key != old.key) ||
+                      (entry->key2 != old.key2) ||
+                      (entry->key3 != old.key3)));
         }
+        if (++entry >= end)
+            entry = hash->table;
     }
 }
 
diff --git a/result/issue626.xml b/result/issue626.xml
new file mode 100644
index 0000000..001b3d9
--- /dev/null
+++ b/result/issue626.xml
@@ -0,0 +1,14 @@
+<?xml version="1.0"?>
+<!DOCTYPE doc [
+<!ATTLIST e a1 CDATA #IMPLIED>
+<!ATTLIST e a2 CDATA #IMPLIED>
+<!ATTLIST e a3 CDATA #IMPLIED>
+<!ATTLIST e a4 CDATA #IMPLIED>
+<!ATTLIST e a5 CDATA #IMPLIED>
+<!ATTLIST e a6 CDATA #IMPLIED>
+]>
+<doc>
+    <!-- This tests whether xmlCleanSpecialAttr works. The attribute values
+         must not be normalized. -->
+    <e a1=" x  x " a2=" x  x " a3=" x  x " a4=" x  x " a5=" x  x " a6=" x  x "/>
+</doc>
diff --git a/result/issue626.xml.rde b/result/issue626.xml.rde
new file mode 100644
index 0000000..a488238
--- /dev/null
+++ b/result/issue626.xml.rde
@@ -0,0 +1,12 @@
+0 10 doc 0 0
+0 1 doc 0 0
+1 14 #text 0 1 
+    
+1 8 #comment 0 1  This tests whether xmlCleanSpecialAttr works. The attribute values
+         must not be normalized. 
+1 14 #text 0 1 
+    
+1 1 e 1 0
+1 14 #text 0 1 
+
+0 15 doc 0 0
diff --git a/result/issue626.xml.rdr b/result/issue626.xml.rdr
new file mode 100644
index 0000000..a488238
--- /dev/null
+++ b/result/issue626.xml.rdr
@@ -0,0 +1,12 @@
+0 10 doc 0 0
+0 1 doc 0 0
+1 14 #text 0 1 
+    
+1 8 #comment 0 1  This tests whether xmlCleanSpecialAttr works. The attribute values
+         must not be normalized. 
+1 14 #text 0 1 
+    
+1 1 e 1 0
+1 14 #text 0 1 
+
+0 15 doc 0 0
diff --git a/result/issue626.xml.sax b/result/issue626.xml.sax
new file mode 100644
index 0000000..8e6b59b
--- /dev/null
+++ b/result/issue626.xml.sax
@@ -0,0 +1,23 @@
+SAX.setDocumentLocator()
+SAX.startDocument()
+SAX.internalSubset(doc, , )
+SAX.attributeDecl(e, a1, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a2, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a3, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a4, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a5, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a6, 1, 3, NULL, ...)
+SAX.externalSubset(doc, , )
+SAX.startElement(doc)
+SAX.characters(
+    , 5)
+SAX.comment( This tests whether xmlCleanSpecialAttr works. The attribute values
+         must not be normalized. )
+SAX.characters(
+    , 5)
+SAX.startElement(e, a1=' x  x ', a2=' x  x ', a3=' x  x ', a4=' x  x ', a5=' x  x ', a6=' x  x ')
+SAX.endElement(e)
+SAX.characters(
+, 1)
+SAX.endElement(doc)
+SAX.endDocument()
diff --git a/result/issue626.xml.sax2 b/result/issue626.xml.sax2
new file mode 100644
index 0000000..edc2c1f
--- /dev/null
+++ b/result/issue626.xml.sax2
@@ -0,0 +1,23 @@
+SAX.setDocumentLocator()
+SAX.startDocument()
+SAX.internalSubset(doc, , )
+SAX.attributeDecl(e, a1, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a2, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a3, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a4, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a5, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a6, 1, 3, NULL, ...)
+SAX.externalSubset(doc, , )
+SAX.startElementNs(doc, NULL, NULL, 0, 0, 0)
+SAX.characters(
+    , 5)
+SAX.comment( This tests whether xmlCleanSpecialAttr works. The attribute values
+         must not be normalized. )
+SAX.characters(
+    , 5)
+SAX.startElementNs(e, NULL, NULL, 0, 6, 0, a1=' x  ...', 6, a2=' x  ...', 6, a3=' x  ...', 6, a4=' x  ...', 6, a5=' x  ...', 6, a6=' x  ...', 6)
+SAX.endElementNs(e, NULL, NULL)
+SAX.characters(
+, 1)
+SAX.endElementNs(doc, NULL, NULL)
+SAX.endDocument()
diff --git a/result/noent/issue626.xml b/result/noent/issue626.xml
new file mode 100644
index 0000000..001b3d9
--- /dev/null
+++ b/result/noent/issue626.xml
@@ -0,0 +1,14 @@
+<?xml version="1.0"?>
+<!DOCTYPE doc [
+<!ATTLIST e a1 CDATA #IMPLIED>
+<!ATTLIST e a2 CDATA #IMPLIED>
+<!ATTLIST e a3 CDATA #IMPLIED>
+<!ATTLIST e a4 CDATA #IMPLIED>
+<!ATTLIST e a5 CDATA #IMPLIED>
+<!ATTLIST e a6 CDATA #IMPLIED>
+]>
+<doc>
+    <!-- This tests whether xmlCleanSpecialAttr works. The attribute values
+         must not be normalized. -->
+    <e a1=" x  x " a2=" x  x " a3=" x  x " a4=" x  x " a5=" x  x " a6=" x  x "/>
+</doc>
diff --git a/result/noent/issue626.xml.sax2 b/result/noent/issue626.xml.sax2
new file mode 100644
index 0000000..edc2c1f
--- /dev/null
+++ b/result/noent/issue626.xml.sax2
@@ -0,0 +1,23 @@
+SAX.setDocumentLocator()
+SAX.startDocument()
+SAX.internalSubset(doc, , )
+SAX.attributeDecl(e, a1, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a2, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a3, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a4, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a5, 1, 3, NULL, ...)
+SAX.attributeDecl(e, a6, 1, 3, NULL, ...)
+SAX.externalSubset(doc, , )
+SAX.startElementNs(doc, NULL, NULL, 0, 0, 0)
+SAX.characters(
+    , 5)
+SAX.comment( This tests whether xmlCleanSpecialAttr works. The attribute values
+         must not be normalized. )
+SAX.characters(
+    , 5)
+SAX.startElementNs(e, NULL, NULL, 0, 6, 0, a1=' x  ...', 6, a2=' x  ...', 6, a3=' x  ...', 6, a4=' x  ...', 6, a5=' x  ...', 6, a6=' x  ...', 6)
+SAX.endElementNs(e, NULL, NULL)
+SAX.characters(
+, 1)
+SAX.endElementNs(doc, NULL, NULL)
+SAX.endDocument()
diff --git a/test/issue626.xml b/test/issue626.xml
new file mode 100644
index 0000000..5b0f683
--- /dev/null
+++ b/test/issue626.xml
@@ -0,0 +1,13 @@
+<!DOCTYPE doc [
+<!ATTLIST e a1 CDATA #IMPLIED>
+<!ATTLIST e a2 CDATA #IMPLIED>
+<!ATTLIST e a3 CDATA #IMPLIED>
+<!ATTLIST e a4 CDATA #IMPLIED>
+<!ATTLIST e a5 CDATA #IMPLIED>
+<!ATTLIST e a6 CDATA #IMPLIED>
+]>
+<doc>
+    <!-- This tests whether xmlCleanSpecialAttr works. The attribute values
+         must not be normalized. -->
+    <e a1=" x  x " a2=" x  x " a3=" x  x " a4=" x  x " a5=" x  x " a6=" x  x "/>
+</doc>