一个简朴的HashMap C语言实现

副标题#e#

用C语言实现一个简朴实用的hashmap，具有必然的实际意义。尤其我们不想利用STL内里的map<…>类的时候。我实现的这个hashmap，用来做key—value的映射，key必需是有效的字符串，value是挪用者分派的任意范例的数据。这个hashmap适合在一些简朴的场所下，耗损少少的资源。

首先界说头文件如下：

/*
　* hashmap.h
　*　　　　　　　 Generic hash map: key(string)-value(any type).
　*　　　　　　　 cheungmine
　*　　　　　 Sep. 22, 2007.　 All rights reserved.
　*/
#ifndef HASHMAP_H_INCLUDED
#define HASHMAP_H_INCLUDED

#include "unistd.h"

/* You should always use 1024 */
#define　　　　 HASHMAP_SIZE　　　 1024

/* Opaque struct pointer to _hash_map_t */
typedef struct　　　 _hash_map_t*　　　　　　　 hash_map;

typedef void(*pfcb_hmap_value_free)(void* value);

/* An example of free value function implemented by caller:
void my_hmap_free_value(void* pv)
{
　　　 free(pv);
}
*/

/* Create before use. eg:
　* hash_map　 hm;
　* hmap_create (&hm, HASHMAP_SIZE);
　* assert (hm);　　　　 // out of memory if hm==NULL
　* void* mydata=malloc(n);
　* hmap_insert(hm, "shanghai", -1, mydata);
　　 ...
　* hmap_destroy(hm, my_hmap_free_value);
　*/
extern void
hmap_create(hash_map *hmap, int size);

/* Destroy after use */
extern void
hmap_destroy(hash_map hmap, pfcb_hmap_value_free);

/* Insert a key-value into hash map. value is a pointer to callee-allocated memory */
extern void
hmap_insert(hash_map hmap, const char* key, int key_len/* -1 for strlen to be called */, void* value);

/* Search a hash map for value of given key string */
extern void*
hmap_search(hash_map hmap, const char　 *key);

#endif　 /* HASHMAP_H_INCLUDED */

#p#副标题#e#

实现文件如下：

/*
　* hashmap.c
　*　　　　　　　 Generic hashmap implementation.
　*　　　　　 a map for pair of key-value. key must be a null-end string, value is any type of data.
　*　　　　　　　 cheungmine
　*　　　　　 Sep. 22, 2007.　 All rights reserved.
　*/

#include "hashmap.h"
#include "list.h"

typedef struct _hash_map_t
{
　　　 size_t　　　　　　　　　　　 size;
　　　 listnode_t**　　　 key;
　　　 listnode_t**　　　 value;
}hash_map_t;

/* Hash a string, return a hash key */
static ulong　 hash_string(const char　 *s, int len)
{
　　　 ulong h = 0;
　　　 int　　 i = 0;
　　　 assert (s);
　　　 if (len < 0)
　　　　　　　 len = (s? (int)strlen(s): 0);
　　　 while(i++ < len) { h = 17*h + *s++; }
　　　 return h;
}

static void _free_map_key(listnode_t* node)
{
　　　 listnode_t　　　 *old;
　　　 while(node)
　　　 {　　　　　　　
　　　　　　　 old = node;
　　　　　　　 node = node->next;

　　　　　　　 free(old->data);
　　　　　　　 free (old);
　　　 }
}

static void _free_map_value(listnode_t* node, pfcb_hmap_value_free pfunc)
{
　　　 listnode_t　　　 *old;
　　　 while(node)
　　　 {　　　　　　　
　　　　　　　 old = node;
　　　　　　　 node = node->next;

　　　　　　　 if (pfunc)
　　　　　　　　　　　 (*pfunc)(old->data);
　　　　　　　 free (old);
　　　 }
}

/*=============================================================================
　　　　　　　　　　　　　　　　　　　　　　　　　　　 Public Functions
=============================================================================*/
/* Create before use */
void
hmap_create(hash_map *hmap, int size)
{
　　　 (*hmap) = (hash_map_t*) malloc(sizeof(hash_map_t));
　　　 (*hmap)->size = size;
　　　 (*hmap)->key = (listnode_t**) calloc(size, sizeof(listnode_t*));
　　　 (*hmap)->value = (listnode_t**) calloc(size, sizeof(listnode_t*));
}

/* Destroy after use */
extern void
hmap_destroy(hash_map hmap, pfcb_hmap_value_free pfunc)
{
　　　 size_t i;
　　　 for(i=0; i<hmap->size; i++){
　　　　　　　 _free_map_key(hmap->key[i]);
　　　　　　　 _free_map_value(hmap->value[i], pfunc);
　　　 }

　　　 free(hmap->key);
　　　 free(hmap->value);
　　　 free(hmap);
}

/* Insert a key-value into hash map. value is a pointer to callee-allocated memory */
void
hmap_insert(hash_map hmap, const char* key, int key_len, void* value)
{
　　　 listnode_t　　　 *node_key, *node_val;
　　　 ulong　　　　　　　 h;
　　　 char　　　　　　　 *s;
　　　 assert (key);

　　　 if (key_len<0) key_len = (int) strlen (key);
　　　 s = (char*) malloc (key_len+1);
　　　 assert(s);

#pragma warning(push)　　　 /* C4996 */
#pragma warning( disable : 4996 )
　　　 strncpy (s, key, key_len);
#pragma warning(pop)　　　 /* C4996 */
　　　 s[key_len] = 0;

　　　 node_key = list_node_create ( (void*)s );
　　　 node_val = list_node_create ( value );
　　　 assert(node_key && node_val);

　　　 h = hash_string (s, key_len) % hmap->size;

　　　 node_key->next = hmap->key[h];
　　　 hmap->key[h] = node_key;

　　　 node_val->next = hmap->value[h];
　　　 hmap->value[h] = node_val;
}

/* Search a hash map for value of given key string */
void*
hmap_search(hash_map hmap, const char *key)
{
　　　 ulong　　　　　　　 h　　　 = hash_string (key, -1) % hmap->size;
　　　 listnode_t　 *pk = hmap->key[h];
　　　 listnode_t　 *pv = hmap->value[h];

　　　 while (pk)
　　　 {
　　　　　　　 if (strcmp(key, pk->str) == 0)
　　　　　　　　　　　 return pv->data;
　　　　　　　 pk = pk->next;
　　　　　　　 pv = pv->next;
　　　 }

　　　 return NULL;
}

好了，其顶用到的其他文件（unistd.h，list.h，list.c）看我下一篇文章！

C语言实现一个简朴的单向链表list