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)37 HashingBase::HashingBase(int minTableSize)
38 {
39 	m_count = 0;
40 	init(m_minTableSize = minTableSize);
41 }
42 
43 
HashingBase(const HashingBase & H)44 HashingBase::HashingBase(const HashingBase &H)
45 {
46 	copyAll(H);
47 }
48 
49 
~HashingBase()50 HashingBase::~HashingBase()
51 {
52 	free(m_table);
53 }
54 
55 
init(int tableSize)56 void 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()69 void 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)83 void 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()100 void 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)110 HashingBase &HashingBase::operator=(const HashingBase &H)
111 {
112 	destroyAll();
113 	free(m_table);
114 	copyAll(H);
115 	return *this;
116 }
117 
118 
resize(int newTableSize)119 void 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)144 void 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)155 void 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) const173 HashElementBase *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) const183 HashElementBase *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) const196 size_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