OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 22 Октябрь, 2019 09:51

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 18 ] 
Автор Сообщение
 Заголовок сообщения: реализация очереди-списка на C++
СообщениеДобавлено: Среда, 20 Январь, 2010 00:12 

Зарегистрирован: Вторник, 19 Январь, 2010 23:54
Сообщения: 136
Отделено отсюда: viewtopic.php?p=40457#p40457
Извините за длинное сообщение.

Высказывание интересно. И очень - из жизни.
После многих лет применения stl и прочего похожего (и своего подобного), написал свой класс очереди-списка.
Совместимость по типу нужна только в операции получения элемента. В остальном - самодостаточная вещь.
Перевести на КП, думаю, будет не так сложно. Потокобезопасность должна обеспечиваться внешними средствами.

Код:
//----------------------------------------------------------------------------
class Queue
{
public:

   typedef void(FreeObjectFunc_t) ( void* object );
   typedef bool(FindIfCheckFunc_t)( void* object, void *data );
   typedef void(ForEachFunc_t)    ( void* object, void *data );

private:

   struct QueueItem
   {
      QueueItem *prev_, *next_;
      void*      object_;
      QueueItem( QueueItem *prev = NULL, QueueItem *next = NULL, void* object = NULL )
      : prev_( prev ), next_( next ), object_( object )
      { };
   };

   QueueItem        *freeItems_;
   QueueItem        *items_;
   QueueItem        *last_;
   int               count_;
   int               capacityDelta_;
   FreeObjectFunc_t *pFreeObjectFunc_;

   static void FreeQueueItems( QueueItem* *items, FreeObjectFunc_t *pFreeObjectFunc );
   void InnerRemove( QueueItem* item );
   void AddToFree  ( QueueItem* item );
   void FreeItem   ( QueueItem* item );
   void MakeFirst  ( QueueItem* item );

public:
   //---------------------------------------------------------------------------
    Queue( FreeObjectFunc_t *pFreeObjectFunc = NULL, int startCapacity = 16, int capacityDelta = 4 );
   ~Queue();
   //---------------------------------------------------------------------------
   int   Count ();
   bool  Put   ( void* object );
   void* Front ();
   void* Get   ();
   bool  Remove( void* object );
   //---------------------------------------------------------------------------
   bool  Has    ( void* object, bool makeFirst = false );
   void* FindIf ( FindIfCheckFunc_t *pCheckFunc,   void *data, bool makeFirst = false );
   void  ForEach( ForEachFunc_t     *pForEachFunc, void *data = NULL );
   //---------------------------------------------------------------------------
};
//----------------------------------------------------------------------------


//---------------------------------------------------------------------------
Queue::Queue( FreeObjectFunc_t *pFreeObjectFunc, int startCapacity, int capacityDelta )
: freeItems_      ( NULL ),
  items_          ( NULL ),
  last_           ( NULL ),
  count_          ( 0 ),
  capacityDelta_  ( capacityDelta ),
  pFreeObjectFunc_( pFreeObjectFunc )
{
   while( startCapacity-- )
   {
      QueueItem *item;
      try{ item = new QueueItem( NULL, freeItems_, NULL ); }catch(...){ item = NULL; }
      if( ! item  )
         throw -1;
      freeItems_ = item;
   }
}

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

   void Queue::FreeQueueItems( QueueItem* *items, FreeObjectFunc_t *pFreeObjectFunc )
   {
      while( *items )
      {
         QueueItem *item = *items; *items = item->next_;
         if( pFreeObjectFunc && item->object_ )
            (*pFreeObjectFunc)( item->object_ );
         delete item;
      }
   }

Queue::~Queue()
{
   FreeQueueItems( &items_,     pFreeObjectFunc_ );
   FreeQueueItems( &freeItems_, NULL );
}

//---------------------------------------------------------------------------
int Queue::Count()
{
   return count_;
}
//---------------------------------------------------------------------------
bool Queue::Put( void* object )
{
   QueueItem *item = freeItems_;
   if( item )
      freeItems_ = item->next_;
   else
   {
      try{ item = new QueueItem(); }catch(...){ item = NULL; }
      if( ! item )
         return false;
      if( (capacityDelta_-1) > 0 )
         for( int i = 1; i < capacityDelta_; ++i )
         {
            QueueItem *freeItem;
            try{ freeItem = new QueueItem( NULL, freeItems_, NULL ); }catch(...){ freeItem = NULL; }
            if( ! freeItem )
               break;
            freeItems_ = freeItem;
         }
   }
   *item = QueueItem( last_, NULL, object );
   if( last_ )
      last_->next_ = item;
   else
      items_ = item;
   last_ = item;

   ++count_;

   return true;
}
//---------------------------------------------------------------------------
void* Queue::Front()
{
   return (items_) ? items_->object_ : NULL ;
}


   void Queue::InnerRemove( QueueItem* item )
   {
      if( item->prev_ )
         item->prev_->next_ = item->next_;
      else
         items_ = item->next_;

      if( item->next_ )
         item->next_->prev_ = item->prev_;
      else
         last_ = item->prev_;

      item->next_ = item->prev_ = NULL;
   }

   void Queue::AddToFree( QueueItem* item )
   {
      item->next_ = freeItems_;
      freeItems_ = item;
   }

   void Queue::FreeItem( QueueItem* item )
   {
      InnerRemove( item );
      AddToFree( item );
      --count_;
   }

   void Queue::MakeFirst( QueueItem* item )
   {
      InnerRemove( item );
      item->next_ = items_;
      items_ = item;
   }



//---------------------------------------------------------------------------
void* Queue::Get()
{
   QueueItem *item = items_; if( ! item ) return NULL;
   FreeItem( item );
   return item->object_;
}
//---------------------------------------------------------------------------
bool Queue::Remove( void* object )
{
   bool res;
   QueueItem *item = items_;
   for( ; item && item->object_ != object ; item = item->next_ ) /* !!! */ ;
   if( (res = (item != NULL)) )
      FreeItem( item );
   return res;
}


//---------------------------------------------------------------------------
void* Queue::FindIf( FindIfCheckFunc_t *pCheckFunc, void *data, bool makeFirst )
{
   void* object;
   if( ! pCheckFunc )
      object = NULL;
   else
   {
      QueueItem *item = items_;
      for( ; item && !(*pCheckFunc)( item->object_, data ) ; item = item->next_ ) /* !!! */ ;
      if( ! item )
         object = NULL;
      else
      {
         object = item->object_;
         if( makeFirst && item != items_ )
            MakeFirst( item );
      }
   }
   return object;
}

//---------------------------------------------------------------------------
bool Queue::Has( void* object, bool makeFirst )
{
   QueueItem *item = items_;
   for( ; item && (item->object_ != object) ; item = item->next_ ) /* !!! */ ;
   if( ! item )
      return false;
   if( makeFirst && item != items_ )
      MakeFirst( item );
   return true;
}

//-----------------------------------------------------------------------------
void Queue::ForEach( ForEachFunc_t *pForEachFunc, void *data )
{
   if( pForEachFunc )
   {
      for( QueueItem *item = items_; item ; item = item->next_ )
         (*pForEachFunc)( item->object_, data );
   }
}


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 20 Январь, 2010 00:19 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Тут есть отлично известная проблема с void*. Типизацию-то теряем.

В КП можно и не терять. :)
Подсказка к такому подходу давалась:

viewtopic.php?f=2&t=2006


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 20 Январь, 2010 00:25 

Зарегистрирован: Вторник, 19 Январь, 2010 23:54
Сообщения: 136
Илья Ермаков писал(а):
Подсказка к такому подходу давалась:
viewtopic.php?f=2&t=2006

Извините, я там не понял почти ничего...
Можете вкратце идею объяснить здесь?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 20 Январь, 2010 00:31 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Если Вы имеете:
1) абстракцию двоичного потока (одинаковую и для внешней, и для оперативной памяти, и для любой другой реализации);
2) возможность метапрограммирования в языке (т.е. разбора типа RECORD-а и его свойств);
3) нормальные стековые RECORD (потому что в той же Жабе их нет),

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

Библиотечный file of record, только на новом уровне, с абстракцией.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 20 Январь, 2010 00:33 

Зарегистрирован: Вторник, 19 Январь, 2010 23:54
Сообщения: 136
А разве реализация абстракции потока и разбор метаданных не будут лишние такты забирать?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 20 Январь, 2010 00:35 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Будут. Но это слагаемые, что вполне терпимо.

Главное, что не множители и степени, как в случае Жабы-Шарпа, в которых нормальное системное программирование вообще затруднено, без нагрузки на сборщик мусора на каждый чих и т.п.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 20 Январь, 2010 00:36 

Зарегистрирован: Вторник, 19 Январь, 2010 23:54
Сообщения: 136
Да и не вижу я особой опасности с моей очередью делать
а = (AnyType*)queue.Get();
когда я знаю точно, что у меня в этой очереди-списке только AnyType + потомки.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 20 Январь, 2010 13:00 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Созерцатель писал(а):
а = (AnyType*)queue.Get();
В Вашем контейнере лежат указатели на объекты, а Илья говорит про ситуацию когда в контейнере лежат не указатели на объекты, а сами объекты.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 20 Январь, 2010 13:10 

Зарегистрирован: Вторник, 19 Январь, 2010 23:54
Сообщения: 136
Сергей Губанов писал(а):
Созерцатель писал(а):
а = (AnyType*)queue.Get();
В Вашем контейнере лежат указатели на объекты, а Илья говорит про ситуацию когда в контейнере лежат не указатели на объекты, а сами объекты.
С течением времени данный вариант стал наимение логически обоснованным для использования. С указателями быстрее работать-копировать. Кроме того, из объектов были выброшены отдельные поля, отвечающие за их состояние. Вместо этого объекты (ссылки-указатели на них) переходят из одной очереди-списка в другую. Под охраной критических секций.
Со временем вариант с непосредственным хранением объектов в коллекциях вообще вышел из нашей практики. Только ссылки-указатели.


Последний раз редактировалось Созерцатель Среда, 20 Январь, 2010 21:31, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: реализация очереди-списка на C#
СообщениеДобавлено: Среда, 20 Январь, 2010 19:43 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3096
Откуда: Астрахань
Еще я не понял, при чем здесь Додиез, то есть C#. Это ж чистый С++!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: реализация очереди-списка на C++
СообщениеДобавлено: Среда, 20 Январь, 2010 20:04 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4522
Откуда: Россия, Орёл
Настолько отвык, что беглый взгляд попутал... В мозгу идёт сборка мусора :mrgreen:


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 20 Январь, 2010 22:50 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Созерцатель писал(а):
С указателями быстрее работать-копировать.
..
Со временем вариант с непосредственным хранением объектов в коллекциях вообще вышел из нашей практики.


Зато при хранении по значению можно не различать оперативную и внешнюю память.
Ссылочные же структуры строятся по индексу. Эквивалент указателя - пара (КОНТЕЙНЕР, ИНДЕКС). Плюсы по сравнению с указателями, кроме прозрачности: безопасность при явном выделении-освобождении памяти.

В Композите (viewforum.php?f=21), кстати, "pointer-free programming" сделано именно по такой схеме - введены хорошие ассоциативные разрежённые массивы (хотя мне не нравится встройка решения в язык). Ещё на СУБД Cache у них похоже.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 20 Январь, 2010 22:54 

Зарегистрирован: Вторник, 19 Январь, 2010 23:54
Сообщения: 136
Илья Ермаков писал(а):
Эквивалент указателя - пара (КОНТЕЙНЕР, ИНДЕКС)
ЧТо в данном кортеже есть КОНТЕЙНЕР? Тип его значения какой?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: реализация очереди-списка на C++
СообщениеДобавлено: Среда, 20 Январь, 2010 22:58 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
В программе - объект обычный (в КП - POINTER TO RECORD).

Но можно целое число - код типа записей, на которые ссылаемся ("номер таблицы БД").

На самом же деле, если у Вас статически известно, какого типа ссылка, то можно просто LONGINT, сделанный как подтип целого (обёрнутый в RECORD: TYPE PersonLink = RECORD id: LONGINT END). Это получается, в терминах БД, внешний ключ (foreign key). Первичный ключ (Primary key) - индекс в контейнере.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: реализация очереди-списка на C++
СообщениеДобавлено: Среда, 20 Январь, 2010 23:19 

Зарегистрирован: Вторник, 19 Январь, 2010 23:54
Сообщения: 136
Илья Ермаков писал(а):
В программе - объект обычный (в КП - POINTER TO RECORD).
Но можно целое число - код типа записей, на которые ссылаемся ("номер таблицы БД").
Что тогда будет означать "удаление объекта"? Обнуление всей записи? Изменение какого-то поля внутри объекта?
Это что В КАЖДОМ объекте (вне зависимости от типа) иметь поле "актуальность", "активность", "живой"?
Илья Ермаков писал(а):
На самом же деле, если у Вас статически известно, какого типа ссылка, то можно просто LONGINT, сделанный как подтип целого (обёрнутый в RECORD: TYPE PersonLink = RECORD id: LONGINT END). Это получается, в терминах БД, внешний ключ (foreign key). Первичный ключ (Primary key) - индекс в контейнере.
Понятийная база у нас разная. Нам придётся писать код преобразования идентификатора объекта, опирающегося на значение множества адресов памяти и операций с ними в чуждый задаче понятийный аппарат реляционных БД. Нам это далеко не всегда нужно и выгодно.
Вы плодите лишние сущности. Выгоды от этого я не вижу.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: реализация очереди-списка на C++
СообщениеДобавлено: Среда, 20 Январь, 2010 23:35 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Так у нас задачи разные :)

Мы, фактически, этим заменяем БД и делаем перманентность.

Кроме того, простой File (при реализации в памяти) и ReadRec/WriteRec используется для работы с двоичными данными в тех же сетевых компонентах. Т.е. большинство системных модулей оказывается без использования IMPORT SYSTEM, языковыми безопасными средствами (по эффективности практически прямой доступ, со слагаемым на вызов абстрактных методов интерфейсa File).

Если сравнивать с тем же Go... То слайсы мы такие используем. Поэтому, когда Go опубликовали, у меня сразу большое дежа-вю: "так всё это я уже видел..." у себя же :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 21 Январь, 2010 14:36 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3096
Откуда: Астрахань
Созерцатель писал(а):
Со временем вариант с непосредственным хранением объектов в коллекциях вообще вышел из нашей практики. Только ссылки-указатели.

ИМХО, два разных выхода (этот и у Ильи) - это следствие двух разных подходов при создании основ. То есть ББ+КП и С++ с любой средой.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 21 Январь, 2010 15:06 

Зарегистрирован: Вторник, 19 Январь, 2010 23:54
Сообщения: 136
Валерий Лаптев писал(а):
Созерцатель писал(а):
Со временем вариант с непосредственным хранением объектов в коллекциях вообще вышел из нашей практики. Только ссылки-указатели.
ИМХО, два разных выхода (этот и у Ильи) - это следствие двух разных подходов при создании основ. То есть ББ+КП и С++ с любой средой.
Вы не правы.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


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

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB