[xml] xmlHash patch, phase two

[Sander Vesik <Sander Vesik Sun COM>]

Please test (and hopefully Daniel will commit it) - this is phase two of
the xmlHash patch, it is intended to reduce L1 cache pollution and get to
the data with lower latency. it will have larger inpact on larger
documents[1] and on steeper memory hierarchies. 

[1] there is the advantage of an eliminated level of indirection even if
the working set fits in L1, but that is probably not measurable.

	Sander

	you'll rescue me right?
	in the exact same way that they never did
	i'll be happy right?
	when your healing powers kick in

Index: hash.c
===================================================================
RCS file: /cvs/gnome/gnome-xml/hash.c,v
retrieving revision 1.21
diff -u -r1.21 hash.c
--- hash.c	18 Jun 2002 07:58:33 -0000	1.21
+++ hash.c	19 Jun 2002 14:08:04 -0000
@@ -42,13 +42,14 @@
     xmlChar *name2;
     xmlChar *name3;
     void *payload;
+    int valid;
 };
 
 /*
  * The entire hash table
  */
 struct _xmlHashTable {
-    struct _xmlHashEntry **table;
+    struct _xmlHashEntry *table;
     int size;
     int nbElems;
 };
@@ -101,9 +102,9 @@
     if (table) {
         table->size = size;
 	table->nbElems = 0;
-        table->table = xmlMalloc(size * sizeof(xmlHashEntryPtr));
+        table->table = xmlMalloc(size * sizeof(xmlHashEntry));
         if (table->table) {
-  	    memset(table->table, 0, size * sizeof(xmlHashEntryPtr));
+  	    memset(table->table, 0, size * sizeof(xmlHashEntry));
   	    return(table);
         }
         xmlFree(table);
@@ -125,7 +126,7 @@
     unsigned long key;
     int oldsize, i;
     xmlHashEntryPtr iter, next;
-    struct _xmlHashEntry **oldtable;
+    struct _xmlHashEntry *oldtable;
 #ifdef DEBUG_GROW
     unsigned long nbElem = 0;
 #endif
@@ -142,16 +143,31 @@
     if (oldtable == NULL)
         return(-1);
   
-    table->table = xmlMalloc(size * sizeof(xmlHashEntryPtr));
+    table->table = xmlMalloc(size * sizeof(xmlHashEntry));
     if (table->table == NULL) {
 	table->table = oldtable;
 	return(-1);
     }
-    memset(table->table, 0, size * sizeof(xmlHashEntryPtr));
+    memset(table->table, 0, size * sizeof(xmlHashEntry));
     table->size = size;
 
+    /*	If the two loops are merged, there would be situations where
+	a new entry needs to allocated and data copied into it from 
+	the main table. So instead, we run through the array twice, first
+	copying all the elements in the main array (where we can't get
+	conflicts) and then the rest, so we only free (and don't allocate)
+    */
     for (i = 0; i < oldsize; i++) {
-	iter = oldtable[i];
+	if (oldtable[i].valid == 0) 
+	    continue;
+	key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2,
+				oldtable[i].name3);
+	memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));
+	table->table[key].next = NULL;
+    }
+
+    for (i = 0; i < oldsize; i++) {
+	iter = oldtable[i].next;
 	while (iter) {
 	    next = iter->next;
 
@@ -161,8 +177,14 @@
 
 	    key = xmlHashComputeKey(table, iter->name, iter->name2,
 		                    iter->name3);
-	    iter->next = table->table[key];
-	    table->table[key] = iter;
+	    if (table->table[key].valid == 0) {
+		memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));
+		table->table[key].next = NULL;
+		xmlFree(iter);
+	    } else {
+	    	iter->next = table->table[key].next;
+	    	table->table[key].next = iter;
+	    }
 
 #ifdef DEBUG_GROW
 	    nbElem++;
@@ -195,12 +217,16 @@
     int i;
     xmlHashEntryPtr iter;
     xmlHashEntryPtr next;
+    int inside_table = 0;
 
     if (table == NULL)
 	return;
     if (table->table) {
 	for(i = 0; i < table->size; i++) {
-	    iter = table->table[i];
+	    iter = &(table->table[i]);
+	    if (iter->valid == 0)
+		continue;
+	    inside_table = 1;
 	    while (iter) {
 		next = iter->next;
 		if (f)
@@ -212,10 +238,12 @@
 		if (iter->name3)
 		    xmlFree(iter->name3);
 		iter->payload = NULL;
-		xmlFree(iter);
+		if (!inside_table)
+		    xmlFree(iter);
+		inside_table = 0;
 		iter = next;
 	    }
-	    table->table[i] = NULL;
+	    inside_table = 0;
 	}
 	xmlFree(table->table);
     }
@@ -355,10 +383,10 @@
      * Check for duplicate and insertion location.
      */
     key = xmlHashComputeKey(table, name, name2, name3);
-    if (table->table[key] == NULL) {
+    if (table->table[key].valid == 0) {
 	insert = NULL;
     } else {
-	for (insert = table->table[key]; insert->next != NULL;
+	for (insert = &(table->table[key]); insert->next != NULL;
 	     insert = insert->next) {
 	    if ((xmlStrEqual(insert->name, name)) &&
 		(xmlStrEqual(insert->name2, name2)) &&
@@ -372,21 +400,25 @@
 	    return(-1);
     }
 
-    entry = xmlMalloc(sizeof(xmlHashEntry));
-    if (entry == NULL)
-	return(-1);
+    if (insert == NULL) {
+	entry = &(table->table[key]);
+    } else {
+	entry = xmlMalloc(sizeof(xmlHashEntry));
+	if (entry == NULL)
+	     return(-1);
+    }
+
     entry->name = xmlStrdup(name);
     entry->name2 = xmlStrdup(name2);
     entry->name3 = xmlStrdup(name3);
     entry->payload = userdata;
     entry->next = NULL;
+    entry->valid = 1;
 
 
-    if (insert == NULL) {
-	table->table[key] = entry;
-    } else {
+    if (insert != NULL) 
 	insert->next = entry;
-    }
+
     table->nbElems++;
 
     if (len > MAX_HASH_LEN)
@@ -425,10 +457,10 @@
      * Check for duplicate and insertion location.
      */
     key = xmlHashComputeKey(table, name, name2, name3);
-    if (table->table[key] == NULL) {
+    if (table->table[key].valid == 0) {
 	insert = NULL;
     } else {
-	for (insert = table->table[key]; insert->next != NULL;
+	for (insert = &(table->table[key]); insert->next != NULL;
 	     insert = insert->next) {
 	    if ((xmlStrEqual(insert->name, name)) &&
 		(xmlStrEqual(insert->name2, name2)) &&
@@ -449,20 +481,24 @@
 	}
     }
 
-    entry = xmlMalloc(sizeof(xmlHashEntry));
-    if (entry == NULL)
-	return(-1);
+    if (insert == NULL) {
+	entry =  &(table->table[key]);
+    } else {
+	entry = xmlMalloc(sizeof(xmlHashEntry));
+	if (entry == NULL)
+	     return(-1);
+    }
+
     entry->name = xmlStrdup(name);
     entry->name2 = xmlStrdup(name2);
     entry->name3 = xmlStrdup(name3);
     entry->payload = userdata;
     entry->next = NULL;
+    entry->valid = 1;
     table->nbElems++;
 
 
-    if (insert == NULL) {
-	table->table[key] = entry;
-    } else {
+    if (insert != NULL) {
 	insert->next = entry;
     }
     return(0);
@@ -490,7 +526,9 @@
     if (name == NULL)
 	return(NULL);
     key = xmlHashComputeKey(table, name, name2, name3);
-    for (entry = table->table[key]; entry != NULL; entry = entry->next) {
+    if (table->table[key].valid == 0)
+	return(NULL);
+    for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
 	if ((xmlStrEqual(entry->name, name)) &&
 	    (xmlStrEqual(entry->name2, name2)) &&
 	    (xmlStrEqual(entry->name3, name3)))
@@ -549,7 +587,9 @@
 
     if (table->table) {
 	for(i = 0; i < table->size; i++) {
-	    iter = table->table[i];
+	    if (table->table[i].valid == 0) 
+		continue;
+	    iter = &(table->table[i]);
 	    while (iter) {
 		next = iter->next;
 		if (f)
@@ -610,7 +650,9 @@
 
     if (table->table) {
 	for(i = 0; i < table->size; i++) {
-	    iter = table->table[i];
+	    if (table->table[i].valid == 0)
+		continue;
+	    iter = &(table->table[i]);
 	    while (iter) {
 		next = iter->next;
 		if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
@@ -649,7 +691,9 @@
     ret = xmlHashCreate(table->size);
     if (table->table) {
 	for(i = 0; i < table->size; i++) {
-	    iter = table->table[i];
+	    if (table->table[i].valid == 0)
+		continue;
+	    iter = &(table->table[i]);
 	    while (iter) {
 		next = iter->next;
 		xmlHashAddEntry3(ret, iter->name, iter->name2,
@@ -737,10 +781,10 @@
         return(-1);
 
     key = xmlHashComputeKey(table, name, name2, name3);
-    if (table->table[key] == NULL) {
+    if (table->table[key].valid == 0) {
         return(-1);
     } else {
-        for (entry = table->table[key]; entry != NULL; entry = entry->next) {
+        for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
             if (xmlStrEqual(entry->name, name) &&
                     xmlStrEqual(entry->name2, name2) &&
                     xmlStrEqual(entry->name3, name3)) {
@@ -753,11 +797,18 @@
                     xmlFree(entry->name2);
                 if(entry->name3)
                     xmlFree(entry->name3);
-                if(prev)
+                if(prev) {
                     prev->next = entry->next;
-                else
-                    table->table[key] = entry->next;
-                xmlFree(entry);
+		    xmlFree(entry);
+		} else {
+		    if (entry->next == NULL) {
+			entry->valid = 0;
+		    } else {
+			entry = entry->next;
+			memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
+			xmlFree(entry);
+		    }
+		}
                 table->nbElems--;
                 return(0);
             }