Как изменить элемент на месте (без копирования / передачи буфера)

Question

Я часто видел функции, похожие на следующие в C:

do_something(buffer, original_data)

В этом случае он берет исходные данные (часто const) и возвращает данные, запрошенные пользователем, вбуфер.Например, такая функция, как gets или readline.

Что делать, если в программе имеется определенное ограничение памяти и нет места для возврата как исходных данных, так и запрашиваемых данных.Например, что делать, если есть 1 ГБ текстовых данных, которые необходимо отсортировать, а пользователю не доступно 2 ГБ.Что может быть примером функции (например, функции сортировки), которая может быть запущена путем изменения данных на месте?

Answer 1

Стандартная библиотечная функция qsort.

void qsort(void *base, size_t nmemb, size_t size,
              int (*compar)(const void *, const void *));

Сортируемый массив передается в base, его длина в nmemb, размер каждого элемента в size и сравнениефункция в compar.

Вызов выглядит примерно так:

char **strings = NULL;
size_t nstrings = 0;
// do something to load strings;

//...

// sort the strings
qsort(strings, nstrings, sizeof(char *), string_comparer);


int string_comparer(const void *a, const void *b) { return strcmp(*(const char *)a, *const char *b); }

Этот API выглядит немного старым и неуклюжим из-за отсутствия дубинки для передачи в функцию, но срасширение gcc, позволяющее внутренним функциям обращаться к переменным во внешних функциях, это больше не является реальной проблемой.

Чье-то зеркало glibc qsort здесь: https://code.woboq.org/userspace/glibc/stdlib/qsort.c.html и версия ядра здесь: https://github.com/torvalds/linux/blob/8a72f3820c4d14b27ad5336aed00063a7a7f1bef/lib/sort.c