home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Fish 'n' More 2
/
fishmore-publicdomainlibraryvol.ii1991xetec.iso
/
dirs
/
dkbtrace_397.lzh
/
DKBTrace
/
DKBSource.LZH
/
showprioq.c
< prev
next >
Wrap
C/C++ Source or Header
|
1990-08-26
|
6KB
|
220 lines
/*****************************************************************************
*
* showprioq.c
*
* from DKBTrace (c) 1990 David Buck
*
* This file manages a priority queue for DumpToIFF
*
* This software is freely distributable. The source and/or object code may be
* copied or uploaded to communications services so long as this notice remains
* at the top of each file. If any changes are made to the program, you must
* clearly indicate in the documentation and in the programs startup message
* who it was who made the changes. The documentation should also describe what
* those changes were. This software may not be included in whole or in
* part into any commercial package without the express written consent of the
* author. It may, however, be included in other public domain or freely
* distributed software so long as the proper credit for the software is given.
*
* This software is provided as is without any guarantees or warranty. Although
* the author has attempted to find and correct any bugs in the software, he
* is not responsible for any damage caused by the use of the software. The
* author is under no obligation to provide service, corrections, or upgrades
* to this package.
*
* Despite all the legal stuff above, if you do find bugs, I would like to hear
* about them. Also, if you have any comments or questions, you may contact me
* at the following address:
*
* David Buck
* 22C Sonnet Cres.
* Nepean Ontario
* Canada, K2H 8W7
*
* I can also be reached on the following bulleton boards:
*
* ATX (613) 526-4141
* OMX (613) 731-3419
* Mystic (613) 731-0088 or (613) 731-6698
*
* Fidonet: 1:163/109.9
* Internet: David_Buck@Carleton.CA
*
*
*****************************************************************************/
#include <stdio.h>
#include <exec/types.h>
#include "showprioq.h"
#include "dumptoiff.h"
#include "dumproto.h"
char *malloc();
struct prioq_struct *pq_new (index_size, value_size)
int index_size, value_size;
{
struct prioq_struct *pq;
unsigned char *tmp_array;
int i;
if (index_size > 256)
return (NULL);
if ((pq = (struct prioq_struct *) malloc
(sizeof (struct prioq_struct))) == NULL)
return (NULL);
if ((pq -> queue = (struct q_entry *)
malloc (index_size * sizeof (struct q_entry))) == NULL) {
free (pq);
return (NULL);
}
if ((pq -> array = (unsigned char *) malloc (value_size)) == NULL) {
free (pq -> queue);
free (pq);
return (NULL);
}
for (i=0, tmp_array = pq -> array ; i<value_size ; i++, tmp_array++)
*tmp_array = 0;
pq -> queue_size = index_size;
pq -> array_size = value_size;
pq -> current_entry = 0;
return (pq);
}
void pq_add (q, index, value)
struct prioq_struct *q;
unsigned int index, value;
{
unsigned int existing_entry;
if (value >= q -> array_size)
return;
if ((existing_entry = pq_find_value(q, value)) != 0) {
if ((q -> queue[existing_entry].index) < index)
(q -> queue[existing_entry].index) = index;
pq_balance (q, existing_entry);
}
else {
q -> current_entry++;
if (q -> current_entry >= q -> queue_size) {
q -> current_entry--;
q -> array [q->queue[q->current_entry].value] = 0;
}
q -> queue [q -> current_entry].index = index;
q -> queue [q -> current_entry].value = value;
q -> array [value] = q -> current_entry;
pq_balance (q, q -> current_entry);
}
return;
}
int pq_find_value (q, value)
struct prioq_struct *q;
unsigned int value;
{
if (value < q -> array_size)
return ((int) q -> array[value]);
else
return (0);
}
void pq_balance(q, entry_pos1)
struct prioq_struct *q;
unsigned int entry_pos1;
{
register struct q_entry *entry1, *entry2;
register unsigned int tmp_index, tmp_value, entry_pos2;
entry1 = &q->queue[entry_pos1];
if ((entry_pos1 * 2 < q->queue_size)
&& (entry_pos1 * 2 <= q -> current_entry))
{
if ((entry_pos1*2+1 > q->current_entry) ||
(q->queue[entry_pos1*2].index > q->queue[entry_pos1*2+1].index))
entry_pos2 = entry_pos1*2;
else
entry_pos2 = entry_pos1*2+1;
entry2 = &q->queue[entry_pos2];
if (entry1->index < entry2->index) {
q -> array [entry1->value] = entry_pos2;
q -> array [entry2->value] = entry_pos1;
tmp_index = entry1->index;
entry1->index = entry2->index;
entry2->index = tmp_index;
tmp_value = entry1->value;
entry1->value = entry2->value;
entry2->value = tmp_value;
pq_balance (q, entry_pos2);
}
}
if (entry_pos1 / 2 >= 1 )
{
entry_pos2 = entry_pos1 / 2;
entry2 = &q->queue[entry_pos2];
if (entry1->index > entry2->index) {
q -> array [entry1->value] = entry_pos2;
q -> array [entry2->value] = entry_pos1;
tmp_index = entry1->index;
entry1->index = entry2->index;
entry2->index = tmp_index;
tmp_value = entry1->value;
entry1->value = entry2->value;
entry2->value = tmp_value;
pq_balance (q, entry_pos2);
}
}
}
int pq_get_highest_index(q)
struct prioq_struct *q;
{
if (q -> current_entry >= 1)
return ((int) q -> queue[1].index);
else
return (0);
}
int pq_get_highest_value(q)
struct prioq_struct *q;
{
if (q -> current_entry >= 1)
return ((int) q -> queue[1].value);
else
return (0);
}
void pq_delete_highest (q)
struct prioq_struct *q;
{
q -> queue[1].index = q -> queue[q -> current_entry].index;
q -> queue[1].value = q -> queue[q -> current_entry--].value;
pq_balance (q, 1);
}
void pq_free (q)
struct prioq_struct *q;
{
free (q ->queue);
free (q -> array);
free (q);
}