inarray-allocator - hash, динамический массив, malloc, связный список, кольцевой буфер в shared memory или в указанном массиве байт

Linux C/C++ hash-table shared-memory

Задача: сделать на Си связный отсортированный список с ограниченным размером или хэш-таблицу, необходимо, что весь список занимал не более N байт в куче (стек не считается).

Реализация

Возможные варианты: 1) сделать счетчик сколько выделено и освобождено и при достижении значения не выделять больше, т.е написать враппер для malloc, calloc, realloc; 2) выделить массив нужного размера и все операции по размещению элементов делать в этом массиве, проверяя границы; 3) поискать готовое решение по реализации хэш, массивов или списков на ограниченном участке памяти.

Первый вариант неплох, второй неудобен и требует много кода и отладки, поробуем тертий.

Есть библиотека inarray-allocator(http://docs.putey.net/ru/inarrayalloc), которая позволит реализовать такой функционал.

yum install CUnit CUnit-devel cmake gcc git 
git clone https://github.com/bayrepo/arrayallocator.git 
cd arrayallocator/build 
cmake .. 
make 
make unit-test 
make install

Библиотека построена на базе uthash исходников с реализованным алгоритмом malloc на массиве памяти. Текст программы с пояснениями ниже:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "bayrepomalloc.h"
#include "utlist.h"

#define MAX_WORD_LEN 10

В качестве наполняемых данных будут структуры, содержащие имя, память под которое тоже выделяется динмаически

typedef struct el {
    char *person_name;
    struct el *next, *prev;
} el;

int namecmp(el *a, el *b) {
    return strcmp(a->person_name, b->person_name);
}

Сделаем генератор слов для примера

void word_create(char *buffer, int buffer_len) {
    int new_len = 3 + rand() % (buffer_len - 4);
    memset(buffer, 0, buffer_len);
    int index = 0;
    for (index = 0; index < new_len; index++) {
        char c = 'a' + rand() % 20;
        buffer[index] = c;
    }
}

int main() {

head - это голова списка

    el *head = NULL;
    el *new_elem, *elt, *tmp = NULL;
    char buf[MAX_WORD_LEN];

в массиве storage будет храниться список и строки с именем

    srand(time(NULL));
    char storage[1000] = { 0 };

размечаем массив, как область для приема данных с помощью фнкции brp_malloc_init(http://docs.putey.net/ru/inarrayalloc#brp_malloc_init)

    if (brp_malloc_init((void * )storage, 1000)) {
        fprintf(stderr, "Something wrong on initialization\n");
        exit(-1);
    }

Заполняем список до тех пор, пока не закончится память, а точнее массив памяти

    do {

Выделяем память под струкутуру с помощью функции brp_malloc(http://docs.putey.net/ru/inarrayalloc#brp_malloc)

        new_elem = brp_malloc((void *) storage, sizeof(el));
        if (new_elem) {
                word_create(buf, MAX_WORD_LEN);
                new_elem->person_name = brp_strdup((void *) storage, buf);
            if (!new_elem->person_name) {
                brp_free((void *) storage, new_elem);
                new_elem = NULL;
            } else {
                DL_APPEND(head, new_elem);
            }
        }
    } while (new_elem);

Сортирую и вывожу список объектов

    DL_SORT(head, namecmp);
    DL_FOREACH(head, new_elem)
    {
        printf("%s\n", new_elem->person_name);
    }

Освобождаю память в массиве командой brp_free(http://docs.putey.net/ru/inarrayalloc#brp_free)

    DL_FOREACH_SAFE(head,elt,tmp)
    {
        brp_free((void *) storage, elt->person_name);
        DL_DELETE(head, elt);
        brp_free((void *) storage, elt);
    }
}

Все довольно просто. Больше информации о библиотеке по адресу http://docs.putey.net/ru/inarrayalloc

Добавить комментарий

Следующая запись Предыдущая запись