Algumas perguntas sobre meu código modular usando void* como tipo de dados dinâmico em c

StackOverflow https://stackoverflow.com/questions/2395216

Pergunta

Alguns dias atrás eu postei essa questão E todos me sugeriram para usar void*, o que eu fiz. Eu acho que alguns deles também apontaram algumas coisas que eu precisaria cuidar, mas não tenho certeza do que exatamente eles eram. No entanto, estou tendo alguns problemas com isso ...

Não vou postar todo o meu código onde porque é bastante grande, em vez disso, postarei as coisas que acho importantes e espero que você seja suficiente para você me ajudar.

Minha estrutura de tabela de hash é assim:

typedef void * HashKey;
typedef void * HashValue;

typedef struct sHashItem {
    HashKey key;
    HashValue value;

    char status;
} HashItem;

typedef struct sHashTable {
    HashItem *items;

    int count;
    float load;
    int size;

    Bool (*compare)(HashKey, HashKey);
    unsigned (*hash)(void *);
} HashTable;

A assinatura da minha função de inserção é esta:

Bool hashInsert(HashTable * const table, HashKey key, HashValue value);

E em algum lugar dentro dessa função, quando encontro um balde livre na tabela de hash, faço isso:

table->items[index].key = key;
table->items[index].value = value;
table->items[index].status = USED;
table->load = ++table->count / (float)table->size;

Tudo isso apresenta alguns problemas:

1) Como você pode ver acima, estou simplesmente configurando cada par de tecla/valor do balde livre para o mesmo ponteiro passado que a chave/valor hashInsert Argumentos da função. Isso apresenta um problema como você já deve ter notado ... por exemplo, fazer algo assim:

char str[50];
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)5);
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)3);

E se a entrada for "keya" e depois "keyb", ambos terão "keyb" como as chaves dos baldes. O mesmo se aplica ao valor e não apenas à chave, pois eles são basicamente do mesmo tipo, porque eu quero ter meu código totalmente modular, para qualquer tipo de dados.

Como eu poderia resolver isso?

Meu primeiro é usar strdup(str) e passar isso para o hashInsert função. Isso resolveria o problema. E como isso foi tratado no código principal, eu poderia usar facilmente malloc() Também para qualquer outro tipo de dados que eu precise passar como o valor (a chave provavelmente sempre será uma string ou uma int).

Mas esta solução apresenta outro problema ...

2) Como devo libertar essa memória alocada? Claro, foi alocado pelo "programador principal" e não pelo "programador de módulos de tabela de hash de hash", então, o "programador principal" deve libertá -lo no código principal, certo? No entanto, isso não parece muito com código modular para mim.

Meu código também tem um hashDestroy função, para libertar toda a memória alocada. Mas como posso usar essa função para libertar tudo? Não posso apenas iterar sobre cada chave/valor e usar free() neles porque talvez alguns deles não tenham sido malloc'd por qualquer programador em primeiro lugar e não preciso libertá -los.

Como posso descobrir quais hashDestroy Deve libertar e quais não deveria?

3) Para terminar, acho que também posso lançar esse problema na mistura ... no ponto um, minha sugestão era usar strdup() ou malloc Para "corrigir" esse problema específico (ao apresentar outro), mas isso também não parece muito modular para mim. Essa alocação de memória deve ser feita no código do módulo da tabela de hash e não no código principal pelo "Programador Principal".

Como você sugere que eu resolva isso? Quero dizer, os tipos de dados podem ser qualquer coisa e enquanto o uso de strdup() Ajuda muito, funciona apenas para cordas. E se eu precisar alocar memória para alguma estrutura específica ou apenas um INT?

Desculpe pelo grande post, mas acho que essas perguntas estão todas relacionadas e preciso de ajuda para descobrir, já que meu conhecimento C não é tão extremo. Eu só aprendi recentemente sobre void* assim...

Foi útil?

Solução

WOW: Isso vai levar algumas respostas na íntegra. No entanto, uma das principais coisas que você precisará é o tamanho do que você está processando - é bom usar um ponteiro vazio, mas você precisa saber o tamanho do objeto cujo endereço está recebendo.

...] Todo mundo sugeriu que eu usasse o Void*, o que eu fiz. [...

Minha estrutura de tabela de hash é assim:

typedef void * HashKey;
typedef void * HashValue;

typedef struct sHashItem {
    HashKey key;
    HashValue value;
    char status;
} HashItem;

typedef struct sHashTable {
    HashItem *items;
    int count;
    float load;
    int size;

    Bool (*compare)(HashKey, HashKey);
    unsigned (*hash)(void *);
} HashTable;

É provável que você precise de um size_t key_sz; e a size_t val_sz; membro em HashItem. Seu ponteiro de função de hash precisará saber o tamanho da chave a ser hashed.

Estou em duas mentes sobre o que o hashkey deveria ser. Depende em parte de como você está usando essas coisas. Parece que você quer:

  • Dado esse valor -chave da minha escolha,
  • Armazene/retorne esses dados associados a eles.

Nesse caso, você provavelmente também precisa armazenar o número de hash em algum lugar no HashItem; Esse é o valor retornado pela sua função de hash - aparentemente um número inteiro não assinado. Não tenho certeza do que a assinatura no compare função (ponteiro da função) deve ser; Suspeito que seja necessário um par de valores de hashkey e tamanho, ou possivelmente um par de ponteiros de hashitem.

A assinatura da minha função de inserção é esta:

Bool hashInsert(HashTable * const table, HashKey key, HashValue value);

E em algum lugar dentro dessa função, quando encontro um balde livre na tabela de hash, faço isso:

table->items[index].key = key;
table->items[index].value = value;
table->items[index].status = USED;
table->load = ++table->count / (float)table->size;

Tudo isso apresenta alguns problemas:

1) Como você pode ver acima, estou simplesmente configurando cada par de teclas/valor do balde livre para o mesmo ponteiro passado que os argumentos da função de chave/valor. Isso apresenta um problema como você já deve ter notado ... por exemplo, fazer algo assim:

char str[50];
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)5);
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)3);

A chave para usar void * é passar endereços. O elenco deve ser desnecessário em C. Você também precisa passar o tamanho das coisas. Por isso:

Bool hashInsert(HashTable * const table, HashKey key, size_t key_sz,
                HashValue value, size_t val_sz);

char str[50];
scanf("%s%*c", str);
int value = 5;
hashInsert(t1, str, strlen(str)+1, &value, sizeof(value));

Internamente, você copiará os dados - não usando 'strdup ()', pois você não sabe que não há bytes interiores nul ' 0' nele.

E se a entrada for "keya" e depois "keyb", ambos terão "keyb" como as chaves dos baldes. O mesmo se aplica ao valor e não apenas à chave, pois eles são basicamente do mesmo tipo, porque eu quero ter meu código totalmente modular, para qualquer tipo de dados.

Como eu poderia resolver isso?

Você precisa definir quem é o que é e se (e como) o contêiner copia os dados. Em C ++, os contêineres fazem uma cópia de tudo o que estão armazenando.

Meu primeiro pensamento é usar o STRDUP (STR) e passar isso para a função Hashinssert. Isso resolveria o problema. E como isso foi tratado no código principal, eu poderia facilmente usar o MALLOC () para qualquer outro tipo de dados que eu precise passar como o valor (a chave provavelmente sempre será uma string ou uma int).

Você não pode usar 'strdup ()' porque, em geral, nem os valores nem as teclas são strings. Se eles são sempre strings, por que você está usando 'void *' em vez de 'char *'?

Você pode decidir copiar o valor e a chave - desde que conheça os tamanhos.

Mas esta solução apresenta outro problema ...

2) Como devo libertar essa memória alocada? Claro, foi alocado pelo "programador principal" e não pelo "programador de módulos de tabela de hash de hash", então, o "programador principal" deve libertá -lo no código principal, certo? No entanto, isso não parece muito com código modular para mim.

Meu código também possui uma função de hashestroy, para libertar toda a memória alocada. Mas como posso usar essa função para libertar tudo? Não posso apenas iterar sobre cada chave/valor e usar gratuitamente () neles, porque talvez alguns deles não tenham sido mallocos por nenhum programador em primeiro lugar e não preciso libertá -los.

Como posso descobrir quais devem ser libertados e quais deveriam?

Você não pode. Você precisa definir uma política e somente se essa política permitir que você faça a destruição, caso faça isso. Se você copiar tudo, você tem um tempo fácil. Se você não copia nada, você tem um tempo fácil diferente (sem dúvida mais fácil), mas seus consumidores têm um tempo infernal porque precisam de uma estrutura para acompanhar o que precisam lançar - talvez uma lista de hash ...

3) Para terminar, acho que também posso lançar esse problema na mistura ... no ponto um, minha sugestão era usar o strdup () ou o malloc para "corrigir" esse problema específico (enquanto apresentava outro), mas que também não Parece muito modular para mim. Essa alocação de memória deve ser feita no código do módulo da tabela de hash e não no código principal pelo "Programador Principal".

Sim ... essa é basicamente minha recomendação.

Como você sugere que eu resolva isso? Quero dizer, os tipos de dados podem ser qualquer coisa e, embora o uso de strdup () ajude muito, ele funciona apenas para strings. E se eu precisar alocar memória para alguma estrutura específica ou apenas um INT?

Observe que a cópia só faz cópias rasas. Se as estruturas que você estiver copiando contêm ponteiros, o código de duplicação copiará apenas o ponteiro e não o apontado para os dados.

Portanto, uma solução geral exigirá algum tipo de função de cópia. Pode ser necessário exigir que o usuário forneça uma função 'liberação' que libera a memória em um item. Pode ser necessário que o usuário forneça dados já alocados. Você precisa pensar em quem possui o que a função de pesquisa retorna - ainda está 'na tabela de hash ou foi removida. Olhe com força para o sistema STL C ++ - ele geralmente fala um excelente trabalho e modelando seus requisitos sobre o que ele exige pode fazer sentido. Mas lembre -se, o C ++ tem construtores e destruidores para ajudá -lo.

Outras dicas

Eu iria malloc todos os dados e permitiria que o cliente nas funções de hash registre um item_free() Função no horário da tabela de hash. Dessa forma, cabe ao "programador principal" como lidar com isso.

Hmmm, pelo que vejo no seu exemplo, o problema não é colisões de hashtable (embora você também pareça ter esse problema), é como gerenciar a memória dos itens armazenados na tabela. Eu acho que a maneira padrão de fazer esse tipo de coisa é forçar o usuário da estrutura de dados (a hashtable) a fazer o trabalho de alocar o espaço para todas as coisas que serão colocadas na tabela. A hashtable só deve ter que se preocupar com os ponteiros. Suponha que você faça uma alocação e copie na estrutura de dados: como o usuário saberia como negociar a memória quando o item for removido do Hastable?

Existem duas soluções gerais para lidar com colisões em uma hashtable:

  1. Use o próximo balde livre.
  2. Um balde armazena uma lista vinculada para que vários itens possam ser armazenados no mesmo balde.

Com qualquer um deles, a questão de quando libertar o que nunca surge, pois todos os tipos de dados são alocados pela tabela de hash ou pelo cliente da tabela de hash. Se você ainda está curioso, a resposta curta para esse dilema é usar Ponteiros inteligentes.

Para implementar uma tabela de hash, precisamos de um conjunto de baldes. E como vários elementos podem hash no mesmo balde, cada balde precisa de uma lista vinculada.

Faz

HashItem *items;

executar o segundo requisito acima?

Pela sua explicação, não fica claro se isso acontece.

Para um excelente exemplo, consulte a Seção 6.6 da K&R. link onde nome = hashkey e defn = hashValue.TEXTO DE ALT HTTP://www.goldfish.org/books/the%20c%20Programing%20Language%20-%20k&r/pic64.gif

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top