Форум программистов [Powered by Invision Power Board]

Код


#include <stdio.h>
#include <stdlib.h>

#include <stddef.h>
#include <stdint.h>
/*-----------------------------------------------------------------------------*/
#define TABLE_SIZE 40
#define MAX_STR_SIZE 25
/*-----------------------------------------------------------------------------*/
uint_least32_t CRC32(unsigned char *buf, size_t len)
{
    uint_least32_t crc_table[256];
    uint_least32_t crc; int i, j;
 
    for (i = 0; i < 256; i++)
    {
        crc = i;
        for (j = 0; j < 8; j++)
            crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1;
 
        crc_table[i] = crc;
    };
 
    crc = 0xFFFFFFFFUL;
 
    while (len--) 
        crc = crc_table[(crc ^ *buf++) & 0xFF] ^ (crc >> 8);
 
    return crc ^ 0xFFFFFFFFUL;
}
/*-----------------------------------------------------------------------------*/
struct hash_list
{
    char data[MAX_STR_SIZE];
    struct hash_list *next;
};
/*-----------------------------------------------------------------------------*/
void list_store(struct hash_list *node, char *data)
{
    if (!node->next)
    {
        node->next = calloc(1, sizeof(struct hash_list));
        if (!node->next)
        {
            printf("Ошибка при распределении памяти #2\n");
            exit(1);
        }                
        strcpy(node->next->data,data);            
    }    
    else
    {
        list_store(node->next, data); 
    }

}
/*-----------------------------------------------------------------------------*/
void show(struct hash_list *list)
{
    unsigned i;
    for(i = 0; i <= TABLE_SIZE; ++i)
    {    
        if (list[i].data[0] == '\0') continue;
        show_node(&list[i],&i);
    }

}

void show_node(struct hash_list *node, unsigned *key)
{
    if (!node->next) printf("%u : %s; \n",*key,node->data);
    else
    {
        printf("%u : %s -> ",*key,node->data);            
        show_node(node->next, key);
    }
}
/*-----------------------------------------------------------------------------*/
void free_mem(struct hash_list *list)
{
    unsigned i;
    for(i = 0; i <= TABLE_SIZE; ++i)
    {    
        if (!list[i].next) continue;
        free_node(&list[i]);
    }
    free(list);
}

void free_node(struct hash_list *node)
{        
    if (!node->next->next) free(node->next);
    else
    {
        free_node(node->next);
        free(node->next);
    }
}
/*-----------------------------------------------------------------------------*/

int main(void)
{
    char file_name[255];
    char buf[MAX_STR_SIZE];
    buf[0] = '\0';
    FILE *fp;
    unsigned collision = 0;    

    unsigned utmp;    

    struct hash_list *list = calloc(TABLE_SIZE, sizeof(struct hash_list));
    if(!list) 
    {
        printf("Ошибка при распределении памяти #1\n");
        exit(1);
    }

    //printf("Ведите имя файла\n");    
    //gets(file_name);        
    if((fp=fopen("/home/mor/expire/hash_string/CRL.words","r")) == NULL)
    {
        printf("Ошибка при открытии файла.\n");
        exit(1);
    }

    while (!feof(fp))
    {
        fscanf(fp,"%s",buf);        
        if(buf[0]=='\0') continue;        
        utmp = (CRC32(buf,strlen(buf))) % TABLE_SIZE;    
        if (list[utmp].data[0] != '\0')
        {
            ++collision;
            list_store(&list[utmp],buf);
        }
        else
        {
            strcpy(list[utmp].data,buf);
        }

        buf[0] = '\0';
    }

    
    
    //printf("%u\n",CRC32(buf,0));
    
    show(list);
    printf("Количество коллизий: %u\n",collision);    


    fclose(fp);
    free_mem(list);


    return 0;
}

Код


if (list[i].data[0] == '\0')
    continue;

Код


main.c: In function ‘list_store’:
main.c:48: warning: incompatible implicit declaration of built-in function ‘strcpy’
main.c: At top level:
main.c:68: warning: conflicting types for ‘show_node’
main.c:63: note: previous implicit declaration of ‘show_node’ was here
main.c:89: warning: conflicting types for ‘free_node’
main.c:84: note: previous implicit declaration of ‘free_node’ was here
main.c: In function ‘main’:
main.c:129: warning: incompatible implicit declaration of built-in function ‘strlen’
main.c:137: warning: incompatible implicit declaration of built-in function ‘strcpy’

Цитата(gggl @ 18.11.2011, 16:50

)

struct hash_list *list =(struct hash_list*) calloc(TABLE_SIZE, sizeof(struct hash_list));
if(!list)     {
    printf("Ошибка при распределении памяти #1\n");
    exit(1);
}

Код


#define MALLOC_FAILURE_MSG \
        x_verbose(LOG_DEBUG, "Memory Allocation Failure in function %s at line %d of %s\n", func, lineno, file);
/*!
 * \brief A wrapper for malloc()
 *
 * x_malloc() is a wrapper for malloc() that will generate an log
 * message in the case that the allocation fails.
 *
 * The argument and return value are the same as malloc()
 */

#define x_malloc(len) \
        _x_malloc((len), __FILE__, __LINE__, __PRETTY_FUNCTION__)

inline void *attribute_malloc _x_malloc(size_t len, const char *file, int lineno, const char *func)
{
        void *p;

        if (!(p = malloc(len)))
                MALLOC_FAILURE_MSG;

        return p;
}

Код


if (!node->next)
    printf("%u : %s; \n",*key,node->data);
else
{
    printf("%u : %s -> ",*key,node->data);            
    show_node(node->next, key);
}

Код


if (!node->next)
{
    printf("%u : %s; \n",*key,node->data);
}
else
{
    printf("%u : %s -> ",*key,node->data);            
    show_node(node->next, key);
}

Цитата(gggl @ 19.11.2011, 16:53

)

Вы предлагаете мне написать свою inline функцию для выделения памяти?

Цитата(gggl @ 19.11.2011, 17:25

)

или фигурные скобки обязательны?

Код


if (node->next) {
    printf("%u : %s -> ",*key,node->data);            
    show_node(node->next, key);
} else
    printf("%u : %s; \n",*key,node->data);

Цитата(math64 @ 19.11.2011, 22:27

)

3. Результат malloc/calloc лучше привести к нужному типу - если придётся компилировать C++, будет Ok.