heap.c
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include <stdio.h>
00022 #include <stdlib.h>
00023
00024 #include "type.h"
00025 #include "heap.h"
00026
00027
00028
00029 void dglHeapInit(dglHeap_s * pheap)
00030 {
00031 pheap->index = 0;
00032 pheap->count = 0;
00033 pheap->block = 256;
00034 pheap->pnode = NULL;
00035 }
00036
00037 void dglHeapFree(dglHeap_s * pheap, dglHeapCancelItem_fn pfnCancelItem)
00038 {
00039 int iItem;
00040
00041 if (pheap->pnode) {
00042 if (pfnCancelItem) {
00043 for (iItem = 0; iItem <= pheap->index; iItem++) {
00044 pfnCancelItem(pheap, &pheap->pnode[iItem]);
00045 }
00046 }
00047 free(pheap->pnode);
00048 }
00049 pheap->pnode = NULL;
00050 }
00051
00052 int dglHeapInsertMin(dglHeap_s * pheap,
00053 long key, unsigned char flags, dglHeapData_u value)
00054 {
00055 long i;
00056
00057 if (pheap->index >= pheap->count - 1) {
00058 pheap->count += pheap->block;
00059 if ((pheap->pnode =
00060 realloc(pheap->pnode,
00061 sizeof(dglHeapNode_s) * pheap->count)) == NULL)
00062 return -1;
00063 }
00064
00065 i = ++pheap->index;
00066
00067 while (i != 1 && key < pheap->pnode[i / 2].key) {
00068 pheap->pnode[i] = pheap->pnode[i / 2];
00069 i /= 2;
00070 }
00071
00072 pheap->pnode[i].key = key;
00073 pheap->pnode[i].flags = flags;
00074 pheap->pnode[i].value = value;
00075
00076 return i;
00077 }
00078
00079 int dglHeapExtractMin(dglHeap_s * pheap, dglHeapNode_s * pnoderet)
00080 {
00081 dglHeapNode_s temp;
00082 long iparent, ichild;
00083
00084 if (pheap->index == 0)
00085 return 0;
00086
00087 *pnoderet = pheap->pnode[1];
00088
00089 temp = pheap->pnode[pheap->index--];
00090
00091 iparent = 1;
00092 ichild = 2;
00093
00094 while (ichild <= pheap->index) {
00095 if (ichild < pheap->index &&
00096 pheap->pnode[ichild].key > pheap->pnode[ichild + 1].key) {
00097 ichild++;
00098 }
00099 if (temp.key <= pheap->pnode[ichild].key)
00100 break;
00101
00102 pheap->pnode[iparent] = pheap->pnode[ichild];
00103 iparent = ichild;
00104 ichild *= 2;
00105 }
00106 pheap->pnode[iparent] = temp;
00107
00108 return 1;
00109 }
00110
00111 int dglHeapInsertMax(dglHeap_s * pheap,
00112 long key, unsigned char flags, dglHeapData_u value)
00113 {
00114 long i;
00115
00116 if (pheap->index >= pheap->count - 1) {
00117 pheap->count += pheap->block;
00118 if ((pheap->pnode =
00119 realloc(pheap->pnode,
00120 sizeof(dglHeapNode_s) * pheap->count)) == NULL)
00121 return -1;
00122 }
00123
00124 i = ++pheap->index;
00125
00126 while (i != 1 && key > pheap->pnode[i / 2].key) {
00127 pheap->pnode[i] = pheap->pnode[i / 2];
00128 i /= 2;
00129 }
00130
00131 pheap->pnode[i].key = key;
00132 pheap->pnode[i].flags = flags;
00133 pheap->pnode[i].value = value;
00134
00135 return i;
00136 }
00137
00138 int dglHeapExtractMax(dglHeap_s * pheap, dglHeapNode_s * pnoderet)
00139 {
00140 dglHeapNode_s temp;
00141 long iparent, ichild;
00142
00143 if (pheap->index == 0)
00144 return 0;
00145
00146 *pnoderet = pheap->pnode[1];
00147
00148 temp = pheap->pnode[pheap->index--];
00149
00150 iparent = 1;
00151 ichild = 2;
00152
00153 while (ichild <= pheap->index) {
00154 if (ichild < pheap->index &&
00155 pheap->pnode[ichild].key < pheap->pnode[ichild + 1].key) {
00156 ichild++;
00157 }
00158 if (temp.key >= pheap->pnode[ichild].key)
00159 break;
00160
00161 pheap->pnode[iparent] = pheap->pnode[ichild];
00162 iparent = ichild;
00163 ichild *= 2;
00164 }
00165 pheap->pnode[iparent] = temp;
00166
00167 return 1;
00168 }