#ifndef FIFOH
#define FIFOH
//---------------------------------------------------------------------------
#include <windows.h>
//---------------------------------------------------------------------------
struct BufItem{
void *DataPointer;
BufItem *Next;
};
//---------------------------------------------------------------------------
class FIFO
{
private:
int FCount;
BufItem *Begin,*End;
CRITICAL_SECTION BufOperation;
public:
FIFO();
~FIFO();
bool Push(void *DataPointer);
void *Pop();
__property int PtsCount={read=FCount};
};
//---------------------------------------------------------------------------
#endif
Как организовать Fifo? Подскажите....
Нужен буфер в памяти в котором можно было бы накапливать данные, и при этом первый объект, вошедший в буфер, при чтении из буфера тоже вышел первым...
Организовывал так называемым кольцевым буфером, но при возможности долговременных затыконов кольцо переполняется, а делать его сразу сильно большим - тоже не очень.....
В общем FIFO нужен...:o :o :o
Организовывал так называемым кольцевым буфером, но при возможности долговременных затыконов кольцо переполняется, а делать его сразу сильно большим - тоже не очень.....
В общем FIFO нужен...:o :o :o
Цитата:
Originally posted by Jump
Нужен буфер в памяти в котором можно было бы накапливать данные, и при этом первый объект, вошедший в буфер, при чтении из буфера тоже вышел первым...
Организовывал так называемым кольцевым буфером, но при возможности долговременных затыконов кольцо переполняется, а делать его сразу сильно большим - тоже не очень.....
В общем FIFO нужен...:o :o :o
Нужен буфер в памяти в котором можно было бы накапливать данные, и при этом первый объект, вошедший в буфер, при чтении из буфера тоже вышел первым...
Организовывал так называемым кольцевым буфером, но при возможности долговременных затыконов кольцо переполняется, а делать его сразу сильно большим - тоже не очень.....
В общем FIFO нужен...:o :o :o
Что у тебя "кольцевой буфер", и если он переполняется - значит несовсем кольцевой :) ? Простейший пример очереди ФИФО - вектор добавление элементов которого происходит в конец а чтение сначала. Когда то приходилось реализовывать ФИФО гдето даже помоему остались исходники, буду на работе - посмотрю. Но посути ничего особосложного здесь нет, я если память не изменяет реализовал это используя класс-шаблон определив для него функции чтения, записи, сравнения и поиска. Так же гдето попадалась реализация кольцевого буфера на основе stream.
Цитата:
Originally posted by kot_
Что у тебя "кольцевой буфер", и если он переполняется - значит несовсем кольцевой :)
Что у тебя "кольцевой буфер", и если он переполняется - значит несовсем кольцевой :)
Кольцевой у меня - кусок памяти по которому лазят 2 указателя: читающий и пишущий. Пишущий, если доходит до конца блока, то пишет с начала, но при этом ему нельзя "обгонять" читающий, т.к. это приведет к потере еще не прочитанных данных - отсюда ограничение....
Уже самому идея пришла: Сделать по принципу дерева, т.е. каждый блок содержит указатель на следующий. Тогда легко можно будет "довыделять" память при забиси и освобождать память от первого (читаемого) блока, переназначая при этом указатель начала "стека" указателем на следующий блок. Вроде идея :) Даже через АПИху легко реализуется ;).
ЗЫ: А классицски "кольцевой" что должен из себя представлять?
Цитата:
Originally posted by Jump
Пишущий, если доходит до конца блока, то пишет с начала,
Пишущий, если доходит до конца блока, то пишет с начала,
ну в принципе здесь у тебя и ошибка. Пишущий указатель никогда не станет на начало - потому как читающий должен смещаться вслед за пишущим точнее пишущий пишет вслед за читающим, если ты меня понимаешь :). Так как принципиальное положение "первый пришел - первый ушел" то им именно читающий указатель должен определять скорость движения очереди - а не пишущий. Запись возможна тогда - когда освободилась память под запись, если ты будешь учитывать этот момент - ситуация переполнения у тебя возникать не будет.
Цитата:
Originally posted by kot_
ну в принципе здесь у тебя и ошибка. Пишущий указатель никогда не станет на начало - потому как читающий должен смещаться вслед за пишущим точнее пишущий пишет вслед за читающим, если ты меня понимаешь :).
ну в принципе здесь у тебя и ошибка. Пишущий указатель никогда не станет на начало - потому как читающий должен смещаться вслед за пишущим точнее пишущий пишет вслед за читающим, если ты меня понимаешь :).
Я понял :) На самом деле у меня так и есть... Я еще забыл написать, что читающий тоже не может обгонять пишущий (это автоматом по размеру проверялось). Т.е. они оба не имеют права перепрыгивать друг через друга.
Но я не понял: почему "Пишущий указатель никогда не станет на начало" ? Кусок памяти ведь ограниченный... Куда деваться, если дошли до конца? X)-
Кому интересно, написал код. Можно даже покритиковать :)
FIFO.h
FIFO.cpp
Код в многопоточном не проверял...... пока. В обычном режиме точно работает.
FIFO.h
Код:
FIFO.cpp
Код:
//---------------------------------------------------------------------------
#include "FIFO.h"
#pragma hdrstop
#pragma package(smart_init)
//---------------------------------------------------------------------------
FIFO::FIFO(){
InitializeCriticalSection(&BufOperation);
Begin = NULL;
End = NULL;
FCount = 0;
};
//---------------------------------------------------------------------------
FIFO::~FIFO(){
while(FCount)Pop();
DeleteCriticalSection(&BufOperation);
};
//---------------------------------------------------------------------------
//Помещаем указатель на элемент в конец стека
bool FIFO::Push(void *DataPointer){
BufItem *Tmp;
try{
Tmp = new BufItem;
}
catch(...){
return false;
};
Tmp->DataPointer = DataPointer;
Tmp->Next = NULL;
EnterCriticalSection(&BufOperation);
if(FCount)End->Next = Tmp;
else Begin = Tmp;
End = Tmp;
FCount++;
LeaveCriticalSection(&BufOperation);
return true;
};
//---------------------------------------------------------------------------
//Возвращаем указатель на элемент из начала стека и удаляем его
void *FIFO::Pop(){
BufItem *Tmp;
void *RetVal;
EnterCriticalSection(&BufOperation);
if(FCount){
RetVal = Begin->DataPointer;
Tmp = Begin;
Begin = Begin->Next;
delete Tmp;
FCount--;
LeaveCriticalSection(&BufOperation);
return RetVal;
};
LeaveCriticalSection(&BufOperation);
return NULL;
};
//---------------------------------------------------------------------------
#include "FIFO.h"
#pragma hdrstop
#pragma package(smart_init)
//---------------------------------------------------------------------------
FIFO::FIFO(){
InitializeCriticalSection(&BufOperation);
Begin = NULL;
End = NULL;
FCount = 0;
};
//---------------------------------------------------------------------------
FIFO::~FIFO(){
while(FCount)Pop();
DeleteCriticalSection(&BufOperation);
};
//---------------------------------------------------------------------------
//Помещаем указатель на элемент в конец стека
bool FIFO::Push(void *DataPointer){
BufItem *Tmp;
try{
Tmp = new BufItem;
}
catch(...){
return false;
};
Tmp->DataPointer = DataPointer;
Tmp->Next = NULL;
EnterCriticalSection(&BufOperation);
if(FCount)End->Next = Tmp;
else Begin = Tmp;
End = Tmp;
FCount++;
LeaveCriticalSection(&BufOperation);
return true;
};
//---------------------------------------------------------------------------
//Возвращаем указатель на элемент из начала стека и удаляем его
void *FIFO::Pop(){
BufItem *Tmp;
void *RetVal;
EnterCriticalSection(&BufOperation);
if(FCount){
RetVal = Begin->DataPointer;
Tmp = Begin;
Begin = Begin->Next;
delete Tmp;
FCount--;
LeaveCriticalSection(&BufOperation);
return RetVal;
};
LeaveCriticalSection(&BufOperation);
return NULL;
};
//---------------------------------------------------------------------------
Код в многопоточном не проверял...... пока. В обычном режиме точно работает.
ИМХО, не самый удачный код. Нет контроля lifetime хранящихся указателей. Связанный список хранит указатели на неизвестно что.
Цитата:
Originally posted by honeybeer
ИМХО, не самый удачный код. Нет контроля lifetime хранящихся указателей. Связанный список хранит указатели на неизвестно что.
ИМХО, не самый удачный код. Нет контроля lifetime хранящихся указателей. Связанный список хранит указатели на неизвестно что.
Указатель End указывает на последний элемент - это ошибка. Тебе нужно проверять полон ли буффер или пуст - у тебя данная проверка отсутствует.
Код:
class CicularFIFO:public streambuf{
char *buffer;
int size;
int overflow(int);
int underflow();
public:
CircularFIFO(int size);
~CircularFIFO(){delete buffer;}
IsEmpty();
IsFull();
};
class ioCircularFIFOstream:public iostream{
public:
ioCircularFIFOstream(CircularFIFO *f):iostream(f){}
int IsFull(){return (((CircularFIFO*)rdbuf())->IsFull());}
int IsEmpty(){return (((CircularFIFO*)rdbuf())->IsEmpty());}
};
//circular.cpp
CircularFIFO::CircularFIFO(int s)::streambuf(){
buffer = new char[size];
setbuf(buffer,s);
size = s;
setp(buffer,&buffer[size]);
setg(buffer,buffer,&buffer[size]);
}
int CircularFIFO::overflow(int c){
if(IsFull) return EOF;
setp(base(),ebuf());
return sputc(c);
}
int CircularFIFO::underflow(){
if(IsEmpty()) return EOF;
setg(base(),ebuf());
return sgetc(c);
}
int CircularFIFO::IsEmpty(){
return (gptr()==pptr())? 1: 0;
}
int CircularFIFO::IsFull()
{
if(gptr()==base())
return (pptr()== ebuf())?1:0;
else
return (pptr()== gptr()-1)?1:0;
}
char *buffer;
int size;
int overflow(int);
int underflow();
public:
CircularFIFO(int size);
~CircularFIFO(){delete buffer;}
IsEmpty();
IsFull();
};
class ioCircularFIFOstream:public iostream{
public:
ioCircularFIFOstream(CircularFIFO *f):iostream(f){}
int IsFull(){return (((CircularFIFO*)rdbuf())->IsFull());}
int IsEmpty(){return (((CircularFIFO*)rdbuf())->IsEmpty());}
};
//circular.cpp
CircularFIFO::CircularFIFO(int s)::streambuf(){
buffer = new char[size];
setbuf(buffer,s);
size = s;
setp(buffer,&buffer[size]);
setg(buffer,buffer,&buffer[size]);
}
int CircularFIFO::overflow(int c){
if(IsFull) return EOF;
setp(base(),ebuf());
return sputc(c);
}
int CircularFIFO::underflow(){
if(IsEmpty()) return EOF;
setg(base(),ebuf());
return sgetc(c);
}
int CircularFIFO::IsEmpty(){
return (gptr()==pptr())? 1: 0;
}
int CircularFIFO::IsFull()
{
if(gptr()==base())
return (pptr()== ebuf())?1:0;
else
return (pptr()== gptr()-1)?1:0;
}
Этот код приведен у Фейсона, я использовал его в одном из проектов для реализации кругового буфера. Использовал практически без изменений перегрузив в своем классе оператор записи и чтения из потока для своих структур данных.
А через динамический список слабо?
Цитата:
Originally posted by honeybeer
ИМХО, не самый удачный код. Нет контроля lifetime хранящихся указателей. Связанный список хранит указатели на неизвестно что.
ИМХО, не самый удачный код. Нет контроля lifetime хранящихся указателей. Связанный список хранит указатели на неизвестно что.
Просто там где я его применяю этот контроль особо не нужен...
Указатели не на неизвестно что, а на все, что угодно. Мне приходят блоки данных, я сохраняю на них указатели в стек. Потом по мере возможности извлекаю указатели, обрабатываю связанные с ними блоки данных и удаляю эти блоки.
Цитата:
Originally posted by Jump
Указатели не на неизвестно что, а на все, что угодно.
Указатели не на неизвестно что, а на все, что угодно.
А есть разница? :)
Цитата:
Originally posted by kot_
Указатель End указывает на последний элемент - это ошибка. Тебе нужно проверять полон ли буффер или пуст - у тебя данная проверка отсутствует.
Указатель End указывает на последний элемент - это ошибка. Тебе нужно проверять полон ли буффер или пуст - у тебя данная проверка отсутствует.
Указатель End не может быть ошибкой хотябы по тому, что данный код - не кольцевого буфера FIFO (как возможно Вы подумали. Т.е. читаем с одной стороны, пихаем с другой). Проверка полон ли буфер отсутствуе по одной простой причине - данный FIFO ограничен в емкости только запасом оперативной памяти компьютера (проверка на это присутствует). Проверить пуст ли буфер можно через свойство PtsCount (если пуст, равно 0)
ЗЫ: Благодарю за код кольцевого :)
Цитата:
Originally posted by wanja
А через динамический список слабо?
А через динамический список слабо?
Меееееедленно.
Мой код за секунду способен поместить в буфер мульён указателей, и на следующей все это вернуть.
Цитата:
Originally posted by kot_
А есть разница? :)
А есть разница? :)
Ну.... Конечно есть :) "неизвестно что" - это когда мы не знаем, что у нас в буфере. А "все, что угодно" - значит, что буфер у нас общего назначения. Уж я то сам знаю, какой тип данных я сохраняю. А буферы просто нет ни какой разницы....
Цитата:
Originally posted by Jump
Ну.... Конечно есть :) "неизвестно что" - это когда мы не знаем, что у нас в буфере. А "все, что угодно" - значит, что буфер у нас общего назначения. Уж я то сам знаю, какой тип данных я сохраняю. А буферы просто нет ни какой разницы....
Ну.... Конечно есть :) "неизвестно что" - это когда мы не знаем, что у нас в буфере. А "все, что угодно" - значит, что буфер у нас общего назначения. Уж я то сам знаю, какой тип данных я сохраняю. А буферы просто нет ни какой разницы....
Я имел ввиду тот факт, что контроль валидности отсутствует и если блок памяти был высвобожден где-то вовне, указатель будет адресовать ХЗ что.
Цитата:
Originally posted by honeybeer
Я имел ввиду тот факт, что контроль валидности отсутствует и если блок памяти был высвобожден где-то вовне, указатель будет адресовать ХЗ что.
Я имел ввиду тот факт, что контроль валидности отсутствует и если блок памяти был высвобожден где-то вовне, указатель будет адресовать ХЗ что.
Честно гря с трудом понимаю смысл данной критики.... Это можно отнести к минусам в принципе любого указателя. В самом классе такого (случайного или даже не знаю...) высвобождения не предусмотрено... Им вообще не предусмотрен доступ к блокам памяти, за исключением блока, который на выходе... Если необходимо определять тип данных то можно расширить структуру BufItem элементом "int DataType" - и ради бога, храни данные разных типов, а можно это и в самих данных определить и класс не трогать.
Кстати, насчет "lifetime" хранящихся элементов: реализовать тоже не сложно. Вот 2 способа:
1. Каждый элемент должен сохранять печать времени. И далее при извлечении "старого" элемента его просто убивать и извлекать следующий.
2. Плодить таймер к каждому созданному элементу, по истечении которого элемент убивать.
Да, собсно, а чем не устраивали smart_ptr и queue из STL?
Цитата:
Originally posted by honeybeer
Да, собсно, а чем не устраивали smart_ptr и queue из STL?
Да, собсно, а чем не устраивали smart_ptr и queue из STL?
Гы... Чтоб они не нравились, их надо узнать. А я не знал :D
Ща потестим...
Цитата:
Originally posted by Jump
Гы... Чтоб они не нравились, их надо узнать. А я не знал :D
Ща потестим...
Гы... Чтоб они не нравились, их надо узнать. А я не знал :D
Ща потестим...
queue:
что не понравилось: метод pop() не освобождает память и при этом нет ни какого другого метода для данной цели. Т.е. единожды разбухнув на затыконе эта штучка такой и останется.
что понравилось - скорость. Для сохранении мульёна элементов типа int потребовалось 150 мс (+100 мс на вход-выход в/из крит.секции(предполагаю, что сам компонент многопоточность не поддерживает...), против 320 мс у моего метода). А для чтение этого "массива" понадобилось всего 80 мс (против 400 у моего), но эт понятно почему. Надо будет мне своему методу тоже подобную фишку прикрутить :).
Памяти съедено обоими методами одинаковое количество.
smart_ptr: чет по нем хелпа нет у меня... Как его юзать, и как его объявить-то хоть? P(
Цитата:
Originally posted by Jump
Надо будет мне своему методу тоже подобную фишку прикрутить :)
Надо будет мне своему методу тоже подобную фишку прикрутить :)
И прекрутил. Сейчас у меня при повторном чтении (без учета крит.секций) муль блоков читается за 30 мс, а чтение без удаления - 20 мс. queue - отдыхает :)