Dir: ./
A Hashtable In C
2011-08-20 02:58:38

1. It's mainly for storing struct data.
2. Auto-resize.
3. Avoid data copy when rehashing.
5. No delete method at present.
 
/*jmhashtable.h*/
#ifndef _jmhashtable_h_
#define _jmhashtable_h_
 
typedef struct sjmhashtable
{
  int iItemSize;
  int iKeySize;/*==0:string*/
  
  int *pHashTable;
  int *pNextTable;
  int *pHashValue;
  
  int iDataArrayCount;
  int *pDataArray;
  int iDataArraySize;
  int iDataSlotSize;
  
  int iCapacity;/*=iDataSlotSize*iDataArrayCount*/
  int iCount;
  int (*pHashFunc)(void *pData);/*return hash value*/
  int (*pCompareFunc)(void *pData1, void *pData2);/*return 0:equal, >0:Data1>Data2, <0:Data1<Data2*/
}JMHashTable;
 
/*return >0:OK, NULL:error*/
#define JMHTInit(iItemSize, iKeySize) JMHTInitEx(iItemSize, iKeySize, 512, 1024, NULL, NULL)
 
JMHashTable *JMHTInitEx(int iItemSize, int iKeySize, int iDataArraySize, int iDataSlotSize,
  int (*pHashFunc)(void *pData),
  int (*pCompareFunc)(void *pData1, void *pData2));
 
/*return 0:OK, -1:key conflict/error*/
int JMHTAddEx(JMHashTable *pHT, void *pData);
 
/*return >0:OK, NULL:error*/
void *JMHTGetEx(JMHashTable *pHT, void *pData);
 
/*return 0:OK, -1:error
int JMHTDeleteEx(JMHashTable *pHT, void *pData);*/
 
/*release memory*/
void JMHTFree(JMHashTable **ppHT);
 
#endif
 
 
 
/*-
 * ..................
 * $FreeBSD: src/sys/sys/fnv_hash.h,v 1.3.22.1.4.1 2010/06/14 02:09:06 kensmith Exp $
 */
typedef unsigned int Fnv32_t;
 
#define FNV1_32_INIT ((Fnv32_t) 33554467UL)
#define FNV_32_PRIME ((Fnv32_t) 0x01000193UL)
#define u_int8_t unsigned char
 
static  Fnv32_t
fnv_32_buf(const void *buf, int len, Fnv32_t hval)
{
  const u_int8_t *s = (const u_int8_t *)buf;
 
  while (len-- != 0) {
    hval *= FNV_32_PRIME;
    hval ^= *s++;
  }
  return hval;
}
 
static  Fnv32_t
fnv_32_str(const char *str, Fnv32_t hval)
{
  const u_int8_t *s = (const u_int8_t *)str;
  Fnv32_t c;
 
  while ((c = *s++) != 0) {
    hval *= FNV_32_PRIME;
    hval ^= c;
  }
  return hval;
}
/*$FreeBSD: src/sys/sys/fnv_hash.h*/
 
/*jmhashtable.c*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
#include "jmhashtable.h"
 
/*internal func*/
/*return 0:OK, -1:error*/
static int JM_HTExtendData(JMHashTable *pHT);
 
/*return 0:OK, -1:error*/
static int JM_HTRehash(JMHashTable *pHT);
 
/*return 0:OK, -1:key conflict. Avoid recal hashvalue*/
static int JM_HTAddKeyToHash(JMHashTable *pHT, int iKeyHashValue, int iKeyPos);
 
/*return:hash value*/
static int JM_HTCalKeyValue(JMHashTable *pHT, void *pData);
 
/*return ==0:pData1==pData2, <0:pData1<pData2, >0:pData1>pData2*/
static int JM_HTCompare(JMHashTable *pHT, void *pData1, void *pData2);
 
static void JM_HTSearch(JMHashTable *pHT, void *pData, void **ppReturn, int **ppIndex);
 
#define JM_ERROR -1
#define JM_OK 0
#define JM_ERR_NO_MEMORY(R) JMError(0, "No memory!");return R;
#define JM_ERR_RETURN(R,M) JMError(0, M);return R;
 
static void JMError(int iLevel, const char *msg)
{
  printf("%s", msg);
}
 
JMHashTable *JMHTInitEx(int iItemSize, int iKeySize, int iDataArraySize, int iDataSlotSize,
  int (*pHashFunc)(void *pData),
  int (*pCompareFunc)(void *pData1, void *pData2))
{
  JMHashTable *pHT;
 
  if(iItemSize <= 0 || iKeySize < 0 || iDataArraySize <= 0 || iDataSlotSize <= 0
    || pHashFunc && !pCompareFunc || pCompareFunc && !pHashFunc)
  {
    JM_ERR_RETURN(NULL, "Parameter invalid!");
  }
 
  if (!(pHT = (JMHashTable *)malloc(sizeof(JMHashTable)) ) )
  {
    JM_ERR_NO_MEMORY(NULL);
  }
  memset(pHT, 0, sizeof(JMHashTable) );
  
  pHT->iItemSize = iItemSize;
  pHT->iKeySize = iKeySize;
  pHT->iDataArraySize = iDataArraySize;
  pHT->iDataSlotSize = iDataSlotSize;
  pHT->pHashFunc = pHashFunc;
  pHT->pCompareFunc = pCompareFunc;
 
  if (JM_HTExtendData(pHT) == JM_ERROR)
  {
    JMHTFree(&pHT);
    return NULL;
  }
    
  return pHT;
}
 
/*return 0:OK, -1:error*/
static int JM_HTExtendData(JMHashTable *pHT)
{
  int *p, iTempSize;
  if (pHT->iDataArrayCount == 0 || pHT->iDataArrayCount == pHT->iDataArraySize)
  {
    if (!(pHT->pDataArray = (int *)realloc(pHT->pDataArray, sizeof(int) * (pHT->iDataArraySize + pHT->iDataArrayCount)) ) )
    {
      JM_ERR_NO_MEMORY(JM_ERROR);
    }
    pHT->iDataArraySize += pHT->iDataArrayCount;
  }
  
  p = pHT->pDataArray + pHT->iDataArrayCount;
  iTempSize = pHT->iItemSize * pHT->iDataSlotSize;
  if (!(*p = (int)malloc(iTempSize)) )
  {
    JM_ERR_NO_MEMORY(JM_ERROR);
  }
  memset( (void *)*p, 0, iTempSize);
  pHT->iCapacity += pHT->iDataSlotSize;
  
  if (JM_HTRehash(pHT) == JM_ERROR)
  {
    return JM_ERROR;
  }
  
  ++pHT->iDataArrayCount;
  return JM_OK;
}
 
/*return 0:OK, -1:error*/
static int JM_HTRehash(JMHashTable *pHT)
{
  int i, iNewSize;
  
  iNewSize = pHT->iCapacity * sizeof(int);
  
  if (!(pHT->pHashTable = (int *)realloc(pHT->pHashTable, iNewSize) ) )
  {
    JM_ERR_NO_MEMORY(JM_ERROR);
  }
  memset(pHT->pHashTable, -1, iNewSize);
  
  if (!(pHT->pNextTable = (int *)realloc(pHT->pNextTable, iNewSize) ) )
  {
    JM_ERR_NO_MEMORY(JM_ERROR);
  }
  memset(pHT->pNextTable, -1, iNewSize);
  
  if (!(pHT->pHashValue = (int *)realloc(pHT->pHashValue, iNewSize) ) )
  {
    JM_ERR_NO_MEMORY(JM_ERROR);
  }
  
  for (i=0; i<pHT->iCount; i++)
  {
    if (JM_HTAddKeyToHash(pHT, pHT->pHashValue[i], i) < 0)
    {
      JM_ERR_RETURN(JM_ERROR, "Rehash Error!");
    }
  }
  return JM_OK;
}
 
/*return 0:OK, -1:key conflict*/
static int JM_HTAddKeyToHash(JMHashTable *pHT, int iKeyHashValue, int iKeyPos)
{
  int i, hv, index, *pPosition, iDataArrayIndex, iDataSlotIndex;
  void *pCmp, *pData;
  
  iDataArrayIndex = iKeyPos / pHT->iDataSlotSize;
  iDataSlotIndex = iKeyPos % pHT->iDataSlotSize;
  pData = (char *)pHT->pDataArray[iDataArrayIndex] + pHT->iItemSize * iDataSlotIndex;
  
  hv = (unsigned)iKeyHashValue % (unsigned)pHT->iCapacity;
  pPosition = pHT->pHashTable + hv;
  index = *pPosition;
  
  for (i = pHT->iCount; i>0 && index!=-1; i--)
  {
    iDataArrayIndex = index / pHT->iDataSlotSize;
    iDataSlotIndex = index % pHT->iDataSlotSize;
    pCmp = (char *)pHT->pDataArray[iDataArrayIndex] + pHT->iItemSize * iDataSlotIndex;
    if (JM_HTCompare(pHT, pCmp, pData) == 0)
    {
      JM_ERR_RETURN(JM_ERROR, "Key conflict!");
    }
    pPosition = pHT->pNextTable + index;
    index = *pPosition;
  }
  if (i < 0 || i == 0 && pHT->iCount != 0)
  {
    JM_ERR_RETURN(JM_ERROR, "Next table data error!");
  }
  if (pPosition)
  {
    *pPosition = iKeyPos;
  }
  return JM_OK;
}
 
void JMHTFree(JMHashTable **ppHT)
{
  int i;
  JMHashTable *pHT;
 
  if (!ppHT || !*ppHT)
  {
    JM_ERR_RETURN( , "Invalid param!");
  }
 
  pHT = *ppHT;
  for (i=pHT->iDataArrayCount-1; i>=0; i--)
  {
    free( (void *)pHT->pDataArray[i]);
  }
  free(pHT->pDataArray);
  free(pHT->pHashTable);
  free(pHT->pNextTable);
  free(pHT->pHashValue);
 
  free(pHT);
  *ppHT = NULL;
}
 
/*return 0:OK, -1:key conflict/error*/
int JMHTAddEx(JMHashTable *pHT, void *pData)
{
  int iKeyHashValue, iDataArrayIndex, iDataSlotIndex;
  
  if (!pHT || !pData)
  {
    JM_ERR_RETURN(JM_ERROR, "Invalid param!");
  }
 
  if (pHT->iCount == pHT->iCapacity)
  {
    if (JM_HTExtendData(pHT) == JM_ERROR)
    {
      return JM_ERROR;
    }
  }
 
  iKeyHashValue = JM_HTCalKeyValue(pHT, pData);
  pHT->pHashValue[pHT->iCount] = iKeyHashValue;
  iDataArrayIndex = pHT->iCount / pHT->iDataSlotSize;
  iDataSlotIndex = pHT->iCount % pHT->iDataSlotSize;
  memcpy( (char *)pHT->pDataArray[iDataArrayIndex] + pHT->iItemSize * iDataSlotIndex, pData, pHT->iItemSize);
 
  if (JM_HTAddKeyToHash(pHT, iKeyHashValue, pHT->iCount) == JM_ERROR)
  {
    return JM_ERROR;
  }
  pHT->iCount++;
  return JM_OK;
}
 
/*return:key hash value*/
static int JM_HTCalKeyValue(JMHashTable *pHT, void *pData)
{
  if (pHT->pHashFunc)
  {
    return (*pHT->pHashFunc)(pData);
  }
  if (pHT->iKeySize > 0)
    return fnv_32_buf(pData, pHT->iKeySize, FNV1_32_INIT);
  else
    return fnv_32_str(*(char **)pData, FNV1_32_INIT);
}
 
/*return ==0:pData1==pData2, <0:pData1<pData2, >0:pData1>pData2*/
static int JM_HTCompare(JMHashTable *pHT, void *pData1, void *pData2)
{
  if (pHT->pCompareFunc)
  {
    return (*pHT->pCompareFunc)(pData1, pData2);
  }
  if (pHT->iKeySize > 0)
    return memcmp(pData1, pData2, pHT->iKeySize);
  else
    return strcmp(*(char **)pData1, *(char **)pData2);
}
 
static void JM_HTSearch(JMHashTable *pHT, void *pData, void **ppReturn, int **ppIndex)
{
  int i, *pPosition, iKeyHashValue, index, iDataArrayIndex, iDataSlotIndex;
  void *pCmp;
 
  *ppReturn = NULL;
  *ppIndex = NULL;
  iKeyHashValue = JM_HTCalKeyValue(pHT, pData);
 
  /*search*/
  pPosition = pHT->pHashTable + (unsigned)iKeyHashValue % (unsigned)pHT->iCapacity;
  index = *pPosition;
  
  for (i = pHT->iCount; i>0 && index != -1; i--)
  {
    iDataArrayIndex = index / pHT->iDataSlotSize;
    iDataSlotIndex = index % pHT->iDataSlotSize;
    pCmp = (char *)pHT->pDataArray[iDataArrayIndex] + pHT->iItemSize * iDataSlotIndex;
    if (JM_HTCompare(pHT, pCmp, pData) == 0)
    {
      *ppReturn = pCmp;
      *ppIndex = pPosition;
      return;
    }
    pPosition = pHT->pNextTable + index;
    index = *pPosition;
  }
}
 
/*return >0:OK, NULL:not found/error*/
void *JMHTGetEx(JMHashTable *pHT, void *pData)
{
  int *pIndex;
  void *pReturn;
  
  if (!pData || !pHT)
  {
    JM_ERR_RETURN(NULL, "Invalid param!");
  }
  
  JM_HTSearch(pHT, pData, &pReturn, &pIndex);
  if (!pReturn || !pIndex)
  {
    JM_ERR_RETURN(NULL, "Not Found!");
  }
  return pReturn;
}
 
/*return 0:OK, -1:not found/error*/
int JMHTDeleteEx(JMHashTable *pHT, void *pData)
{
  /*int *pIndex;
  void *pReturn;
  
  if (!pData || !pHT)
  {
    JM_ERR_RETURN(JM_ERROR, "Invalid param!");
  }
  
  JM_HTSearch(pHT, pData, &pReturn, &pIndex);
  if (!pReturn || !pIndex)
  {
    JM_ERR_RETURN(JM_ERROR, "Not Found!");
  }
  
  pHT->pHashValue[*pIndex] = -1;
  *pIndex = pHT->pNextTable[*pIndex];*/
  return JM_OK;
}
 
void JM_HTDebug(JMHashTable *pHT)
{
  int i;
  FILE *fp = fopen("JMHashTable.dump", "w+");
  
  if (!fp)return;
  fprintf(fp, "itemsize=%d, keysize=%d, dataarraycount=%d\r\n"
    "dataarraysize=%d, dataslotsize=%d, count=%d, capacity=%d :\r\n"
    "%10s\t%10s\t%s\r\n"
    ,pHT->iItemSize, pHT->iKeySize, pHT->iDataArrayCount
    ,pHT->iDataArraySize, pHT->iDataSlotSize, pHT->iCount, pHT->iCapacity
    ,"HashTable", "NextTable", "HashValue");
    
  for (i=0; i<pHT->iCapacity; i++)
  {
    fprintf(fp, "%10d\t%10d\t%u\r\n", pHT->pHashTable[i], pHT->pNextTable[i], pHT->pHashValue[i]);
  }
  fclose(fp);
}

--END