|
/*
* Copyright (C) 2002-2008 XimpleWare, info@ximpleware.com
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program 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 General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
/* intHash implements a simple hash table that speeds up the
uniqueness checking */
#include "xpath1.h"
/* the constructor */
IntHash* createIntHash(){
/*int i=0;
IntHash *ih = (IntHash *) malloc(sizeof(IntHash));
if (ih==NULL) {
throwException2(out_of_mem,
"IntHash allocation failed ");
}
ih->storage = (FastIntBuffer **) malloc(sizeof(FastIntBuffer*)<<ih_hashWidthE);
ih->hw = ih_hashWidth;
ih->m1 = ih_mask1;
ih->m2 = ih_mask2;
ih->maxDepth = 0;
ih->pse = ih_pageSizeE;*/
/* initialize everything to null */
/*for (i=0;i<ih->hw;i++){
ih->storage[i]= NULL;
}*/
return createIntHash2(0);
}
IntHash* createIntHash2(int hashWidthExpo){
int i=0;
IntHash *ih = (IntHash *) malloc(sizeof(IntHash));
if (ih==NULL) {
throwException2(out_of_mem,
"IntHash allocation failed ");
return NULL;
}
ih->storage = (FastIntBuffer **) malloc(sizeof(FastIntBuffer*)<<ih_hashWidthE);
ih->hw = 1<<hashWidthExpo;
ih->m1 = ih->hw -1;
ih->m2 = (~ih->m1) & 0xffffffff;
ih->maxDepth = 0;
ih->pse = ih_pageSizeE;
/* initialize everything to null */
for (i=0;i<ih->hw;i++){
ih->storage[i]= NULL;
}
return ih;
}
/* free intHash */
void freeIntHash(IntHash *ih){
int i=0;
if (ih !=NULL){
for (i=0;i<=ih->maxDepth;i++){
freeFastIntBuffer(ih->storage[i]);
}
free(ih->storage);
free(ih);
}
}
/* Test whether the input i is unique;
if not, insert into the hash table and return false
otherwise, return true */
Boolean isUniqueIntHash(IntHash *ih,int i){
int j,size;
int temp = i & ih->m1;
if (temp>ih->maxDepth){
ih->maxDepth = temp;
}
if (ih->storage[temp]==NULL) {
ih->storage[temp]= createFastIntBuffer2(ih->pse);
if (ih->storage[temp]==NULL) {
throwException2(out_of_mem,
"FastIntBuffer allocation failed ");
}
appendInt(ih->storage[temp],i);
return TRUE;
}
else{
size = ih->storage[temp]->size;
for (j=0;j<size;j++){
if (i == intAt(ih->storage[temp],j)){
return FALSE;
}
}
appendInt(ih->storage[temp],i);
return TRUE;
}
}
/* reset intHash */
void resetIntHash(IntHash *ih){
int i=0;
for (i=0;i<=ih->maxDepth;i++){
if (ih->storage[i]!=NULL){
clearFastIntBuffer(ih->storage[i]);
}
}
}
int determineHashWidth(int i){
if (i<(1<<8))
return 3;
if (i<(1<<9))
return 4;
if (i<(1<<10))
return 5;
if (i<(1<<11))
return 6;
if (i<(1<<12))
return 7;
if (i<(1<<13))
return 8;
if (i<(1<<14))
return 9;
if (i<(1<<15))
return 10;
if (i<(1<<16))
return 11;
return 12;
}
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
Jimmy Zhang is a cofounder of XimpleWare, a provider of high performance XML processing solutions. He has working experience in the fields of electronic design automation and Voice over IP for a number of Silicon Valley high-tech companies. He holds both a BS and MS from the department of EECS from U.C. Berkeley.