3

思うように解決できないのかもしれませんが、よくわからないので質問させてください...

ユーザーが必要な数のアイテムで初期化できるように、動的配列を使用して単純な Queue を実装しました。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、ライブラリにすべてのメモリ割り当て/解放を処理させることができますか?

4

3 に答える 3

2

あなたの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;
}
于 2010-04-18T09:16:06.620 に答える
2

何を保存するかについての考えを変えたいと思います。ユーザーは、割り当てたメモリへのポインタを提供するため、割り当てを解除することを期待する必要があります。値を memcpy したり解放したりする必要はありません。ポインターを追跡するだけで済みます。キューにプッシュすると所有権がキューに転送され、キューからポップすると所有権がユーザーに転送されます。したがって、「val」ポインターをコピーするだけです。

また、終了時にキュー ストレージをクリーンアップするには、おそらくqueueDestroy(Queue* q)関数が必要です。

編集：

  • QueueItem は必要なく、QueueValue の配列を格納できることに注意してください。
  • また、メモリ管理はライブラリの仕事であると明言していることに気づきましたが、それは問題に遭遇したときです（あなたが遭遇したようなものです）。ライブラリは、独自のメモリ管理 (キュー) を処理する必要があります。ただし、アイテムの割り当てと解放はユーザーの仕事でなければなりません。
  • もう 1 つのオプションは、値を返す queueFront(Queue *q) を提供することですが、その値は queuePop(Queue *q) によって解放されます。私はあなたの現在のアプローチを好みます:)
  • ユーザーがキューの最大サイズを定義する必要があるのは、ちょっと制限的です。これをジェネリック++、モジュラー++にしたい場合は、事前定義された定数を使用し、いっぱいになっている場合は queuePush() で拡張する必要があります。別の方法として、連結リストの実装を使用することもできます (ただし、連続したメモリは一般的にはるかに高速です)。
于 2010-04-18T02:18:15.913 に答える
1

他の人は (正しく) あなたの設計の厳しい制限を指摘していますが、これはあなたが持っているものを修正します。呼び出し元は、オブジェクトがプッシュおよびポップされるサイズを知っていると想定しています。

理論的には、これらの変更のうち絶対に不可欠なものは 2 つだけですが、他の変更は (プログラマーのエラーによる) クラッシュの可能性を ~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;
}

編集：

私がそのまま残したかもしれないと指摘され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。私は気が変わって、完全に元に戻したと思いましたが、SOにはバージョン管理がありません:)

于 2010-04-18T04:04:08.233 に答える