Rename a number of libraries and executables to avoid conflicts with KDE4

1 files changed, 345 insertions, 0 deletions

diff --git a/tdehtml/misc/multimap.h b/tdehtml/misc/multimap.h
new file mode 100644
index 000000000..125e8e07d
--- /dev/null
+++ b/tdehtml/misc/multimap.h
@@ -0,0 +1,345 @@
+/*
+ * This file is part of the DOM implementation for KDE.
+ *
+ * Copyright (C) 2006 Allan Sandfeld Jensen (kde@carewolf.com)
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ *
+ */
+
+#ifndef _MultiMap_h_
+#define _MultiMap_h_
+
+#include <tqptrdict.h>
+#include <tqptrlist.h>
+#include <assert.h>
+#include <stdlib.h>
+
+template<class T> class MultiMapPtrList;
+
+// KMultiMap is an implementaition of a Map with multiple entries per key.
+// It is originally designed to work like a shell for TQPtrDict<TQPtrList>, but
+// TQPtrList have been replaced with a much faster hash set.
+template<class T>
+class KMultiMap {
+public:
+    KMultiMap() : dict(257) { dict.setAutoDelete(true); }
+    ~KMultiMap() {};
+
+    typedef MultiMapPtrList<T> List;
+
+    void append(void* key, T* element) {
+        List *list = dict.find(key);
+        if (!list){
+             list = new List(8);
+             dict.insert(key, list);
+        }
+        list->append(element);
+    }
+    void remove(void* key, T* element) {
+        List *list = dict.find(key);
+        if (list) {
+            list->remove(element);
+            if (list->isEmpty()) dict.remove(key);
+        }
+    }
+    void remove(void* key) {
+        dict.remove(key);
+    }
+    List* find(void* key) {
+        return dict.find(key);
+    }
+private:
+    TQPtrDict<List> dict;
+
+};
+
+static inline unsigned int stupidHash(void* ptr)
+{
+    unsigned long val = (unsigned long)ptr;
+    // remove alignment and multiply by a prime unlikely to be a factor of size
+    val = (val >> 4) * 1237;
+    return val;
+}
+
+#define START_PTRLIST_SIZE 4
+#define MAX_PTRLIST_SIZE 27
+
+class PtrListEntry {
+public:
+    PtrListEntry(unsigned int log_size) : count(0), log_size(log_size), search(log_size), next(0) {
+//         entry = new T* [size];
+        assert(log_size < MAX_PTRLIST_SIZE);
+        entry = (void**)calloc ((1<<log_size), sizeof(void*));
+    }
+    ~PtrListEntry() {
+//         delete[] entry;
+        free(entry);
+    }
+    bool insert(void* e) {
+        unsigned int t_size = size();
+        if (count == t_size) return false;
+        unsigned int hash = stupidHash(e);
+        void** firstFree = 0;
+        // Only let elements be placed 'search' spots from their hash
+        for(unsigned int j=0; j<search; j++) {
+            unsigned int i = (hash + j) & (t_size-1); // modulo size
+            // We need check to all hashes in 'search' to garuantee uniqueness
+            if (entry[i] == 0) {
+                if (!firstFree)
+                    firstFree = entry + i;
+            } else
+            if (entry[i] == e)
+                return true;
+        }
+        if (firstFree) {
+            *firstFree = e;
+            count++;
+            return true;
+        }
+        // We had more than 'search' collisions
+        if (count < (t_size/3)*2) {
+            // only 2/3 full => increase search
+            unsigned int s = search *2;
+            if (s >= t_size) s = t_size;
+            search = s;
+            return insert(e);
+        }
+        return false;
+    }
+    // Insert another smaller set into this one
+    // Is only garuantied to succede when this PtrList is new
+    void insert(PtrListEntry* listEntry) {
+        assert(size() >= listEntry->count * 2);
+        unsigned int old_size = 1U << listEntry->log_size;
+        for(unsigned int i = 0; i < old_size; i++) {
+            bool s = true;
+            void *e = listEntry->entry[i];
+            if (e) s = insert(e);
+            assert(s);
+        }
+    }
+    bool remove(void* e) {
+        if (count == 0) return false;
+        unsigned int size = (1U<<log_size);
+        unsigned int hash = stupidHash(e);
+        // Elements are at most placed 'search' spots from their hash
+        for(unsigned int j=0; j<search; j++) {
+            unsigned int i = (hash + j) & (size-1); // modulo size
+            if (entry[i] == e) {
+                entry[i] = 0;
+                count--;
+                return true;
+            }
+        }
+        return false;
+    }
+    bool contains(void* e) {
+        if (count == 0) return false;
+        unsigned int t_size = size();
+        unsigned int hash = stupidHash(e);
+        // Elements are at most placed 'search' spots from their hash
+        for(unsigned int j=0; j<search; j++) {
+            unsigned int i = (hash + j) & (t_size-1); // modulo size
+            if (entry[i] == e) return true;
+        }
+        return false;
+    }
+    void* at(unsigned int i) const {
+        assert (i < (1U<<log_size));
+        return entry[i];
+    }
+    bool isEmpty() const {
+        return count == 0;
+    }
+    bool isFull() const {
+        return count == size();
+    }
+    unsigned int size() const {
+        return (1U << log_size);
+    }
+
+    unsigned int count;
+    const unsigned short log_size;
+    unsigned short search;
+    PtrListEntry *next;
+    void** entry;
+};
+
+// An unsorted and unique PtrList that is implement as a linked list of hash-sets
+// Optimized for fast insert and fast lookup
+template<class T>
+class MultiMapPtrList {
+public:
+    MultiMapPtrList(unsigned int init_size= 16) : m_first(0), m_current(0), m_pos(0) {
+        assert(init_size > 0);
+        unsigned int s = init_size - 1;
+        unsigned int log_size = 0;
+        while (s > 0) {
+            log_size++;
+            s = s >> 1;
+        }
+        m_first = new PtrListEntry(log_size);
+    }
+    MultiMapPtrList(const MultiMapPtrList& ptrList) : m_first(0), m_current(0), m_pos(0) {
+        unsigned int t_count = ptrList.count();
+        unsigned int log_size = 0;
+        while (t_count > 0) {
+            log_size++;
+            t_count = t_count >> 1;
+        }
+        // At least as large as the largest ptrListEntry in the original
+        if (t_count < ptrList.m_first->log_size) log_size = ptrList.m_first->log_size;
+        m_first = new PtrListEntry(log_size);
+
+        PtrListEntry *t_current = ptrList.m_first;
+        while (t_current) {
+            unsigned int t_size = t_current->size();
+            for(unsigned int i=0; i < t_size; i++) {
+                void* e = t_current->at(i);
+                if (e != 0) {
+                    bool t = m_first->insert(e);
+                    if (!t) {
+                        // Make a new, but keep the size
+                        PtrListEntry *t_new = new PtrListEntry(log_size);
+                        t_new->insert(e);
+                        t_new->next = m_first;
+                        m_first = t_new;
+                    }
+                }
+            }
+            t_current = t_current->next;
+        }
+    }
+    ~MultiMapPtrList() {
+        PtrListEntry *t_next, *t_current = m_first;
+        while (t_current) {
+            t_next = t_current->next;
+            delete t_current;
+            t_current = t_next;
+        }
+    }
+    void append(T* e) {
+        PtrListEntry *t_last = 0, *t_current = m_first;
+        int count = 0;
+        while (t_current) {
+            if (t_current->insert(e)) return;
+            t_last = t_current;
+            t_current = t_current->next;
+            count++;
+        }
+        // Create new hash-set
+        unsigned int newsize = m_first->log_size+1;
+        if (newsize > MAX_PTRLIST_SIZE) newsize = MAX_PTRLIST_SIZE;
+        t_current = new PtrListEntry(newsize);
+        bool t = t_current->insert(e);
+        assert(t);
+        // Prepend it to the list, for insert effeciency
+        t_current->next = m_first;
+        m_first = t_current;
+        // ### rehash some of the smaller sets
+        /*
+        if (count > 4) {
+            // rehash the last in the new
+            t_current->insert(t_last);
+        }*/
+    }
+    void remove(T* e) {
+        PtrListEntry *t_next, *t_last = 0, *t_current = m_first;
+        // Remove has to check every PtrEntry.
+        while (t_current) {
+            t_next = t_current->next;
+            if (t_current->remove(e) && t_current->isEmpty()) {
+                if (t_last) {
+                    t_last->next = t_current->next;
+                }
+                else {
+                    assert (m_first == t_current);
+                    m_first = t_current->next;
+                }
+                delete t_current;
+            } else {
+                t_last = t_current;
+            }
+            t_current = t_next;
+        }
+    }
+    bool contains(T* e) {
+        PtrListEntry *t_current = m_first;
+        while (t_current) {
+            if (t_current->contains(e)) return true;
+            t_current = t_current->next;
+        }
+        return false;
+    }
+    bool isEmpty() {
+        if (!m_first) return true;
+        PtrListEntry *t_current = m_first;
+        while (t_current) {
+            if (!t_current->isEmpty()) return false;
+            t_current = t_current->next;
+        }
+        return true;
+    }
+    unsigned int count() const {
+        unsigned int t_count = 0;
+        PtrListEntry *t_current = m_first;
+        while (t_current) {
+            t_count += t_current->count;
+            t_current = t_current->next;
+        }
+        return t_count;
+    }
+// Iterator functions:
+    T* first() {
+        m_current = m_first;
+        m_pos = 0;
+        // skip holes
+        if (m_current && !m_current->at(m_pos))
+            return next();
+        else
+            return current();
+    }
+    T* current() {
+        if (!m_current)
+            return (T*)0;
+        else
+            return (T*)m_current->at(m_pos);
+    }
+    T* next() {
+        if (!m_current) return (T*)0;
+        m_pos++;
+        if (m_pos >= m_current->size()) {
+            m_current = m_current->next;
+            m_pos = 0;
+        }
+        // skip holes
+        if (m_current && !m_current->at(m_pos))
+            return next();
+        else
+            return current();
+    }
+private:
+    PtrListEntry *m_first;
+// iteration:
+    PtrListEntry *m_current;
+    unsigned int m_pos;
+};
+
+#undef START_PTRLIST_SIZE
+#undef MAX_PTRLIST_SIZE
+
+#endif