1 /* 2 3 Copyright (C) 2015-2018 Night Dive Studios, LLC. 4 5 This program is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation, either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. 17 18 */ 19 #ifndef __PQUEUE_H 20 #define __PQUEUE_H 21 22 /* 23 * $Source: n:/project/lib/src/dstruct/RCS/pqueue.h $ 24 * $Revision: 1.1 $ 25 * $Author: mahk $ 26 * $Date: 1993/08/09 20:31:11 $ 27 * 28 * $Log: pqueue.h $ 29 * Revision 1.1 1993/08/09 20:31:11 mahk 30 * Initial revision 31 * 32 * 33 */ 34 35 // ----------------------------------- 36 // Priority Queue Abstraction 37 // ----------------------------------- 38 /* Herein lies a binary heap implementation of a priority queue 39 The queue can have elements of any size, as the client specifies 40 the element size and comparison function. */ 41 42 43 44 45 // Includes 46 #include "lg.h" // every file should have this 47 #include "error.h" 48 #include <stdio.h> 49 #include <stdint.h> 50 51 // Defines 52 // Comparson function, works like strcmp 53 typedef int (*QueueCompare)(void* elem1, void* elem2); 54 55 #pragma pack(push,2) 56 typedef struct _pqueue 57 { 58 int32_t size; 59 int32_t fullness; 60 int32_t elemsize; 61 uchar grow; 62 char* vec; 63 QueueCompare comp; 64 } PQueue; 65 66 // Prototypes 67 errtype pqueue_init(PQueue* q, int size, int elemsize, QueueCompare comp, uchar grow); 68 // Initializes a Priority queue to a particular size, with a 69 // particular element size and comparison function. 70 71 errtype pqueue_insert(PQueue* q, void* elem); 72 // Insert an element into the queue (log time) 73 74 errtype pqueue_extract(PQueue* q, void* elem); 75 // Copies the least element in the queue into *elem, 76 // and removes that element. (log time) 77 78 errtype pqueue_least(PQueue* q, void* elem); 79 // Copies the least element into *elem, but does not 80 // remove it. (constant time) 81 82 errtype pqueue_write(PQueue* q,FILE *fd,void (*writefunc)(FILE *fd,void* elem)); 83 // Writes out a queue to file number fd, calling writefunc to write out each element. 84 // If writefunc is NULL, simply writes the literal data in each element. 85 86 errtype pqueue_read(PQueue* q, FILE *fd, void (*readfunc)(FILE *fd, void* elem)); 87 // Reads in a queue from file number fd, calling readfunc to read each element. 88 // If readfunc is NULL, reads each element literally. 89 90 errtype pqueue_destroy(PQueue* q); 91 // Destroys a priority queue. 92 93 94 95 96 97 // Globals 98 99 #pragma pack(pop) 100 101 #endif // __PQUEUE_H 102