Форум 'C/C++' на RSDN.RU

триангуляция

Wed, 17 Mar 2010 20:17:49 GMT

Не подскажите, желательно свободной, библиотеки на С++/С содержащей функции триангуляции. Или пакета, с возможностью обращения к нему из C++-программы.

P.S. В пакетах такая возможность есть, например MATLAB функция delaunay() выполняет триангуляцию Делоне.

Вызов нескольких derived classes из массива

Wed, 17 Mar 2010 13:23:10 GMT

Добрый!
Вопрос нуба. В проге решил из структуры сделать объекты, что бы всё было как у взрослых дядек. Но ничего не получилось. Вот упрощенный вариант:

class A
{
public:
    virtual void VFunc() = 0;
};

class B: public A
{
public:
    void VFunc()
    {
        printf("class B\n");
    }
};

class C: public A
{
public:
    void VFunc()
    {
        printf("class C\n");
    }
};

// здесь можно что-то упростить?
B b = B();
C c = C();

static A *a[] = {&b, &c, 0 /*маркер конца списка*/};
static A *aa[] = {&B(), &C(), 0 /*маркер конца списка*/};
static A aaa[] = {B(), C()};

int _tmain(int argc, _TCHAR* argv[])
{
    // пока работает
    a[0]->VFunc();
    a[1]->VFunc();

    // коварно вылетает
    aa[0]->VFunc();
    aa[1]->VFunc();

    // даже не линкуется
    // в реальной проге линкуется, но идет вызов pure virtual
    aaa[0].VFunc();
    aaa[1].VFunc();

    return 0;
}

Как сделать правильно?

Транслятор R в C++

Wed, 17 Mar 2010 10:27:34 GMT

Здравствуйте!

По работе потребовалось портировать программы с R на С++. Предположительно будет большой объём таких програм, так что я решил написать транслятор. Я примерно знаю как его делать, но хотелось бы узнать у публики, есть ли какие-то готовые инструменты, позволяющие писать такие трансляторы. Если я ошибся форумом, перекиньте куда надо.

Заранее спасибо.

STLPort + DigitalMars

Tue, 16 Mar 2010 07:06:45 GMT

Добрый день!

Пытаюсь собрать STLPort компилятором Digital Mars.

Версия компилятора Digital Mars: 8.51,
Версия STLPort: 4.5.
Компилятор и STLPort я скачал с официального сайта. То есть этот STLPort уже адаптирован для компилирования Digital Mars.

Необходимо, чтобы DM собирал программы под DOS, с инструкциями процессора 8088, с моделью памяти Large и эмуляцией операций с плавающей точкой.
Без STLPort'a удалось настроить компилятор таким образом.

Привожу пример make файла:

#    -*- Makefile -*-
.SUFFIXES: .cpp .c .obj .dll .exe .rc .res

CXX=dmc
CC=dmc -cpp
LIB=lib
LINK=dmc
RC=rcc

LIB_BASENAME=stlp45dm_dosl

OBJS = build\c_locale.obj build\c_locale_stub.obj build\codecvt.obj \
    build\collate.obj build\complex.obj build\complex_exp.obj \
    build\complex_io.obj build\complex_io_w.obj build\complex_trig.obj \
    build\ctype.obj build\dll_main.obj \
    build\facets_byname.obj build\fstream.obj build\ios.obj \
    build\iostream.obj build\istream.obj build\locale.obj \
    build\locale_catalog.obj build\locale_impl.obj \
    build\messages.obj build\monetary.obj build\num_get.obj \
    build\num_get_float.obj build\num_put.obj \
    build\num_put_float.obj build\numpunct.obj build\ostream.obj \
    build\sstream.obj build\stdio_streambuf.obj \
    build\streambuf.obj build\string_w.obj build\strstream.obj \
    build\time_facets.obj

BUILD_DIRS=..\lib ..\build \
    ..\build\static ..\build\static\release \
    ..\build\static\debug ..\build\static\stldebug

CXXFLAGS_COMMON = -Ae -Ar -ml -C -S -0 -a2 -c -D_NOTHREADS -D_STLP_NO_NATIVE_WIDE_FUNCTIONS -DSTRICT -D__BUILDING_STLPORT -I../stlport

CXXFLAGS_RELEASE_static = $(CXXFLAGS_COMMON) -o+space -Nc

CXXFLAGS_DEBUG_static = $(CXXFLAGS_COMMON) -g -Nc

CXXFLAGS_STLDEBUG_static = $(CXXFLAGS_DEBUG_static) -D_STLP_DEBUG -g -Nc

.cpp{..\build\static\release}.obj:
    $(CXX) -c -o"$@" $(CXXFLAGS_RELEASE_static) "$<"

.cpp{..\build\static\debug}.obj:
    $(CXX) -c -o"$@" $(CXXFLAGS_DEBUG_static) "$<"

.cpp{..\build\static\stldebug}.obj:
    $(CXX) -c -o"$@" $(CXXFLAGS_STLDEBUG_static) "$<"

.c{..\build\static\release}.obj:
    $(CC) -c -o"$@" $(CXXFLAGS_RELEASE_static) "$<"

.c{..\build\static\debug}.obj:
    $(CC) -c -o"$@" $(CXXFLAGS_DEBUG_static) "$<"

.c{..\build\static\stldebug}.obj:
    $(CC) -c -o"$@" $(CXXFLAGS_STLDEBUG_static) "$<"

.rc{..\build}.res:
    $(RC) -32 -o"$@" "$<"

all:    directories all_static

directories:    $(BUILD_DIRS)

$(BUILD_DIRS):
    mkdir $@

all_static:    ..\lib\$(LIB_BASENAME)_static.lib ..\lib\$(LIB_BASENAME)_debug_static.lib ..\lib\$(LIB_BASENAME)_stldebug_static.lib

..\lib\$(LIB_BASENAME)_static.lib:    $(OBJS:build\=..\build\static\release\)
    *$(LIB) -c -n -p256 "$@" "$**"

..\lib\$(LIB_BASENAME)_debug_static.lib:    $(OBJS:build\=..\build\static\debug\)
    *$(LIB) -c -n -p256 "$@" "$**"

..\lib\$(LIB_BASENAME)_stldebug_static.lib:    $(OBJS:build\=..\build\static\stldebug\)
    *$(LIB) -c -n -p256 "$@" "$**"

Этот make файл получен из make файла, который поставлялся вместе с STLPort для компилятора Digital Mars. Я просто убрал все упоминания о динамических сборках STLPort и добавил дополнительные ключи компилятора, задающие тип процессора и модель памяти.
Ключи, которые были добавлены: -ml -C -S -0 -a2 -c.
Дефайны, которые были добавлены: _STLP_NO_NATIVE_WIDE_FUNCTIONS.

STLPort с этим make файлом не собирается!

Если убрать дефайн _STLP_NO_NATIVE_WIDE_FUNCTIONS, вылезут другие ошибки в заголовочных файлах, связанных со строками.

Выдается странная ошибка компилятора о том, что он (компилятор) не может найти прототип функции 'sqrt':

C:\Development\dm851c\dm\stlport\src>smake -f dm_dos.mak

SMAKE  Program Maintenance Utility (Console) Version 7.50
Copyright (c) 1994-1995 Innovative Data Concepts Incorporated
Copyright (c) 1994-2001 Digital Mars
All Rights Reserved

        dmc -c -o"..\build\static\release\complex.obj" -Ae -Ar -ml -C -S -0 -a2
-c -D_NOTHREADS -D_STLP_NO_NATIVE_WIDE_FUNCTIONS -DSTRICT -D_BUILDING_STLPORT -I
../stlport -o+space -Nc "complex.cpp"
using _STLP_VENDOR_CSTD::sqrt;
                            ^
../stlport\cmath(73) : Error: undefined identifier 'sqrt'
inline float sqrt (float __x)                 { return _STLP_DO_SQRT(float)(__x)
; }
                                                                           ^
../stlport\stl/_cmath.h(163) : Error: function 'sqrt' has no prototype
--- errorlevel 1
SMAKE fatal error: command "dmc" returned with error code 1
Stopping.

Примечательно еще и то, что STLPort прекрасно собирается без моих дополнительных ключей компилятора, то есть под Windows, а если установить мои ключи, выдает ошибку про функцию 'sqrt'.

Может нужно установить какой-нибудь хитрый define?

Подскажите пожалуйста.

Реальный размер структуры в памяти

Mon, 15 Mar 2010 16:04:49 GMT

Добрый день!

Вот возник вопрос, как узнать реальный размер заполненной структуры?
платформа Linux

struct STest
{
STest() : mChar(NULL)
{}

~STest()
{
if(mChar)
delete [] mChar;
mChar = NULL;
}

char *mChar;
std::string mStr;
};

int main()
{
STest tmp;

tmp.mChar = new char[100];
tmp.mStr = "test";

// хотелось бы тут получить реальный размер, это грубо говоря 4+4 + 100 + 4 = 112
// грубо говоря потому что std::string("test") явно не 4 байта в памяти занимат

return 0;
}

Спасибо за ответы и за советы )

Удаление одинаковых элементов

Mon, 15 Mar 2010 09:32:10 GMT

можно ли просто и эффективно с помощью stl удалить из сортированного списка элементы которые
1) встречаются 2 раза
2) более одного раза
3) удалить попарно, тоесть если будет 1,3,3,3 на выходе должно быть 1,3

?

Свежие новости с C++0x фронта

Sun, 14 Mar 2010 18:13:15 GMT

Завершилось собрание коммитета по стандартизации C++ в Пицбурге. Кое что о нем можно почитать у Саттера: http://herbsutter.wordpress.com/2010/03/13/trip-report-march-2010-iso-c-standards-meeting/

Вкратце, произошли следующие важные вещи:
* одобрили финальный драфт (FCD), что делает вероятным выпуск стандарта в следующем году. Те. это будет C++11.
* export templates выброшена из языка. Саттеру пришлось целый год лично удовлетворять все прихоти и желания разработчиков EDG пока они не согласились
* exception specifications deprecated. А вместо throw(), которого каждый компилятор реализует по-своему, теперь будет noexcept (с булевским параметром — забавно).

Для чего for_each возвращает копию функтора

Sun, 14 Mar 2010 13:38:21 GMT

Интересно, для чего for_each возвращает копию функционального объекта. Возможно, есть какие-то приемы, использующие эту фичу?

Баг или Фитча?

Sat, 13 Mar 2010 13:13:47 GMT

Этот код 2005-я студия скомпилила успешно.

template< typename T=int >
struct S {
    T a;
};


typedef std::vector<S<>>  vS; //<-- нету пробела > >

first-class

Sat, 13 Mar 2010 12:05:27 GMT

Мне задали вопрос по С:
1 — Что такое first-class?
2 — Являются ли массивы и списки(list.h) first-class?

В гугле я искал и ничего не нашел.
Спасибо.

ошибка на g++

Sat, 13 Mar 2010 10:05:36 GMT

#define PR_ADD_FEATURE_P(key, func) \
        m_featureProcessors.insert(FeatureProcessors::value_type(key, \
        boost::bind( boost::mem_fn( &Processor::##func ), this, _1) \
        ) );

        void Processor::setupFeatureProcessors()
        {
                PR_ADD_FEATURE_P("DSID", processDSID);
        }

#undef PR_ADD_FEATURE_P

error: pasting "::" and "processDSID" does not give a valid preprocessing token

объясните плиз в чем проблемма...

[Q] index_t, index_cast ?

Fri, 12 Mar 2010 19:04:18 GMT

Иногда (вплоть до "часто") возникает ситуация, когда смешиваются типы индексов.
Например, если в интерфейсе int, а в реализации std::vector с size_t.
Или, что ещё веселее, если в реализации используются ATL::CArray (size_t) и ATL::CSimpleArray (int).

Это порождает такие конструкции

void foo(int i)
{
  //CArray
  if(i < (int)arr.GetCount()) {} // иначе - варнинг о смешивании signed/unsigned
  if((size_t)i < arr.GetCount()) {} // более опасно, т.к. i<0 более вероятно, чем GetCount()<0 :)
  int n = (int)arr.GetCount();
  for(int j=0, c=arr.GetCount(); j!=c; ++j) {} // волшебным образом, компилятор здесь не выругался
}
void bar(size_t i)
{
  //CSimpleArray
  if(i < (size_t)arr.GetSize()) {}
  if((int)i < arr.GetSize()) {} // более опасно, т.к. i>MAX_INT более вероятно, чем GetSize()>MAX_INT (понадеемся...)
  arr.GetAt((int)i);
}

Отказаться от int в пользу size_t можно не всегда.
Во-первых, иногда удобно расширять диапазон индексов в обе стороны: перед-началом и за-концом.
Во-вторых, сигнальное состояние индекса — интуитивно понятное -1 против ~0
В-третьих, legacy, legacy, legacy...
и т.п.

Конечно, когда заранее известно, что количество элементов способно перевалить за 2Г (а там и за 4Г, если платформа 64-битная) — нужно использовать правильные типы и вообще быть очень аккуратными.
Но в остальных ситуациях такой ad-hoc-кастинг
1) раздражает
2) вызывает вопросы (откуда куда кастить?)
3) маскирует проблему
Маскировка — ровно та же, что и с C-style-cast: теряется смысл приведения типа в конкретном месте, на фоне похожих по форме, но иных по сути приведений в других местах.

Решением могло бы стать введение платформенно-комфортного типа.
Что-то в таком роде

typedef int index_t;

const size_t  size_t_npos = ~(size_t)0;
const int     int_npos    = -1;
const index_t npos        = -1;

inline index_t valid_index_cast(int  i) { assert(i>=0); return i; }
inline index_t valid_index_cast(size_t) { assert(i>=0 && i<INT_MAX); return (index_t)i; }

inline index_t maybe_index_cast(int  i) { assert(i>=-1); return i; }
inline index_t maybe_index_cast(size_t) { assert(i>=0 && i<INT_MAX || i==size_t_npos); return (index_t)i; }

Тогда код выше превратится в

void foo(int _i)
{
  index_t i = maybe_index_cast(_i);
  //CArray
  if(i < valid_index_cast(arr.GetCount())) {}
  index_t n = valid_index_cast(arr.GetCount());
  for(index_t j=0, c=arr.GetCount(); j!=c; ++j) {}
}
void bar(size_t _i)
{
  index_t i = maybe_index_cast(_i); // или valid_index_cast? ага! вопрос себе: нам точно не придёт сигнальное значение?
  //CSimpleArray 
  // - к счастью, он совместим с index_t, поэтому можем проигнорировать кастинг...
  //   хотя, если очень хочется, то valid_index_cast для проверки диапазона - пригодится
  if(i < arr.GetSize()) {}
  arr.GetAt(i); 
}

Может, чего более симпатичного предложите?

RAII + exceptions

Fri, 12 Mar 2010 11:35:21 GMT

У меня возникло ощущение, что RAII крайне сложно реализуется в С++.
Обычно применяют такую схему: создается ResourceHolder, который в конструкторе захватывает ресурс, а в деструкторе освобождает его.
Теперь важный момент: освобождение ресурса может породить исключение (варианты писать в деструкторе BOOL x = CloseHandle(handle); assert(x); считаю некачественным решением), которое уже нельзя просто так кидать из деструктора.

Каким образом вы решаете эту проблему?
1) это не проблема, assert меня устраивает в деструкторе, глушу исключение
2) плююсь в лог об ошибке, глушу исключение
3) закрытие ресурсов проектируется таким образом, чтобы исключений не было
4) в BOOST_SCOPE_EXIT эта проблема решена, и я его использую без классов ResourceHolder
5) не стесняюсь использовать std::unhandled_exception в деструкторе и выкидываю исключение из деструктора, если можно
6) ваш вариант

Спасибо.

Этюдик с++

Thu, 11 Mar 2010 20:55:13 GMT

найдите ошибку в коде:

template<typename T, intptr_t SIZE>
intptr_t atomic_max_distance_eq(T (&arr)[SIZE])
{
    typedef int assert[__is_class(T)?-1:1];
    intptr_t result = 0;
    for (intptr_t i = SIZE - 1; i > result; i--)
    {
        intptr_t j = -1;
        while (arr[++j] != arr[i]);
        result = max(result, i - j);
    }
    return result;
}

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

Lock-Free FIFO MPMC

Thu, 11 Mar 2010 17:35:18 GMT

Раз тут объявлен конкурс на lock-free контейнеры, посмотрите, плз.

Используется набор буферов фиксированной длины, связанных в двойной список.

Контейнер используется в проекте, поэтому есть зависимости от других подсистем, не имеющих отношения к самому контейнеру.
— _Deconst<T>, снимает константность.
— HELPER::Timable объявляет time_t, использование ниже.
— HELPER::DataMove::Construct, HELPER::DataMove::Move позволяют использовать move-семантику для конструирования и присваивания объектов. Использует std::swap_move_category для определения возможности использования move-семантики. Прямая проверка наличия swap не используется, т.к. это не всегда выгодно. В общем случае это простое конструирование копии и assigning.
— _Constructor::Construct, _Constructor::Destroy вызывают конструктор и деструктор объекта.
— SYS::Allocate, SYS::RCIFree выделяет и удаляют память. Используется свой менеджер памяти на основе per-thread букета буферов.

namespace LF
{        
    //  односвязный список
    struct SingleLink
    {
        SingleLink* volatile _lf_next;
    };
    //  двусвязный список
    struct DoubleLink : public SingleLink
    {
        DoubleLink* volatile _lf_prev;
    };

    //  QueueTraits объявляет буфер элементов и использует отдельный массив флагов для
    //  указания состояния слотов буфера. Может использоваться в общем случае.

    template <typename T, size_t _N = 256>
    struct QueueTraits
    {
        typedef typename _Deconst<T>::Type        data_t;
        
        typedef struct _BANK : 
            public LF::DoubleLink,
            public HELPER::Timable
        {
            BYTE        buffer[sizeof(data_t) * _N];
            volatile BYTE    mask[_N];        

            __forceinline _BANK() throw()
                { memset((BYTE*)mask, 0, sizeof(mask)); }

            __forceinline ~_BANK() throw()
            {
                data_t* objects = reinterpret_cast<data_t*>(buffer);
                for (size_t i = 0; i < _N; ++i)
                    if (QueueTraits::_getMask(this, i))
                        _Constructor::Destroy(&objects[i]);
            }
        } BANK;

        static __forceinline size_t getSize() throw()
            { return _N; }

        static __forceinline void Fill(BANK* bank, size_t index, data_t& d) throw()
        {
            data_t* objects = reinterpret_cast<data_t*>(bank->buffer);
            HELPER::DataMove::Construct(&objects[index], d);  // new(&objects[index]) data_t(d);
            //  #StoreStore
            _setMask(bank, index);
        }

        static __forceinline void Erase(BANK* bank, size_t index, data_t& d) throw()
        {
            _resetMask(bank, index);
            //  #StoreStore
            data_t* objects = reinterpret_cast<data_t*>(bank->buffer);
            HELPER::DataMove::Move(d, objects[index]);  // d = objects[index];
            _Constructor::Destroy(&objects[index]);
        }        

        static __forceinline BOOL IsValid(BANK* bank, size_t index) throw()
            { return (0 != _getMask(bank, index)); }

    protected:
        static __forceinline BOOL _getMask(BANK* bank, size_t index) throw()
            { return (0 != bank->mask[index]); }
        static __forceinline void _setMask(BANK* bank, size_t index) throw()
            { bank->mask[index] = 1; }
        static __forceinline void _resetMask(BANK* bank, size_t index) throw()
            { bank->mask[index] = 0; }    
    };

    //    QueueTraitsDef позволяет использовать "выделенное" значение объекта для 
    //    обозначения "пустого" слота буфера. Позволяет сэкономить на флагах.
 
    template <typename T, T _Def = T(), size_t _N = 256>
    struct QueueTraitsDef
    {
        typedef typename _Deconst<T>::Type        data_t;
        
        typedef struct _BANK : 
            public _RCI LF::DoubleLink,
            public _RCI HELPER::Timable
        {
            BYTE    buffer[sizeof(data_t) * _N];

            __forceinline _BANK() throw()
            {
                data_t* objects = reinterpret_cast<data_t*>(buffer);
                for (size_t i = 0; i < _N; ++i)
                    _Constructor::Construct(&objects[i], _Def);
            }

            __forceinline ~_BANK() throw()
            {
                data_t* objects = reinterpret_cast<data_t*>(buffer);
                for (size_t i = 0; i < _N; ++i)
                    _Constructor::Destroy(&objects[i]);
            }
        } BANK;

        static __forceinline size_t getSize() throw()
            { return _N; }

        static __forceinline void Fill(BANK* bank, size_t index, data_t& d) throw()
        {
            data_t* objects = reinterpret_cast<data_t*>(bank->buffer);
            HELPER::DataMove::Move(objects[index], d);
        }

        static __forceinline void Erase(BANK* bank, size_t index, data_t& d) throw()
        {
            data_t* objects = reinterpret_cast<data_t*>(bank->buffer);
            HELPER::DataMove::Move(d, objects[index]);
            objects[index] = _Def;
        }        

        static __forceinline BOOL IsValid(BANK* bank, size_t index) throw()
        {
            data_t* objects = reinterpret_cast<data_t*>(bank->buffer);
            return !(objects[index] == _Def);
        }
    };

    //    QueueTraitsPtr - частный случай QueueTraitsDef для указателей. 
    //      NULL - "выделенное" значение. Нулевые указатели контейнер хранить не может.

    template <typename T, size_t _N = 256>
    struct QueueTraitsPtr
    {
        typedef typename _Deconst<T>::Type        data_t;

        //    boost не используется, поэтому вот такие "самокаты"...
        template <typename P>
        struct IsPointer
        {
            static __forceinline void __fastcall Initialize(P p[]) throw()
                { }
        };

        template <typename P>
        struct IsPointer<P*>
        {
            static __forceinline void __fastcall Initialize(P* p[]) throw()
                { memset(p, 0, _N * sizeof(P*)); }
        };
        
        typedef struct _BANK : 
            public LF::DoubleLink,
            public HELPER::Timable
        {
            data_t        objects[_N];

            __forceinline _BANK() throw()
                { IsPointer<data_t>::Initialize(objects); }
        } BANK;

        static __forceinline size_t getSize() throw()
            { return _N; }

        static __forceinline void Fill(BANK* bank, size_t index, data_t& d) throw()
            { bank->objects[index] = d; }

        static __forceinline void Erase(BANK* bank, size_t index, data_t& d) throw()
            { d = bank->objects[index]; bank->objects[index] = NULL; }        

        static __forceinline BOOL IsValid(BANK* bank, size_t index) throw()
            { return !(bank->objects[index] == NULL); }
    };

    //    QueueBase, класс очереди.
    //    Примерная схема хранения буферов:
    //
    //                          NULL
    //                          |     <--| data
    //              Reader  ->  PNddddoooooooooooooooo
    //              (Tail)      ||                       ^ _lf_prev
    //                          PNdddddddddddddddddddd   |
    //                          ||                       v _lf_next
    //                          PNdddddddddddddddddddd
    //                          ||
    //              Writer   -> PNoooooooodddddddddddd
    //              (Head)       |        |<-- data
    //                          NULL
    //        

    template <typename T, typename _Traits = _RCI LF::QueueTraits<T> >
    class QueueBaseT
    {
        typedef typename _Traits::data_t        data_t;
        typedef typename _Traits::BANK            BANK;
        
        //    Head и Tail содержат пару (указатель на буфер, индекс элемента).
        //    Индекс отсчитывается от _N к нулю. 
        //    Для Head индекс - это индекс последнего добавленного элемента.
        //    Для Tail индекс - это индекс последнего удаленного элемента.
        //    Реализация для 32-битной x86 архитектуры. Для 64 бит немного сложнее.
#ifndef _WIN64

        union BANK_PTR
        {
            volatile __int64    scalar;
            struct
            {
                volatile __int32    low;    //    указатель
                volatile __int32    high;    //    stamp + index
            };

            __forceinline const BANK_PTR& __fastcall operator =(const volatile BANK_PTR& p) throw()
                { scalar = p.scalar; return *this; }
            __forceinline BOOL __fastcall operator ==(const volatile BANK_PTR& p) const volatile throw()
                { return (p.scalar == scalar); }
            __forceinline BOOL __fastcall operator ==(const BANK_PTR& p) const throw()
                { return (p.scalar == scalar); }
        };

        static __forceinline void __fastcall _Init(volatile BANK_PTR& p) throw()
            { p.scalar = 0i64; }

        static __forceinline long __fastcall _GetIndex(BANK_PTR& p) throw()
            { return long(p.high); }
        static __forceinline void __fastcall _SetIndex(BANK_PTR& p, long index) throw()
            { p.high = __int32(index); }

        static __forceinline BANK* __fastcall _GetBank(BANK_PTR& p) throw()
            { return (BANK*)(ULONG_PTR)p.low; }
        static __forceinline void __fastcall _SetBank(BANK_PTR& p, BANK* b) throw()
            { p.low = (__int32)(ULONG_PTR)b; }

        static __forceinline BOOL __fastcall _CAS(volatile BANK_PTR& p, BANK_PTR& pNew, BANK_PTR& pOld) throw()
            { return pOld.scalar == _InterlockedCompareExchange64(&p.scalar, pNew.scalar, pOld.scalar); }

        static __forceinline void __fastcall _Read(BANK_PTR& dst, volatile BANK_PTR& src) throw()
            { do { dst.high = src.high; dst.low = src.low; } while (dst.high != src.high); }

#endif    //    _WIN64

        //      В программе есть сервис фоновой "нормализации" приложения, отдельный поток,
        //      который периодически чистит всякий мусор. AutoGarbage - это lock-free
        //      multiple-produces-single-consumer контейнер, "корзина" для хранения мусора, 
        //      которая удаляет объекты (с помощью фонового потока) через определенное время 
        //      (скажем, через минуту после попадания в "корзину"). 
        //      Сам этот контейнер использует интерфейс SingleLink самих буферов, и отдельных
        //      сущностей типа "нода" для них не создает. Для определения последнего
        //      жизненного цикла используется интерфейс Timable.

        typedef HELPER::AutoGarbage<BANK*, немного всякой bla-bla-bla>    BANKS_AG;
        
        QueueBaseT(const QueueBaseT&);
        const QueueBaseT& operator =(const QueueBaseT&);
    public:
        __forceinline QueueBaseT() throw()
        { 
            _Init(m_head);
            _Init(m_tail);
        }
        __forceinline ~QueueBaseT() throw()
        { 
            BANK_PTR head;

            _Read(head, m_head);

            BANK* banks = _GetBank(head);

            if (NULL != banks)
            {
                do
                {
                    BANK* bank = banks;
                    banks = 
                        static_cast<BANK*>(banks->_lf_prev);    

                    _Constructor::Destroy(bank);
                    SYS::RCIFree(bank);
                }
                while (NULL != banks);
            }
        }

    public:
        //  константность не указывается, т.к. используется move-семантика для типов,
        //  для которых это явно разрешено (через std::swap_move_category).

        __forceinline void __fastcall Push(data_t& d)
        {
            BANK_PTR headOld;
            BANK_PTR headNew;

            for (;;)
            {
                long index;
                
                do
                {
                    _Read(headOld, m_head);    

                    //    Берем индекс следующего свободного слота. 
                    //    Если новый индекс меньше нуля, весь head-буфер заполнен.

                    index = _GetIndex(headOld) - 1;
                    if (index < 0)
                        break;

                    _SetBank(headNew, _GetBank(headOld));
                    _SetIndex(headNew, index);
                }
                while (!_CAS(m_head, headNew, headOld));

                if (index >= 0)
                {
                    //    Кладем элемент в слот и на выход.
                    _Traits::Fill(_GetBank(headNew), index, d);

                    return;
                }

                BANK* bankNew = reinterpret_cast<BANK*>(SYS::RCIAllocate(sizeof(BANK)));
                if (NULL == bankNew)
                    throw out_of_memory;
                
                _Constructor::Construct(bankNew);
                
                //    Это guard-объект, который удалит новый созданный буфер, если что...
                _GUARD_DATA1(guard, bla-bla-bla, BANK*, bankNew);

                _SetBank(headNew, bankNew);
                _SetIndex(headNew, (long)_Traits::getSize());

                BANK* bankOld = _GetBank(headOld);
                bankNew->_lf_prev = bankOld;
                bankNew->_lf_next = NULL;

                //    Используем CAS чтобы вставить новый буфер в head.
                //    Если не получилось, guard удалит созданный буфер.

                if (_CAS(m_head, headNew, headOld))
                {
                    //    Если старый буфер существовал, связываем новый к старому.
                    //    Только после этого связывания tail может перейти к новому буферу.
                    //    Если старый буфер не существовал, в контейнере только что создан
                    //    самый первый буфер, в этом случае просто записываем его в tail.

                    if (NULL != bankOld)
                        bankOld->_lf_next = bankNew;
                    else
                    {
                        _Init(headOld);

                        _CAS(m_tail, headNew, headOld);
                    }

                    //    Буфер сохранен, "сбрасываем" guard, чтобы он не удалил его.
                    guard.Detach();
                }
            }
        }

        __forceinline BOOL Pop(data_t& d) throw()
        {
            BANK_PTR tailOld;
            BANK_PTR tailNew;
            
            for (;;)
            {
                long index;
                
                BANK* bankOld;

                do
                {
                    for (;;)
                    {
                        _Read(tailOld, m_tail);
                        _Read(tailNew, m_head);

                        //    Если head совпадает c tail - очередь пуста.

                        if (tailOld == tailNew)
                            return FALSE;
                        
                        //    Если индекс следующего слота меньше нуля - 
                        //    весь tail-буфер прочитан. Выходим из цикла,
                        //    чтобы удалить его, и перейти к следующему
                        //    буферу по цепочке.

                        index = _GetIndex(tailOld) - 1;
                        if (index < 0)
                            break;

                        //    Если элемент в следующем слоте готов для
                        //    считывания, выходим из цикла, чтобы попытаться
                        //    забрать индекс слота себе, и считать элемент.

                        bankOld = _GetBank(tailOld);
                        if (_Traits::IsValid(bankOld, index))
                            break;    

                        //    Если выбранный элемент не готов для считывания,
                        //    он либо еще не дописан методом Push (и тогда
                        //    считывать нечего), либо уже считан кем-то другим.
                        //    В последнем случае должен измениться указатель
                        //    на tail, если это так - продолжаем попытки.

                        _Read(tailNew, m_tail);
                        if (tailNew == tailOld)
                            return FALSE;
                    }

                    if (index < 0)
                        break;

                    _SetBank(tailNew, bankOld);
                    _SetIndex(tailNew, index);
                }
                while (!_CAS(m_tail, tailNew, tailOld));

                if (index >= 0)
                {
                    //    Элемент готов для считывания и зарезервирован.
                    //    Забираем и уходим.

                    _Traits::Erase(_GetBank(tailNew), index, d);

                    return TRUE;
                }

                bankOld = _GetBank(tailOld);
                if (NULL == bankOld)
                    return FALSE;        //    Tail еще не задан, очередь "пуста".
                //    #LoadLoad
                BANK* bankNew = 
                    static_cast<BANK*>(bankOld->_lf_next);
                if (NULL == bankNew)
                    return FALSE;        //    Следующий буфер еще не прилинкован, очередь "пуста".

                _SetBank(tailNew, bankNew);
                _SetIndex(tailNew, (long)_Traits::getSize());

                //    Отцепляем "хвост"                                
                bankNew->_lf_prev = NULL;

                //    Если CAS удался - кладем удаленный буфер в "корзину".
                //    При этом, другие потоки могут все еще считывать элементы
                //    из этого буфера, для этого "корзина" гарантирует существование
                //    буфера в течении определенного времени. 

                if (_CAS(m_tail, tailNew, tailOld))
                    m_ag.Push(bankOld);
            }
            //    unreached code
            return FALSE;
        }

        __forceinline BOOL IsEmpty() const throw()
            { return (m_head == m_tail); }

                //  Чистка "корзины", периодически вызывается фоновым потоком.
        __forceinline size_t Normalize(volatile long* stop) throw()
            { return m_ag.Normalize(stop); }

    protected:
        volatile BANK_PTR    m_head;        
        volatile BANK_PTR    m_tail;        
        BANKS_AG        m_ag;        
    };
};

VC8 [BUG], создание экземпляра абстрактрного класса

Thu, 11 Mar 2010 15:24:22 GMT

VS2005, разрешает создавать экземпляр абстрактного класса, в качестве временного обьекта.

В чатности:

class AbstractClass
{
public:
    AbstractClass(int id)
    {
    }
    virtual void foo()=0;
};

void function (const AbstractClass& aaa)
{
}

int main()
{
    int id=0;
    function(id);
}

компилируется без ошибок.

P.S.
Comeau C/C++ и MinGW выдают ошибку. error: cannot allocate an object of type `const AbstractClass'

set из stl

Thu, 11 Mar 2010 12:21:16 GMT

необходимо описать структуру set из stl на С
помогите кто чем может.))

с контейнерами знаком лишь в общих чертах:
если можно еще и по ним что-нибудь посоветуйте почитать

заранее спасибо)

template

Thu, 11 Mar 2010 08:22:02 GMT

subj.
Идея понятна? как теперь заставить это компилироваться?

О lock-free алгоритмах (+бонус)

Wed, 10 Mar 2010 17:09:44 GMT

[пост получился достаточно длинный, поэтому сразу скажу о бонусе — это простой и эффективный алгоритм очереди на основе буфера фиксированного размера — нетерпеливые могут сразу перемещаться к концу поста ]

Последние дни на RSDN шла своего рода распределенная игра по написанию lock-free контейнеров. Вначале vf запостил lock-free стек для .Net:
http://www.rsdn.ru/forum/dotnet/3719883.aspx
Я указал, что в стеке содержится достаточно изощренная ошибка:
http://www.rsdn.ru/forum/dotnet/3721436.1.aspx

Потом Caracrist запостил lock-free очередь для С++:
http://www.rsdn.ru/forum/src/3725942.1.aspx
Я указал на ряд ошибок:
http://www.rsdn.ru/forum/src/3726327.1.aspx

Потом дали ссылку на блог некого товарища из Яндекса с описанием lock-free стека для С++:
http://users.livejournal.com/_foreseer/34284.html
Я тоже указал на ошибку:
http://www.rsdn.ru/forum/dotnet/3721636.1.aspx

К чему я это? Что не надо писать lock-free контейнеры? Это смотрите сами, мне всё равно. Это пусть говорят другие, те которые сами не умеют писать lock-free алгоритмы В целом lock-free алгоритмы писать вполне реалистично, единственное надо немного сноровки, ревью коллег, и соответствующие инструменты.
Кстати, по поводу инструментов, тут я не могу не упомянуть в качестве рекламы свой Relacy Race Detector. Если последние 2 ошибки удалось найти при просмотре кода, то первую смог вскрыть только Relacy Race Detector (кстати, если кто следит за такими тулзами, то CHESS от Microsoft не смог её найти — ограничение планировщика потоков).

Я должен отметить, что Caracrist в итоге запостил корректный алгоритм очереди, ну по-крайней мере я не вижу ошибок:
http://www.rsdn.ru/forum/src/3727286.1.aspx
Однако алгоритм получился достаточно сложный — 6 независимых переменных состояния, плюс достаточно не эффективный — 6 Interlocked инструкций на операцию. Для сравнения аналогичный алгоритм с применением спин-мьютекса будет исполнять по 1 Interlocked инструкций на операцию, и соотв. Будет в 6 раз быстрее в случае низкой конкуренции.

В чём сложность создания таких алгоритмов? В том, что последовательность атомарных операций сама по себе не является атомарной операций, это по-прежнему разрозненная последовательность (в отличие от алгоритмов, основанных на мьютексах). Наибольшую сложность представляют промежуточные состояния структуры данных, которые возникают в процессе выполнения последовательности. Каждое такое состояние должно быть полностью целостным. Целостным в том плане, что если придёт другой поток, то он должен посмотреть на структуру; определить, что это за состояние; понять, что ему делать дальше; и при этом не порушить планы первого потока. Даже хуже — прерываний потоков может быть несколько, т.е. первый поток перевёл структуру в какое промежуточное состояние; потом пришёл второй поток, и тоже выполнил часть операции; потом пришёл третий поток, выполнил ещё несколько незаконченных действий, и т.д. И после всего этого структура всё ещё должна оставаться в понятном консистентном состоянии.
В идеале поток целиком выполняет операцию за одну атомарную операцию, т.е. считывает состояние структуры, проверяет его, вычисляет новое состояние, и пытается атомарно перевести структуру из исходного состояния в новое с помощью CAS (InterlockedCompareExchange). Так работает известный алгоритм lock-free стека:
http://www.rsdn.ru/forum/dotnet/3721740.1.aspx
В таком алгоритме нет промежуточных (читай — потенциально проблематичных) состояний, структура либо не модифицирована вообще, либо операция полностью выполнена.
Однако это применимо только для простейших случаев, в более сложных случаях невозможно выполнить операцию за одну атомарную операцию — как в случае с очередью на основе фиксированного буфера, тут надо и записать данные и сместить позицию записи.

Кстати, к вопросу о сложных операциях с множеством промежуточных состояний, есть такая интересная презентация Cliff Click (сейчас он работает в Azul Systems, ранее в Sun – и там и там он был ключевой фигурой в разработке JVM) о реализации полностью lock-free хэш-мап (код доступен в сети):
http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
Представьте себе хэш-мап, в котором несколько потоков одновременно добавляют один и тот же элемент, несколько пытаются его считать, несколько удалить, и плюс одновременно с этим происходит увеличение размера таблицы. Каково? Клиф подошёл к вопросу фундаментально — он нарисовал в явном виде стейт-машину для ячейки таблицы; для каждого состояния описал как его можно определить (в смысле понять, что ячейка сейчас находится именно в этом состоянии); для каждой пары (состояние, тип операции (чтение, добавление, удаление)) описал, что потоку делать дальше; и потом реализовал все переходы между состояниями с помощью атомарных CAS.
Это если поверхностно, в реальности там много деталей и есть некоторые негативные моменты, которые он сам же внёс дабы реализовать хэш полностью без блокировок. Например, элементы никогда полностью не удаляются из таблицы, они просто помечаются как удалённые. Как следствие, даже если количество элементов в таблице остаётся постоянным, но происходят вставки и удаления элементов, ему приходится делать периодические фиктивные ресайзы таблицы, что бы «подчистить мусор». Ещё там могут быть проблематичными рекурсивные ресайзы таблицы... ну ладно, это я уже удаляюсь от темы.

Теперь обещанный бонус — алгоритм bounded multi-producer/multi-consumer очереди без блокировок. Контейнер не использует динамического выделения/управления памятью в процессе работы (за исключением изначального выделения фиксированного буфера).
Каждая операция содержит всего по 1 Interlocked инструкции, и как следствие будет достаточно быстрой.
Тут ситуация существенно попроще, чем у Клифа с его таблицей (и это к лучшему). Каждая операция (чтение/запись) состоит из 2 атомарных действий. (1) поток проверяет и резервирует элемент для чтения/записи, и (2) после выполнения фактического чтения/записи, помечает элемент как доступный для следующей операции (записи/чтения соответственно). Тут есть только одно промежуточное состояние — между (1) и (2) — которое должным образом обрабатывается.
Далее собственно код с комментариями:

template<typename T>
class mpmc_bounded_queue
{
public:
    mpmc_bounded_queue(size_t buffer_size)
        : buffer_(new cell_t [buffer_size])
        , buffer_mask_(buffer_size - 1)
    {
        typedef char assert_nothrow [__has_nothrow_assign(T) || __has_trivial_assign(T) || !__is_class(T) ? 1 : -1];
        assert((buffer_size >= 2) && ((buffer_size & (buffer_size - 1)) == 0));
        for (size_t i = 0; i != buffer_size; i += 1)
            buffer_[i].sequence_.store(i, std::memory_order_relaxed);
        enqueue_pos_.store(0, std::memory_order_relaxed);
        dequeue_pos_.store(0, std::memory_order_relaxed);
    }

    ~mpmc_bounded_queue()
    {
        delete [] buffer_;
    }

    bool enqueue(T const& data)
    {
        cell_t* cell;
        // загружаем текущую позицию для добавления в очередь
        size_t pos = enqueue_pos_.load(std::memory_order_relaxed);
        for (;;)
        {
            // находим текущий элемент
            cell = &buffer_[pos & buffer_mask_];
            // загружаем статус (sequence) текущего элемента
            size_t seq = cell->sequence_.load(std::memory_order_acquire);
            intptr_t dif = (intptr_t)seq - (intptr_t)pos;
            // элемент готов для записи
            if (dif == 0)
            {
                // пытаемся сдвинуть позицию для добавления
                if (enqueue_pos_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed))
                    break;
                // если не получилось, то начинаем сначала
            }
            // элемент ещё не готов для записи (очередь полна или типа того)
            else if (dif < 0)
                return false;
            // нас кто-то опередил
            // перезагружаем текущий элемент и начинаем сначала
            else /* if (dif > 0) */
                pos = enqueue_pos_.load(std::memory_order_relaxed);
        }

        // в данной точке мы зарезервировали элемент для записи

        // пишем данные
        cell->data_ = data;
        // помечаем элемент как готовый для потребления
        cell->sequence_.store(pos + 1, std::memory_order_release);

        return true;
    }

    bool dequeue(T& data)
    {
        cell_t* cell;
        // загружаем текущую позицию для извлечения из очереди
        size_t pos = dequeue_pos_.load(std::memory_order_relaxed);
        for (;;)
        {
            // находим текущий элемент
            cell = &buffer_[pos & buffer_mask_];
            // загружаем статус (sequence) текущего элемента
            size_t seq = cell->sequence_.load(std::memory_order_acquire);
            intptr_t dif = (intptr_t)seq - (intptr_t)(pos + 1);
            // элемент готов для извлечения
            if (dif == 0)
            {
                // пытаемся сдвинуть позицию для извлечения
                if (dequeue_pos_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed))
                    break;
                // если не получилось, то начинаем сначала
            }
            // элемент ещё не готов для потребления (очередь пуста или типа того)
            else if (dif < 0)
                return false;
            // нас кто-то опередил
            // перезагружаем текущий элемент и начинаем сначала
            else /* if (dif > 0) */
                pos = dequeue_pos_.load(std::memory_order_relaxed);
        }

        // в данной точке мы зарезервировали элемент для чтения

        // читаем данные
        data = cell->data_;
        // помечаем элемент как готовый для следующей записи
        cell->sequence_.store(pos + buffer_mask_ + 1, std::memory_order_release);

        return true;
    }

private:
    struct cell_t
    {
        std::atomic<size_t>     sequence_;
        T                       data_;
    };

    static size_t const         cacheline_size = 64;
    typedef char                cacheline_pad_t [cacheline_size];

    cacheline_pad_t             pad0_;
    cell_t* const               buffer_;
    size_t const                buffer_mask_;
    cacheline_pad_t             pad1_;
    std::atomic<size_t>         enqueue_pos_;
    cacheline_pad_t             pad2_;
    std::atomic<size_t>         dequeue_pos_;
    cacheline_pad_t             pad3_;

    mpmc_bounded_queue(mpmc_bounded_queue const&);
    void operator = (mpmc_bounded_queue const&);
};

И вот реализация подмножества C++0x std::atomic, необходимого для компиляции очереди (MSVC, x86-32):

#include <intrin.h>

enum memory_order
{
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,
    memory_order_release,
    memory_order_acq_rel,
    memory_order_seq_cst,
};

class atomic_uint
{
public:
    unsigned load(memory_order mo) const volatile
    {
        (void)mo;
        assert(mo == memory_order_relaxed
            || mo == memory_order_consume
            || mo == memory_order_acquire
            || mo == memory_order_seq_cst);
        unsigned v = val_;
        _ReadWriteBarrier();
        return v;
    }

    void store(unsigned v, memory_order mo) volatile
    {
        assert(mo == memory_order_relaxed
            || mo == memory_order_release
            || mo == memory_order_seq_cst);

        if (mo == memory_order_seq_cst)
        {
            _InterlockedExchange((long volatile*)&val_, (long)v);
        }
        else
        {
            val_ = v;
            _ReadWriteBarrier();
        }
    }

    bool compare_exchange_weak(unsigned& cmp, unsigned xchg, memory_order mo) volatile
    {
        unsigned prev = (unsigned)_InterlockedCompareExchange((long volatile*)&val_, (long)xchg, (long)cmp);
        if (prev == cmp)
            return true;
        cmp = prev;
        return false;
    }

private:
    unsigned volatile           val_;
};

template<typename T>
class atomic;

template<>
class atomic<unsigned> : public atomic_uint
{
};

SFINAE: hasMethos + isMethodProtected

Wed, 10 Mar 2010 13:55:19 GMT

Привет, всем!
Вообщем, нужно проверить есть ли у класса метод и если есть, то в какой секции.
Проверить наличие метода это на аць-два, а вот с меткой доступа проблеммы.
не подскажете это вообще возможно?