[cdev] Задача_6. гр 135

[Grigoriy A. Sitkarev]

Лена Довжко пишет:
> 	
> можно написать xmalloc()  :)

Можно было написать. Потому что Лёша забывает например в prioq_new()
проверить что вернул первый malloc(3) хотя я ему посылал свой пример там
была проверка.

Дело в том что не всегда xmalloc(), который просто вызывает exit(2) если
не удалось памяти выделить, панацея - объясню почему. Предположим вы
пишите какой-нибудь сервер, который обслуживает много подключений. При
попытке инициировать новое подключение закончилась память и malloc(2)
вернул NULL. В таком случае рационально отказать в новой сессии клиенту,
но не вызывать exit(2) т.к. остальные смогут продолжить работу.

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

> 
>  в remove нету free ^_^ (а где-то он должен быть)

Нет, у Лёши в этом смысле всё верно. Потому что prioq_remove() только
извлекает элемент из очереди и ничего высвобождать не должна.

Теперь по ошибкам.

1.

Сначала мои ошибки и неточности, я в prioq_put() забыл сказать return
после проверки аргументов на NULL. На самом деле я привык делать макросы
и пользоваться ими, приведу их здесь:

#define return_if_fail(expr) \
{ \
	if (!(expr)) { \
		fprintf(stderr, "%s:%d:%s(): expression `%s' failed\n", \
			__FILE__, \
			__LINE__, \
			__FUNCTION__, \
			#expr); \
		return; \
	} \
}

#define return_val_if_fail(expr, val) \
{ \
	if (!(expr)) { \
		fprintf(stderr, "%s:%d:%s(): expression `%s' failed\n", \
			__FILE__, \
			__LINE__, \
			__FUNCTION__, \
			#expr); \
		return (val); \
	} \
}

Какой макрос использовать для проверки аргументов на валидность, зависит
от того возвращает ли функция какое-то значение или нет. Если не
возвращает, тогда мы просто делаем return. Если возвращает, тогда
используем return_val_if_fail. Эти макросы надо использовать для public
функций и проверять на валидность аргументы, если какие-то из них
обязательны и т.д.

Кроме того, я часто заключаю их в #ifdef DEBUG и делаю пустышки с такими
же именами, когда DEBUG не определён, т.е. этот код можно будет
исключить на стадии компиляции (после отладки).

#ifdef DEBUG

#define return_val_if_fail(expr, val) \
	....
#define return_if_fail(expr, val) \
	...
#else

#define return_val_if_fail(expr, val)
#define return_if_fail(expr, val)

#endif

Поэтому в prioq_put() стоило бы проверить аргументы так:

int prioq_put(struct prioq *q, struct prioq_head *h)
{
	int i;

	return_val_if_fail(q != NULL, -1);
	return_val_if_fail(h != NULL, -1);

	...
}

2. Лёша, алгоритмы у тебя не везде верно реализованы. Во-первых, ты
забываешь, что мы вынуждены в заголовке prioq_head поддерживать
правильнй индекс в очереди. Если у тебя где-то идёт перестановка
элементов, то ты должен менять это поле индекса корректно, иначе будет
проблема потом при удалении, потому что позиция элемента и поле индекса
не будут совпадать.

Я тебе говорил что в псевдокоде этого нет (ты сам знаешь где это сделать).

3. В prioq_heapify() посмотри внимательно на псевдокод и на то что у
тебя получилось.

if (queue->compare(queue->heap[largest], queue->heap[largest++]) < 0)
	largest++;

Вот здесь ошибка, потому что уже после проверки увеличивается largest на
1 и потом ещё раз увеличивается на 1. Сверься с псевдокодом, ведь там
largest в первый раз использовался как largset+1 (но само значение
largest не изменялось) и только потом, если условие было верно, к нему
прибавлялся 1.

4. В prioq_remove(), в Си есть и инкремент (++) и декремент (--) причём
оба могут быть как в префиксной форме (сначала изменяем значение,
изменённое значение результат выражения) и в постфиксной (значение
выражения изменяется после). Поэтому:

queue->used -= 1;

не хорошо, лучше:

queue->used--;

или (здесь без разницы):

--queue->used;

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

5. Ещё раз прошу обратить внимание на оформление, что-то всё уползает
куда-то. Да, и проверь компиляцию с -Wall, не должно быть предупреждений.

Что-то ещё замечу, напишу. Надо делать, тебе чуть-чуть осталось.

--
Г.А.