Простая реализация map int -> *ptr

Что можете порекомандовать, чтобы относительно быстро и несложно в реализации? Ну или может готовое что-то есть небольшое, однофайловое?

Рекомендую написать и отладить hash-контейнер самому. Это полезный опыт. Объём работы - часа на 4.

С матчастью можно ознакомиться тут: http://en.wikipedia.org/wiki/Hash_table#Open_addressing

А если из стандартного, то man hcreate, man bsearch

carb_blog11

Пожалуйтса, реализация в одном файле:

#include <assert.h>
#include <stdlib.h>

static void **map;
static size_t size;

void
init(size_t n)
{
        size = n;
        map = calloc(size, sizeof(void *));
        assert(map);
}

void
set(size_t pos, void *val)
{
        assert(pos < size);
        map[pos] = val;
}

void *
get(size_t pos)
{
        assert(pos < size);
        return map[pos];
}

void
del(size_t pos)
{
        set(pos, NULL);
}

int
has(size_t pos)
{
        assert(pos < size);
        return map[pos] != NULL;
}

void
kill(void)
{
        free(map);
}

#if 0
int
main()
{
        int *p, i;

        init(100);
        set(10, &i);
        p = get(10);
        assert(p == &i);
        del(10);
        kill();

        return 0;
}
#endif

Предлагаешь топикстартеру сделать calloc(INT_MAX, sizeof(void *)) ? :-)

void *data;

int p; //size , prim;
data = malloc(p);
void *at(unsigned key) {
  return data[key % p];
}

разрешение коллизий можешь чейнингом сделать.

Только вот ключи в такой реализации должны идти от 0 до size. В реальной жизни это не так. Хочется при size, скажем 1000, запихать ключ 3330

Потребовалась, значит, такая структура данных, отобржающая int в указатель.

А вас не учили описывать конкретней задачу? Что такое инт, что в нём хранится и т.п.

Что можете порекомандовать, чтобы относительно быстро и несложно в реализации?

С такой формулировкой тебе никто и нечего, кроме дефолтного бревна/хеша не выкатит. А это всяко не быстро и не просто.

О, ылита пришла. Для ылиты реализация хэш-таблицы — это «не просто». Пааанимаю. Сложный вопрос, очень.

RAM дешёвый. ;) Если исходить из int64, то всего-то 16EB. Для uint32 и того меньше — 32G на всё про всё.

Но ТС спрашивал, про диапозон 0..1000 (да даже если и short). То тут это быстрое, простое, злое и дешёвое решение.

http://lxr.free-electrons.com/source/lib/idr.c

realloc я уже не стал пихать. Идея, думаю, и так ясна. realloc добавить оставляю как домашнее задание.

Я так понял, он имел ввиду предполагаемое максимальное количество элементов. Впрочем, чёрт его знает, чего он имел ввиду.

Моя наколенная реализация hash-таблицы занимает 650 строк, работает в среднем на 10-15% быстрее той, что входит в состав glib2, и имеет настраиваемый баланс «жрать память <-> жрать CPU». Но её я тут не покажу, потому что я её свелосипедил на прошлой неделе, и она наверняка забагована. :-)

Эсли элементов мало, а ключи большие, то можно альтернативно задействовать <sys/queue.h>. Тоже влезет в два экрана.

А ещё можно хранить в виде бинарного дерева... но стоп! Всё уже придумано до нас.

Кстати, я может быть, велосипед изобрёл, но нигде не встречал идеи сочетать списочные корзинки и крупноблочное выделение памяти (как для open addressing).

Суть такова: выделяется буфер, в котором лежит N элементов. Элементы могут образовывать списки (в структуре есть место под указатель).

Из них первые M образуют головы корзинок, а остальные (N - M) формируют список свободных элементов.

При добавлении элемента: если корзинка пуста, складываем данные в неё. Если в корзинка занята, выделяем элемент из списка свободных и цепляем его в список, головой которого служит корзинка.

Когда список пустых блоков заканчивается, выделяем больший буфер и инкрементально перехешируем туда данные. (Можно и не инкрементально. Но я люблю алгоритмы с предсказуемым временем реакции.)

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

RAM дешёвый.

И медленный. Ты бы ещё на серверах амазона предложил хранить.

TODO в коде хэш-таблицы? Ты издеваешься?

это задание автору на дом :)
не буду ж я за него писать хэш таблицу :)

такая структура данных

кастани и все дела. за примерами в glib. там инты легально в указатели кастуются.

Ну или может готовое что-то есть небольшое, однофайловое?

libdict

static int m[1];

int *ItP(int i){ return m+i;}

int PtI(int *p){ return p-m;}

видимо не понял.

http://troydhanson.github.io/uthash/

Вот он, ваш велосипед . В его сишном исходнике структура так и называется Bucket.

Всем спасибо. Самым подходящим показался вариант предложенный imb. Ну а остановился пока на двоичном дереве поиска. Дёшево и сердито. Вот такой 180-строчник получился: https://github.com/olegwtf/p5-Net-DNS-Native/blob/master/bstree.h
Потом можно будет доделать в какое-нибудь дерево с автобалансировкой.

хм, если у тебя размер только 1000 около

на сов. машинах бин поиск нужен только на размерах больше ~400 элементов где меньше линейный уже быстрее :(