| |
|
  |
 Быстрый доступ к элементу. |
|
|
|
|
 Oct 24 2017, 11:12
|
Профессионал
Группа: Участник
Сообщений: 1 778
Регистрация: 29-03-12
Пользователь №: 71 075
|
Цитата(Rst7 @ Oct 24 2017, 15:09)  Ну правильно вот так Код memcpy(messages[idx].data, msg, sizeof(messages[0].data)); Но все же, это все не совсем то, о чем говорили все предыдущие посты. Вы носите весь массив вместе с данными для вставки/удаления, а надо только указатели. не совсем понимаю. memmove переносит из адреса в адрес поэлементно. или я что то не понимаю?
|
|
|
|
|
|
|
|
Oct 24 2017, 11:41
|
Йа моск ;)
Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610
|
QUOTE не совсем понимаю. memmove переносит из адреса в адрес поэлементно. или я что то не понимаю? Вы переносите структуру размером int+char[20], что для 32хбитной архитектуры будет 24 байта. И таких может быть аж столько, сколько размер массива. На самом деле надо переносить структуру int+pkt*, что есть всего 8 байт, в 3 раза меньше. Но для этого еще надо организовать очередь пустых элементов (для добавления нового/удаления). Очередь эту вполне можно организовать прямо на месте тел сообщений. Должно быть как-то так 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 found;
int glob_pos;
int BinarySearch(TEST_MESSAGE_P *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;
}
}
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, &found);
if (found) //command NEW but the element exists - issue UPDATE
{
UpdateElement(idx, msg);
}
else //element not found - add one
{
TEST_MESSAGE *nm=AllocMessage();
if (nm)
{
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, &found);
if (found)
{
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--;
}
} Обратите внимание, что есть процедура InitMessageQ, ее надо вызвать в самом начале.
--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
|
|
|
|
|
|
|
|
Oct 24 2017, 11:57
|
Йа моск ;)
Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610
|
QUOTE ммм...а можете показать как. я не понимаю на что будет указывать pkt*. Обновите страничку, в предыдущем посте я уже Вам код написал. На самом деле есть одно узкое место. Зависит от того, что Вам нужно делать при переполнении буфера пакетов. Я имею в виду функцию InsertElement. Возможно, она должна выглядеть чуть по другому CODE void InsertElement(int id, char msg[])
{
int idx;
idx = BinarySearch(msg_p, glob_pos, id, &found);
if (found) //command NEW but the element exists - issue UPDATE
{
UpdateElement(idx, msg);
}
else //element not found - add one
{
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++;
}
}
--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
|
|
|
|
|
|
|
|
Oct 24 2017, 12:10
|
Йа моск ;)
Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610
|
Ну и чисто эстетический момент. Лично меня вымораживает возврат таких простых флагов через указатели на переменные. Куда оптимальнее выглядит все вот так: 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--;
}
}
QUOTE а зачем делать алокацию? у меня статический масив. место уже выделено. по времени это не будет одно и то же? мне все равно придется создать место для элемента. Что значит одно и то же? Копирование, скажем 128 элементов по 24 байта это медленнее, чем копирование 128 элементов по 8 байт? Или одно и то же? Очередь свободных элементов создана заранее, прямо на месте буфера данных. Аллоцирование и освобождение элемента занимает буквально несколько тактов, это же не malloc из библиотеки, посмотрите на функции, я же их написал.
--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
|
|
|
|
|
|
|
|
Oct 24 2017, 12:17
|
Профессионал
Группа: Участник
Сообщений: 1 778
Регистрация: 29-03-12
Пользователь №: 71 075
|
Цитата(Rst7 @ Oct 24 2017, 17:10) Ну и чисто эстетический момент. Лично меня вымораживает возврат таких простых флагов через указатели на переменные. Куда оптимальнее выглядит все вот так: 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
Эскизы прикрепленных изображений
|
|
|
|
|
|
|
|
Oct 26 2017, 07:34
|
Профессионал
Группа: Участник
Сообщений: 1 778
Регистрация: 29-03-12
Пользователь №: 71 075
|
по моему в Код TEST_MESSAGE *AllocMessage(void)
{
TEST_MESSAGE *p = MsgFreeQ;
if (p) MsgFreeQ=p->next;
return p;
} вместо if (p) MsgFreeQ=p->next; должно быть MsgFreeQ=msg_p[g_pos+1].p;
|
|
|
|
|
|
|
|
Oct 26 2017, 08:00
|
Йа моск ;)
Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610
|
QUOTE Элементы вставляются но p->data всех элементов содержит данные последнего элемента и p->next всех элементов указазывает на последний элемент. Ээээ, так у Вас массив пустой, который msg_p. Где-то потеряна запись в поле msg_p[xxx].p. QUOTE вместо if (p) MsgFreeQ=p->next; должно быть MsgFreeQ=msg_p[g_pos+1].p; Нет, конечно. Все должно быть так, как написано. Это же добыватель элемента из односвязного списка. Вы там, случайно, процедуру инициализации не забыли вызвать? И только один раз ее можно вызывать, если что.
--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
|
|
|
|
|
|
|
|
Oct 26 2017, 09:47
|
Йа моск ;)
Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610
|
QUOTE (Jenya7 @ Oct 26 2017, 12:23) Да. Не было инициализицаии. Добавляю 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
--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
|
|
|
|
|
|
|
|
Oct 26 2017, 10:39
|
Профессионал
Группа: Участник
Сообщений: 1 778
Регистрация: 29-03-12
Пользователь №: 71 075
|
Цитата(Rst7 @ Oct 26 2017, 15:47) Я так за Вас всю работу сделаю. Вот код, проверенный на большом брате (кроме банальных описок ничего не исправлялось): Спасибо большое. У меня на последней строчке - InsertElement(6,"6666"); при вставке в середину происходит странное явление - соседние элементы меняют дату на ту же. Буду отлаживать. что то не так - p->next у всех одинаковый. мы его должны обновлять в InsertElement - он должен указывать на следующую ячейку.
Сообщение отредактировал Jenya7 - Oct 26 2017, 10:54
Эскизы прикрепленных изображений
|
|
|
|
|
|
|
|
Oct 26 2017, 11:29
|
Йа моск ;)
Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610
|
Я не понимаю, что Вы смотрите. Все поля msg_p[i].p у Вас нулевые. Это неправильно. Кроме того, p->next валиден только для пустых элементов. Я же специально написал вменяемую функцию дампа этой базы в последнем примере: CODE 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);
}
} Что печатает эта функция в Вашем случае? QUOTE что то не так - p->next у всех одинаковый. мы его должны обновлять в InsertElement - он должен указывать на следующую ячейку. p->next не должен там обновляться. Он всего лишь указывает на следующий элемент в очереди пустых (которая MsgFreeQ)! Когда элемент занят, то из очереди MsgFreeQ он исключен, и указатель на него хранится только в массиве msg_p, а указатель next невалиден, он заполнен данными data (там же специально union написан, а не struct, объединяющий next и data).
--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
|
|
|
|
|
|
|
|
Oct 26 2017, 11:36
|
Профессионал
Группа: Участник
Сообщений: 1 778
Регистрация: 29-03-12
Пользователь №: 71 075
|
Цитата(Rst7 @ Oct 26 2017, 16:29) Что печатает эта функция в Вашем случае? у меня в IAR printf почему то не выводит информацию в окно Debug. Я не нашел где это настраиваеся. Но на картинке - это элементы массива msg_p. поотлаживаю еще. а! во! msg_p[0].p адрес правильный -> 0x200047A0 а следующие - нули. то есть после InsertElement(3, "0000003333"); идем в if (!nm) nm=msg_p[MESSAGE_ARR_SIZE-1].p; и мы видим nm = 0x200047A0 а дальше InsertElement(5, "0000005555"); идем в if (!nm) nm=msg_p[MESSAGE_ARR_SIZE-1].p; и уже nm = 0x00000000 поэтому printf вылетает на второй итерации. КАТЕГОРИЧЕСКИ ИЗВИНЯЮСЬ! МОЯ ОПИСКА! ВСЕ РАБОТАЕТ! РЕСПЕКТ И УВАЖУХА! 
Сообщение отредактировал Jenya7 - Oct 26 2017, 12:22
|
|
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
