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 if ( pheap->pnode ) {
00041 if ( pfnCancelItem ) {
00042 for (iItem = 0 ; iItem <= pheap->index ; iItem ++) {
00043 pfnCancelItem(pheap, & pheap->pnode[iItem] );
00044 }
00045 }
00046 free( pheap->pnode );
00047 }
00048 pheap->pnode = NULL;
00049 }
00050
00051 int dglHeapInsertMin(
00052 dglHeap_s * pheap ,
00053 long key ,
00054 unsigned char flags ,
00055 dglHeapData_u value
00056 )
00057 {
00058 long i;
00059
00060 if ( pheap->index >= pheap->count - 1 )
00061 {
00062 pheap->count += pheap->block;
00063 if ( (pheap->pnode = realloc( pheap->pnode , sizeof( dglHeapNode_s ) * pheap->count )) == NULL ) return -1;
00064 }
00065
00066 i = ++pheap->index;
00067
00068 while( i != 1 && key < pheap->pnode[ i / 2 ].key )
00069 {
00070 pheap->pnode[ i ] = pheap->pnode[ i / 2 ];
00071 i /= 2;
00072 }
00073
00074 pheap->pnode[ i ].key = key;
00075 pheap->pnode[ i ].flags = flags;
00076 pheap->pnode[ i ].value = value;
00077
00078 return i;
00079 }
00080
00081 int dglHeapExtractMin(
00082 dglHeap_s * pheap,
00083 dglHeapNode_s * pnoderet
00084 )
00085 {
00086 dglHeapNode_s temp;
00087 long iparent , ichild;
00088
00089 if ( pheap->index == 0 ) return 0;
00090
00091 *pnoderet = pheap->pnode[ 1 ];
00092
00093 temp = pheap->pnode[ pheap->index-- ];
00094
00095 iparent = 1;
00096 ichild = 2;
00097
00098 while( ichild <= pheap->index )
00099 {
00100 if ( ichild < pheap->index && pheap->pnode[ ichild ].key > pheap->pnode[ ichild + 1 ].key )
00101 {
00102 ichild ++;
00103 }
00104 if ( temp.key <= pheap->pnode[ ichild ].key ) break;
00105
00106 pheap->pnode[ iparent ] = pheap->pnode[ ichild ];
00107 iparent = ichild;
00108 ichild *= 2;
00109 }
00110 pheap->pnode[ iparent ] = temp;
00111
00112 return 1;
00113 }
00114
00115 int dglHeapInsertMax(
00116 dglHeap_s * pheap ,
00117 long key ,
00118 unsigned char flags ,
00119 dglHeapData_u value
00120 )
00121 {
00122 long i;
00123
00124 if ( pheap->index >= pheap->count - 1 )
00125 {
00126 pheap->count += pheap->block;
00127 if ( (pheap->pnode = realloc( pheap->pnode , sizeof( dglHeapNode_s ) * pheap->count )) == NULL ) return -1;
00128 }
00129
00130 i = ++pheap->index;
00131
00132 while( i != 1 && key > pheap->pnode[ i / 2 ].key )
00133 {
00134 pheap->pnode[ i ] = pheap->pnode[ i / 2 ];
00135 i /= 2;
00136 }
00137
00138 pheap->pnode[ i ].key = key;
00139 pheap->pnode[ i ].flags = flags;
00140 pheap->pnode[ i ].value = value;
00141
00142 return i;
00143 }
00144
00145 int dglHeapExtractMax(
00146 dglHeap_s * pheap,
00147 dglHeapNode_s * pnoderet
00148 )
00149 {
00150 dglHeapNode_s temp;
00151 long iparent , ichild;
00152
00153 if ( pheap->index == 0 ) return 0;
00154
00155 *pnoderet = pheap->pnode[ 1 ];
00156
00157 temp = pheap->pnode[ pheap->index-- ];
00158
00159 iparent = 1;
00160 ichild = 2;
00161
00162 while( ichild <= pheap->index )
00163 {
00164 if ( ichild < pheap->index && pheap->pnode[ ichild ].key < pheap->pnode[ ichild + 1 ].key )
00165 {
00166 ichild ++;
00167 }
00168 if ( temp.key >= pheap->pnode[ ichild ].key ) break;
00169
00170 pheap->pnode[ iparent ] = pheap->pnode[ ichild ];
00171 iparent = ichild;
00172 ichild *= 2;
00173 }
00174 pheap->pnode[ iparent ] = temp;
00175
00176 return 1;
00177 }
00178