fs2open.github.com/code/localization/fhash.cpp

/*
 * Copyright (C) Volition, Inc. 1999.  All rights reserved.
 *
 * All source code herein is the property of Volition, Inc. You may not sell 
 * or otherwise commercially exploit the source or things you created based on the 
 * source.
 *
*/



#include <cstdlib>
#include <memory.h>
#include <cstring>
#include "globalincs/pstypes.h"
#include "localization/fhash.h"



// -----------------------------------------------------------------------------------------------
// HASH DEFINES/VARS
//

// hash node
typedef struct fhash_node {
	char *str;							// allocated dynamically
	int id;								// can be -1
	fhash_node *next, *prev;			// for chaining in an individual hash table entry (non-circular, doubly linked list)
} fhash_node;

// hash table itself (with chained nodes)
#define HASH_TABLE_SIZE				253					// works better when not a power of 2, and is prime
fhash_node *Hash_table_fred[HASH_TABLE_SIZE];

// if the hash table is active
int Fhash_active = 0;


// -----------------------------------------------------------------------------------------------
// HASH FORWARD DECLARATIONS
//

// hash a string. return an index into the hash table where it should be inserted
int fhash_get_hash_index(const char *str);

// insert a string into hash table index N, will take care of allocating/chaining everything
void fhash_insert(const char *str, int id, int n);


// -----------------------------------------------------------------------------------------------
// HASH FUNCTIONS
//

// initialize the hash table
void fhash_init()
{
	memset(Hash_table_fred, 0, sizeof(fhash_node *) * HASH_TABLE_SIZE);
}

// set the hash table to be active for parsing
void fhash_activate()
{	
	Fhash_active = 1;	
}

// set the hash table to be inactive for parsing
void fhash_deactivate()
{	
	Fhash_active = 0;
}

// if the hash table is active
int fhash_active()
{
	return Fhash_active;
}

// flush out the hash table, freeing up everything
void fhash_flush()
{
	int idx;
	fhash_node *moveup, *backup;

	// go through each element
	for(idx=0; idx<HASH_TABLE_SIZE; idx++){
		if(Hash_table_fred[idx] != NULL){
			moveup = Hash_table_fred[idx];
			while(moveup != NULL){
				// next element
				backup = moveup;
				moveup = moveup->next;

				// free up this element
				if(backup->str != NULL){
					vm_free(backup->str);
				}
				vm_free(backup);
			}

			// null this element
			Hash_table_fred[idx] = NULL;
		}
	}
}

// add a string with the given id# to the hash table
void fhash_add_str(const char *str, int id)
{
	int hash_index;

	// if the hash table isn't active, don't bother
	Assert(Fhash_active);
	if(!Fhash_active){
		return;
	}

	// determine where the string goes in the hash table
	Assert(str != NULL);
	if(str == NULL){
		return;
	}
	hash_index = fhash_get_hash_index(str);

	// insert into the hash table
	fhash_insert(str, id, hash_index);
}

// determine if the passed string exists in the table
// returns : -2 if the string doesn't exit, or >= -1 as the string id # otherwise
int fhash_string_exists(const char *str)
{
	int hash_index;
	fhash_node *moveup;

	Assert(str != NULL);
	if(str == NULL){
		return -2;
	}

	// get the hash index for this string
	hash_index = fhash_get_hash_index(str);

	// if there are no entries, it doesn't exist
	if(Hash_table_fred[hash_index] == NULL){
		return -2;
	}

	// otherwise compare against all strings in this code
	moveup = Hash_table_fred[hash_index];
	while(moveup != NULL){
		// do a string compare on this item
		Assert(moveup->str != NULL);
		if(moveup->str != NULL){
			if(!strcmp(moveup->str, str)){
				return moveup->id;
			}
		}
		
		// next item
		moveup = moveup->next;
	}

	// didn't find it
	return -2;
}


// -----------------------------------------------------------------------------------------------
// HASH FORWARD DEFINITIONS
//

// hash a string. return an index into the hash table where it should be inserted
int fhash_get_hash_index(const char *str)
{
	int accum = 0;
	size_t idx, str_len;
	int ret;

	// add up the string
	str_len = strlen(str);
	for(idx=0; idx<str_len; idx++){
		accum += str[idx];
	}

	ret = abs(accum) % 253;	
	return ret;
}

// insert a string into hash table index N, will take care of allocating/chaining everything
void fhash_insert(const char *str, int id, int n)
{
	fhash_node *new_node;
	fhash_node *moveup;

	// allocate the new node
	new_node = (fhash_node*)vm_malloc(sizeof(fhash_node));
	Assert(new_node);
	if(new_node == NULL){
		return;
	}

	// fill in the node
	new_node->str = vm_strdup(str);
	new_node->id = id;
	new_node->next = NULL;
	new_node->prev = NULL;

	// if this hash index is NULL, just assign it
	if(Hash_table_fred[n] == NULL){
		Hash_table_fred[n] = new_node;
	} else {
		moveup = Hash_table_fred[n];
		while(moveup->next != NULL){
			moveup = moveup->next;
		}
		new_node->prev = moveup;
		moveup->next = new_node;
	}
}