Problema com a estrutura de dados da fila de matriz dinâmica com ponteiro de vazio

Question

Talvez não haja como resolver isso do jeito que eu gostaria, mas não sei tudo, então é melhor eu perguntar ...

Eu implementei uma fila simples com uma matriz dinâmica para que o usuário possa inicializar com o número de itens que desejar. Eu também estou tentando usar um void Ponteiro para permitir qualquer tipo de dados, mas esse é o problema.

Aqui está o meu código:

typedef void * QueueValue;

typedef struct sQueueItem {
    QueueValue value;
} QueueItem;

typedef struct sQueue {
    QueueItem *items;

    int first;
    int last;
    int size;
    int count;
} Queue;

void queueInitialize(Queue **queue, size_t size) {
    *queue = xmalloc(sizeof(Queue));

    QueueItem *items = xmalloc(sizeof(QueueItem) * size);

    (*queue)->items = items;
    (*queue)->first = 0;
    (*queue)->last = 0;
    (*queue)->size = size;
    (*queue)->count = 0;
}

Bool queuePush(Queue * const queue, QueueValue value, size_t val_sz) {
    if(isNull(queue) || isFull(queue)) return FALSE;

    queue->items[queue->last].value = xmalloc(val_sz);
    memcpy(queue->items[queue->last].value, value, val_sz);

    queue->last = (queue->last+1) % queue->size;
    queue->count += 1;

    return TRUE;
}

Bool queuePop(Queue * const queue, QueueValue *value) {
    if(isEmpty(queue)) return FALSE;

    *value = queue->items[queue->first].value;

    free(queue->items[queue->first].value);

    queue->first = (queue->first+1) % queue->size;
    queue->count -= 1;

    return TRUE;
}

O problema está no queuePop função. Quando eu chamo, perco o valor porque o liberto imediatamente. Não consigo resolver esse dilema. Eu quero que minha biblioteca seja genérica e modular. O usuário não deve se preocupar em alocar e liberar memória, esse é o trabalho da biblioteca.

Como o usuário ainda pode obter o valor de queuePop E deixe a biblioteca lidar com todos os aloces/liberas de memória?

Answer 1

Outros (corretamente) apontaram as severas limitações do seu design, mas isso consertará o que você tem. Ele pressupõe que o chamador saiba qual o tamanho do objeto está sendo empurrado e estourado.

Teoricamente, apenas duas dessas mudanças são absolutamente essenciais, mas as outras servem para diminuir a probabilidade de um acidente (devido a erro de programador) de ~ 100% para ~ 80%.

typedef struct sQueueItem {
    QueueValue value;
    size_t     item_size;               // <-- you'll need this for the Pop
} QueueItem;

Bool queuePush(Queue * const queue, QueueValue value, size_t val_sz) {
    if(isNull(queue) || isFull(queue)) return FALSE;

    queue->items[queue->last].value = xmalloc(val_sz);
    memcpy(queue->items[queue->last].value, value, val_sz);
    queue->items[queue->last].item_size = val_sz;        // <-- save the size

    queue->last = (queue->last+1) % queue->size;
    queue->count += 1;

    return TRUE;
}

Bool queuePop(Queue * const queue, 
               QueueValue **value, // ESSENTIAL: now char **
               size_t item_size)   // so we can ensure enough room
{                                         
    if(isEmpty(queue)) return FALSE;

     // just for readability
    QueueItem *p = queue->items[queue->first];

    // watch for programmer error (maybe you should throw() something)
    assert(p->item_size == item_size);       

    // ESSENTIAL: copy the item to the caller's memory
    memcpy(*value, p->value, p->item_size); 

    free(queue->items[queue->first].value);

    queue->first = (queue->first+1) % queue->size;
    queue->count -= 1;

    return TRUE;
}

Editar:

Foi apontado que eu poderia ter deixado queuePop Como

Bool queuePop(Queue * const queue, 
               QueueValue *value,  // stet
               size_t item_size)   // so we can ensure enough room

and changed the `memcpy` to 

    // ESSENTIAL: copy the item to the caller's memory
    memcpy(value, p->value, p->item_size); 

Eu escrevi em algum momento, então se o chamador passou um nulo em item_size, queuePop faria um malloc() e passe o ponteiro de volta para o chamador via **value. Mudei de idéia e pensei que voltei completamente, mas não tenho controle de versão :)

Answer 2

Sua queuePop() A função precisa funcionar da mesma maneira que queuePush() - Pegue o tamanho da localização e memcpy() para isso.

Bool queuePop(Queue * const queue, QueueValue value, size_t val_sz)
{
    if (isEmpty(queue)) return FALSE;

    memcpy(value, queue->items[queue->first].value, val_sz);

    free(queue->items[queue->first].value);

    queue->first = (queue->first+1) % queue->size;
    queue->count -= 1;

    return TRUE;
}

Answer 3

Eu acho que você quer mudar sua ideia sobre o que armazenar. Um usuário fornece um ponteiro a alguma memória que ela alocou, para que ela espere desaloculá -lo. Você não precisa memcpy ou libertar o valor, só precisa acompanhar o ponteiro. Empurrar na fila deve transferir a propriedade para a fila, e a saída da fila deve transferir a propriedade de volta ao usuário. Então, tudo o que você precisa fazer é copiar em torno do ponteiro 'Val'.

Além disso, para limpar o armazenamento da fila quando terminar, você provavelmente deseja um queueDestroy(Queue* q) função.

Editar:

• Observe que você não precisa de QueueItem e pode armazenar uma variedade de filas.
• Além disso, percebo que você disse explicitamente que o gerenciamento de memória era o trabalho da biblioteca, mas é aí que você encontra problemas (como o que está encontrando). A biblioteca deve cuidar de seu próprio gerenciamento de memória (a fila). Mas o AlloC & Dealloc dos itens deve ser o trabalho do usuário.
• Outra opção é fornecer uma fila (fila *q) que passa de volta o valor, mas é desalocudado pelo QueuEpop (fila *Q). Eu prefiro sua abordagem atual :)
• Exigir que o usuário defina um tamanho máximo para a fila é meio restritivo. Se você deseja que isso seja genérico ++, modular ++, use uma constante predefinida e cresça no queuepush (), se estiver cheio. Como alternativa, você pode usar uma implementação da lista vinculada (mas a memória contígua geralmente é muito mais rápida).