#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
/*65536 : KEY POINT, NEVER CHANGE VALUE, VERY IMFORTANT INFORMATION*/
#define MAX_HASHTABLE_SIZE 65536
#if(1)
/*
* HASH TABLE FUNCTION DEFINITION BEGIN
*/
struct entry_s {
char *key;
char *value;
struct entry_s *next;
};
typedef struct entry_s entry_t;
struct hashtable_s {
int size;
struct entry_s **table;
};
typedef struct hashtable_s hashtable_t;
static hashtable_t *ht_create( int size );
static int ht_hash( hashtable_t *hashtable, char *key );
static entry_t *ht_newpair( char *key, char *value );
static void ht_set( hashtable_t *hashtable, char *key, char *value );
static char *ht_get( hashtable_t *hashtable, char *key );
/*
* HASH TABLE FUNCTION DEFINITION END
*/
#endif
#if(1)
/*TEST, CODE RELATED WITH THIS HASH PROGRAM*/
/*TEST, CODE RELATED WITH THIS HASH PROGRAM*/
size_t sizeof_malloc( void* p )
{
return _msize( p );
}
#endif
int main( int argc, char **argv )
{
hashtable_t *hashtable = ht_create( MAX_HASHTABLE_SIZE );
char tmp_key [10+1];
char tmp_data[10+1];
int ii,kk,jj,ff;
for(kk=0; kk<4000; kk++)
{
memset(tmp_key,0x00,sizeof(tmp_key));
memset(tmp_data,0x00,sizeof(tmp_data));
sprintf(tmp_key, "%d", 1000000 + kk + 1);
sprintf(tmp_data, "%d", 3000000 + kk + 1);
ht_set( hashtable, tmp_key, tmp_data);
}
for(kk=0; kk<4000; kk++)
{
memset(tmp_key,0x00,sizeof(tmp_key));
sprintf(tmp_key, "%d", 1000000 + kk + 1);
if(ht_get( hashtable, tmp_key ) != NULL)
{
printf( "NO[%.5d],KEY(%s),DATA(%s) SUCC\n", kk + 1, tmp_key, ht_get( hashtable, tmp_key ) );
}
else
{
printf( "NO[%.5d],KEY(%s),DATA(%s) FAIL\n", kk + 1, tmp_key, ht_get( hashtable, tmp_key ) );
}
}
return 0;
}
int main_tmp( int argc, char **argv )
{
hashtable_t *hashtable = ht_create( MAX_HASHTABLE_SIZE );
char *hash_size = malloc(50000); /*TEST, CODE RELATED WITH THIS HASH PROGRAM*/
char tmp_key [10+1];
char tmp_data[10+1];
int ii,kk,jj,ff;
for(kk=0; kk<4000; kk++)
{
memset(tmp_key,0x00,sizeof(tmp_key));
memset(tmp_data,0x00,sizeof(tmp_data));
sprintf(tmp_key, "%d", 1000000 + kk + 1);
sprintf(tmp_data, "%d", 3000000 + kk + 1);
ht_set( hashtable, tmp_key, tmp_data);
printf( "sizeof_malloc(%d)\n", sizeof_malloc( hashtable ) ); /*TEST, CODE RELATED WITH THIS HASH PROGRAM*/
printf( "sizeof_malloc(%d)\n", sizeof_malloc( hash_size ) ); /*TEST, CODE RELATED WITH THIS HASH PROGRAM*/
}
for(kk=0; kk<4000; kk++)
{
memset(tmp_key,0x00,sizeof(tmp_key));
sprintf(tmp_key, "%d", 1000000 + kk + 1);
if(ht_get( hashtable, tmp_key ) != NULL)
{
printf( "NO[%.5d],KEY(%s),DATA(%s) SUCC\n", kk + 1, tmp_key, ht_get( hashtable, tmp_key ) );
}
else
{
printf( "NO[%.5d],KEY(%s),DATA(%s) FAIL\n", kk + 1, tmp_key, ht_get( hashtable, tmp_key ) );
}
}
free(hashtable);
free(hash_size); /*TEST, CODE RELATED WITH THIS HASH PROGRAM*/
return 0;
}
#if(1)
/*
* HASH TABLE FUNCTION BEGIN
*/
/* Create a new hashtable. */
hashtable_t *ht_create( int size )
{
hashtable_t *hashtable = NULL;
int i;
if( size < 1 ) return NULL;
/* Allocate the table itself. */
if( ( hashtable = malloc( sizeof( hashtable_t ) ) ) == NULL ) {
return NULL;
}
/* Allocate pointers to the head nodes. */
if( ( hashtable->table = malloc( sizeof( entry_t * ) * size ) ) == NULL ) {
return NULL;
}
for( i = 0; i < size; i++ ) {
hashtable->table[i] = NULL;
}
hashtable->size = size;
return hashtable;
}
/* Hash a string for a particular hash table. */
int ht_hash( hashtable_t *hashtable, char *key )
{
unsigned long int hashval;
int i = 0;
/* Convert our string to an integer */
while( hashval < ULONG_MAX && i < strlen( key ) ) {
hashval = hashval << 8;
hashval += key[ i ];
i++;
}
return hashval % hashtable->size;
}
/* Create a key-value pair. */
entry_t *ht_newpair( char *key, char *value )
{
entry_t *newpair;
if( ( newpair = malloc( sizeof( entry_t ) ) ) == NULL ) {
return NULL;
}
if( ( newpair->key = strdup( key ) ) == NULL ) {
return NULL;
}
if( ( newpair->value = strdup( value ) ) == NULL ) {
return NULL;
}
newpair->next = NULL;
return newpair;
}
/* Insert a key-value pair into a hash table. */
void ht_set( hashtable_t *hashtable, char *key, char *value )
{
int bin = 0;
entry_t *newpair = NULL;
entry_t *next = NULL;
entry_t *last = NULL;
bin = ht_hash( hashtable, key );
next = hashtable->table[ bin ];
while( next != NULL && next->key != NULL && strcmp( key, next->key ) > 0 ) {
last = next;
next = next->next;
}
/* There's already a pair. Let's replace that string. */
if( next != NULL && next->key != NULL && strcmp( key, next->key ) == 0 ) {
free( next->value );
next->value = strdup( value );
/* Nope, could't find it. Time to grow a pair. */
}
else {
newpair = ht_newpair( key, value );
/* We're at the start of the linked list in this bin. */
if( next == hashtable->table[ bin ] ) {
newpair->next = next;
hashtable->table[ bin ] = newpair;
/* We're at the end of the linked list in this bin. */
} else if ( next == NULL ) {
last->next = newpair;
/* We're in the middle of the list. */
} else {
newpair->next = next;
last->next = newpair;
}
}
}
/* Retrieve a key-value pair from a hash table. */
char *ht_get( hashtable_t *hashtable, char *key )
{
int bin = 0;
entry_t *pair;
bin = ht_hash( hashtable, key );
/* Step through the bin, looking for our value. */
pair = hashtable->table[ bin ];
while( pair != NULL && pair->key != NULL && strcmp( key, pair->key ) > 0 ) {
pair = pair->next;
}
/* Did we actually find anything? */
if( pair == NULL || pair->key == NULL || strcmp( key, pair->key ) != 0 ) {
return NULL;
} else {
return pair->value;
}
}
/*
* HASH TABLE FUNCTION END
*/
#endif
/*결과
NO[03938],KEY(1003938),DATA(3003938) SUCC
NO[03939],KEY(1003939),DATA(3003939) SUCC
NO[03940],KEY(1003940),DATA(3003940) SUCC
NO[03941],KEY(1003941),DATA(3003941) SUCC
NO[03942],KEY(1003942),DATA(3003942) SUCC
NO[03943],KEY(1003943),DATA(3003943) SUCC
NO[03944],KEY(1003944),DATA(3003944) SUCC
NO[03945],KEY(1003945),DATA(3003945) SUCC
NO[03946],KEY(1003946),DATA(3003946) SUCC
NO[03947],KEY(1003947),DATA(3003947) SUCC
NO[03948],KEY(1003948),DATA(3003948) SUCC
NO[03949],KEY(1003949),DATA(3003949) SUCC
NO[03950],KEY(1003950),DATA(3003950) SUCC
NO[03951],KEY(1003951),DATA(3003951) SUCC
NO[03952],KEY(1003952),DATA(3003952) SUCC
NO[03953],KEY(1003953),DATA(3003953) SUCC
NO[03954],KEY(1003954),DATA(3003954) SUCC
NO[03955],KEY(1003955),DATA(3003955) SUCC
NO[03956],KEY(1003956),DATA(3003956) SUCC
NO[03957],KEY(1003957),DATA(3003957) SUCC
NO[03958],KEY(1003958),DATA(3003958) SUCC
NO[03959],KEY(1003959),DATA(3003959) SUCC
NO[03960],KEY(1003960),DATA(3003960) SUCC
NO[03961],KEY(1003961),DATA(3003961) SUCC
NO[03962],KEY(1003962),DATA(3003962) SUCC
NO[03963],KEY(1003963),DATA(3003963) SUCC
NO[03964],KEY(1003964),DATA(3003964) SUCC
NO[03965],KEY(1003965),DATA(3003965) SUCC
NO[03966],KEY(1003966),DATA(3003966) SUCC
NO[03967],KEY(1003967),DATA(3003967) SUCC
NO[03968],KEY(1003968),DATA(3003968) SUCC
NO[03969],KEY(1003969),DATA(3003969) SUCC
NO[03970],KEY(1003970),DATA(3003970) SUCC
NO[03971],KEY(1003971),DATA(3003971) SUCC
NO[03972],KEY(1003972),DATA(3003972) SUCC
NO[03973],KEY(1003973),DATA(3003973) SUCC
NO[03974],KEY(1003974),DATA(3003974) SUCC
NO[03975],KEY(1003975),DATA(3003975) SUCC
NO[03976],KEY(1003976),DATA(3003976) SUCC
NO[03977],KEY(1003977),DATA(3003977) SUCC
NO[03978],KEY(1003978),DATA(3003978) SUCC
NO[03979],KEY(1003979),DATA(3003979) SUCC
NO[03980],KEY(1003980),DATA(3003980) SUCC
NO[03981],KEY(1003981),DATA(3003981) SUCC
NO[03982],KEY(1003982),DATA(3003982) SUCC
NO[03983],KEY(1003983),DATA(3003983) SUCC
NO[03984],KEY(1003984),DATA(3003984) SUCC
NO[03985],KEY(1003985),DATA(3003985) SUCC
NO[03986],KEY(1003986),DATA(3003986) SUCC
NO[03987],KEY(1003987),DATA(3003987) SUCC
NO[03988],KEY(1003988),DATA(3003988) SUCC
NO[03989],KEY(1003989),DATA(3003989) SUCC
NO[03990],KEY(1003990),DATA(3003990) SUCC
NO[03991],KEY(1003991),DATA(3003991) SUCC
NO[03992],KEY(1003992),DATA(3003992) SUCC
NO[03993],KEY(1003993),DATA(3003993) SUCC
NO[03994],KEY(1003994),DATA(3003994) SUCC
NO[03995],KEY(1003995),DATA(3003995) SUCC
NO[03996],KEY(1003996),DATA(3003996) SUCC
NO[03997],KEY(1003997),DATA(3003997) SUCC
NO[03998],KEY(1003998),DATA(3003998) SUCC
NO[03999],KEY(1003999),DATA(3003999) SUCC
NO[04000],KEY(1004000),DATA(3004000) SUCC
*/
