Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Explanation

Reply
Thread Tools

Explanation

 
 
Alessandro Zucchini
Guest
Posts: n/a
 
      07-22-2004
does someone can understand this function?can you explain me what do they do
one by one?thankyou

PQUEUE *pqueue_new(void)
{
PQUEUE *pq;

if ((pq = (PQUEUE *) my_malloc(sizeof(PQUEUE))) == NULL)
return (NULL);
pq->count = 0;
pq->priorities = NULL;
return pq;
}

int pqueue_insert(PQUEUE * pq, COORD coord, int wt)
{
ELIST *e;
PLIST *p, *pp;

if (pq == NULL)
return -1;

if ((e = (ELIST *) my_malloc(sizeof(ELIST))) == NULL)
return -1;
e->coord = coord;
e->next = NULL;


if (pq->priorities == NULL || pq->priorities->wt > wt) {

if ((p = (PLIST *) my_malloc(sizeof(PLIST))) == NULL)
return -1;

p->wt = wt;
p->elements = e;
p->next = pq->priorities;
pq->priorities = p;
pq->count++;

return 0;
}
pq->count++;

for (p = pq->priorities; p->next && p->next->wt <= wt; p = p->next);

if (p->wt == wt) {
e->next = p->elements;
p->elements = e;
return 0;
}
if ((pp = (PLIST *) my_malloc(sizeof(PLIST))) == NULL)
return -1;

pp->wt = wt;
pp->elements = e;
pp->next = p->next;
p->next = pp;
pq->count++;

return 0;
}

int pqueue_peekmin(PQUEUE * pq, PCOORD coord)
{
if (pq == NULL || pq->priorities == NULL || pq->priorities->elements ==
NULL)
return -1;

*coord = pq->priorities->elements->coord;

return 0;
}

int pqueue_popmin(PQUEUE * pq, PCOORD coord)
{
ELIST *tmpe;
PLIST *tmpp;

if (pqueue_peekmin(pq, coord) < 0)
return -1;

pq->count--;

tmpe = pq->priorities->elements;
pq->priorities->elements = pq->priorities->elements->next;
my_free(tmpe, sizeof(ELIST));

if (pq->priorities->elements == NULL) {
tmpp = pq->priorities;
pq->priorities = pq->priorities->next;
my_free(tmpp, sizeof(PLIST));
}
return 0;
}


 
Reply With Quote
 
 
 
 
Richard Bos
Guest
Posts: n/a
 
      07-22-2004
"Alessandro Zucchini" <(E-Mail Removed)> wrote:

> does someone can understand this function?can you explain me what do they do
> one by one?thankyou


Well, a couple of type definitions wouldn't have gone amiss, but it
looks like code for handling a priority queue. You can call pqueue_new()
to create a new, empty queue; pqueue_insert() to insert a new item with
priority wt and payload coord into a queue; and pqueue_peekmin() and
pqueue_popmin() to look at, resp. pop, the first element with maximum
priority off the queue.
Note that:
- if the queue can get large, a tree may be a better implementation than
a list;
- this higher-level interface makes it possible to switch to a tree
implementation without many changes, if any at all, to the user code,
should it become necessary, and is thus a Good Thing;
- pqueue_peekmin() and pqueue_popmin() seem misnamed to me, since they
refer to the element with the _maximum_, not minimum, priority;
- should I comment on the wisdom of casting malloc(), or writing a
malloc() wrapper which does not return a void *? Thought not.

Richard
 
Reply With Quote
 
 
 
 
Karthik
Guest
Posts: n/a
 
      07-23-2004
Alessandro Zucchini wrote:

> does someone can understand this function?can you explain me what do they do
> one by one?thankyou
>
> PQUEUE *pqueue_new(void)
> {
> PQUEUE *pq;
>
> if ((pq = (PQUEUE *) my_malloc(sizeof(PQUEUE))) == NULL)
> return (NULL);
> pq->count = 0;
> pq->priorities = NULL;
> return pq;
> }
>
> int pqueue_insert(PQUEUE * pq, COORD coord, int wt)
> {
> ELIST *e;
> PLIST *p, *pp;
>
> if (pq == NULL)
> return -1;
>
> if ((e = (ELIST *) my_malloc(sizeof(ELIST))) == NULL)
> return -1;
> e->coord = coord;
> e->next = NULL;
>
>
> if (pq->priorities == NULL || pq->priorities->wt > wt) {
>
> if ((p = (PLIST *) my_malloc(sizeof(PLIST))) == NULL)
> return -1;
>
> p->wt = wt;
> p->elements = e;
> p->next = pq->priorities;
> pq->priorities = p;
> pq->count++;
>
> return 0;
> }
> pq->count++;
>
> for (p = pq->priorities; p->next && p->next->wt <= wt; p = p->next);
>
> if (p->wt == wt) {
> e->next = p->elements;
> p->elements = e;
> return 0;
> }
> if ((pp = (PLIST *) my_malloc(sizeof(PLIST))) == NULL)
> return -1;
>
> pp->wt = wt;
> pp->elements = e;
> pp->next = p->next;
> p->next = pp;
> pq->count++;
>
> return 0;
> }
>
> int pqueue_peekmin(PQUEUE * pq, PCOORD coord)
> {
> if (pq == NULL || pq->priorities == NULL || pq->priorities->elements ==
> NULL)
> return -1;
>
> *coord = pq->priorities->elements->coord;
>
> return 0;
> }
>
> int pqueue_popmin(PQUEUE * pq, PCOORD coord)
> {
> ELIST *tmpe;
> PLIST *tmpp;
>
> if (pqueue_peekmin(pq, coord) < 0)
> return -1;
>
> pq->count--;
>
> tmpe = pq->priorities->elements;
> pq->priorities->elements = pq->priorities->elements->next;
> my_free(tmpe, sizeof(ELIST));
>
> if (pq->priorities->elements == NULL) {
> tmpp = pq->priorities;
> pq->priorities = pq->priorities->next;
> my_free(tmpp, sizeof(PLIST));
> }
> return 0;
> }
>
>

I would suggest to get a good book on data structures and look out
for priority queues and what they mean. And then of course, about lists
( singly linked lists). Then come back to this code. It would be much
simple to understand this then.


--
Karthik
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Simple Explanation to Networking Wirelessly?? Jaxim Wireless Networking 4 08-19-2005 05:04 AM
explanation Mariusz VHDL 1 01-13-2004 02:10 AM
Debug message explanation Dean Cisco 1 01-07-2004 12:38 PM
DVMRP Explanation Acer0001 Cisco 0 11-20-2003 04:41 AM
Need Explanation Kaladhaur Palaniappa Perl 0 08-07-2003 09:47 AM



Advertisments