- Changed fast node list to only operate on large number of child nodes

2 files changed, 123 insertions, 90 deletions

diff --git a/libs/files/domc-library.patch b/libs/files/domc-library.patch
index bed3fc8..2dcc9d0 100644
--- a/libs/files/domc-library.patch
+++ b/libs/files/domc-library.patch
@@ -1,6 +1,8 @@
+Only in domc/: libdomc.a
+Only in domc/: libdomc.so.0.7.1
 diff -r -U3 domc-0.7.1/Makefile domc/Makefile
 --- domc-0.7.1/Makefile	2004-08-05 22:32:24.000000000 -0600
-+++ domc/Makefile	2004-08-31 19:19:15.992009233 -0600
++++ domc/Makefile	2004-09-01 11:00:30.657569070 -0600
 @@ -1,7 +1,8 @@
 -prefix     = /usr/local
 -includedir = $(prefix)/include
@@ -41,7 +43,7 @@ diff -r -U3 domc-0.7.1/Makefile domc/Makefile
  
 diff -r -U3 domc-0.7.1/Makefile.msvc domc/Makefile.msvc
 --- domc-0.7.1/Makefile.msvc	2004-08-04 17:20:02.000000000 -0600
-+++ domc/Makefile.msvc	2004-08-31 19:27:30.565550149 -0600
++++ domc/Makefile.msvc	2004-09-01 11:00:30.659568751 -0600
 @@ -1,22 +1,29 @@
  !include <win32.mak>
 -LIBMBA=..\libmba-0.8.9
@@ -80,7 +82,7 @@ diff -r -U3 domc-0.7.1/Makefile.msvc domc/Makefile.msvc
  	del domc.dll domc.lib domc.exp $(OBJS)
 diff -r -U3 domc-0.7.1/src/defines.h domc/src/defines.h
 --- domc-0.7.1/src/defines.h	2003-03-22 16:35:36.000000000 -0700
-+++ domc/src/defines.h	2004-08-31 18:30:01.078131014 -0600
++++ domc/src/defines.h	2004-09-01 11:00:30.673566512 -0600
 @@ -7,7 +7,7 @@
  #define HAVE_ENCDEC 0
  #define HAVE_STRDUP 1
@@ -110,12 +112,12 @@ diff -r -U3 domc-0.7.1/src/defines.h domc/src/defines.h
  #define HAVE_SNPRINTF 1
 diff -r -U3 domc-0.7.1/src/domc.h domc/src/domc.h
 --- domc-0.7.1/src/domc.h	2004-08-04 17:32:30.000000000 -0600
-+++ domc/src/domc.h	2004-08-31 18:30:01.079130884 -0600
++++ domc/src/domc.h	2004-09-01 11:00:30.675566192 -0600
 @@ -41,6 +41,13 @@
    #include <stdint.h>
  #endif
  
-+/* Enable this for hashing and fast access to child node lists */
++/* Enable this for hashing and fast access to large child node lists */
 +#define FAST_NODELIST 1
 +
 +#if FAST_NODELIST
@@ -139,7 +141,7 @@ diff -r -U3 domc-0.7.1/src/domc.h domc/src/domc.h
  	unsigned short filter;
  	struct DOM_NodeList *list; /* Used for entities and notations */
 +#if FAST_NODELIST
-+	struct hashmap _map;
++	struct hashmap* _map;
 +#endif
 +    unsigned int rtfxRefCount; /* Reference counting added for RTFX */
  };
@@ -156,9 +158,11 @@ diff -r -U3 domc-0.7.1/src/domc.h domc/src/domc.h
  int DOM_DocumentLS_save(DOM_DocumentLS *this, const char *uri, const DOM_Node *node);
  int DOM_DocumentLS_fwrite(const DOM_DocumentLS *this, FILE *stream);
  
+Only in domc/src: dom.o
+Only in domc/src: events.o
 diff -r -U3 domc-0.7.1/src/expatls.c domc/src/expatls.c
 --- domc-0.7.1/src/expatls.c	2004-08-04 17:28:49.000000000 -0600
-+++ domc/src/expatls.c	2004-08-31 19:17:46.448679654 -0600
++++ domc/src/expatls.c	2004-09-01 11:01:50.710764140 -0600
 @@ -70,6 +70,14 @@
  
  DOM_Node *Document_createNode(DOM_Document *doc, unsigned short nodeType);
@@ -208,9 +212,24 @@ diff -r -U3 domc-0.7.1/src/expatls.c domc/src/expatls.c
          default:
              AMSG("");
              break;
+@@ -853,11 +850,6 @@
+     		fputs(" version=\"", stream);
+ 			fputds(node->u.Document.version ? node->u.Document.version : "1.0", stream);
+ 			fputc('\"', stream);
+-#ifdef CODESET
+-			fputs(" encoding=\"", stream);
+-			fputs(nl_langinfo(CODESET), stream);
+-			fputc('\"', stream);
+-#endif
+ 			if (node->u.Document.standalone != 0) {
+ 				fputs(" standalone=\"yes\"", stream);
+ 			}
+Only in domc/src: expatls.o
+Only in domc/src: mbs.o
+Only in domc/src: namednodemap.o
 diff -r -U3 domc-0.7.1/src/node.c domc/src/node.c
 --- domc-0.7.1/src/node.c	2004-08-04 17:29:12.000000000 -0600
-+++ domc/src/node.c	2004-08-31 18:30:01.097128538 -0600
++++ domc/src/node.c	2004-09-01 11:00:30.691563633 -0600
 @@ -337,7 +337,6 @@
  DOM_Node *
  DOM_Node_replaceChild(DOM_Node *node, DOM_Node *newChild, DOM_Node *oldChild)
@@ -235,70 +254,104 @@ diff -r -U3 domc-0.7.1/src/node.c domc/src/node.c
  		return NULL;
 diff -r -U3 domc-0.7.1/src/nodelist.c domc/src/nodelist.c
 --- domc-0.7.1/src/nodelist.c	2004-08-04 17:19:25.000000000 -0600
-+++ domc/src/nodelist.c	2004-08-31 18:30:01.117125932 -0600
-@@ -30,6 +30,14 @@
++++ domc/src/nodelist.c	2004-09-01 11:00:30.711560434 -0600
+@@ -30,6 +30,68 @@
  #include "domc.h"
  #include "dom.h"
  
 +#if FAST_NODELIST
-+static void _removeFromMap(struct hashmap* hm, void* key)
++
++/* The number of nodes required in a list before hashing starts */
++#define FAST_FILLFACTOR 16
++
++static void _removeFromMap(DOM_NodeList* nl, DOM_Node* key)
 +{
-+	void* d = NULL;
-+	hashmap_remove(hm, &key, &d);
++	if (nl->_map) {
++		if (hashmap_get(nl->_map, key) != NULL) {
++			void* d = NULL;
++			void* k = key;
++			hashmap_remove(nl->_map, &k, &d);
++		}
++	}
 +}
++
++static int _addToMap(DOM_NodeList* nl, DOM_Node* key, NodeEntry* val)
++{
++	if (!nl->_map && nl->length > FAST_FILLFACTOR) {
++		
++		nl->_map = hashmap_new(0, NULL, NULL, NULL);
++		
++		/* Hash what we currently have */
++		if (nl->_map) {
++			NodeEntry *e = nl->first;
++			while (e) {
++				_addToMap(nl, e->node, e);
++				e = e->next;
++			}
++		}
++	}
++	
++	if (nl->_map) {
++		_removeFromMap(nl, key);
++			
++		if (hashmap_put(nl->_map, key, val) == -1) {
++			DOM_Exception = errno;
++			return -1;
++		}		
++	}
++	
++	return 0;
++}
++
 +#endif
 +
++static NodeEntry* _lookupNode(DOM_NodeList* nl, DOM_Node* node)
++{
++	NodeEntry* s;
++	
++#if FAST_NODELIST
++	if (nl->_map)
++		s = (NodeEntry*)hashmap_get(nl->_map, node);
++	else 
++#endif
++		for (s = nl->first; s != NULL && s->node != node; s = s->next) {
++			;
++		}
++		
++	return s;
++}
++
  /* NodeList
   */
  
-@@ -42,8 +50,16 @@
- 		DOM_Exception = errno;
- 		PMNO(DOM_Exception);
- 	}
-+
- 	r->_ownerDocument = doc;
- 
-+	if(hashmap_init(&(r->_map), 0, NULL, NULL, NULL, NULL) == -1) {
-+		DOM_Exception = errno;
-+		PMNO(DOM_Exception);
-+		free(r);
-+		r = NULL;
-+	}
-+
- 	return r;
- }
- void
-@@ -63,6 +79,7 @@
+@@ -63,6 +125,12 @@
  				free(tmp); 
  			}
  		}
-+		hashmap_deinit(&(nl->_map), NULL, NULL, NULL);
++
++#if FAST_NODELIST
++		if(nl->_map)		
++			hashmap_del(nl->_map, NULL, NULL, NULL);
++#endif
++		
  		free(nl);
  	}
  }
-@@ -110,7 +127,8 @@
+@@ -110,6 +178,7 @@
  NodeList_insert(DOM_NodeList *nl, DOM_Node *newChild, DOM_Node *refChild)
  {
  	NodeEntry *e;
--
 +	NodeEntry *s = NULL;
-+	
+ 
  	if (nl == NULL) {
  		DOM_Exception = NULL_POINTER_ERR;
- 		PMNO(DOM_Exception);
-@@ -122,12 +140,40 @@
+@@ -122,12 +191,30 @@
  		return NULL;
  	}
  
 +	if(refChild != NULL)
 +	{
-+#if FAST_NODELIST
-+		s = (NodeEntry*)hashmap_get(&(nl->_map), refChild);
-+#else
-+		for (s = nl->first; s != NULL && s->node != refChild; s = s->next) {
-+			;
-+		}
-+#endif		
++		s = _lookupNode(nl, refChild);
 +		if(s == NULL || s->node != refChild) {
 +			DOM_Exception = DOM_NOT_FOUND_ERR;
 +			PMNO(DOM_Exception);
@@ -313,11 +366,7 @@ diff -r -U3 domc-0.7.1/src/nodelist.c domc/src/nodelist.c
  	}
  
 +#if FAST_NODELIST
-+	if(hashmap_get(&(nl->_map), newChild) != NULL)
-+		_removeFromMap(&(nl->_map), newChild);
-+		
-+	if(hashmap_put(&(nl->_map), newChild, e) == -1) {
-+		DOM_Exception = errno;
++	if (_addToMap(nl, newChild, e) == -1) {
 +		PMNO(DOM_Exception);
 +		free(e);
 +		return NULL;
@@ -327,7 +376,7 @@ diff -r -U3 domc-0.7.1/src/nodelist.c domc/src/nodelist.c
  	e->node = newChild;
  	if (nl->length == 0) {
  		nl->first = nl->last = e;
-@@ -136,18 +182,6 @@
+@@ -136,18 +223,6 @@
  		nl->last->next = e;
  		nl->last = e;
  	} else {
@@ -346,17 +395,14 @@ diff -r -U3 domc-0.7.1/src/nodelist.c domc/src/nodelist.c
  		e->prev = s->prev;
  		e->next = s;
  		if (s == nl->first) {
-@@ -184,14 +218,32 @@
+@@ -184,14 +259,21 @@
  		return NULL;
  	}
  
-+#if FAST_NODELIST
-+	e = (NodeEntry*)hashmap_get(&(nl->_map), oldChild);
-+#else
- 	for (e = nl->first; e != NULL && e->node != oldChild; e = e->next) {
- 		;
- 	}
-+#endif
+-	for (e = nl->first; e != NULL && e->node != oldChild; e = e->next) {
+-		;
+-	}
++	e = _lookupNode(nl, oldChild);
  	if (e == NULL) {
  		DOM_Exception = DOM_NOT_FOUND_ERR;
  		PMNO(DOM_Exception);
@@ -364,13 +410,8 @@ diff -r -U3 domc-0.7.1/src/nodelist.c domc/src/nodelist.c
  	}
 +
 +#if FAST_NODELIST
-+	_removeFromMap(&(nl->_map), oldChild);
-+		
-+	if(hashmap_get(&(nl->_map), newChild) != NULL)
-+		_removeFromMap(&(nl->_map), newChild);
-+				
-+	if(hashmap_put(&(nl->_map), newChild, e) == -1) {
-+		DOM_Exception = errno;
++	_removeFromMap(nl, oldChild);
++	if(_addToMap(nl, newChild, e) == -1) {
 +		PMNO(DOM_Exception);
 +		return NULL;
 +	}
@@ -379,37 +420,30 @@ diff -r -U3 domc-0.7.1/src/nodelist.c domc/src/nodelist.c
  	e->node = newChild;
  
  	if (oldChild->nodeType == DOM_ATTRIBUTE_NODE) {
-@@ -216,12 +268,20 @@
+@@ -216,12 +298,14 @@
  		return NULL;
  	}
  
-+#if FAST_NODELIST
-+	e = (NodeEntry*)hashmap_get(&(nl->_map), oldChild);
-+#else
- 	for (e = nl->first; e != NULL && e->node != oldChild; e = e->next) {
- 		;
- 	}
-+#endif
+-	for (e = nl->first; e != NULL && e->node != oldChild; e = e->next) {
+-		;
+-	}
++	e = _lookupNode(nl, oldChild);
  	if (e == NULL) {
  		return NULL;
  	}
 +	
 +#if FAST_NODELIST
-+	_removeFromMap(&(nl->_map), oldChild);	
++	_removeFromMap(nl, oldChild);	
 +#endif
  
  	if (nl->first == nl->last) {
  		nl->first = nl->last = NULL;
-@@ -269,6 +329,18 @@
+@@ -269,6 +353,14 @@
  		return NULL;
  	}
  
 +#if FAST_NODELIST
-+	if(hashmap_get(&(nl->_map), newChild) != NULL)
-+		_removeFromMap(&(nl->_map), newChild);
-+		
-+	if(hashmap_put(&(nl->_map), newChild, e) == -1) {
-+		DOM_Exception = errno;
++	if(_addToMap(nl, newChild, e) == -1) {
 +		PMNO(DOM_Exception);
 +		free(e);
 +		return NULL;
@@ -419,18 +453,18 @@ diff -r -U3 domc-0.7.1/src/nodelist.c domc/src/nodelist.c
  	e->node = newChild;
  	if (nl->first == NULL) {
  		nl->first = nl->last = e;
-@@ -311,9 +383,14 @@
+@@ -311,9 +403,7 @@
  		return 0;
  	}
  
-+#if FAST_NODELIST
-+	e = (NodeEntry*)hashmap_get(&(nl->_map), child);
-+#else	
- 	for (e = nl->first; e != NULL && e->node != child; e = e->next) {
- 		;
- 	}
-+#endif
-+
+-	for (e = nl->first; e != NULL && e->node != child; e = e->next) {
+-		;
+-	}
++	e = _lookupNode(nl, child);
  	return e != NULL;
  }
  
+Only in domc/src: nodelist.o
+Only in domc/src: node.o
+Only in domc/src: timestamp.o
+Only in domc/src: wcwidth.o
diff --git a/src/domcxx.h b/src/domcxx.h
index 3d7b77a..9ebc023 100644
--- a/src/domcxx.h
+++ b/src/domcxx.h
@@ -53,7 +53,6 @@ namespace DOM
 {
 	extern "C"
 	{
-		#define FAST_NODELIST 1
         #define this _this
         #include <domc.h>
         #include <dom.h>