hashtable.c

Boosting is a meta-learning approach that aims at combining an ensemble of weak classifiers to form

		}
	}
	return (off_t)-1;
}

void _hashtable_freeelement(void* data, void* metadata)
{
	hashelement_t* element=*(hashelement_t**)data;
	FREE(element->key);
	FREE(element);
}

void hashtable_free(hashtable_t* input)
{
	int i;
	for(i=0;i<input->size;i++)
	{
		hashelement_t* element=input->buckets[i];
		while(element)
		{
			hashelement_t* tmp=element->next_in_bucket;
#ifdef HASHTABLE_CENTRALIZE_KEYS
			if(input==_hashtable_key_repository) FREE(element->key);
#else
			FREE(element->key);
#endif
			FREE(element);
			element=tmp;
		}
	}
	FREE(input->buckets);
	FREE(input);
}


void hashtable_optimize(hashtable_t* h)//, int (*compare)(const void* a,const void* b))
{
	warn("hashtable_optimize(%p) is deprecated", h);
}

size_t hashtable_memory_size(hashtable_t* input)
{
	size_t memory=sizeof(hashtable_t);
	memory+=input->size*sizeof(hashelement_t*);
	memory+=input->size*sizeof(hashelement_t);
#ifdef HASHTABLE_CENTRALIZE_KEYS
	if(input==_hashtable_key_repository)
#endif
	{
		int i;
		for(i=0;i<input->size;i++)
		{
			hashelement_t* element=input->buckets[i];
			while(element)
			{
				memory+=element->key_length;
				element=element->next_in_bucket;
			}
		}
	}
	return memory;
}

void hashtable_stats(hashtable_t* input,FILE* stream)
{
	size_t memory=hashtable_memory_size(input);
	fprintf(stream,"hashtable_stats(%p) size=%zd elements=%zd avg_coll=%.2f"
#ifdef HASHTABLE_GATHER_STATS
		" avg_access=%.2f"
#endif
		" Bpe=%.2f memory=%.2fk\n",
		input,input->size,input->length,input->length/(double)input->size,
#ifdef HASHTABLE_GATHER_STATS
		input->num_hits_per_access/(double)input->num_accesses,
#endif
		memory/(double)input->length,memory/1024.0);
}

int hashtable_save(hashtable_t* h,FILE* file, off_t (*saveValue)(hashelement_t* element,void* metadata), void* metadata)
{
	int i;
	off_t bucketLocation[h->size];
	off_t begining=ftello(file);
	fseeko(file,h->size*(sizeof(int)*2+sizeof(off_t))+sizeof(int)*2,SEEK_CUR);
	size_t *bucketLength=MALLOC(sizeof(size_t)*h->size);
	for(i=0;i<h->size;i++)
	{
		bucketLocation[i]=ftello(file);
		bucketLength[i]=0;
		hashelement_t* element=h->buckets[i];
		while(element!=NULL)
		{
			bucketLength[i]++;
			fwrite(&element->key_length,sizeof(size_t),1,file);
			fwrite(element->key,element->key_length,1,file);
			if(saveValue!=NULL)
			{
				off_t location=saveValue(element, metadata);
				fwrite(&location,sizeof(off_t),1,file);
			}
			else
			{
				fprintf(stderr,">value %p\n",element->value);
				fwrite(&element->value,sizeof(void*),1,file);
			}
			element=element->next_in_bucket;
		}
	}
	off_t end=ftello(file);
	fseeko(file,begining,SEEK_SET);
	int magic=HASHTABLE_MAGIC;
	fwrite(&magic,sizeof(int),1,file);
	fwrite(&(h->size),sizeof(size_t),1,file);
	// magic, size, size*[location,length,size]
	size_t zero=0;
	for(i=0;i<h->size;i++)
	{
		fwrite(&bucketLocation[i],sizeof(off_t),1,file);
		if(h->buckets[i]!=NULL)
		{
			fwrite(&bucketLength[i],sizeof(size_t),1,file);
			size_t diskSize=0;
			if(i<h->size-1)diskSize=bucketLocation[i+1]-bucketLocation[i];
			else diskSize=end-bucketLocation[i];
			fwrite(&diskSize,sizeof(size_t),1,file);
			//warn("%d %lld %d %d",i,bucketLocation[i],h->buckets[i]->length,diskSize);
		}
		else
		{
			//warn("%d %lld %d %d",i,bucketLocation[i],0,0)
			fwrite(&zero,sizeof(size_t),1,file);
			fwrite(&zero,sizeof(size_t),1,file);
		}
	}
	fseeko(file,end,SEEK_SET);
	FREE(bucketLength);
	return 0;
}

hashtable_t* hashtable_load(FILE* file, void* (*loadValue)(const void* key,size_t key_length,off_t location,void* metadata),void* metadata)
{
	int i,j;
	size_t size;
	int magic=-1;
	fread(&magic,sizeof(int),1,file);
	if(magic!=HASHTABLE_MAGIC)
	{
		warn("bad magic %d!=%d",magic,HASHTABLE_MAGIC);
		return NULL;
	}
	fread(&size,sizeof(size_t),1,file);
	hashtable_t* h=hashtable_new_size(size);
	off_t bucketLocation[size];
	size_t bucketLength[size];
	size_t bucketSize[size];
	for(i=0;i<h->size;i++)
	{
		fread(&bucketLocation[i],sizeof(off_t),1,file);
		fread(&bucketLength[i],sizeof(size_t),1,file);
		fread(&bucketSize[i],sizeof(size_t),1,file);
	}
	for(i=0;i<h->size;i++)
	{
		//warn("%d %lld %d %d",i,bucketLocation[i],bucketLength[i],bucketSize[i]);
		if(bucketLength[i]!=0)
		{
			fseeko(file,bucketLocation[i],SEEK_SET);
			char buffer[bucketSize[i]];
			fread(buffer,bucketSize[i],1,file);
			char* ptr=buffer;
			for(j=0;j<bucketLength[i];j++)
			{
				size_t key_length=*(size_t*)ptr;
				ptr+=sizeof(size_t);
				char* key=ptr;
				ptr+=key_length;
				void* value=NULL;
				if(loadValue!=NULL)
				{
					value=loadValue(key,key_length,*(off_t*)ptr,metadata);
					ptr+=sizeof(off_t);
				}
				else
				{
					value=*(void**)ptr;
					ptr+=sizeof(void*);
				}
				hashtable_set(h,key,key_length,value);
			}
		}
	}
	return h;
}

void hashtable_apply(hashtable_t* h, void (*callback)(hashelement_t* element, void* metadata),void* metadata)
{
	int i;
	for(i=0;i<h->size;i++)
	{
		hashelement_t* element=h->buckets[i];
		while(element!=NULL)
		{
			callback(element,metadata);
			element=element->next_in_bucket;
		}
	}
}

vector_t* hashtable_elements(hashtable_t* h)
{
	int i;
	vector_t* output=vector_new(h->length);
	for(i=0;i<h->size;i++)
	{
		hashelement_t* element=h->buckets[i];
		while(element!=NULL)
		{
			vector_push(output,element);
			element=element->next_in_bucket;
		}
	}
	return output;
}

vector_t* hashtable_keys(hashtable_t* h)
{
	int i;
	vector_t* output=vector_new(h->length);
	for(i=0;i<h->size;i++)
	{
		hashelement_t* element=h->buckets[i];
		while(element!=NULL)
		{
			vector_push(output,element->key);
			element=element->next_in_bucket;
		}
	}
	return output;
}

vector_t* hashtable_values(hashtable_t* h)
{
	int i;
	vector_t* output=vector_new(h->length);
	for(i=0;i<h->size;i++)
	{
		hashelement_t* element=h->buckets[i];
		while(element)
		{
			vector_push(output,element->value);
			element=element->next_in_bucket;
		}
	}
	return output;
}

hashelement_t* hashtable_first_element(hashtable_t* h)
{
	int i;
	if(h->length==0)return NULL;
	for(i=0;i<h->size;i++)
	{
		if(h->buckets[i]!=NULL)
		{
			h->current_element=h->buckets[i];
			return h->buckets[i];
		}
	}
	return NULL;
}

hashelement_t* hashtable_next_element(hashtable_t* h)
{
	uint32_t i;
	if(h->current_element->next_in_bucket!=NULL)
	{
		h->current_element=h->current_element->next_in_bucket;
		return h->current_element;
	}
	uint32_t next_bucket=h->current_element->hashcode%h->size+1;
	for(i=next_bucket;i<h->size;i++)
	{
		if(h->buckets[i]!=NULL)
		{
			h->current_element=h->buckets[i];
			return h->buckets[i];
		}
	}
	return NULL;
}

void* hashtable_first_key(hashtable_t* h)
{
	hashelement_t* element=hashtable_first_element(h);
	if(element==NULL)return NULL;
	return element->key;
}

void* hashtable_next_key(hashtable_t* h)
{
	hashelement_t* element=hashtable_next_element(h);
	if(element==NULL)return NULL;
	return element->key;
}

void* hashtable_first_value(hashtable_t* h)
{
	hashelement_t* element=hashtable_first_element(h);
	if(element==NULL)return NULL;
	return element->value;
}

void* hashtable_next_value(hashtable_t* h)
{
	hashelement_t* element=hashtable_next_element(h);
	if(element==NULL)return NULL;
	return element->value;
}

void hashtable_freevalue(hashelement_t* element, void* metadata)
{
	FREE(element->value);
}

void _hashtable_replicate(hashelement_t* element, void* metadata)
{
	hashtable_t* h=(hashtable_t*)metadata;
	hashtable_set(h,element->key,element->key_length,element->value);
}

void hashtable_resize(hashtable_t* input, size_t new_size)
{
	//hashtable_print_stats(input,stdout);
	hashelement_t** old_buckets=input->buckets;
	input->buckets=MALLOC(sizeof(hashelement_t*)*new_size);
	memset(input->buckets,0,sizeof(hashelement_t*)*new_size);
	int i;
	for(i=0;i<input->size;i++)
	{
		hashelement_t* element=old_buckets[i];
		while(element)
		{
			hashelement_t* tmp=element->next_in_bucket;
			uint32_t bucket=element->hashcode%new_size;
			element->next_in_bucket=input->buckets[bucket];
			input->buckets[bucket]=element;
			element=tmp;
		}
	}
	input->size=new_size;
	FREE(old_buckets);
	//hashtable_print_stats(input,stdout);
}