作っているM5StickLogger、セントラル側のM5StackはBluetoothで複数のペリフェラルから受信データを配列で保存してたが手間が増えてきたからスタックなどを実装することにした。
std::vectorなどを使うのが本道なんだろうが、簡単で頭の体操も兼ね自分で使いやすいように実装。
//
// スタック（LIFO）とキュー（FIFO)の実装
//
#include <stdio.h>
#include <malloc.h>
#include <string.h>
//
// スタック用の構造体
//
typedef struct _Stack {
// データ保持に使う
struct _Container {
void *pData;
_Container *next;
} *containers;
//
int sizeData; // 保持するデータサイズ
int countContainer; // データの数
//
// スタック初期化
void init(const int _sizeData) {
sizeData = _sizeData;
countContainer = 0;
containers = NULL;
}
//
// データ数を返す
int sizeof() { return countContainer; }
//
// データ保管
_Container *push(void *_pData) {
_Container *pTmp,*p;
pTmp = (_Container *)malloc(sizeof(_Container));
pTmp->pData = malloc(sizeData);
memcpy((void *)pTmp->pData,(void *)_pData,sizeData);
pTmp->next = NULL;
if (containers == NULL) {
containers = pTmp;
} else {
p = containers;
while (p->next != NULL) { p = p->next; }
p->next = pTmp;
}
countContainer++;
return (_Container *)pTmp;
}
//
// インデックスでデータ取得（データは削除しない）
void *get(void *_pData,const int idx) {
int k;
_Container *p;
if (containers == NULL) return NULL;
if (idx < 0 && countContainer <= idx) return NULL;
p = containers;
k = 0;
while (k != idx) { p = p->next; k++; }
memcpy(_pData,p->pData,sizeData);
return _pData;
}
//
// データ取得FIFO（取り出したデータは削除）
void *popFIFO(void *_pData) {
_Container *pCurt;
if (containers == NULL) return NULL;
pCurt = containers;
containers = pCurt->next;
memcpy(_pData,pCurt->pData,sizeData);
free(pCurt->pData);
free(pCurt);
countContainer--;
return _pData;
}
//
// データ取得LIFO(取り出したデータ削除）
void *popLIFO(void *_pData) {
_Container *pCurt,*pPrev = NULL;
if (containers == NULL) return NULL;
pCurt = containers;
while (pCurt->next != NULL) { pPrev = pCurt; pCurt = pCurt->next; }
if (pPrev == NULL) {
memcpy(_pData,containers->pData,sizeData);
free(containers->pData);
free(containers);
containers = NULL;
} else {
memcpy(_pData,pCurt->pData,sizeData);
free(pCurt->pData);
free(pPrev->next);
pPrev->next = NULL;
}
countContainer--;
return _pData;
}
} Stack;
//=====================================================
int main() {
int i,j,*k;
Stack *container = NULL;
// 構造体の初期化
// container = new Stack;
container = (Stack *)malloc(sizeof(Stack));
container->init(sizeof(int));
// データを積む
i = 123; container->push((void *)&i);
i = 323; container->push((void *)&i);
i = 10; container->push((void *)&i);
i = 25; container->push((void *)&i);
i = 999; container->push((void *)&i);
// 中ほど（４番目）のデータを得る
if ((k = (int *)container->get((void *)&j,3)) != NULL) {;
printf("get(3) %d(%d)\n",*k,j);
}
// データを追加
i = 32; container->push((void *)&i);
// 全データを取り出す
while ((k = (int *)container->popFIFO((void *)&j)) != NULL) {
printf("FIFO %d(%d)\n",j,container->sizeOf());
}
}
解説
データ構造
container構造体に実データ用（pData）と次のcontainer構造体（next）へのポインターを格納、新しいデータを格納毎に実データ用の領域およびcontainer構造体をmallocで確保しcontainersからnextで辿ったリストの最後に追加する。
init関数
実データを格納するため、格納したいデータサイズを引数で渡す。
整数や浮動小数でなくアプリに合わせた構造体を積むのでこの形にしました。
sizeof関数
保管データ数を返す
push関数
格納するデータをvoid*で渡す。
箱（container）領域をmallocで確保、実データ保管用にも領域をinit関数で与えたサイズ分確保する、memcpyで実データをコピー。
pushの引数_pDataのサイズは実データの場所を指すアドレスのサイズになるから注意。
あとはルートとなるcontainersから辿って最後に追加する。
get関数
配列と同じように添字を与えてデータ取得する、０始まり。
popXX関数同様に取り出したデータの保管先（コピー先）を引数で必要としている。popと形体を合わせた。
格納の実態は削除（free）しないからアドレスを返すだけでも良かった。（下記）
void *get(const int idx) {
int k;
_Container *p;
if (containers == NULL) return NULL;
if (idx < 0 && countContainer <= idx) return NULL;
p = containers;
k = 0;
while (k != idx) { p = p->next; k++; }
return p->pData;
}
popFIFO関数
先入れ先出し。（キュー）
最初に入れたのを最初に出す、なのでルート側（containers）から出すことになる
取り出すデータはfreeで削除する、ついては取り出したデータを保管用の入れ物を引数で渡す必要がある。
ルートを次のcontainerに置き換えてルートだった領域はfreeで削除する、削除前にデータをコピーする。
popLIFO関数
先入れ後出し。（スタック）
最後に入れたのを最初に出す、なのでnextで辿り行き着いた先を出すことになる。
頭（ルート）を挿げ替えるFIFOと違い、一番最後まで辿る処理、最後のデータ（ルート）とルート以外で処理が変わるのが注意。
最後のデータを取り出すときはcontainers変数をクリア（NULL代入）と余分な処理が必要。
使い方
ルートとなるStack構造体をnewなりmalloc等でメモリ確保し、格納したいデータサイズをinit関数の引数に渡す。
データの格納・取り出しはちょっと解り難いが格納したデータのアドレス渡しとなっている。
これは好きなデータを格納するためで整数（int）や実数（double）など決まったデータ型ならば値渡しにすればよい。
今時なら「NULL」ー＞「nullptr」だな、「typedef struct _Stack」の構造体をclass化するのもそんな難しくないだろう。
