Проблема с динамическим массивом Структура данных очереди с пустым указателем - PullRequest
Новая
       40

Проблема с динамическим массивом Структура данных очереди с пустым указателем

3 голосов
/ 18 апреля 2010

Может быть, нет способа решить это так, как мне бы хотелось, но я не знаю всего, поэтому лучше спросить ...

Я реализовал простую очередь с динамическим массивом, чтобы пользователь мог инициализировать с любым количеством элементов, которые он хочет. Я также пытаюсь использовать указатель void, чтобы разрешить любой тип данных, но это проблема.

Вот мой код: 

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

Проблема заключается в функции queuePop. Когда я называю это, я теряю ценность, потому что освобождаю это сразу. Я не могу решить эту дилемму. Я хочу, чтобы моя библиотека была универсальной и модульной. Пользователь не должен заботиться о выделении и освобождении памяти, это работа библиотеки.

Как пользователь все еще может получить значение из queuePop и позволить библиотеке обрабатывать все выделения / освобождения памяти?

Ответы [ 3 ]

2 голосов
/ 18 апреля 2010

Ваша функция queuePop() должна работать так же, как queuePush() - взять размер местоположения и memcpy() к нему. 

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;
}
2 голосов
/ 18 апреля 2010

Я думаю, что вы хотите изменить свое представление о том, что хранить. Пользователь дает вам указатель на некоторую память, которую он выделил, поэтому он должен ожидать, чтобы освободить ее. Вам не нужно memcpy или освобождать значение, вам просто нужно следить за указателем. Нажатие на очередь должно передать владение в очередь, а извлечение из очереди должно вернуть владение обратно пользователю. Поэтому все, что вам нужно сделать, это скопировать указатель 'val'.

Кроме того, чтобы очистить хранилище очереди, когда вы закончите, вы, вероятно, захотите функцию queueDestroy(Queue* q).

Edit:

  • Обратите внимание, вам не нужен QueueItem, и вы можете хранить массив QueueValues.
  • Кроме того, я понимаю, что вы прямо сказали, что управление памятью было задачей библиотеки, но именно тогда вы столкнулись с проблемами (например, с той, с которой вы столкнулись). Библиотека должна позаботиться о собственном управлении памятью (очереди). Но выделение и удаление элементов должно быть задачей пользователя.
  • Другим вариантом является предоставление queueFront (Queue * q), который передает значение назад, но затем освобождается queuePop (Queue * q). Я предпочитаю ваш текущий подход, хотя:)
  • Требование пользователя определить максимальный размер очереди является своего рода ограничением. Если вы хотите, чтобы это был универсальный ++, модульный ++, то вам следует использовать предопределенную константу, а затем увеличить на queuePush (), если она заполнена. В качестве альтернативы вы можете использовать реализацию связанного списка (но непрерывная память обычно намного быстрее).
1 голос
/ 18 апреля 2010

Другие (правильно) указали на серьезные ограничения вашего дизайна, но это исправит то, что у вас есть. Предполагается, что вызывающая сторона знает, какого размера объект выталкивается и выталкивается.

Теоретически, только два из этих изменений абсолютно необходимы, но другие служат для снижения вероятности сбоя (из-за ошибки программиста) с ~ 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:

Было отмечено, что я мог оставить queuePop как 

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

В какой-то момент я написал это так, что если бы вызывающий передавал NULL в item_size, queuePop сделал бы malloc() и передал бы указатель вызывающему через **value. Я передумал и думал, что полностью откатился, но ТАК не имеет контроля версий:)

...