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

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

но а+2 не будет адресом элемента a[2].

Что значит не будет? Вы бы почитали про адресную арифметику в Си, для начала.

&(a[2])==a+2, если что.

[Jenya7]

Что значит не будет? Вы бы почитали про адресную арифметику в Си, для начала.

&(a[2])==a+2, если что.

ой. что то я туплю. вы правы.

ну вот я тут накропал. уж не знаю...

Код

#define MESSAGE_ARR_SIZE 128

typedef struct TEST_MESSAGE_S
{
    int id;
    char data[20];
}TEST_MESSAGE;

TEST_MESSAGE messages[MESSAGE_ARR_SIZE8];

int found;
int glob_pos;

int BinarySearch(TEST_MESSAGE a[], int pos, int key, int *found)
{
    int first = 0;
    int last = pos;
    int mid;
    
    if (pos == 0)  //empty array
    {
        *found = 0;
        return 0;
    }
    else if (a[0].id > key)
    {
        *found = 0;
        return 0;
    }
    else if (a[pos - 1].id < key)
    {
        *found = 0;
        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)
    {
        *found = 1;
        return last;
    }
    else
    {
                *found = 0;
        return last;
    }
}

void InsertElement(int id, char msg[])
{
    int idx;
    
    idx = BinarySearch(messages, glob_pos, id, &found);
    
    if (found)  //command NEW but the element exists - issue UPDATE
    {
        UpdateElement(idx, msg);
    }
    else //element not found - add one
    {
        memmove(messages+(idx+1), messages+idx, sizeof(TEST_MESSAGE)*glob_pos-1-idx);
        messages[idx].id = id;
        memcpy(messages[idx].data,  msg, sizeof(msg);

        
       if (glob_pos < MESSAGE_ARR_SIZE)
           glob_pos++;
    }
}

void DeleteElement(int id)
{
     int idx;
    
    idx = BinarySearch(messages, glob_pos, id, &found);
    
    if (found)
    {
       memmove(messages+idx, messages+(idx+1), sizeof(TEST_MESSAGE)*glob_pos-1-idx);
      
       if (glob_pos > 0)
           glob_pos--;
    }
}

Сообщение отредактировал Jenya7 - Oct 23 2017, 14:39