この記事では、Linuxカーネルの二重リンクリストの実装の使用について説明します。
Linuxカーネルの二重リンクリストは、 include /linux/list.hファイルに実装されています 。 list.h [1]の適合バージョンを使用します。これは、ユーザースペースの使用において元のものとは異なります。 たとえば、list.hに基づく任意のデータ型の先着順で要素にアクセスできるデータ構造であるキューを作成します。
これを行うには、キュー構造とキュー要素構造を作成します。
ファイルfifo.h：
#ifndef FIFO_H #define FIFO_H #include "list.h" struct fifo_item { void* data; // struct list_head list; // }; struct fifo { struct list_head headlist; // int length; // void (*item_free)(struct fifo_item*); // }; // int fifo_init(struct fifo * fifo, void (*item_free)(struct fifo_item*)); int fifo_exit(struct fifo * fifo); // int fifo_push(struct fifo * fifo, void* data); void* fifo_pop(struct fifo * fifo); // int fifo_for_each(struct fifo * fifo, void (*func)(struct fifo_item*)); #endif
キュー構造での作業の開始と完了は、それぞれfifo_initとfifo_exitによって行われます。 fifo_initの2番目の引数は、キューが完了したときに呼び出される関数です。 この関数は、バッファの処理が完了すると、バッファ要素が占有しているメモリを解放するために使用されます。
データの追加と取得は、それぞれfifo_pushとfifo_popを使用して行われます。 キュー内のデータは、fifo_pushの2番目の引数によって渡されるポインターによって格納され、fifo_popが返されます。
Fifo_for_eachは、キュー要素に対して同じタイプの操作を実行するために使用されます。 2番目の引数は、必要な操作を実装する関数です。 以下は可能な実装です。
Fifo.sファイル：
#include <stdlib.h> #include "fifo.h" int fifo_init(struct fifo *fifo, void (*item_free)(struct fifo_item*)) { INIT_LIST_HEAD(&(fifo->headlist)); fifo->length = 0; fifo->item_free = item_free; return 0; } int fifo_exit(struct fifo* fifo) { int res = 0; struct list_head *pos, *q; struct fifo_item* item; list_for_each_safe(pos, q, &(fifo->headlist)) { item = list_entry(pos, struct fifo_item, list); fifo->item_free(item); list_del(pos); free(item); } return res; } int fifo_push(struct fifo* fifo, void* data) { int res = -1; struct fifo_item* item; item = (struct fifo_item*)malloc(sizeof(struct fifo_item)); if(NULL != item) { item->data = data; list_add_tail(&(item->list), &(fifo->headlist)); fifo->length++; } return res; } void* fifo_pop(struct fifo* fifo) { void* res = NULL; struct fifo_item* item = list_entry(fifo->headlist.next, struct fifo_item, list); if(!list_empty(&(fifo->headlist))) { res = item->data; list_del(&(item->list)); free(item); fifo->length--; } return res; } int fifo_for_each(struct fifo* fifo, void (*func)(struct fifo_item*)) { int res = 0; struct fifo_item* item; list_for_each_entry(item, &(fifo->headlist), list) func(item); return res; }
リストヘッドはfifo_init：INIT_LIST_HEAD（＆（fifo-> headlist））で初期化され、長さはゼロに設定され、キューの完了時にメモリをクリアする方法はゼロに設定されます。
Fifo_exitは、リストのすべての要素を「保護」パススルーします。 キューの各要素について、データに割り当てられたメモリが解放され、その後要素がリストから削除され、占有していたメモリが解放されます。
fifo_pushでは、リストアイテムにメモリが割り当てられます。 この操作が成功すると、データへのポインターがキュー要素に保存され、要素がリストの末尾に追加されます。 キューの長さはそれぞれ増加します。
fifo_popでは、キューの最初の要素が最初に配置されます。 リストが空でなく、そのような要素が見つかった場合、データへのポインターが保存されます。 次に、アイテムがリストから削除され、使用していたメモリが解放されます。 キューの長さがそれぞれ短縮されます。
任意のデータ構造にこのキュー実装を使用するには、必要に応じて、バッファーの操作が終了したときに要素のデータメモリを解放するfreeメソッドと、バッファー要素の一般的な操作のメソッドを作成する必要があります。
この例では、mydata_freeが使用されます。これは、キュー要素のデータに割り当てられたメモリを解放するのに役立ち、mydata_print-画面にキューの要素を表示する関数です。 データはmydata構造体のfloat型です。
Main.cファイル：
#include <stdlib.h> #include "fifo.h" struct mydata { float value; }; void* mydata_create(void) { return (struct mydata *)malloc(sizeof(struct mydata)); } void mydata_free(struct fifo_item* item) { free(item->data); } void mydata_print(struct fifo_item* item) { struct mydata* data = (struct mydata*)item->data; printf("item: %f\n", data->value ); } int main() { int i; struct fifo myfifo; struct mydata* newdata; // FIFO fifo_init(&myfifo, mydata_free); for(i = 0; i < 10; i++) { // newdata = mydata_create(); if(!newdata) { return -1; } newdata->value = (float)i*0.1; // FIFO fifo_push(&myfifo, newdata); } // printf("FIFO:\n"); fifo_for_each(&myfifo, mydata_print); printf("\n"); do { newdata = fifo_pop(&myfifo); if(newdata) { printf("pop: %f\n", newdata->value ); } if(myfifo.length == 5) { printf("\nFIFO:\n"); fifo_for_each(&myfifo, mydata_print); printf("\n"); } } while(newdata); // FIFO fifo_exit(&myfifo); return 0; }
メイン関数には、バッファーを使用したテスト操作が含まれています。
仕事の結果：
$ ./testfifo FIFO: item: 0.000000 item: 0.100000 item: 0.200000 item: 0.300000 item: 0.400000 item: 0.500000 item: 0.600000 item: 0.700000 item: 0.800000 item: 0.900000 pop: 0.000000 pop: 0.100000 pop: 0.200000 pop: 0.300000 pop: 0.400000 FIFO: item: 0.500000 item: 0.600000 item: 0.700000 item: 0.800000 item: 0.900000 pop: 0.500000 pop: 0.600000 pop: 0.700000 pop: 0.800000 pop: 0.900000
使用したソース
1. Linuxカーネルリンクリストの説明 （ロシア語翻訳）