Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Ronin Magus

What do you think of this, much code.

This topic is 5251 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

In a non-graphics orientied engine I''m programming (uses Irrilcht for graphics) called Dusty Engine I found I needed a very fast associative container. Looking into hash_map, I found it wasn''t actually C++ standard and was just an extension. So instead of fumble mindlessly with it, I decided to create my own to slightly mimic its functionality. This is what I''ve come up with. It uses a vector of lists as the hash. Does it suck? Is it useful? Let me know, please! One issue I know is a flaw is that it has a very simple, hardcoded hashing statement: hashIndex = key % hash_size.. I know this is limited, and limits the key type by requireing a modulus operator, but I did not want to get too complex. Please let me know what you think of this, I am about to put Dusty Engine up for download (it''ll be version 0.1) and I''d like to see how people might react to it. I''m very pleased with how it''s working dustymapnode.h
#ifndef __DUSTY_HASH_NODE__H__
#define __DUSTY_HASH_NODE__H__

namespace DustyEngine
{
	//! HashMapNode is a node for HashMap.  Fairly straight-forward.

	template <class KeyType, class ValueType>
	class HashMapNode
	{
	public:
		//! key is the key to reference the value with.

		KeyType key;

		//! value is the value to reference.

		ValueType value;
	};
}

#endif
dustyhashmap.h
#ifndef __DUSTY__HASHMAP_H__
#define __DUSTY__HASHMAP_H__

#include <vector>
#include <list>
#include "dustyengine.h"
#include <irrlicht.h>

namespace DustyEngine
{
	//! HashMap is a VERY SIMPLE templated hash map class.

	/**HashMap is a simple, fast implementation of an associative hash.  In this implementation,
	the hash function is hardcoded no more than (key % total_hash_size).  This means that the key type must
	be one with a modulate operator (which should return an integer), and the key type must also have
	an equality(==) operator.  This is mostly used internally, but if used externally it is recommended
	that the key be an int.
	*/
	template <class KeyType, class ValueType>
	class HashMap
	{
	public:
		//! Default constructor creates the hash vector, with a default hash size of 1000.

		HashMap() : numNodes(0)
		{
			hashVector.resize(1000);
		}

		//! "Build" constructor creates a hash vector, with a specified size.

		//! \param size: Size of the hash vector.

		HashMap(irr::s32 size) : numNodes(0)
		{
			if (size <= 0)
				size = 1;

			hashVector.resize(size);
		}

		//! GetHashSize returns the size of the hash vector.

		//! \return Returns the size of the hash vector.

		irr::s32 GetHashSize()
		{
			return hashVector.size();
		}

		//! NumNodes returns the number of nodes current stored in the hash map.

		//! \return Returns the number of nodes stored in the hash.

		irr::s32 NumNodes()
		{
			return numNodes;
		}

		//! Clear deletes all nodes from the hash vector.  If the value type is a pointer, it will NOT release the pointer''s memory.

		void Clear()
		{
			typename std::vector<std::list<HashMapNode<KeyType, ValueType> > >::iterator it;

			for(it = hashVector.begin(); it != hashVector.end(); ++it) {
				(*it).clear();
			}
		}

		//! AddNode adds a node into the hash, indexed by key.

		//! \param key: The key to index this node with.

		//! \param value: The value to store in the hash.

		void AddNode(const KeyType & key, const ValueType & value)
		{
			irr::s32 index = key % hashVector.size();
			HashMapNode<KeyType, ValueType> temp;

			temp.key = key;
			temp.value = value;

			hashVector[index].push_back(temp);
			numNodes++;
		}

		//! RemoveNode removes a node from the hash.  If the node type is a pointer, it will NOT release memory.

		//! \param key: The key of the node to remove.

		void RemoveNode(const KeyType & key)
		{
			irr::s32 index = key % hashVector.size();
			typename std::list<HashMapNode<KeyType, ValueType> >::iterator it;

			for(it = hashVector[index].begin(); it != hashVector[index].end(); ++it) {
				if((*it).key == key) {
					hashVector[index].erase(it);
					numNodes--;
					break;
				}
			}
		}

		//! GetNode returns A POINTER to the value indexed by key.  To access the value''s data, the pointer must be dereferenced.  If the key does not exist in the hash, GetNode returns NULL.

		//! \param key: Key of the value to return.

		//! \return Returns a pointer to the value indexed by key.

		ValueType * GetNode(const KeyType & key)
		{
			irr::s32 index = key % hashVector.size();
			typename std::list<HashMapNode<KeyType, ValueType> >::iterator it;

			for(it = hashVector[index].begin(); it != hashVector[index].end(); ++it) {
				if((*it).key == key) {
					return &(*it).value;
				}
			}

			return NULL;
		}

	private:
		std::vector<std::list<HashMapNode<KeyType, ValueType> > > hashVector;

		irr::s32 numNodes;
	};
}

#endif
a simple example of its use, main.cpp
#include <dustyengine/dustyengine.h>

using namespace DustyEngine;

int main()
{
	HashMap <int, int> myMap;

	// make a hash of 100 objects

	for(int i = 0; i < 100; i++) {
		myMap.AddNode(i, i);
	}

	// change the first 10 objects

	int * result = NULL;
	
	for(int i = 0; i < 10; i++) {
		// only change the result if the key exists

		// (which we know it does in this simple example,

		// but this is how to check for it)

		if(result = myMap.GetNode(i)) {
			(*result) = 0;
		}
	}
	
	// print the items in the hash, remember to DEREFERENCE!

	for(int i = 0; i < 100; i ++) {
		std::cout << (*myMap.GetNode(i)) << std::endl;
	}
}

daveandrews.org - a Christian Programmer''s Weblog | Dusty Engine - a task engine using Irrlicht | Computer Guys Run the World
How to be a Programmer

Share this post


Link to post
Share on other sites
Advertisement

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!