Задача: сделать на Си связный отсортированный список с ограниченным размером или хэш-таблицу, необходимо, что весь список занимал не более N байт в куче (стек не считается).
Реализация
Возможные варианты: 1) сделать счетчик сколько выделено и освобождено и при достижении значения не выделять больше, т.е написать враппер для malloc, calloc, realloc; 2) выделить массив нужного размера и все операции по размещению элементов делать в этом массиве, проверяя границы; 3) поискать готовое решение по реализации хэш, массивов или списков на ограниченном участке памяти.
Первый вариант неплох, второй неудобен и требует много кода и отладки, поробуем тертий.
Есть библиотека inarray-allocator(https://brepo.ru/post/inarray-allocator-hash-dinamicheskij-massiv-malloc-svyaznyj-spisok-koljcevoj-bufer-v-shared-memory-ili-v-ukazannom-massive-bajt), которая позволит реализовать такой функционал.
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
if (brp_malloc_init((void * )storage, 1000)) {
fprintf(stderr, "Something wrong on initialization\n");
exit(-1);
}
Заполняем список до тех пор, пока не закончится память, а точнее массив памяти
do {
Выделяем память под струкутуру с помощью функции 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
DL_FOREACH_SAFE(head,elt,tmp)
{
brp_free((void *) storage, elt->person_name);
DL_DELETE(head, elt);
brp_free((void *) storage, elt);
}
}
Все довольно просто. Больше информации о библиотеке по адресу https://brepo.ru/post/inarray-allocator-hash-dinamicheskij-massiv-malloc-svyaznyj-spisok-koljcevoj-bufer-v-shared-memory-ili-v-ukazannom-massive-bajt