priority queue with double priority

[COKEDUDE]

I am using a priority queue with a double as the priority. I am guessing this is cause so issues. I used these numbers first with no issues.

34.365681
34.481879
34.539832
36.715120

I then used these numbers and had a segmentation fault.

45.411042
40.481879
37.702110
38.951187

struct PRIORITYQUEUE
    {
    int x_pq; 
    int y_pq;
    double heuristic_pq;
    int priority;
    int info;
    struct PRIORITYQUEUE *next;
}*start, *q, *temp, *new;

typedef struct PRIORITYQUEUE *N;

void insert(int x, int y, double heuristic)
{

    int item; 
    double itprio;
    //new = ( N* ) malloc( sizeof( N ) );
    new = malloc( sizeof( N ) );

    itprio = heuristic;
    new->x_pq = x;
    new->y_pq = y;
    new->heuristic_pq = itprio;

    if ( start == NULL || itprio < start->heuristic_pq )
    {
        new->next = start;
        start = new;
    }
    else
        {
            q = start;
            while ( q->next != NULL && q->next->heuristic_pq <= itprio )
                q = q->next;

            new->next = q->next;
            q->next = new;
        }
}

void del()
{
    if ( start == NULL )
    {
         printf( "\nQUEUE UNDERFLOW\n" );
    }
    else
    {
    new = start;
    printf( "\nDELETED ITEM IS %d\n", new->info );
    start = start->next;
    free( start );

    }

}

void display()
{
    temp = start;
    if ( start == NULL )
        printf( "QUEUE IS EMPTY\n" );

    else
    {
        printf( "QUEUE IS:\n" );

        while ( temp != NULL )
        {
            printf( "\t x is %d y is %d[heuristic=%lf] \n", temp->x_pq, temp->y_pq, temp->heuristic_pq );
            temp = temp->next;
        }
     }
}

[Schol-R-LEA]

The problem is not in the numbers used, but in the size of the memnory being allocated. The type N is a pointer type, which means that it is likely to be one system word long (probably either 32 or 64 bits, assuming a common Intel or AMD CPU, though it could be 36 on a 32-bit PC with PAE enabled I guess). The structure you want to allocate memory for, however, consists of 4 ints, a double, and a pointer to the struct type, making at least 6 times as large as the amount of memory you are actually allocating.

The solution is to get rid of the typedef entirely, as you aren't using it anywhere else anyway, and just use

new = malloc(sizeof(struct PRIORITYQUEUE));

This will ensure that you have the right memory allocation.

Also, as I told you in my previous post, the del() function is flawed. You want to free new, not start, otherwise you'll lose the whole list and that could also cause the segfault.

I hope you are initializing start to NULL in your main() program. Just to be on the safe side, I would recommend adding a function init_pq() that just nulls out all the global variables used by these functions.

void init_pq()
{
    start = q = temp = new = NULL;
}    

Call that at the beginning of your program and it will ensure that you should get any initialization problems.

Finally, as I said before, this isn't a typical implementation of a priority queue. They usually are built using a data structure called a heap, which is a tree structure in which the keys of the nodes at any given level are always higher (or lower, depending on the ordering) values than those of nodes below them. It is a much more efficient way to implement a priority queue than a linked list, and I would recommend that if you expect your queue to get larger than a dozen or so elements, you should consider using a heap structure instead of a list.

Oh, and please be more consistent with your indentation. Also, why do you need a double for your priority? It doesn't make sense to do that. What is the real goal here?

[COKEDUDE]

I changed the malloc part, added the initialization part, fixed the del() function. My priority is coming from the calculation of a distance formula. As you know when calculating the distance formula you don't always have have pretty numbers. You sometimes get long decimal numbers.

Why didn't it crash after removing like 20 numbers? I used this. The only real change I made to it was changing the malloc part because I got this warning. Was I just lucky or do you have to do something special to remove it?

warning: assignment from incompatible pointer type

   //new = ( N* ) malloc( sizeof( N ) );
    new = malloc( sizeof( N ) );

http://matrixsust.blogspot.com/2011/11/basic-priority-queue-in-c.html

[Schol-R-LEA]

It's very hard to say why it didn't crash, but I'd say mostly you were lucky. What I think may have happened was that you were deleting the elements but not allocating new ones, in which instance it was likely that the freed memory still held the same data it had when it was freed. If you had been alternating deleting and adding nodes, things may have gone differently. The real question to my mind is, why didn't it segfault when you allocated too small a space for the elements in the first place. but the answer to that would depend on the details of the memory allocator. I'm betting, though, if you had entered several nodes in the list, and then gone to look at the earlier entries, you would have found that they were partially overwritten with data from the successive nodes - though again, the details of it depend on how the memory was being allocated.