Я делаю упражнение на C, которое включает создание клиент-серверной программы с обменом сообщениями между клиентом и сервером.Текст упражнения содержит хэш-таблицу этого типа.
#define BITS_IN_int ( sizeof(int) * CHAR_BIT )
#define THREE_QUARTERS ((int) ((BITS_IN_int * 3) / 4))
#define ONE_EIGHTH ((int) (BITS_IN_int / 8))
#define HIGH_BITS ( ~((unsigned int)(~0) >> ONE_EIGHTH ))
/**
* A simple string hash.
*
* An adaptation of Peter Weinberger's (PJW) generic hashing
* algorithm based on Allen Holub's version. Accepts a pointer
* to a datum to be hashed and returns an unsigned integer.
* From: Keith Seymour's proxy library code
*
* @param[in] key -- the string to be hashed
*
* @returns the hash index
*/
static unsigned int
hash_pjw(void* key)
{
char *datum = (char *)key;
unsigned int hash_value, i;
if(!datum) return 0;
for (hash_value = 0; *datum; ++datum) {
hash_value = (hash_value << ONE_EIGHTH) + *datum;
if ((i = hash_value & HIGH_BITS) != 0)
hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;
}
return (hash_value);
}
static int string_compare(void* a, void* b)
{
return (strcmp( (char*)a, (char*)b ) == 0);
}
/**
* Create a new hash table.
*
* @param[in] nbuckets -- number of buckets to create
* @param[in] hash_function -- pointer to the hashing function to be used
* @param[in] hash_key_compare -- pointer to the hash key comparison function to be used
*
* @returns pointer to new hash table.
*/
icl_hash_t *
icl_hash_create( int nbuckets, unsigned int (*hash_function)(void*), int (*hash_key_compare)(void*, void*) )
{
icl_hash_t *ht;
int i;
ht = (icl_hash_t*) malloc(sizeof(icl_hash_t));
if(!ht) return NULL;
ht->nentries = 0;
ht->buckets = (icl_entry_t**)malloc(nbuckets * sizeof(icl_entry_t*));
if(!ht->buckets) return NULL;
ht->nbuckets = nbuckets;
for(i=0;i<ht->nbuckets;i++)
ht->buckets[i] = NULL;
ht->hash_function = hash_function ? hash_function : hash_pjw;
ht->hash_key_compare = hash_key_compare ? hash_key_compare : string_compare;
return ht;
}
/**
* Search for an entry in a hash table.
*
* @param ht -- the hash table to be searched
* @param key -- the key of the item to search for
*
* @returns pointer to the data corresponding to the key.
* If the key was not found, returns NULL.
*/
void *
icl_hash_find(icl_hash_t *ht, void* key)
{
icl_entry_t* curr;
unsigned int hash_val;
if(!ht || !key) return NULL;
hash_val = (* ht->hash_function)(key) % ht->nbuckets;
for (curr=ht->buckets[hash_val]; curr != NULL; curr=curr->next)
if ( ht->hash_key_compare(curr->key, key))
return(curr->data);
return NULL;
}
/**
* Insert an item into the hash table.
*
* @param ht -- the hash table
* @param key -- the key of the new item
* @param data -- pointer to the new item's data
*
* @returns pointer to the new item. Returns NULL on error.
*/
icl_entry_t *
icl_hash_insert(icl_hash_t *ht, void* key, void *data)
{
icl_entry_t *curr;
unsigned int hash_val;
if(!ht || !key) return NULL;
hash_val = (* ht->hash_function)(key) % ht->nbuckets;
for (curr=ht->buckets[hash_val]; curr != NULL; curr=curr->next)
if ( ht->hash_key_compare(curr->key, key))
return(NULL); /* key already exists */
/* if key was not found */
curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
if(!curr) return NULL;
curr->key = key;
curr->data = data;
curr->next = ht->buckets[hash_val]; /* add at start */
ht->buckets[hash_val] = curr;
ht->nentries++;
return curr;
}
/**
* Free one hash table entry located by key (key and data are freed using functions).
*
* @param ht -- the hash table to be freed
* @param key -- the key of the new item
* @param free_key -- pointer to function that frees the key
* @param free_data -- pointer to function that frees the data
*
* @returns 0 on success, -1 on failure.
*/
int icl_hash_delete(icl_hash_t *ht, void* key, void (*free_key)(void*), void (*free_data)(void*))
{
icl_entry_t *curr, *prev;
unsigned int hash_val;
if(!ht || !key) return -1;
hash_val = (* ht->hash_function)(key) % ht->nbuckets;
prev = NULL;
for (curr=ht->buckets[hash_val]; curr != NULL; ) {
if ( ht->hash_key_compare(curr->key, key)) {
if (prev == NULL) {
ht->buckets[hash_val] = curr->next;
} else {
prev->next = curr->next;
}
if (*free_key && curr->key) (*free_key)(curr->key);
if (*free_data && curr->data) (*free_data)(curr->data);
ht->nentries++;
free(curr);
return 0;
}
prev = curr;
curr = curr->next;
}
return -1;
}
/**
* Free hash table structures (key and data are freed using functions).
*
* @param ht -- the hash table to be freed
* @param free_key -- pointer to function that frees the key
* @param free_data -- pointer to function that frees the data
*
* @returns 0 on success, -1 on failure.
*/
int
icl_hash_destroy(icl_hash_t *ht, void (*free_key)(void*), void (*free_data)(void*))
{
icl_entry_t *bucket, *curr, *next;
int i;
if(!ht) return -1;
for (i=0; i<ht->nbuckets; i++) {
bucket = ht->buckets[i];
for (curr=bucket; curr!=NULL; ) {
next=curr->next;
if (*free_key && curr->key) (*free_key)(curr->key);
if (*free_data && curr->data) (*free_data)(curr->data);
free(curr);
curr=next;
}
}
if(ht->buckets) free(ht->buckets);
if(ht) free(ht);
return 0;
}
/**
* Dump the hash table's contents to the given file pointer.
*
* @param stream -- the file to which the hash table should be dumped
* @param ht -- the hash table to be dumped
*
* @returns 0 on success, -1 on failure.
*/
int
icl_hash_dump(FILE* stream, icl_hash_t* ht)
{
icl_entry_t *bucket, *curr;
int i;
if(!ht) return -1;
for(i=0; i<ht->nbuckets; i++) {
bucket = ht->buckets[i];
for(curr=bucket; curr!=NULL; ) {
if(curr->key)
fprintf(stream, "icl_hash_dump: %s: %p\n", (char *)curr->key, curr->data);
curr=curr->next;
}
}
return 0;
}
Программа выполняется правильно, но моя проблема возникает при использовании valgrind, когда я использую функцию icl_hash_find (), пытающуюся зарегистрировать клиента (строку) илипытаясь проверить, зарегистрирован ли клиент уже.
Клиент и сервер обмениваются сообщениями, отправляя структуру такого типа:
typedef struct {
op_t op;
char sender[MAX_NAME_LENGTH+1];
} message_hdr_t;
typedef struct {
char receiver[MAX_NAME_LENGTH+1];
unsigned int len;
} message_data_hdr_t;
typedef struct {
message_data_hdr_t hdr;
char *buf;
} message_data_t;
typedef struct {
message_hdr_t hdr;
message_data_t data;
} message_t;
Вот так я регистрирую клиентов или проверяю, зарегистрированы ли они уже..
char *client_nickname=malloc(sizeof(char));
/******/
client_nickname=realloc(clcan I ient_nickname,strlen(msg->hdr.sender)+1);
strcpy(client_nickname,msg->hdr.sender);
if ( icl_hash_find(hash, client_nickname) != NULL){
printf("%s already registered\n",client_nickname);
}else{
printf("ok %s\n",client_nickname);
icl_hash_insert(hash, client_nickname, (void*)client_nickname);
}
/*****/
и теперь вывод valgrind, который повторяется несколько раз:
==5535== Invalid read of size 1
==5535== at 0x4C33DC4: strcmp (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5535== by 0x109FB5: string_compare (icl_hash.c:58)
==5535== by 0x10A12C: icl_hash_find (icl_hash.c:116)
==5535== by 0x10A928: threadF (main.c:173)
==5535== by 0x4E436DA: start_thread (pthread_create.c:463)
==5535== by 0x517C88E: clone (clone.S:95)
==5535== Address 0x54535a1 is 1 bytes inside a block of size 5 free'd
==5535== at 0x4C31D2F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5535== by 0x10A759: threadF (main.c:131)
==5535== by 0x4E436DA: start_thread (pthread_create.c:463)
==5535== by 0x517C88E: clone (clone.S:95)
==5535== Block was alloc'd at
==5535== at 0x4C31D2F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5535== by 0x10A759: threadF (main.c:131)
==5535== by 0x4E436DA: start_thread (pthread_create.c:463)
==5535== by 0x517C88E: clone (clone.S:95)