Перейти к содержанию
Поиск
    

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

Ответить

Rst7    5

Rst7
Опубликовано · Жалоба

Ну правильно вот так

 

memcpy(messages[idx].data, msg, sizeof(messages[0].data));

 

Но все же, это все не совсем то, о чем говорили все предыдущие посты. Вы носите весь массив вместе с данными для вставки/удаления, а надо только указатели.

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

jenya7    0

jenya7
Опубликовано · Жалоба
Ну правильно вот так

 

memcpy(messages[idx].data, msg, sizeof(messages[0].data));

 

Но все же, это все не совсем то, о чем говорили все предыдущие посты. Вы носите весь массив вместе с данными для вставки/удаления, а надо только указатели.

не совсем понимаю. memmove переносит из адреса в адрес поэлементно. или я что то не понимаю?

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Rst7    5

Rst7
Опубликовано · Жалоба
не совсем понимаю. memmove переносит из адреса в адрес поэлементно. или я что то не понимаю?

 

Вы переносите структуру размером int+char[20], что для 32хбитной архитектуры будет 24 байта. И таких может быть аж столько, сколько размер массива. На самом деле надо переносить структуру int+pkt*, что есть всего 8 байт, в 3 раза меньше. Но для этого еще надо организовать очередь пустых элементов (для добавления нового/удаления). Очередь эту вполне можно организовать прямо на месте тел сообщений.

 

Должно быть как-то так

#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, ее надо вызвать в самом начале.

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

jenya7    0

jenya7
Опубликовано · Жалоба
Вы переносите структуру размером int+char[20], что для 32хбитной архитектуры будет 24 байта. И таких может быть аж столько, сколько размер массива. На самом деле надо переносить структуру int+pkt*, что есть всего 8 байт, в 3 раза меньше. Но для этого еще надо организовать очередь пустых элементов (для добавления нового/удаления). Очередь эту вполне можно организовать прямо на месте тел сообщений.

ммм...а можете показать как. я не понимаю на что будет указывать pkt*.

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Rst7    5

Rst7
Опубликовано · Жалоба
ммм...а можете показать как. я не понимаю на что будет указывать pkt*.

 

Обновите страничку, в предыдущем посте я уже Вам код написал.

 

На самом деле есть одно узкое место. Зависит от того, что Вам нужно делать при переполнении буфера пакетов. Я имею в виду функцию InsertElement. Возможно, она должна выглядеть чуть по другому

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++;
    }
}

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

jenya7    0

jenya7
Опубликовано · Жалоба
Обновите страничку, в предыдущем посте я уже Вам код написал.

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

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Rst7    5

Rst7
Опубликовано · Жалоба

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

#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    0

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

#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 всех элементов указазывает на последний элемент.

post-71075-1508916405_thumb.png

post-71075-1508916415_thumb.png

Изменено пользователем Jenya7

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

jenya7    0

jenya7
Опубликовано · Жалоба

по моему в

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;

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Rst7    5

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

 

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

 

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

 

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

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

jenya7    0

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

 

 

 

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

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

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Rst7    5

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

 

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

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

#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:

---- 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    0

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

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

Буду отлаживать.

 

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

post-71075-1509014359_thumb.png

Изменено пользователем Jenya7

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Rst7    5

Rst7
Опубликовано · Жалоба

Я не понимаю, что Вы смотрите. Все поля msg_p.p у Вас нулевые. Это неправильно. Кроме того, p->next валиден только для пустых элементов. Я же специально написал вменяемую функцию дампа этой базы в последнем примере:

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);
    }
}

 

Что печатает эта функция в Вашем случае?

 

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

 

p->next не должен там обновляться. Он всего лишь указывает на следующий элемент в очереди пустых (которая MsgFreeQ)! Когда элемент занят, то из очереди MsgFreeQ он исключен, и указатель на него хранится только в массиве msg_p, а указатель next невалиден, он заполнен данными data (там же специально union написан, а не struct, объединяющий next и data).

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

jenya7    0

jenya7
Опубликовано (изменено) · Жалоба
Что печатает эта функция в Вашем случае?

у меня в 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

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
К сожалению, ваш контент содержит запрещённые слова. Пожалуйста, отредактируйте контент, чтобы удалить выделенные ниже слова.
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
×
  • Создать...