Problème avec tableau dynamique structure de données de file d'attente avec pointeur vide

Question

Peut-être qu'il n'y a aucun moyen de résoudre ce la façon dont je l'aime mais je ne sais pas tout si je ferais mieux de demander ...

Je l'ai mis en place un File d'attente simple avec un tableau dynamique pour que l'utilisateur puisse s'initialiser avec le nombre d'éléments souhaité. J'essaie également d'utiliser un pointeur void pour autoriser tout type de données, mais c'est le problème.

Voici mon code:

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; 
} 

Le problème se trouve sur la fonction queuePop. Quand je l'appelle, je perds la valeur parce que je la libère tout de suite. Je n'arrive pas à résoudre ce dilemme. Je veux que ma bibliothèque soit générique et modulaire. L'utilisateur ne devrait pas se préoccuper de l'allocation et de la libération de la mémoire, c'est le travail de la bibliothèque.

Comment l'utilisateur peut-il toujours obtenir la valeur de queuePop et laisser la bibliothèque gérer toutes les allocations/libérations de la mémoire?

Answer 1

D'autres ont (correctement) souligné les limites sévères de votre conception, mais cela va corriger ce que vous avez. Il suppose que l'appelant sait quel objet taille est poussé et sauté. Théoriquement, seulement deux de ces changements sont absolument essentiels, mais les autres servent à réduire la probabilité d'un crash (en raison d'une erreur de programmation) de ~ 100% à ~ 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; 
} 

Edit:

Il a été fait remarquer que je aurais pu laisser queuePop comme

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); 

je l'avais à un moment donné par écrit si l'appelant a adopté une valeur NULL dans item_size, queuePop ferait un malloc() et passerait le pointeur à l'appelant via **value. J'ai changé mon esprit et pensais que je revins complètement, mais ont ne le fait pas de contrôle Version :)

Answer 2

Je pense que vous voulez changer votre idée sur ce qu'il faut stocker. Un utilisateur vous donne un pointeur sur un peu de mémoire qu'elle a allouée, alors elle devrait s'attendre à la libérer. Vous n'avez pas besoin de memcpy ou de libérer la valeur, vous avez juste besoin de garder une trace du pointeur. Pousser dans la file d'attente devrait transférer la propriété à la file d'attente, et sauter de la file d'attente devrait transférer la propriété à l'utilisateur. Donc tout ce que vous avez à faire est de copier autour du pointeur 'val'.

En outre, pour nettoyer le stockage de la file d'attente lorsque vous avez terminé, vous souhaitez probablement une fonction queueDestroy(Queue* q).

Edit:

• Avis, vous n'avez pas besoin QueueItem et vous pouvez stocker un tableau de QueueValues.
• En outre, je me rends compte que vous avez explicitement dit que la gestion de la mémoire était le travail de la bibliothèque, mais c'est quand vous rencontrez des problèmes (comme celui que vous rencontrez). La bibliothèque devrait prendre soin de sa propre gestion de la mémoire (la file d'attente). Mais l'allocation & dealloc des éléments devrait être le travail de l'utilisateur.
• Une autre option consiste à fournir un fichier queueFront (Queue * q) qui renvoie la valeur, puis il est désalloué par filePop (Queue * q). Je préfère cependant votre approche actuelle :)
• Demander à l'utilisateur de définir une taille maximale pour la file d'attente est un peu restrictif. Si vous voulez que ce soit générique ++, modulaire ++, vous devez utiliser une constante prédéfinie, puis développer sur filePush(), s'il est complet. Vous pouvez également utiliser une implémentation de liste liée (mais la mémoire contiguë est généralement beaucoup plus rapide).

Answer 3

Votre fonction queuePop() a besoin de travailler de la même manière que queuePush() - prendre la taille de l'emplacement et memcpy() à elle.

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; 
}