ext/OGDF/src/basic/Hashing.cpp

   1 /*
   2  * $Revision: 2549 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-04 23:09:19 +0200 (Mi, 04. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of Hashing (class HashingBase)
  11  *
  12  * \author Carsten Gutwenger
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43 #include <ogdf/basic/Hashing.h>
  44
  45
  46 namespace ogdf {
  47
  48 HashingBase::HashingBase(int minTableSize)
  49 {
  50         m_count = 0;
  51         init(m_minTableSize = minTableSize);
  52 }
  53
  54
  55 HashingBase::HashingBase(const HashingBase &H)
  56 {
  57         copyAll(H);
  58 }
  59
  60
  61 HashingBase::~HashingBase()
  62 {
  63         free(m_table);
  64 }
  65
  66
  67 void HashingBase::init(int tableSize)
  68 {
  69         OGDF_ASSERT(tableSize >= m_minTableSize)
  70
  71         m_tableSize = tableSize;
  72         m_hashMask = tableSize-1;
  73         m_tableSizeHigh = tableSize << 1;
  74         m_tableSizeLow  = (tableSize > m_minTableSize) ? (tableSize >> 1) : -1;
  75
  76         m_table = (HashElementBase **)calloc(tableSize,sizeof(HashElementBase *));
  77 }
  78
  79
  80 void HashingBase::destroyAll()
  81 {
  82         HashElementBase **pList = m_table, **pListStop = m_table+m_tableSize;
  83
  84         for(; pList != pListStop; ++pList) {
  85                 HashElementBase *pElement = *pList, *pNext;
  86                 for (; pElement; pElement = pNext) {
  87                         pNext = pElement->next();
  88                         destroy(pElement);
  89                 }
  90         }
  91 }
  92
  93
  94 void HashingBase::copyAll(const HashingBase &H)
  95 {
  96         m_count = 0;
  97         init(H.m_tableSize);
  98
  99         HashElementBase **pList = H.m_table;
 100         HashElementBase **pListStop = H.m_table+m_tableSize;
 101
 102         for(; pList != pListStop; ++pList) {
 103                 HashElementBase *pElement = *pList;
 104                 for (; pElement; pElement = pElement->next())
 105                         insert(H.copy(pElement));
 106         }
 107 }
 108
 109
 110 void HashingBase::clear()
 111 {
 112         destroyAll();
 113         free(m_table);
 114
 115         m_count = 0;
 116         init(m_minTableSize);
 117 }
 118
 119
 120 HashingBase &HashingBase::operator=(const HashingBase &H)
 121 {
 122         destroyAll();
 123         free(m_table);
 124         copyAll(H);
 125         return *this;
 126 }
 127
 128
 129 void HashingBase::resize(int newTableSize)
 130 {
 131         HashElementBase **oldTable = m_table;
 132         HashElementBase **oldTableStop = oldTable + m_tableSize;
 133
 134         init(newTableSize);
 135
 136         for(HashElementBase **pOldList = oldTable;
 137                 pOldList != oldTableStop; ++pOldList)
 138         {
 139                 HashElementBase *pElement = *pOldList, *pNext;
 140                 for(; pElement; pElement = pNext) {
 141                         pNext = pElement->m_next;
 142
 143                         HashElementBase **pList = m_table +
 144                                 (pElement->m_hashValue & m_hashMask);
 145                         pElement->m_next = *pList;
 146                         *pList = pElement;
 147                 }
 148         }
 149
 150         free(oldTable);
 151 }
 152
 153
 154 void HashingBase::insert(HashElementBase *pElement)
 155 {
 156         if (++m_count == m_tableSizeHigh)
 157                 resize(m_tableSizeHigh);
 158
 159         HashElementBase **pList = m_table + (pElement->m_hashValue & m_hashMask);
 160         pElement->m_next = *pList;
 161         *pList = pElement;
 162 }
 163
 164
 165 void HashingBase::del(HashElementBase *pElement)
 166 {
 167         HashElementBase **pList = m_table + (pElement->m_hashValue & m_hashMask);
 168         HashElementBase *pPrev = *pList;
 169
 170         if (pPrev == pElement) {
 171                 *pList = pElement->m_next;
 172
 173         } else {
 174                 while (pPrev->m_next != pElement) pPrev = pPrev->m_next;
 175                 pPrev->m_next = pElement->m_next;
 176         }
 177
 178         if (--m_count == m_tableSizeLow)
 179                 resize(m_tableSizeLow);
 180 }
 181
 182
 183 HashElementBase *HashingBase::firstElement(HashElementBase ***pList) const
 184 {
 185         HashElementBase **pStop = m_table + m_tableSize;
 186         for(*pList = m_table; *pList != pStop; ++(*pList))
 187                 if (**pList) return **pList;
 188
 189         return 0;
 190 }
 191
 192
 193 HashElementBase *HashingBase::nextElement(HashElementBase ***pList,
 194         HashElementBase *pElement) const
 195 {
 196         if ((pElement = pElement->next()) != 0) return pElement;
 197
 198         HashElementBase **pStop = m_table + m_tableSize;
 199         for(++(*pList); *pList != pStop; ++(*pList))
 200                 if (**pList) return **pList;
 201
 202         return 0;
 203 }
 204
 205
 206
 207 } // end namespace ogdf