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