LINUX.ORG.RU

Подскажите библиотеку/алгоритм

 , , , ,


0

2

Есть, проблема. Нужна реализация llinkedlist и hashmap на чистом С по верх Shared memory(shm). т.е. коллекция должна быть на offset'ах и с выделением памяти из кучи. Такого готового решения я не нашел. Решил написать сам на offset'ах, но опять же встает вопрос с выделением памяти из заранее созданного shared memory сегмента. Операционная система Linux c glibc и ulibc.

Надеюсь, что проблему описал достаточно подробно.

Самая лучшая хэш таблица на Си, из всех что я видел и которую я сам постоянно использую это uthash: http://troydhanson.github.io/uthash

Кстати у того же товарища есть и списки разной связности написанные в том же стиле.

Что касается shared memory, нужно написать свою версию malloc/realloc/free и подменить, переопределив соответствующие макросы.

ashinkarov ()
Ответ на: комментарий от true_admin

Скорость я не сравнивал, так что короткий ответ — не знаю.

Для меня лично радость состоит в том, что это не библиотека, а просто инклюд-файл, а все механизмы написаны на макросах.

Что касается скорости, я думаю, что все зависит от задачи и объемов. Джуди использует trie на 256-символьном алфавите, и таким образом реализует быстрый поиск хэшей. У uthash динамически увеличивается количество ведер по ходу необходимости, и ведра лежат в списке. На маленьких примерах джуди наверное будет быстре, на больших — хз, нужно сравнивать. Опять же тут вот товарищ пишет, что поиск с какого-то момента у джуди становится медленнее: http://preshing.com/20130107/this-hash-table-is-faster-than-a-judy-array Не знаю можно ли ему верить, но все подобные измерения очень уж скользкое дело.

Опять же главное, что оно не тянет никаких библиотек, можно поменть алгоритм хэширования, и переопределить почти все, оно умеет сортировать и итерировать по таблице.

ashinkarov ()

А чем bsd'шные коллекции на препроцессоре не устраивают? Там аллокации нет, считается, что это будет делать пользователь как ему удобно.

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

А там разве у них есть hash table? Я что-то не припомню.

Что касается queue — ок, все работает пока не нужно что-нибудь хитрое сделать. Я вот до сих пор не понимаю, зачем в TAILQ_ENTRY next это указатель, а prev это двойной указатель...

Я помнится пытался по элементу разделить очередь на две, а потом склеить обратно — я задолбался с этими двойными указателями, код вообще не читаемый получается. Так что в этом смысле реализация в ut варианте мне кажется как-то логичнее.

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

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

ashinkarov true_admin Reset

Что касается shared memory, нужно написать свою версию malloc/realloc/free и подменить, переопределив соответствующие макросы.

Очень не хочется велосипедить, может есть готовые проекты?

А чем bsd'шные коллекции на препроцессоре не устраивают? Там аллокации нет, считается, что это будет делать пользователь как ему удобно.

Что такое BSD'ешные коллекции?

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

Я пару лет назад спрашивал на лоре, тогда ничего не нашлось :(.

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

А сколько у тебя ожидается данных, кол-во выделений памяти и освобождений? Может тупой велосипед подойдёт? :)

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

нужно написать свою версию malloc/realloc/free

dlmalloc - смотреть на его MSPACE. Сам использую.

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