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

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

Написал prioq_get, посмотрите.
----------- следущая часть -----------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define RIGHT_CHILD(i)  (((i) * 2) + 2)
#define PARENT(i)       (((i) - 1) / 2)
#define INIT_SIZE 2
#define GROW_SIZE	32
typedef int (*prioq_compare_t)(struct prioq_head *a, struct prioq_head *b);

struct prioq_head{
	    unsigned int index;
};		

struct user_data{
        struct prioq_head head;
		int data;
};		

struct prioq{
        struct prioq_head **heap;
	    size_t size;
        size_t used;
        prioq_compare_t compare;
};	


/*Создание очереди */
struct prioq *
prioq_new(prioq_compare_t compare)
{
	struct prioq *queue;

	queue = (struct prioq*)malloc(sizeof(struct prioq));

	if (queue == NULL) {
		fprintf(stderr, "prioq_new: can't allocate queue\n");
		return NULL;
	}

	memset(queue, 0, sizeof(*queue));

	queue->heap = (struct prioq_head**)malloc(sizeof(struct prioq_head *) * INIT_SIZE);

	if (queue->heap == NULL) {
		fprintf(stderr, "prioq_new: can't allocate heap\n");
		free(queue);
		return NULL;
	}

	memset(queue->heap, 0, sizeof(struct prioq_head *) * INIT_SIZE);

	queue->size = INIT_SIZE;
	queue->used = 0;
	queue->compare = ((compare != NULL) ? compare : compare);

	return queue;
}

#define NEW_SIZE(q)	(((q)->size + GROW_SIZE) * sizeof(struct prioq_head *))
#define OLD_SIZE(q)	((q)->size * sizeof(struct prioq_head *))

int prioq_put(struct prioq *queue, struct prioq_head *hp){

    int i;
	struct prioq_head** tmp;

	if (queue == NULL || hp == NULL) {
		fprintf(stderr, "prioq_put: NULL args\n");
		return NULL; 
    }
	if (queue->size == queue->used) {
		tmp = (struct prioq_head**)realloc(queue->heap, NEW_SIZE(queue));
		if (!tmp) {
			fprintf(stderr, "prioq_put: can't realloc heap\n");
			return -1;
		}
		queue->heap = tmp;
		memset(queue->heap + OLD_SIZE(queue), 0,
		       NEW_SIZE(queue) - OLD_SIZE(queue));
		queue->size += GROW_SIZE;
		
	}

	i = queue->used++;

	while (i && queue->compare(queue->heap[PARENT(i)], hp) < 0) {
 		queue->heap[i] = queue->heap[PARENT(i)];
		queue->heap[i]->index = i;
		i = PARENT(i);
	}

	queue->heap[i] = hp;
	hp->index = i;
    
	return 0;

}	

/*Функция сравнения*/
int
compare(struct prioq_head *a, struct prioq_head *b)
{
	struct user_data *ap = (struct user_data *) a;
	struct user_data *bp = (struct user_data *) b;

	if (ap->data > bp->data)
		return 1;
	else if (ap->data < bp->data)
		return -1;
	return 0;
}

/*---------------------------------------------*/
#define LEFT_CHILD(i)   (((i) * 2) + 1) 
int
prioq_heapify(struct prioq *queue)
{
    unsigned int index, largest;	
	
	struct prioq_head* tmp;
	
	for (index = 0,largest = LEFT_CHILD(index);
	    largest < queue->used;
        index = largest, largest = LEFT_CHILD(index)) {
		
        if (queue->compare(queue->heap[largest],
			queue->heap[largest+1]) < 0) {
            
			largest++;			
        }
	    if (queue->
			compare(queue->heap[index],
			queue->heap[largest])<0) {
			
			tmp = queue->heap[largest];
			queue->heap[largest] = queue->heap[index];
			queue->heap[largest]->index = index;
			queue->heap[index] = tmp;
			queue->heap[index]->index = largest;
		}
		else return 0;
	}	
	if ((largest == queue->used) 
		&& (queue->compare(queue->heap[index],
		    queue->heap[largest]) < 0)) {
        
		tmp = queue->heap[largest];
		queue->heap[largest] = queue->heap[index];
		queue->heap[largest]->index = index;
		queue->heap[index] = tmp;
		queue->heap[index]->index = largest;
	}
	
	return 1;	
}


/*------------------------------------------------*/
void 
prioq_remove(struct prioq *queue, struct prioq_head *hp) 
{
    
	if (hp->index > queue->used)
        fprintf(stderr,"prioq_remove: index out of range\n");
	
	int index = hp->index;
	
	while (index > 0){
	    queue->heap[index] = queue->heap[PARENT(index)];
		queue->heap[index]->index = PARENT(index); 
        index = PARENT(index);
	}
	
	queue->used--;
	
	int used = queue->used;
	queue->heap[0] = queue->heap[used];
    queue->heap[0]->index = used;
	prioq_heapify(queue);
}	

void
prioq_free(struct prioq* queue)
{
    if (queue == NULL) {
        fprintf(stderr,	"prioq_free:The queue not exists\n");
	}	
	else {
	    free(queue->heap);
		free(queue);
		fprintf(stderr,"prioq_free: the queue is free\n");	
	}
	
}	

struct prioq_head *
prioq_peek(struct prioq*queue) 
{
    struct user_data* ptr;
	struct prioq_head* head = queue->heap[0];
	if (queue == NULL) {
		fprintf(stderr,
		"prioq_peek: Can't peek head from queue\n");
		return NULL;
	}
 	if (queue != NULL) {
	    
		if (queue->heap == NULL) {
			fprintf(stderr,
		    "prioq_peek: Can't peek head from queue\n");
		    return NULL;
		} 
		if ((queue->heap != NULL) 
			 && (head != NULL)) {
			ptr = (struct user_data*)head;
	        fprintf(stderr,"prioq_peek:head of queue\n data:%i\n index:%d\n",ptr->data,0);
		}
		else {
            fprintf(stderr,
		    "prioq_peek: Can't peek head from queue\n");
		    return NULL;
 		}	
	}
	return head;
}

struct prioq_head *
prioq_get(struct prioq*queue)
{
	struct prioq_head* head = queue->heap[0];
	struct user_data* ptr;
	unsigned int used;
	
	if (queue == NULL) {
		fprintf(stderr,
		"prioq_get: Can't extract head from queue \n");
		return NULL;
	}
	if ((queue != NULL) && (head != NULL)) {
		ptr = (struct user_data*)head;
		fprintf(stderr,
		"prioq_get: the head of queue\n %d-data\n %d-index",
		ptr->data,0);
		
		used = queue->used;
		if (used > 1) {
		    queue->heap[0] = queue->heap[used];
		    queue->heap[0]->index = used;
		    queue->used--;
		    free(queue->heap[used]);
		    prioq_heapify(queue);
	    } 
		else if (used == 1) {
				free(queue->heap[0]);
				queue->used--;
		}
        else return NULL; 		
	}	
	return head;	
}	
	
int main(void){
    struct prioq *q=prioq_new(compare); 
    struct user_data a,b;
	struct prioq_head *p,*s;
	//struct user_data* dat;
		
    a.data = 0;
    b.data = 5;
	p = &a.head;
	s = &b.head;
		
	prioq_put(q,p);
	prioq_put(q,s);
	prioq_peek(q);
	prioq_get(q);
	
	return q->used;	
}