Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitcf053d6

Browse files
author
Martin Smith
committed
rm ws
1 parent856a5fa commitcf053d6

File tree

2 files changed

+102
-102
lines changed

2 files changed

+102
-102
lines changed

‎HashTable.c‎

Lines changed: 90 additions & 90 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,13 @@
1-
/* RogueNaRok is an algorithm for the identification of rogue taxa in a set of phylogenetic trees.
1+
/* RogueNaRok is an algorithm for the identification of rogue taxa in a set of phylogenetic trees.
22
*
3-
* Moreover, the program collection comes with efficient implementations of
3+
* Moreover, the program collection comes with efficient implementations of
44
* * the unrooted leaf stability by Thorley and Wilkinson
55
* * the taxonomic instability index by Maddinson and Maddison
6-
* * a maximum agreement subtree implementation (MAST) for unrooted trees
7-
* * a tool for pruning taxa from a tree collection.
8-
*
6+
* * a maximum agreement subtree implementation (MAST) for unrooted trees
7+
* * a tool for pruning taxa from a tree collection.
8+
*
99
* Copyright October 2011 by Andre J. Aberer
10-
*
10+
*
1111
* Tree I/O and parallel framework are derived from RAxML by Alexandros Stamatakis.
1212
*
1313
* This program is free software; you may redistribute it and/or
@@ -22,47 +22,47 @@
2222
*
2323
* For any other inquiries send an Email to Andre J. Aberer
2424
* andre.aberer at googlemail.com
25-
*
25+
*
2626
* When publishing work that is based on the results from RogueNaRok, please cite:
27-
* Andre J. Aberer, Denis Krompaß, Alexandros Stamatakis. RogueNaRok: an Efficient and Exact Algorithm for Rogue Taxon Identification. (unpublished) 2011.
28-
*
27+
* Andre J. Aberer, Denis Krompaß, Alexandros Stamatakis. RogueNaRok: an Efficient and Exact Algorithm for Rogue Taxon Identification. (unpublished) 2011.
28+
*
2929
*/
3030

3131
#include"HashTable.h"
3232
#ifdefPARALLEL
3333
#include<pthread.h>
3434
#endif
3535

36-
HashTable*createHashTable(uint32_tsize,
37-
void*commonAttr,
36+
HashTable*createHashTable(uint32_tsize,
37+
void*commonAttr,
3838
uint32_t (*hashFunction)(HashTable*hash_table,void*value),
3939
boolean (*equalFunction)(HashTable*hash_table,void*entryA,void*entryB))
40-
{
41-
staticconstuint32_t
42-
initTable[]= {64,128,256,512,1024,2048,4096,
43-
8192,16384,32768,65536,131072,
40+
{
41+
staticconstuint32_t
42+
initTable[]= {64,128,256,512,1024,2048,4096,
43+
8192,16384,32768,65536,131072,
4444
262144,524288,1048576,2097152,
45-
4194304,8388608,16777216,33554432,
46-
67108864,134217728,268435456,
45+
4194304,8388608,16777216,33554432,
46+
67108864,134217728,268435456,
4747
536870912,1073741824,2147483648U};
48-
49-
HashTable
48+
49+
HashTable
5050
*hashTable=CALLOC(1,sizeof(HashTable));
51-
51+
5252
uint32_t
5353
tableSize,
5454
i,
5555
#ifdefDEBUG
56-
maxSize= (uint32_t)-1,
56+
maxSize= (uint32_t)-1,
5757
#endif
5858
primeTableLength=sizeof(initTable)/sizeof(initTable[0]);
5959

6060
hashTable->hashFunction=hashFunction;
6161
hashTable->equalFunction=equalFunction;
6262
hashTable->commonAttributes=commonAttr;
6363

64-
#ifdefDEBUG
65-
assert(size <=maxSize);
64+
#ifdefDEBUG
65+
assert(size <=maxSize);
6666
#endif
6767
for(i=0;initTable[i]<size&&i<primeTableLength;++i);
6868
assert(i<primeTableLength);
@@ -72,8 +72,8 @@ HashTable *createHashTable(uint32_t size,
7272
#ifdefPARALLEL
7373
hashTable->cntLock=CALLOC(1,sizeof(pthread_mutex_t));
7474
pthread_mutex_init(hashTable->cntLock, (pthread_mutexattr_t*)NULL);
75-
76-
hashTable->lockPerSlot= (pthread_mutex_t**)CALLOC(tableSize,sizeof(pthread_mutex_t*));
75+
76+
hashTable->lockPerSlot= (pthread_mutex_t**)CALLOC(tableSize,sizeof(pthread_mutex_t*));
7777
FOR_0_LIMIT(i,tableSize)
7878
{
7979
hashTable->lockPerSlot[i]= (pthread_mutex_t*)CALLOC(1,sizeof(pthread_mutex_t));
@@ -82,8 +82,8 @@ HashTable *createHashTable(uint32_t size,
8282
#endif
8383

8484
hashTable->table=CALLOC(tableSize,sizeof(HashElem*));
85-
hashTable->tableSize=tableSize;
86-
hashTable->entryCount=0;
85+
hashTable->tableSize=tableSize;
86+
hashTable->entryCount=0;
8787

8888
returnhashTable;
8989
}
@@ -95,8 +95,8 @@ boolean removeElementFromHash(HashTable *hashtable, void *value)
9595
uint32_t
9696
hashValue=hashtable->hashFunction(hashtable,value),
9797
position=hashValue %hashtable->tableSize;
98-
99-
HashElem*elem=hashtable->table[position];
98+
99+
HashElem*elem=hashtable->table[position];
100100

101101
if(NOTelem )
102102
{
@@ -110,20 +110,20 @@ boolean removeElementFromHash(HashTable *hashtable, void *value)
110110
{
111111
hashtable->table[position]=elem->next ;
112112
free(elem);
113-
hashtable->entryCount-- ;
113+
hashtable->entryCount-- ;
114114

115-
return TRUE;
115+
return TRUE;
116116
}
117-
117+
118118
while(elem->next)
119119
{
120120
if(elem->next->fullKey==hashValue&&hashtable->equalFunction(hashtable,elem->next->value,value))
121121
{
122-
void*nextOne=elem->next->next;
122+
void*nextOne=elem->next->next;
123123
free(elem->next);
124124
elem->next=nextOne;
125-
hashtable->entryCount-- ;
126-
return TRUE;
125+
hashtable->entryCount-- ;
126+
return TRUE;
127127
}
128128
elem=elem->next;
129129
}
@@ -134,53 +134,53 @@ boolean removeElementFromHash(HashTable *hashtable, void *value)
134134

135135
void*searchHashTableWithInt(HashTable*hashtable,uint32_thashValue)
136136
{
137-
uint32_t
137+
uint32_t
138138
position=hashValue %hashtable->tableSize;
139-
140-
HashElem
139+
140+
HashElem
141141
*elem;
142-
143-
for(elem=hashtable->table[position];
144-
elem;
142+
143+
for(elem=hashtable->table[position];
144+
elem;
145145
elem=elem->next)
146146
if(elem->fullKey==hashValue)
147-
returnelem->value;
147+
returnelem->value;
148148

149149
returnNULL;
150150
}
151151

152152

153153
void*searchHashTable(HashTable*hashtable,void*value,uint32_thashValue)
154154
{
155-
uint32_t
155+
uint32_t
156156
position=hashValue %hashtable->tableSize;
157-
158-
HashElem
157+
158+
HashElem
159159
*elem;
160-
161-
for(elem=hashtable->table[position];
162-
elem;
160+
161+
for(elem=hashtable->table[position];
162+
elem;
163163
elem=elem->next)
164-
if(elem->fullKey==hashValue&&
164+
if(elem->fullKey==hashValue&&
165165
hashtable->equalFunction(hashtable,elem->value,value))
166-
returnelem->value;
166+
returnelem->value;
167167

168168
returnNULL;
169169
}
170170

171171

172172
voidinsertIntoHashTable(HashTable*hashTable,void*value,uint32_tindex)
173-
{
173+
{
174174
/* just copied this */
175-
HashElem
175+
HashElem
176176
*hashElem=CALLOC(1,sizeof(HashElem));
177-
177+
178178
hashElem->fullKey=index;
179-
179+
180180
index=hashElem->fullKey %hashTable->tableSize;
181-
181+
182182
hashElem->value=value;
183-
hashElem->next=hashTable->table[index];
183+
hashElem->next=hashTable->table[index];
184184
hashTable->table[index]=hashElem;
185185
#ifdefPARALLEL
186186
pthread_mutex_lock(hashTable->cntLock);
@@ -194,21 +194,21 @@ void insertIntoHashTable(HashTable *hashTable, void *value, uint32_t index)
194194

195195
voiddestroyHashTable(HashTable*hashTable,void (*freeValue)(void*value))
196196
{
197-
unsigned
198-
inti;
199-
200-
HashElem
201-
*elemA,
197+
unsigned
198+
inti;
199+
200+
HashElem
201+
*elemA,
202202
*elemB,
203203
**table=hashTable->table;
204-
204+
205205
for(i=0;i<hashTable->tableSize;++i)
206206
{
207207
elemA=table[i];
208208
while(elemA!=NULL)
209209
{
210-
elemB=elemA;
211-
elemA=elemA->next;
210+
elemB=elemA;
211+
elemA=elemA->next;
212212
if(freeValue)
213213
freeValue(elemB->value);
214214
free(elemB);
@@ -218,7 +218,7 @@ void destroyHashTable(HashTable *hashTable, void (*freeValue)(void *value))
218218
#ifdefPARALLEL
219219
pthread_mutex_destroy(hashTable->cntLock);
220220
free(hashTable->cntLock);
221-
221+
222222
FOR_0_LIMIT(i,hashTable->tableSize)
223223
{
224224
pthread_mutex_destroy(hashTable->lockPerSlot[i]);
@@ -227,23 +227,23 @@ void destroyHashTable(HashTable *hashTable, void (*freeValue)(void *value))
227227
free(hashTable->lockPerSlot);
228228
#endif
229229

230-
free(hashTable->commonAttributes);
230+
free(hashTable->commonAttributes);
231231
free(hashTable->table);
232232
free(hashTable);
233233
}
234234

235235

236236
voidupdateEntryCount(HashTable*hashTable)
237237
{
238-
uint32_t
239-
i,
238+
uint32_t
239+
i,
240240
result=0;
241241

242242
for(i=0;i<hashTable->tableSize;++i)
243243
{
244-
HashElem
244+
HashElem
245245
*elem= ((HashElem**)hashTable->table)[i];
246-
246+
247247
while(elem)
248248
{
249249
result++;
@@ -255,18 +255,18 @@ void updateEntryCount(HashTable *hashTable)
255255
}
256256

257257

258-
HashTableIterator*createHashTableIterator(HashTable*hashTable)
258+
HashTableIterator*createHashTableIterator(HashTable*hashTable)
259259
{
260-
unsigned
261-
inti;
262-
263-
HashTableIterator
260+
unsigned
261+
inti;
262+
263+
HashTableIterator
264264
*hashTableIterator=CALLOC(1,sizeof(HashTableIterator));
265-
265+
266266
hashTableIterator->hashTable=hashTable;
267267
hashTableIterator->hashElem=NULL;
268268
hashTableIterator->index=hashTable->tableSize;
269-
269+
270270
if(NOThashTable->entryCount)
271271
returnhashTableIterator;
272272

@@ -279,42 +279,42 @@ HashTableIterator *createHashTableIterator(HashTable *hashTable)
279279
break;
280280
}
281281
}
282-
282+
283283
returnhashTableIterator;
284284
}
285285

286286
booleanhashTableIteratorNext(HashTableIterator*hashTableIterator)
287287
{
288-
uint32_t
289-
i,
288+
uint32_t
289+
i,
290290
tableSize=hashTableIterator->hashTable->tableSize;
291-
292-
HashElem
291+
292+
HashElem
293293
*next=hashTableIterator->hashElem->next;
294-
294+
295295
if(next)
296296
{
297297
hashTableIterator->hashElem=next;
298298
return TRUE;
299299
}
300300

301301
i=hashTableIterator->index+1;
302-
302+
303303
if(i >=tableSize)
304304
{
305305
hashTableIterator->index=i;
306306
return FALSE;
307307
}
308-
308+
309309
while(NOT (next=hashTableIterator->hashTable->table[i]))
310310
{
311-
if(++i >=tableSize)
311+
if(++i >=tableSize)
312312
{
313-
hashTableIterator->index=i;
313+
hashTableIterator->index=i;
314314
return FALSE;
315315
}
316316
}
317-
317+
318318
hashTableIterator->index=i;
319319
hashTableIterator->hashElem=next;
320320

@@ -323,8 +323,8 @@ boolean hashTableIteratorNext(HashTableIterator *hashTableIterator)
323323

324324

325325
void*getCurrentValueFromHashTableIterator(HashTableIterator*hashTableIterator)
326-
{
327-
return ((hashTableIterator->hashElem)
326+
{
327+
return ((hashTableIterator->hashElem)
328328
?hashTableIterator->hashElem->value
329329
:NULL);
330330
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp