Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > PriorityQueue

annotate PriorityQueue.c @ 4:7254bef12749

find changesets by author, revision, files, or words in the commit message
removed "VMS" from function names -- names compatible with pure C version
author Me@portablequad
date Sat, 11 Feb 2012 20:29:34 -0800
parents 4d8a1e0f4336
children 09e51191078a
rev   line source
hausers@0 1 /*
hausers@0 2 * Copyright 2009 OpenSourceStewardshipFoundation.org
hausers@0 3 * Licensed under GNU General Public License version 2
hausers@0 4 *
hausers@0 5 * Author: hausers@cs.tu-berlin.de
hausers@0 6 */
hausers@0 7
hausers@0 8 #include <limits.h>
hausers@0 9 #include <stdio.h>
hausers@0 10 #include <string.h>
hausers@0 11
hausers@0 12 #include "PriorityQueue.h"
hausers@0 13 #ifndef DEBUG
hausers@1 14 #include "../../VMS_Implementations/VMS_impl/vmalloc.h"
hausers@0 15 #endif
hausers@0 16
hausers@0 17 #define left(i) 2*i
hausers@0 18 #define right(i) 2*i+1
hausers@0 19 #define parent(i) i/2
hausers@0 20
hausers@0 21 #ifdef DEBUG
hausers@0 22 #include <stdlib.h>
hausers@0 23 #define VMS__malloc malloc
hausers@0 24 #define VMS__free free
hausers@0 25 #endif
hausers@0 26
hausers@0 27 void swap (PrioQueueStruc *Q, int a, int b) {
hausers@0 28 void *valTmp;
hausers@0 29 int keyTmp;
hausers@0 30 keyTmp= Q->data[a].key;
hausers@0 31 valTmp= Q->data[a].val;
hausers@0 32 Q->data[a].key= Q->data[b].key;
hausers@0 33 Q->data[a].val= Q->data[b].val;
hausers@0 34 Q->data[b].key= keyTmp;
hausers@0 35 Q->data[b].val= valTmp;
hausers@0 36
hausers@0 37 }
hausers@0 38
hausers@0 39 bool increaseKey (PrioQueueStruc *Q, int i, int key) {
hausers@0 40 if (key < Q->data[i].key) return false; // increasing not possible
hausers@0 41
hausers@0 42 Q->data[i].key= key;
hausers@0 43 while (i>0 && Q->data[parent(i)].key < Q->data[i].key) {
hausers@0 44 swap(Q,i,parent(i));
hausers@0 45 i= parent(i);
hausers@0 46 }
hausers@0 47 return true;
hausers@0 48 }
hausers@0 49
hausers@0 50 void heapify (PrioQueueStruc *Q, int i) {
hausers@0 51 int largest;
hausers@0 52 int l,r;
hausers@0 53 l= left(i);
hausers@0 54 r= right(i);
hausers@0 55 if (l < Q->size && Q->data[l].key > Q->data[i].key) largest= l;
hausers@0 56 else largest= i;
hausers@0 57 if (r < Q->size && Q->data[r].key > Q->data[largest].key) largest= r;
hausers@0 58 if (largest != i) {
hausers@0 59 swap(Q,i,largest);
hausers@0 60 heapify(Q,largest);
hausers@0 61 }
hausers@0 62 }
hausers@0 63
hausers@0 64 void enlargePrioQ (PrioQueueStruc *Q) {
hausers@0 65 size_t oldSize, newSize;
hausers@0 66 heapNode *oldData,*newData;
hausers@0 67
hausers@0 68 oldSize= Q->size;
hausers@0 69 newSize= 2*oldSize;
hausers@0 70
hausers@0 71 Q->maxSize= newSize;
hausers@0 72 newData= VMS__malloc(Q->maxSize*sizeof(heapNode));
hausers@0 73 oldData= Q->data;
hausers@0 74
hausers@0 75 memcpy(newData,oldData,Q->maxSize*sizeof(heapNode));
hausers@0 76 Q->data= newData;
hausers@0 77
hausers@0 78 VMS__free(oldData);
hausers@0 79 }
hausers@0 80
hausers@0 81
Me@4 82 PrioQueueStruc* makePrioQ () {
hausers@0 83 PrioQueueStruc *retQ;
hausers@0 84 retQ= VMS__malloc(sizeof(PrioQueueStruc));
hausers@0 85 retQ->maxSize= 1024;
hausers@0 86 retQ->data= VMS__malloc(retQ->maxSize*sizeof(heapNode));
hausers@0 87 retQ->size= 0;
hausers@0 88 return retQ;
hausers@0 89 }
hausers@0 90
hausers@0 91 void* getFirstPrioQ (PrioQueueStruc *Q) {
hausers@0 92 return Q->data[0].val;
hausers@0 93 }
hausers@0 94
hausers@0 95 void* popPrioQ (PrioQueueStruc *Q) {
hausers@0 96 void *max;
hausers@0 97 if (Q->size < 1) max= NULL;
hausers@0 98 else {
hausers@0 99 max= Q->data[0].val;
hausers@0 100 swap(Q,0,Q->size-1);
hausers@0 101 Q->size--;
hausers@0 102 heapify(Q,0);
hausers@0 103 }
hausers@0 104 return max;
hausers@0 105 }
hausers@0 106
hausers@0 107 bool insertPrioQ (void *val, int key, PrioQueueStruc *Q) {
hausers@0 108 if (Q->size == Q->maxSize) enlargePrioQ(Q);
hausers@0 109
hausers@0 110 Q->size++;
hausers@0 111 Q->data[Q->size-1].key= INT_MIN;
hausers@0 112 Q->data[Q->size-1].val= val;
hausers@0 113
hausers@0 114 return increaseKey(Q,Q->size-1,key);
hausers@0 115 }
hausers@0 116
hausers@0 117 void printPrioQ (PrioQueueStruc *Q) {
hausers@0 118 int i;
hausers@0 119 printf("{");
hausers@0 120 if (Q->size>0) printf("%s",(char *)Q->data[0].val);
hausers@0 121 for (i= 1; i<Q->size; i++) printf(",%s",(char *)Q->data[i].val);
hausers@0 122 printf("} ... ");
hausers@0 123
hausers@0 124 }
hausers@0 125
hausers@0 126 void freePrioQ (PrioQueueStruc *Q) {
hausers@0 127 VMS__free(Q->data);
hausers@0 128 VMS__free(Q);
hausers@0 129 }