Быстрый доступ к элементу. Опции

[Jenya7]

Я получаю пакеты данных. Эти пакеты я должен хранить в RAM. Глубина хранения не определена но пока что это 512 пакетов.
То есть в RAM я создал массив 512 пакетов.
У каждого пакета есть два поля ID - ID1/ID2. Значения инденцификационных полей варьируются ID1=0-10000, ID2=0-255.
Мне приходит команда - добавь пакет 700/12, удали пакет 700/12, редактируй пакет 700/12. Команда приходит довольно часто - худший случай - каждую милисекунду поэтому время поиска элемента критично.
Проблема в быстром поиске пакета. Сделать хэш таблицу ID1-ID2 <=> индекс - громадная таблица получиться.
Сейчас к чему я пришел - самое оптимальное связанный список.
И тут я вспомнил работу с SQL базами данных - это ж просто праздник какой то. Добавляй, удаляй, редактируй записи сколько влезет и очень быстро.
В принципе это может быть non-SQL база данных - у меня всего одна таблица.
Есть реализация базы данных для эмбедед? кто нибудь видел такое? может даже реализовывал?

P.S. Погуглил эту тему. Вроде как советуют SQLLite. Но я не нашел примеров SQLLite для эмбеддед в С.

Сообщение отредактировал Jenya7 - Oct 22 2017, 09:02

[Rst7]

Элементы вставляются но p->data всех элементов содержит данные последнего элемента и p->next всех элементов указазывает на последний элемент.

Ээээ, так у Вас массив пустой, который msg_p. Где-то потеряна запись в поле msg_p[xxx].p.

вместо if (p) MsgFreeQ=p->next; должно быть MsgFreeQ=msg_p[g_pos+1].p;

Нет, конечно. Все должно быть так, как написано. Это же добыватель элемента из односвязного списка. Вы там, случайно, процедуру инициализации не забыли вызвать? И только один раз ее можно вызывать, если что.

[Jenya7]

Ээээ, так у Вас массив пустой, который msg_p. Где-то потеряна запись в поле msg_p[xxx].p.



Нет, конечно. Все должно быть так, как написано. Это же добыватель элемента из односвязного списка. Вы там, случайно, процедуру инициализации не забыли вызвать? И только один раз ее можно вызывать, если что.

Да. Не было инициализицаии. Добавляю ID 3 5 7. p->data элементов правильный. Вставляю ID 6 - p->data всех элементов равна последнему.

[Rst7]

Да. Не было инициализицаии. Добавляю ID 3 5 7. p->data элементов правильный. Вставляю ID 6 - p->data всех элементов равна последнему.

Я так за Вас всю работу сделаю. Вот код, проверенный на большом брате (кроме банальных описок ничего не исправлялось):

CODE

//---------------------------------------------------------------------------

#include <stdio.h>
#pragma hdrstop

#include <tchar.h>
//---------------------------------------------------------------------------

#define MESSAGE_ARR_SIZE 128

typedef struct TEST_MESSAGE
{
union
{
char data[20];
struct TEST_MESSAGE *next;
};
}TEST_MESSAGE;


typedef struct
{
int id;
TEST_MESSAGE *p;
}TEST_MESSAGE_P;

TEST_MESSAGE *MsgFreeQ;

TEST_MESSAGE messages[MESSAGE_ARR_SIZE];
TEST_MESSAGE_P msg_p[MESSAGE_ARR_SIZE];

int glob_pos;

int BinarySearch(TEST_MESSAGE_P *a, int pos, int key)
{
int first = 0;
int last = pos;
int mid;

if (pos == 0) //empty array
{
return ~0;
}
else if (a[0].id > key)
{
return ~0;
}
else if (a[pos - 1].id < key)
{
return ~pos;
}

while (first < last)
{
mid = first + (last - first) / 2;

if (key <= a[mid].id)
last = mid;
else
first = mid + 1;
}

if (a[last].id == key)
{
return last;
}
else
{
return ~last;
}
}

TEST_MESSAGE *AllocMessage(void)
{
TEST_MESSAGE *p=MsgFreeQ;
if (p) MsgFreeQ=p->next;
return p;
}


void FreeMessage(TEST_MESSAGE *p)
{
p->next=MsgFreeQ;
MsgFreeQ=p;
}

void InitMessageQ(void)
{
int i;
for(i=0; i<MESSAGE_ARR_SIZE; i++)
{
FreeMessage(messages+i);
}
}

void UpdateElement(TEST_MESSAGE *p, char msg[])
{
memcpy(p->data,msg,sizeof(p->data));
}

void InsertElement(int id, char msg[])
{
int idx;
idx = BinarySearch(msg_p, glob_pos, id);
if (idx>=0) //command NEW but the element exists - issue UPDATE
{
UpdateElement(msg_p[idx].p, msg); //void UpdateElement(TEST_MESSAGE *p, char *inmsg)
}
else //element not found - add one
{
TEST_MESSAGE *nm=AllocMessage();
idx=~idx;
if (!nm) nm=msg_p[MESSAGE_ARR_SIZE-1].p; //Если не удалось аллоцировать новый элемент - заменяем последний
memmove(msg_p+(idx+1), msg_p+idx, sizeof(TEST_MESSAGE_P)*(glob_pos-idx));
msg_p[idx].id = id;
msg_p[idx].p=nm;
memcpy(nm->data, msg, sizeof(nm->data));
if (glob_pos < MESSAGE_ARR_SIZE) glob_pos++;
}
}

void DeleteElement(int id)
{
int idx;
idx = BinarySearch(msg_p, glob_pos, id);
if (idx>=0)
{
FreeMessage(msg_p[idx].p);
memmove(msg_p+idx, msg_p+(idx+1), sizeof(TEST_MESSAGE_P)*(glob_pos-idx));
if (glob_pos > 0) glob_pos--;
}
}

void DumpDatabase(void)
{
int i;
printf("---- DB len=%d -----\n",glob_pos);
for(i=0; i<glob_pos; i++)
{
printf("idx=%d id=%d data=%s\n",i,msg_p[i].id,msg_p[i].p->data);
}
}

#pragma argsused
int _tmain(int argc, _TCHAR* argv[])
{
InitMessageQ();
InsertElement(3,"3333");
DumpDatabase();
InsertElement(5,"5555");
DumpDatabase();
InsertElement(7,"7777");
DumpDatabase();
InsertElement(6,"6666");
DumpDatabase();
return 0;
}
//---------------------------------------------------------------------------

Выдача после работы функции main:

CODE

---- DB len=1 -----
idx=0 id=3 data=3333
---- DB len=2 -----
idx=0 id=3 data=3333
idx=1 id=5 data=5555
---- DB len=3 -----
idx=0 id=3 data=3333
idx=1 id=5 data=5555
idx=2 id=7 data=7777
---- DB len=4 -----
idx=0 id=3 data=3333
idx=1 id=5 data=5555
idx=2 id=6 data=6666
idx=3 id=7 data=7777

[Jenya7]

Я так за Вас всю работу сделаю. Вот код, проверенный на большом брате (кроме банальных описок ничего не исправлялось):

Спасибо большое. У меня на последней строчке - InsertElement(6,"6666"); при вставке в середину происходит странное явление - соседние элементы меняют дату на ту же.
Буду отлаживать.

что то не так - p->next у всех одинаковый. мы его должны обновлять в InsertElement - он должен указывать на следующую ячейку.

Сообщение отредактировал Jenya7 - Oct 26 2017, 10:54

Эскизы прикрепленных изображений