Problema con array dinamico struttura dati della coda con il puntatore nullo

Question

Forse non c'è modo per risolvere questo il modo in cui mi piacerebbe, ma non so tutto così ho meglio chiedo ...

Ho implementato una semplice coda con un array dinamico in modo che l'utente possa inizializzare con qualsiasi numero di oggetti che vuole. Sto anche cercando di utilizzare un puntatore void da consentire qualsiasi tipo di dati, ma questo è il problema.

Ecco il mio codice:

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 bugie problema sulla funzione queuePop. Quando lo chiamo io, perdo il valore perché mi libero subito. Io non riesco a risolvere questo dilemma. Voglio che la mia libreria per essere generico e modulare. L'utente non deve preoccuparsi di allocazione e la liberazione della memoria, che è compito della biblioteca.

Come può l'utente ancora ottenere il valore da queuePop e lasciare che la maniglia libreria di tutta la memoria Allocati / frees?

Answer 1

Altri hanno (giustamente) ha sottolineato le gravi limitazioni del vostro disegno, ma questo risolverà quello che hai. Si presuppone che il chiamante sa quello oggetto dimensione è sempre spinto e spuntato.

In teoria, solo due di questi cambiamenti sono assolutamente essenziali, ma gli altri servono a ridurre la probabilità di un incidente (a causa di errore programmatore) da ~ 100% al ~ 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;
}

Modifica

E 'stato fatto notare che avrei potuto avere queuePop sinistra come

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

ho avuto ad un certo punto scritto così se il chiamante ha approvato una NULL nel item_size, queuePop farebbe una malloc() e passare il puntatore torna al chiamante tramite **value. Ho cambiato la mia mente e il pensiero sono ritornato completamente, ma così non ha il controllo di versione:)

Answer 2

Le vostre esigenze di funzionalità queuePop() di lavorare allo stesso modo di queuePush() -. Prendere la dimensione della posizione e memcpy() ad esso

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

Credo che si desidera cambiare la vostra idea su cosa conservare. Un utente ti dà un puntatore a qualche ricordo che lei allocata, così lei deve aspettarsi di rilasciare esso. Non è necessario a memcpy o liberare il valore, non vi resta che tenere traccia del puntatore. Spingendo in coda dovrebbe trasferire la proprietà alla coda, e popping dalla coda dovrebbe trasferire di nuovo la proprietà per l'utente. Quindi tutto quello che dovete fare è copiare tutto il 'val' puntatore.

Inoltre, per ripulire l'archiviazione coda quando finito, si desidera probabilmente una funzione queueDestroy(Queue* q).

Modifica:

• Si noti, non è necessario QueueItem e si può memorizzare una serie di QueueValues.
• Inoltre, mi rendo conto che non esplicitamente detto che la gestione della memoria era il lavoro della biblioteca, ma in quel momento che si esegue in problemi (come quello che si sta eseguendo in). La biblioteca dovrebbe prendersi cura della propria gestione della memoria (la coda). Ma l'alloc & dealloc degli articoli dovrebbero essere il lavoro dell'utente.
• Un'altra opzione è quella di fornire un queueFront (coda * q) che passa indietro il valore, ma poi viene deallocato da queuePop (coda * q). Io preferisco il vostro approccio attuale però:)
• richiedere all'utente di definire una dimensione massima per la coda è un pò limitando. Se si desidera che questo sia generica ++, modulare ++ allora si dovrebbe utilizzare una costante predefinita, poi crescere su queuePush (), se è pieno. In alternativa è possibile utilizzare un'implementazione lista collegata (ma memoria contigua è in genere molto molto più veloce).