/**
 * This is just a memeory allocation function for xmlReconciliateNs
 */

int
xmlReconciliateNsAllocMap(xmlNsPtr **oldNs, xmlNsPtr  **newNs, int **createdNs, int sizeCache, int reall) {
    if (! reall) {
	*oldNs = (xmlNsPtr *) xmlMalloc(sizeCache * sizeof(xmlNsPtr));
	if (oldNs == NULL) {
	    xmlGenericError(xmlGenericErrorContext, "xmlReconciliateNs : memory pbm\n");
	    return(0);
	}
	*newNs = (xmlNsPtr *) xmlMalloc(sizeCache * sizeof(xmlNsPtr));
	if (newNs == NULL) {
	    xmlGenericError(xmlGenericErrorContext, "xmlReconciliateNs : memory pbm\n");
	    xmlFree(oldNs);
	    return(0);
	}
	*createdNs = (int *) xmlMalloc(sizeCache * sizeof(int));
	if (createdNs == NULL) {
	    xmlGenericError(xmlGenericErrorContext, "xmlReconciliateNs : memory pbm\n");
	    xmlFree(createdNs);
	    return(0);
	}
    } else {
	*oldNs = (xmlNsPtr *) xmlRealloc(oldNs, sizeCache * sizeof(xmlNsPtr));
	if (oldNs == NULL) {
	    xmlGenericError(xmlGenericErrorContext, "xmlReconciliateNs : memory pbm\n");
	    xmlFree(newNs);
	    return(0);
	}
	*newNs = (xmlNsPtr *) xmlRealloc(newNs, sizeCache * sizeof(xmlNsPtr));
	if (newNs == NULL) {
	    xmlGenericError(xmlGenericErrorContext, "xmlReconciliateNs : memory pbm\n");
	    xmlFree(oldNs);
	    return(0);
	}
	*createdNs = (int *) xmlRealloc(createdNs, sizeCache * sizeof(int));
	
	if (createdNs == NULL) {
	    xmlGenericError(xmlGenericErrorContext, "xmlReconciliateNs : memory pbm\n");
	    xmlFree(createdNs);
	    return(0);
	}

    }
    return (1);
}

/**
 * This is just a memeory allocation function for xmlReconciliateNs
 */

int
xmlReconciliateNsAllocBag(xmlNsPtr **bag, int sizeCache, int reall) {
    if (! reall) {
	*bag = (xmlNsPtr *) xmlMalloc(sizeCache * sizeof(xmlNsPtr));
	if (bag == NULL) {
	    xmlGenericError(xmlGenericErrorContext, "xmlReconciliateNs : memory pbm\n");
	    return(0);
	}	
    } else {
	*bag = (xmlNsPtr *) xmlRealloc(bag, sizeCache * sizeof(xmlNsPtr));
	if (bag == NULL) {
	    xmlGenericError(xmlGenericErrorContext, "xmlReconciliateNs : memory pbm\n");
	    xmlFree(bag);
	    return(0);
	}
    }
    return (1);
}

/**
 * This one will return 1 if a namespace is declared in the ancestor-or-self axis of @node and 
 * @breakNs does not exist in between; returns 0 otherwise.
 */

int
xmlReconciliateNsIsReachableNs(xmlNodePtr node, xmlNsPtr ns, xmlNsPtr breakNs) {
    xmlNodePtr curNode = node;
    xmlNsPtr curNs;
    if ((node == NULL) || (ns == NULL))
	return(0);
    while (curNode != NULL) {
	curNs = curNode->nsDef;
	while (curNs != NULL) {
	    if (breakNs == curNs)
		return(0);
	    if (curNs == ns) 
		return(1);
	    curNs = curNs->next;
	}
	curNode = curNode->parent;
    }
    return(0);
}


int
xmlReconciliateNs(xmlDocPtr doc, xmlNodePtr tree) {
    // Namespace map.    
    xmlNsPtr *oldNs = NULL;
    xmlNsPtr *newNs = NULL;
    int *createdNs = NULL;  
    int mapSizeCache = 0;
    int mapnbCache = 0;
    // Namespace bag.
    xmlNsPtr *nsBag = NULL;
    int bagSizeCache = 0;
    int bagnbCache = 0;

    xmlNsPtr n;   
    xmlNodePtr node = tree, tmpNode;
    xmlAttrPtr attr;
    int ret = 0, i, j;
    xmlNsPtr *ancNsList = NULL, *curAncNs = NULL;
    int found;
    xmlChar prefix[50];
    int counter;
   
    // Put namespaces of ancestors into the namespace bag.
    if (node->parent != NULL)
        ancNsList = xmlGetNsList(doc, node->parent);
    if (ancNsList != NULL) {
	// Initialize the ns bag cache if needed.	    
	if (bagSizeCache == 0) {
	    bagSizeCache = 10;
	    if (! xmlReconciliateNsAllocBag(&nsBag, bagSizeCache, 0))
		return(-1);   
	}
	curAncNs = ancNsList;
	while (*curAncNs != NULL) {
	    if (bagSizeCache <= bagnbCache) {
		bagSizeCache *= 2;
		if (! xmlReconciliateNsAllocBag(&nsBag, bagSizeCache, 1))
		    return(-1);
            }
            nsBag[bagnbCache++] = *curAncNs;   
	    curAncNs++;
	}	    
	xmlFree(ancNsList);
    }        
    // Walk the tree.
    while (node != NULL) {	
	if ((mapSizeCache == 0) && ((node->nsDef != NULL) || (node->ns != NULL))) {
            mapSizeCache = 10;
	    if (! xmlReconciliateNsAllocMap(&oldNs, &newNs, &createdNs, mapSizeCache, 0))
		return(-1);
        }	
        // Put declared namespaces of the subtree into the namespace bag.
        if (node->nsDef != NULL) {
	    // Initialize the ns bag cache if needed.	    
	    if (bagSizeCache == 0) {
		bagSizeCache = 10;
		if (! xmlReconciliateNsAllocBag(&nsBag, bagSizeCache, 0))
		    return(-1);   
	    }
            n = node->nsDef;
            while (n != NULL) {
                // Check if we need to grow the bag cache buffer.
                if (bagSizeCache <= bagnbCache) {
                    bagSizeCache *= 2;
                    if (! xmlReconciliateNsAllocBag(&nsBag, bagSizeCache, 1))
			return(-1);
                }
                nsBag[bagnbCache++] = n;                
                n = n->next;
            }
	}
	if (node->ns != NULL) {
	    found = 0;
            // Try to remap namespaces.
	    for (i = 0;i < mapnbCache;i++) {
		// Additionally we have to check if this one is in scope at all.
		if ( (oldNs[i] == node->ns) && xmlReconciliateNsIsReachableNs(node, newNs[i], node->ns) ) {		    		    	    
		    node->ns = newNs[i];		    
		    found = 1;
		    break;
		}
	    }
	    if (! found) {
		// Search in the parental axis for a namespace with an equal URI.
		n = xmlSearchNsByHref(doc, node, node->ns->href);		
		found = (n != NULL);
		if (! found) {
		    // Check if an already created namespace can be used.
		    for (i = 0;i < mapnbCache; i++) {	
			if ( createdNs[i] && xmlStrEqual(newNs[i]->href, node->ns->href) ) { 
			    n = newNs[i];
			    found = 1;
			    break;		    			    
			}
		    }
		}
		if (mapSizeCache <= mapnbCache) {
		    mapSizeCache *= 2;
		    if (! xmlReconciliateNsAllocMap(&oldNs, &newNs, &createdNs, mapSizeCache, 1)) {
			printf("1 Alloc error");
			return(-1);
		    }
		}		
		oldNs[mapnbCache] = node->ns;
		if (found) 		    
		    createdNs[mapnbCache] = 0;		    
		else {
		    // We need to create a new namespace.
		    // Note that we don't bother yet with dublicate prefixes this will
		    // be done later. That's why we pass NULL as the node argument to xmlNewNs.		   
		    n = xmlNewNs(NULL, node->ns->href, node->ns->prefix);		    		    
		    createdNs[mapnbCache] = 1;		    
		}		
		newNs[mapnbCache++] = n;
		node->ns = n;      
	    }
	}
	/*
	 * Now check for namespaces hold by the attributes on the node.
	 */
	attr = node->properties;
	while (attr != NULL) {
	    if (attr->ns != NULL) {
		found = 0;
		// Try to remap namespaces.
		for (i = 0;i < mapnbCache;i++) {
		    // Additionally we have to check if this one is in scope at all.
		    if ( (oldNs[i] == attr->ns) && xmlReconciliateNsIsReachableNs(node, newNs[i], attr->ns) ) {		    		    	    
			attr->ns = newNs[i];		    
			found = 1;
			break;
		    }
		}
		if (! found) {
		    // Search in the parental axis for a namespace with an equal URI.
		    n = xmlSearchNsByHref(doc, node, attr->ns->href);		
		    found = (n != NULL);
		    if (! found) {
			// Check if an already created namespace can be used.
			for (i = 0;i < mapnbCache; i++) {	
			    if ( createdNs[i] && xmlStrEqual(newNs[i]->href, attr->ns->href) ) { 
				n = newNs[i];
				found = 1;
				break;		    			    
			    }
			}
		    }
		    if (mapSizeCache <= mapnbCache) {
			mapSizeCache *= 2;
			if (! xmlReconciliateNsAllocMap(&oldNs, &newNs, &createdNs, mapSizeCache, 1)) {
			    printf("1 Alloc error");
			    return(-1);
			}
		    }		
		    oldNs[mapnbCache] = attr->ns;
		    if (found) 		    
			createdNs[mapnbCache] = 0;		    
		    else {
			// We need to create a new namespace.
			// Note that we don't bother yet with dublicate prefixes this will
			// be done later. That's why we pass NULL as the node argument to xmlNewNs.		   
			n = xmlNewNs(NULL, attr->ns->href, attr->ns->prefix);	
			ret++;
			createdNs[mapnbCache] = 1;		    
		    }		
		    newNs[mapnbCache++] = n;
		    attr->ns = n;      
		}
	    }
	    attr = attr->next;			
	}	
	
       /*
        * Browse only element nodes of the subtree.
        */
	found = 0;
        while (!found) {
	    /* Siblings first. */
            if (node != tree) {
                /* Search for next element node sibling. */
                tmpNode = node->next;
                while (tmpNode != NULL) {
                    if (tmpNode->type == XML_ELEMENT_NODE) {
                        node = tmpNode;
			found = 1;
                        break;
                    }
                    tmpNode = tmpNode->next;
                }
            }
            /* Then children. */
	    if ((! found) && (node->children != NULL) && (node->children->type == XML_ELEMENT_NODE)) {
                node = node->children;
                break;
            }            
	    if (! found) {
		/* Go up to parents->next if needed. */		
		while (node != tree) {
		    node = node->parent;	
		    if (node != tree) {
			/* Search for next element node sibling. */
			tmpNode = node->next;
			while (tmpNode != NULL) {
			    if (tmpNode->type == XML_ELEMENT_NODE) {				    
				node = tmpNode;
				found = 1;
				break;
			    }
			    tmpNode = tmpNode->next;
			}
		    }
		}
		if (node == tree) {
		    node = NULL;
		    break;
		}
            }  
        }       
    }	
    // Rename prefixes of newly created namespaces if neccessary. 
    for (i = 0;i < mapnbCache; i++) {	
	if (createdNs[i]) {    
	    n = newNs[i];	    
	    // Find a close prefix which is not already in use.
	    // Let's strip namespace prefixes longer than 20 chars !	          
	    if (n->prefix == NULL)
		snprintf((char *) prefix, sizeof(prefix), "default");	    
	    else
		snprintf((char *) prefix, sizeof(prefix), "%.20s", n->prefix);	  
	    counter = 1;
	    found = 0;
	    while (counter < 1000) { 					
		// Search in namespace bag. 		
		for (j = 0; j < bagnbCache; j++) {
		    // Check if any of the existent namespaces could shadow this prefix.
		    // Note that an equal prefix won't be shadowed if the URI is equal as well.
		    if ( (nsBag[j] != n) && xmlStrEqual(nsBag[j]->prefix, prefix) && (! xmlStrEqual(nsBag[j]->href, n->href))) {			
			found = 1;
			break;		    
		    }
		}		
		if (found) {
		    // This prefix is occupied; try with an other one. 
		    if (n->prefix == NULL)
			snprintf((char *) prefix, sizeof(prefix), "default%d", counter++);
		    else
			snprintf((char *) prefix, sizeof(prefix), "%.20s%d", n->prefix, counter++);					
		    found = 0;
		} else {					
		    // This prefix available. 	
		    if (n->prefix != NULL)
			xmlFree((char *) n->prefix);
		    // Declare this ns on the node.
		    n->prefix = xmlStrdup(prefix);
		    if (tree->nsDef == NULL) {
			tree->nsDef = n;
		    } else {
			xmlNsPtr prev = tree->nsDef;   
			while (prev->next != NULL) {
			    prev = prev->next;		
			}    
			prev->next = n;
		    }
		    // Put it in the bag.
		    if (bagSizeCache <= bagnbCache) {
			bagSizeCache *= 2;
			if (! xmlReconciliateNsAllocBag(&nsBag, bagSizeCache, 1))
			    return(-1);
		    }
		    nsBag[bagnbCache++] = n;
		    
		    break;
		}		
	    }
	    if (counter == 1000) {
		// This is bad: substitution of a ns prefix failed.
		xmlGenericError(xmlGenericErrorContext, "xmlReconciliateNs : substitution of a ns prefix failed\n");
		return(-1);
	    }		
	}
    }
    if (oldNs != NULL)
	xmlFree(oldNs);
    if (newNs != NULL)
	xmlFree(newNs);
    if (createdNs != NULL)
    	xmlFree(createdNs);    
    if (nsBag != NULL)
	xmlFree(nsBag);
    return(ret);    
}