[jenya7 0]

Есть два массива. Я их получаю из двух разных потоков.

В table1.items элементы приходят сразу всем списком из 12 элементов. В table2 элементы приходят по одному.

Мне нужно по ключу(reference_number) найти и переписать поле(priority_level) во всех элементах в table2.

Делаю так.

Spoiler

typedef struct 
{
    uint32_t reference_number; 
    uint32_t priority_level;
}ITEMS;

typedef struct 
{
    ITEMS items[12];
}TABLE1;

typedef struct 
{
    uint32_t reference_number; 
    uint32_t priority_level;
}TABLE2;

TABLE1 table1;
TABLE2 table2[512];

void FindUpdateField(void)
{
    int i = 0, j = 0,  found = 0;
    
    for ( i = 0; i < 12; i++)
    {
       found = 0; 
       while ( (found == 0) && (j < 512))
       {
           if (table2[j].reference_number == table1.items[i].reference_number)
           {
               table2[j].priority_level = table1.items[i].priority_level;
               found = 1;
           }
           else
               j++;
       }
    }
}

 

Но за время поиска в цикле приходят новые данные в  table1.items  и я отправляю пару пакетов(table2) со старыми данными.

Возникла мысль реализовать hashtable. посмотрел реализации hashtable штук 20. Ни одна не понравилась. Нет детерминизма. Каждый malloc должен иметь свой free. А тут я рискую остаться с кучей мусора и фрагментированной памятью.

Есть алгоритм вычисления уникального индекса хэш таблицы по ключу? (idx = hash(key))

 

 

[Kabdim 0]

std::unordered_map?

[jenya7 0]

Just now, Kabdim said:

std::unordered_map?

в голом С?

[Kabdim 0]

1. Нигде не указано что ответ должен быть на голом C.

2. При наличии идиосинкразии к C++ можно посмотреть исходники С++ и переписать на С.

3. Но лучше конечно не изобретать велосипед, который уже написан.

[jenya7 0]

1 hour ago, Kabdim said:

1. Нигде не указано что ответ должен быть на голом C.

2. При наличии идиосинкразии к C++ можно посмотреть исходники С++ и переписать на С.

3. Но лучше конечно не изобретать велосипед, который уже написан.

То что написано не подходит.

Допустим я получил table1.items - и все 12 элементов поместил в хэш таблицу

//insert (key, value)

insert(table1.items[0].reference_number, table1.items[0].priority_level);  //malloc

.................................................................................................

insert( table1.items[11].reference_number, table1.items[11].priority_level); //malloc

 

приходят элементы

//value = get(key)

table2[idx].priority_level = get(table2[idx].reference_number);

delete(table2[idx].reference_number)  //free

 

но элемент может быть удален из table2 за ненадобностью. и он никогда не обратиться к хэш таблице и не освободит память выделенную под него.

 

Весь алгоритм такой.

1. Пришел список table1.items

2. По принятию списка иду в массиве table2 - ищу reference_number в списке table1.items и если нашел обновляю priority_level.

 

я тут подумал... я ведь при удалении элемента из table2 могу вызвать delete(table2[idx].reference_number).

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

 

Изменено 6 февраля, 2019 пользователем jenya7

[xvr 12]

2 hours ago, jenya7 said:

Но за время поиска в цикле приходят новые данные в  table1.items  и я отправляю пару пакетов(table2) со старыми данными.

 Такие слова как mutex, concurrent access, thread safe вам видимо ни о чём не говорят

2 hours ago, jenya7 said:

Есть алгоритм вычисления уникального индекса хэш таблицы по ключу?

В принципе не может быть. Размер хэша может быть меньше, чем количество элементов в таблице - природу не обманешь :)