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

[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]

Ну и чисто эстетический момент. Лично меня вымораживает возврат таких простых флагов через указатели на переменные. Куда оптимальнее выглядит все вот так:

CODE

#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()
{
for(unsigned int i=0; i<MESSAGE_ARR_SIZE; i++)
{
FreeMessage(messages+i);
}
}

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
{
idx=~idx;
TEST_MESSAGE *nm=AllocMessage();
if (!nm) nm=msg_p[MESSAGE_ARR_SIZE-1].p; //Если не удалось аллоцировать новый элемент - заменяем последний
memmove(msg_p+(idx+1), msg_p+idx, sizeof(TEST_MESSAGE_P)*(glob_pos-1-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-1-idx));
if (glob_pos > 0) glob_pos--;
}
}

а зачем делать алокацию? у меня статический масив. место уже выделено. по времени это не будет одно и то же? мне все равно придется создать место для элемента.

Что значит одно и то же? Копирование, скажем 128 элементов по 24 байта это медленнее, чем копирование 128 элементов по 8 байт? Или одно и то же? Очередь свободных элементов создана заранее, прямо на месте буфера данных. Аллоцирование и освобождение элемента занимает буквально несколько тактов, это же не malloc из библиотеки, посмотрите на функции, я же их написал.

[Jenya7]

Ну и чисто эстетический момент. Лично меня вымораживает возврат таких простых флагов через указатели на переменные. Куда оптимальнее выглядит все вот так:

CODE

#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()
{
for(unsigned int i=0; i<MESSAGE_ARR_SIZE; i++)
{
FreeMessage(messages+i);
}
}

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
{
idx=~idx;
TEST_MESSAGE *nm=AllocMessage();
if (!nm) nm=msg_p[MESSAGE_ARR_SIZE-1].p; //Если не удалось аллоцировать новый элемент - заменяем последний
memmove(msg_p+(idx+1), msg_p+idx, sizeof(TEST_MESSAGE_P)*(glob_pos-1-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-1-idx));
if (glob_pos > 0) glob_pos--;
}
}

Что значит одно и то же? Копирование, скажем 128 элементов по 24 байта это медленнее, чем копирование 128 элементов по 8 байт? Или одно и то же? Очередь свободных элементов создана заранее, прямо на месте буфера данных. Аллоцирование и освобождение элемента занимает буквально несколько тактов, это же не malloc из библиотеки, посмотрите на функции, я же их написал.

я понял. сейчас попробую.

Результаты такие. Вставка происходит. Только sizeof(TEST_MESSAGE_P)*(glob_pos-1-idx) я заменил на sizeof(TEST_MESSAGE_P)*(glob_pos-idx) иначе вылетает.
Элементы вставляются но p->data всех элементов содержит данные последнего элемента и p->next всех элементов указазывает на последний элемент.

Сообщение отредактировал Jenya7 - Oct 25 2017, 07:27

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