From dfe289850f068f19ba4a83ab4e7e22a7e09c13c9 Mon Sep 17 00:00:00 2001 From: Timothy Pearson Date: Sat, 26 Jan 2013 13:17:21 -0600 Subject: Rename a number of libraries and executables to avoid conflicts with KDE4 --- tdehtml/misc/multimap.h | 345 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 345 insertions(+) create mode 100644 tdehtml/misc/multimap.h (limited to 'tdehtml/misc/multimap.h') 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 +#include +#include +#include + +template 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, but +// TQPtrList have been replaced with a much faster hash set. +template +class KMultiMap { +public: + KMultiMap() : dict(257) { dict.setAutoDelete(true); } + ~KMultiMap() {}; + + typedef MultiMapPtrList 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 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< 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< +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 -- cgit v1.2.1