Реализация очереди на C

[An_private]

Переоткрытие кольцевого буфера...

[xverizex]

Но мы же статьи пишем не только о новых вещах. Если бы были статьи только о новом, то не было бы статей и переводов об уроках по opengl и т.д.

[aamonster]

Ага, и начинаем их со слов "ко мне пришла идея", чтобы все знали, кто эти вещи изобрёл :-D

[xverizex]

чтобы все знали, кто эти вещи изобрёл

А вдруг была цивилизация до нас и она первая всё это изобрела. Потом все стерли и через много лет заново пере изобрели. Я то сам догадался как сделать, а большинство по книжкам учатся.

[amarao]

Так тип данных DeQueue или RingBuffer? У них совершенно разная семантика, время доступа к элементам, требования по памяти и разное поведение при переполнении (кольцевого буффера).

[dvserg]

del

[includedlibrary]

По-хорошему размеры лучше делать не интами, а size_t. Из queue_add возвращать результат, по которому можно узнать, произошла ли ошибка. Например, можно bool возвращать. Ещё такой момент - создам я очередь, добавлю в неё элемент, тогда q->high будет равен нулю. Однако, в queue_get есть такая строчка: `uint8_t a = q->data[q->high--];, которая сразу приведёт к неверному результату. Плюс неплохо было сделать функцию для освобождения памяти, которую использует очередь

Upd: Сразу не заметил, что вы использовали двойное присваивание `q->low = q->high = size-1`

Upd 2: Очередь с приоритетом страдает от тех же ошибок, что и без приоритета. Плюс ещё парочка замечаний:

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

	for (int i = 0; i < size_prio; i++) {
		q->data[i] = calloc (size, sizeof (uint8_t));
		q->low[i] = q->high[i] = size - 1; // А если size_prio > size?
		q->max[i] = size; // Тут тоже
	}

Для очередей с приоритетами обычно используют другие структуры данных. Однако ваш способ тоже подходит, если приоритетов строго определённое количество. Если же оно не известно, можно использовать следующие структуры данных: двоичная куча, биномиальная куча и другие кучи.

[dvserg]

По-хорошему там на calloc разориться можно. По сути идею инкапсуляции данных в объект queue свели к массиву ее мемберов. Смысл такого финта явно в недопонимании того, чего сам на(ш)кодил.

[includedlibrary]

calloc для поля data можно один сделать: q->data = calloc (size_prio * size, sizeof (void *)); Остальные calloc нужны, потому что создаются size_prio очередей. И из первой, в которой есть элементы достаётся первый элемент.

[Alexandroppolus]

Однако ваш способ тоже подходит, если приоритетов строго определённое количество

желательно ещё и чтобы это количество было небольшим, порядка ln(N) - логарифм от количества элементов, иначе всё равно неэффективно.

[xverizex]

Поменял немного код, теперь побыстрее будет работать. Сделал так, чтобы сразу знать с какого приоритета начинать вести поиск в очереди.

[GarryC]

"Мда, ничего не скажешь, а остальное вы уже видели..."

[iig]

Не знаю как мне приходят такие идеи

На собеседовании спросили разве что? ;)

и я не помню как другие реализуют очередь с приоритетом

Алгоритмы, которые можно вот так взять и изобрести за полчаса - уже изобретены в 70-х годах ;)

[mpa4b]

Результаты маллоков в C всё же принято проверять.

Ну и ещё, если такой кольцевой буфер делать строго в 2^n элементов, то можно обойтись совсем без count, а вместо size будет достаточно маски для младших битов. Далее разветвление: или иметь максимум ровно в 2^n элементов, тогда указатели low и high должны иметь n+1 незамаскированных бит, или иметь 2^n-1 элеметов, тогда low и high имеют n незамаскированных бит.

[e-zig]

Тоже баловался таким, на плюсах только.

https://github.com/e-zig/RwCBuf

[lamerok]

Очередь с приоритетом обычно делается через кучу, которая является является инвариантом двоичного дерева. Т. Е. Достаточно просто двоичное дерево реализовать, дальше оно само.