LINUX.ORG.RU

Реализация generic списков в C

 ,


1

2

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

Реализацию написал такого вида:

typedef struct ListSingly
{
    int64_t              * data;
    struct ListSingly * next;
} ListSingly;

(int64_t * вместо void * из-за того, что void имеет нефиксированный размер)

Вопрос - для generic списка (т.е. когда я в одном месте буду приводить data к float, а в другом к SomeStruct *) такая реализация нормальна? Просто я очень не хочу городить нечитаемый огород из макросов для реализации под каждый конкретный тип.

Как тогда разруливать предупреждения компилятора о том, что типы разного размера, когда, например, я буду использовать signed char для data? Ведь злоупотребление & 0xFF может привести к потере бита знака или его неправильной интерпретации.

★★

Последнее исправление: cetjs2 (всего исправлений: 2)
Ответ на: комментарий от LongLiveUbuntu

Тут лучше хотя бы std::list применить

Ей, я два тега поставил же!

sambist ★★
() автор топика
Ответ на: комментарий от crowbar

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

sambist ★★
() автор топика
Ответ на: комментарий от Eddy_Em

Велосипед знатный, но разве оно заработает, если мне в одном файле потребуется list-int и list-float?

sambist ★★
() автор топика
Ответ на: комментарий от sambist

Ну, у меня такой нужды не было. Но если понадобится, можно переделать: воткнуть void* и при добавлении элемента выделять еще и память под элемент. Костыльно, конечно, но по-другому — только кипой макросов и раздельных контейнеров на каждый тип данных. В сраных плюсах это шаблонами и перегрузкой реализуется, но в итоге получается то же самое: толпа функций, каждая на свой тип данных.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от anonymous

Блин, я что-то думал, что ядро GPL3...

Ну, в принципе, GPL2 тоже пойдет на худой конец.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от sambist

Б. Откомпилируй sizeof(void *) на 32х и 64х битных машинах.

Это не объясняет, зачем ты вместо void * используешь int64_t *

runtime ★★★★
()
struct slist {
    struct slist *next;
    union {
        double d;
        float f;
        int i;
        long l;
        char c;
        char *s;
        void *p;
    } data;
};
item = malloc(sizeof(struct slist *) + sizeof(x));
item->data.<type> = x;
arturpub ★★
()

Кстати, позови супиркакира: вдруг чего дельного подскажет. Но срач-то явно разведет ☺

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от beastie

О, кстати, полистал мануал и вспомнил, что надо еще навелосипедить кольцевой буфер: частенько он используется, и постоянно тащу уйму функций и проверок.

Правда, все равно для микроконтроллеров не годится: жирно.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от sambist

Откомпилируй sizeof(int64_t *) на 32х и 64х битных машинах.

8 и 8 и чо?

Код в студию

runtime ★★★★
()
Ответ на: комментарий от sambist

Как у тебя на 32-битной машине sizeof(void*) может быть 8 байт?

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Использовал в своей OS для atmega32 — не настолько уж и жирное, но дико облегчает дебаг и реализацию.

beastie ★★★★★
()

Не хочу тебя огорчать, но это не обобщённый список, а список элементов типа указатель на int64_t.

Apple-ch ★★
()

Короче, чтобы не дожидаться комментариев автора: int64_t* надо менять на void*, т.к. использование int64_t* по стандарту для данных целей быть использованным не может. Только void* (и, если мне не изменяет память, char*, но могу ошибаться) гарантирует:

  • быть нужного размера, чтобы вместить любой другой указатель
  • отсутствие проблем при приведении указателя к другому типу
runtime ★★★★
()
Ответ на: комментарий от Eddy_Em

Зачем макросами делать, если можно функциями. Я имел ввиду где тут макросы, если не делать универсальное append_auto(list, x), которое будет брать sizeof(x)? Да и в нем сложно заблудиться, хотя тс вон заблудился, тут ты прав...

Но вне рамок заблуждений итт, итемам пофигу что у них после некста, если охота сделать ультрабиблиотеку по жонглированию генерик-итемами, то она не будет зависеть от типизации пайлода. Собственно можно взять готовую — все слисты имеют некст первым членом.

arturpub ★★
()

Вопрос - для generic списка (т.е. когда я в одном месте буду приводить data к float, а в другом к SomeStruct *) такая реализация нормальна? Просто я очень не хочу городить нечитаемый огород из макросов для реализации под каждый конкретный тип.

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

typedef enum {
    LL_TYPE_PTR     = 1,
    LL_TYPE_BLOB    = 2,
    LL_TYPE_INT     = 3,
        /* other payload types... */
} ll_type_t;

typedef struct {
    ll_type_t       type;
    size_t          payload;
} ll_meta_t;

typedef struct {
    ll_head_t       *next;
    const ll_meta_t *meta;

    /* payload data */
} ll_head_t;

void  ll_init(const ll_meta_t*, ll_head_t*);
bool  ll_ensure(const ll_head_t*, ll_type_t);
+ апишечка для итераторов и апишечка с кастами к типам.

mashina ★★★★★
()
Ответ на: комментарий от arturpub

Кстати, можно на макросах сделать автогенерацию нужных функций, скажем, нужны тебе списки целых и двойных, пишешь:

#define LIST_TYPE int
#include <common_list.c>
#undef LIST_TYPE
#define LIST_TYPE double
#include <common_list.c>
и оно наделает функций вроде list_int_add(..), list_double_add(..) и т.п. А к ним уже доступ либо напрямую, либо тоже через макросы.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от sambist

Откомпилируй sizeof(int64_t*) на 32х и 64х битных машинах и удивись.

anonymous
()

А зачем ListSignly последним элементом?

(int64_t * вместо void * из-за того, что void имеет нефиксированный размер)

Дальше не читал, отвечать не собираюсь. И вообще зря я это сюда пишу. Школотред.

nanoolinux ★★★★
()

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

Legioner ★★★★★
()
Ответ на: комментарий от waker

Годно. Но у меня есть задача зависти такой буфер для кадров с v4l2 хранящихся в shm (чтобы множество клиентов можно было обслужить), а еще для микроконтроллеров. В общем, нужно еще и помимо общей реализации сделать частные.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Legioner

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

Не для этого. Макрос потенциально может сэкономить один вызов ф-ии, раньше это было актуально. Ещё с макросами можно засунуть элемент в несколько списков инлайном.

mashina ★★★★★
()
Последнее исправление: mashina (всего исправлений: 1)
Ответ на: комментарий от sambist

8 и 8 и чо?

О сколько нам открытий чудных...

i-rinat ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.