hash_table.cpp File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hash_table.h"

Include dependency graph for hash_table.cpp:

Go to the source code of this file.

Macros
#define	DEBUGF(x)   /*printf x;*/
#define	copyKey(dest, src)   memcpy(dest,src,layout.keySize())
#define	copyObj(dest, src)   memcpy(dest,src,layout.objectSize())
#define	copyEntry(dest, src)   memcpy(dest,src,layout.entrySize())
#define	e2i(entry)   (((entry)-table)/layout.entrySize())
#define	CDECL   extern "C"

Functions
void	CmiAbort (const char *msg)
CkHashCode	CkHashFunction_default (const void *keyData, size_t keyLen)
CkHashCode	CkHashFunction_string (const void *keyData, size_t keyLen)
int	CkHashCompare_default (const void *key1, const void *key2, size_t keyLen)
int	CkHashCompare_string (const void *key1, const void *key2, size_t keyLen)
static unsigned int	primeLargerThan (unsigned int x)
CDECL CkHashtable_c	CkCreateHashtable_int (int objBytes, int initSize)
CDECL CkHashtable_c	CkCreateHashtable_string (int objBytes, int initSize)
CDECL void	CkDeleteHashtable (CkHashtable_c h)
CDECL void *	CkHashtablePut (CkHashtable_c h, const void *atKey)
CDECL void *	CkHashtableGet (CkHashtable_c h, const void *fromKey)
CDECL void	CkHashtableRemove (CkHashtable_c h, const void *doomedKey)

Variables
static const unsigned int	doublingPrimes []

Macro Definition Documentation

#define CDECL   extern "C"

Definition at line 418 of file hash_table.cpp.

#define copyEntry	(		dest,
			src
	)		memcpy(dest,src,layout.entrySize())

Definition at line 128 of file hash_table.cpp.

#define copyKey	(		dest,
			src
	)		memcpy(dest,src,layout.keySize())

Definition at line 126 of file hash_table.cpp.

#define copyObj	(		dest,
			src
	)		memcpy(dest,src,layout.objectSize())

Definition at line 127 of file hash_table.cpp.

#define DEBUGF

(

x

)

/*printf x;*/

Definition at line 72 of file hash_table.cpp.

Referenced by CkHashCompare_default(), CkHashCompare_string(), CkHashFunction_default(), and CkHashFunction_string().

#define e2i

(

entry

)

(((entry)-table)/layout.entrySize())

Function Documentation

CDECL CkHashtable_c CkCreateHashtable_int	(	int	objBytes,
		int	initSize
	)

Definition at line 421 of file hash_table.cpp.

{
  int objStart=2*sizeof(int);
  CkHashtableLayout layout(sizeof(int),sizeof(int),
                           objStart,objBytes,objStart+objBytes);
  return (CkHashtable_c)new CkHashtable(layout,initSize,0.5,
                                        CkHashFunction_int,CkHashCompare_int);
}

CDECL CkHashtable_c CkCreateHashtable_string	(	int	objBytes,
		int	initSize
	)

Definition at line 430 of file hash_table.cpp.

References CkHashCompare_string(), and CkHashFunction_string().

{
  int objStart=2*sizeof(char *);
  CkHashtableLayout layout(sizeof(char *),sizeof(char *),
                           objStart,objBytes,objStart+objBytes);  
  return (CkHashtable_c)new CkHashtable(layout,initSize,0.5,
                                        CkHashFunction_string,CkHashCompare_string);
}

Here is the call graph for this function:

CDECL void CkDeleteHashtable

(

CkHashtable_c

h

)

Definition at line 438 of file hash_table.cpp.

{
        delete (CkHashtable *)h;
}

int CkHashCompare_default	(	const void *	key1,
		const void *	key2,
		size_t	keyLen
	)

Definition at line 102 of file hash_table.cpp.

References DEBUGF, and i.

{
        DEBUGF(("    comparing %d-byte keys--",keyLen))
        const char *a=(const char *)key1;
        const char *b=(const char *)key2;
        for (unsigned int i=0;i<keyLen;i++)
                if (a[i]!=b[i]) {DEBUGF(("different\n")) return 0;}
        DEBUGF(("equal\n"))
        return 1;
}

int CkHashCompare_string	(	const void *	key1,
		const void *	key2,
		size_t	keyLen
	)

Definition at line 112 of file hash_table.cpp.

References DEBUGF.

Referenced by CkCreateHashtable_string().

{
        const char *a=*(const char **)key1;
        const char *b=*(const char **)key2;
        DEBUGF(("    comparing '%s' and '%s'--",a,b))
        while (*a && *b)
                if (*a++!=*b++) {DEBUGF(("different\n")) return 0;}
        DEBUGF(("equal\n"))
        return 1;
}

Here is the caller graph for this function:

CkHashCode CkHashFunction_default	(	const void *	keyData,
		size_t	keyLen
	)

Definition at line 76 of file hash_table.cpp.

References d, DEBUGF, and i.

{
        const unsigned char *d=(const unsigned char *)keyData;
        CkHashCode ret=0;
        for (unsigned int i=0;i<keyLen;i++) {
                int shift1=((5*i)%16)+0;
                int shift2=((6*i)%16)+8;
                ret+=((0xa5^d[i])<<shift2)+(d[i]<<shift1);
        }
        DEBUGF(("    hashing %d-byte key to %08x\n",keyLen,ret))
        return ret;
}

CkHashCode CkHashFunction_string	(	const void *	keyData,
		size_t	keyLen
	)

Definition at line 88 of file hash_table.cpp.

References d, DEBUGF, and i.

Referenced by CkCreateHashtable_string().

{
        const char *d=*(const char **)keyData;
        CkHashCode ret=0;
        for (int i=0;d[i]!=0;i++) {
                int shift1=((5*i)%16)+0;
                int shift2=((6*i)%16)+8;
                ret+=((0xa5^d[i])<<shift2)+(d[i]<<shift1);
        }
        DEBUGF(("    hashed key '%s' to %08x\n",d,ret))
        return ret;
}

Here is the caller graph for this function:

CDECL void* CkHashtableGet	(	CkHashtable_c	h,
		const void *	fromKey
	)

Definition at line 449 of file hash_table.cpp.

{
        return ((CkHashtable *)h)->get(fromKey);
}

CDECL void* CkHashtablePut	(	CkHashtable_c	h,
		const void *	atKey
	)

Definition at line 443 of file hash_table.cpp.

{
        return ((CkHashtable *)h)->put(atKey);
}

CDECL void CkHashtableRemove	(	CkHashtable_c	h,
		const void *	doomedKey
	)

Definition at line 454 of file hash_table.cpp.

{
        ((CkHashtable *)h)->remove(doomedKey);
}

void CmiAbort

(

const char *

msg

)

Definition at line 68 of file hash_table.cpp.

                               {
  fprintf(stderr,"FATAL ERROR> %s\n",msg);
  abort();
}

static unsigned int primeLargerThan ( unsigned int  x )

static

Definition at line 409 of file hash_table.cpp.

References i.

{
        int i=0;
        while (doublingPrimes[i]<=x)
                i++;
        return doublingPrimes[i];
}

Variable Documentation

const unsigned int doublingPrimes[]

static

Definition at line 345 of file hash_table.cpp.