[cdev] Дайджест списка рассылки cdev; том 3, выпуск 5

[Алексей Петрунёв]

Я просто потерял листок с распечаткой псевдокода где находилась ф-я
prioq_get, так что сам немного лишнего написал. Вот, исправил:

struct prioq_head *
prioq_get(struct prioq*queue)
{
	struct prioq_head* head;
	struct user_data* ptr;
	unsigned int used;
	
	if (queue->used == 0) {
		fprintf(stderr,
		"prioq_get: Can't extract head from queue \n");
		return NULL;
	}
   	head =  queue->heap[0];
	ptr = (struct user_data*)head;
	printf("data %d\n index %d\n",ptr->data,0);
	used = queue->used - 1;
	queue->heap[0] = queue->heap[used];
	queue->heap[0]->index = used;
	queue->used--;
	prioq_heapify(queue);
        queue->heap[used] = NULL; 	
	return head;	
}	

А почему не обуляется (в псевдокоде) указатель queue->heap[used]?  Мы
его присваиваем  queue->heap[0], а потом сортируем в prioq_heapify
массив состоящий уже из used-1 элементов. Но queue->heap[used] так и
висит в памяти, когда массив уже меньше на 1.

6 апреля 2010 г. 12:00 пользователь  <cdev-request на wiki.syktsu.ru> написал:
> Сообщения, предназначенные для списка рассылки cdev, необходимо
> отправлять по адресу
>        cdev на wiki.syktsu.ru
>
> Для изменения параметров подписки вы можеже использовать веб-страницу
>        http://wiki.syktsu.ru/cgi-bin/mailman/listinfo/cdev
>
> Для получения информации о том, как пользовать почтовым интерфейсом,
> отправьте письмо, в теле или теме которого будет слово 'help', по
> адресу:
>        cdev-request на wiki.syktsu.ru
>
> Адрес человека, ответственного за этот список рассылки:
>        cdev-owner на wiki.syktsu.ru
>
> При ответе, пожалуйста, измение тему письма так, чтобы она была более
> содержательной чем "Re: Содержание дайджеста списка рассылки cdev..."
>
>
> В этом номере:
>
>   1. Re: Задача_6. гр 135 (Grigoriy A. Sitkarev)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Mon, 05 Apr 2010 21:25:40 +0400
> From: "Grigoriy A. Sitkarev" <sitkarev на komitex.ru>
> Subject: Re: [cdev] Задача_6. гр 135
> To: Young C/UNIX developers <cdev на wiki.syktsu.ru>
> Message-ID: <4BBA1D14.30401 на komitex.ru>
> Content-Type: text/plain; charset=UTF-8; format=flowed
>
> Лёша, в программе есть ошибки.
>
> Функция prioq_get выглядит более чем странно.
>
> 1. Пользователь передаёт нам указатель на queue. Мы решили следовать
> хорошему правилу - проверять указатели на NULL, чтобы отлавливать
> возможные ошибки пользователя при программировании (забыл что высвободил
> аргумент и он теперь NULL например). Нулевой указатель разыменовывать
> нельзя, это ошибка и программа завершится аварийно.
>
> Попробуй сделать вот так:
>
> ((struct prioq *)(NULL))->heap
>
> и немедленно прилетит сигнал SIGSEGV и программа завершится.
>
> Ты до того как проверяешь queue на NULL уже разыменовываешь этот
> (потенциально нулевой) указатель ещё в определении локальных переменных:
>
> struct prioq_head *
> prioq_get(struct prioq*queue)
> {
>        struct prioq_head* head = queue->heap[0];
>        struct user_data* ptr;
>
>
> Это ошибка, так делать нельзя. Поэтому head ты можешь присваивать
> значение только после того как проверил queue на NULL.
>
> Далее, очень сложно сделано, Лёша, зачем? Ведь после того как ты
> проверил queue на NULL, дальше этого делать не надо, тебе известно точно
> что он уже не нулевой указатель. Поэтому такая конструкция избытона:
>
> if ((queue != NULL) && (head != NULL))
>
> Она не нужна.
>
> 2. Ты не корректно реализовал то что было в псевдокоде, посмотри ещё
> раз. Обрати внимание, что прежде чем индексироваться в queue->heap мы
> уменьшили used на 1. У тебя декремент идёт после! Поэтому программа
> сваливается (в лучшем случае, потому что там в массиве указателей они
> NULL) а в худшем будешь искать почему "не тот" элемент получили.
>
> e = queue[0];
> queue.used = queue.used - 1;
> queue[0] = queue[queue.used];
>
> prioq_heapify(queue);
>
> Здесь сначала  уменьшили used на 1 и потом индексируемся. Ведь последний
> элемент имеет индекс queue.used-1, так?
>
> queue->heap[0] = queue->heap[used]; <- лезем в чужую ячейку
> queue->heap[0]->index = used;
> queue->used--;  <- и только теперь уменьшили
>
> Кроме того, зачем ты освобождаешь там указатель с польз. данными?? Этого
> делать не надо, потому что это пользователь только знает, надо их
> освобождать или нет. Твоя очередь не размещала их в памяти, не ей и их
> освобождать.
>
> Ещё раз пересмотри пожалуйста алгоритм извлечения элемента из очереди.
> Он же очень простой, но у тебя он катастрофически сложен!
>
> Что-то с оформлением у нас безобразие, всё уплывает, читать тяжеловато,
> если честно. Посмотри пожалуйста LKCS, внимательно прочитай и далее
> придерживайся этого стиля при программировании на Си таких вещей, хотя
> повторюсь что это не догма. И много предупреждений выдаёт gcc, надо
> править всё.
>
> 3. Если тебе что-то не понятно, как работает на Си, задай вопросы.
> Потому что просто писать что что тебя просят это копировать форму, но не
> содержание, т.е. тебе будет понятно КАК но ЗАЧЕМ - нет. Надо это
> исправить, потому что задача здесь именно понять ЗАЧЕМ.
>
> --
> Г.А.
>
> Алексей Петрунёв пишет:
>> Написал prioq_get, посмотрите.
>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> cdev mailing list
>> cdev на wiki.syktsu.ru
>> http://wiki.syktsu.ru/cgi-bin/mailman/listinfo/cdev
>
>
>
>
> ------------------------------
>
> _______________________________________________
> cdev mailing list
> cdev на wiki.syktsu.ru
> http://wiki.syktsu.ru/cgi-bin/mailman/listinfo/cdev
>
>
> Конец Дайджест списка рассылки cdev; том 3, выпуск 5
> ****************************************************
>