00001
00012 #ifndef _GK_MKPQUEUE2_H
00013 #define _GK_MKPQUEUE2_H
00014
00015
00016 #define GK_MKPQUEUE2(FPRFX, PQT, KT, VT, KMALLOC, VMALLOC, KMAX, KEY_LT)\
00017 \
00018 \
00019 \
00020 PQT *FPRFX ## Create2(ssize_t maxnodes)\
00021 {\
00022 PQT *queue; \
00023 \
00024 if ((queue = (PQT *)gk_malloc(sizeof(PQT), "gk_pqCreate2: queue")) != NULL) {\
00025 memset(queue, 0, sizeof(PQT));\
00026 queue->nnodes = 0;\
00027 queue->maxnodes = maxnodes;\
00028 queue->keys = KMALLOC(maxnodes, "gk_pqCreate2: keys");\
00029 queue->vals = VMALLOC(maxnodes, "gk_pqCreate2: vals");\
00030 \
00031 if (queue->keys == NULL || queue->vals == NULL)\
00032 gk_free((void **)&queue->keys, &queue->vals, &queue, LTERM);\
00033 }\
00034 \
00035 return queue;\
00036 }\
00037 \
00038 \
00039 \
00040 \
00041 \
00042 void FPRFX ## Reset2(PQT *queue)\
00043 {\
00044 queue->nnodes = 0;\
00045 }\
00046 \
00047 \
00048 \
00049 \
00050 \
00051 void FPRFX ## Destroy2(PQT **r_queue)\
00052 {\
00053 PQT *queue = *r_queue; \
00054 if (queue == NULL) return;\
00055 gk_free((void **)&queue->keys, &queue->vals, &queue, LTERM);\
00056 *r_queue = NULL;\
00057 }\
00058 \
00059 \
00060 \
00061 \
00062 \
00063 size_t FPRFX ## Length2(PQT *queue)\
00064 {\
00065 return queue->nnodes;\
00066 }\
00067 \
00068 \
00069 \
00070 \
00071 \
00072 int FPRFX ## Insert2(PQT *queue, VT val, KT key)\
00073 {\
00074 ssize_t i, j;\
00075 KT *keys=queue->keys;\
00076 VT *vals=queue->vals;\
00077 \
00078 ASSERT2(FPRFX ## CheckHeap2(queue));\
00079 \
00080 if (queue->nnodes == queue->maxnodes) \
00081 return 0;\
00082 \
00083 ASSERT2(FPRFX ## CheckHeap2(queue));\
00084 \
00085 i = queue->nnodes++;\
00086 while (i > 0) {\
00087 j = (i-1)>>1;\
00088 if (KEY_LT(key, keys[j])) {\
00089 keys[i] = keys[j];\
00090 vals[i] = vals[j];\
00091 i = j;\
00092 }\
00093 else\
00094 break;\
00095 }\
00096 ASSERT(i >= 0);\
00097 keys[i] = key;\
00098 vals[i] = val;\
00099 \
00100 ASSERT2(FPRFX ## CheckHeap2(queue));\
00101 \
00102 return 1;\
00103 }\
00104 \
00105 \
00106 \
00107 \
00109 \
00110 int FPRFX ## GetTop2(PQT *queue, VT *r_val)\
00111 {\
00112 ssize_t i, j;\
00113 KT key, *keys=queue->keys;\
00114 VT val, *vals=queue->vals;\
00115 \
00116 ASSERT2(FPRFX ## CheckHeap2(queue));\
00117 \
00118 if (queue->nnodes == 0)\
00119 return 0;\
00120 \
00121 queue->nnodes--;\
00122 \
00123 *r_val = vals[0];\
00124 \
00125 if ((i = queue->nnodes) > 0) {\
00126 key = keys[i];\
00127 val = vals[i];\
00128 i = 0;\
00129 while ((j=2*i+1) < queue->nnodes) {\
00130 if (KEY_LT(keys[j], key)) {\
00131 if (j+1 < queue->nnodes && KEY_LT(keys[j+1], keys[j]))\
00132 j = j+1;\
00133 keys[i] = keys[j];\
00134 vals[i] = vals[j];\
00135 i = j;\
00136 }\
00137 else if (j+1 < queue->nnodes && KEY_LT(keys[j+1], key)) {\
00138 j = j+1;\
00139 keys[i] = keys[j];\
00140 vals[i] = vals[j];\
00141 i = j;\
00142 }\
00143 else\
00144 break;\
00145 }\
00146 \
00147 keys[i] = key;\
00148 vals[i] = val;\
00149 }\
00150 \
00151 ASSERT2(FPRFX ## CheckHeap2(queue));\
00152 \
00153 return 1;\
00154 }\
00155 \
00156 \
00157 \
00158 \
00160 \
00161 int FPRFX ## SeeTopVal2(PQT *queue, VT *r_val)\
00162 {\
00163 if (queue->nnodes == 0) \
00164 return 0;\
00165 \
00166 *r_val = queue->vals[0];\
00167 \
00168 return 1;\
00169 }\
00170 \
00171 \
00172 \
00173 \
00175 \
00176 KT FPRFX ## SeeTopKey2(PQT *queue)\
00177 {\
00178 return (queue->nnodes == 0 ? KMAX : queue->keys[0]);\
00179 }\
00180 \
00181 \
00182 \
00183 \
00184 \
00185 int FPRFX ## CheckHeap2(PQT *queue)\
00186 {\
00187 ssize_t i;\
00188 KT *keys=queue->keys;\
00189 \
00190 if (queue->nnodes == 0)\
00191 return 1;\
00192 \
00193 for (i=1; i<queue->nnodes; i++) {\
00194 ASSERT(!KEY_LT(keys[i], keys[(i-1)/2]));\
00195 }\
00196 for (i=1; i<queue->nnodes; i++)\
00197 ASSERT(!KEY_LT(keys[i], keys[0]));\
00198 \
00199 return 1;\
00200 }\
00201
00202
00203 #define GK_MKPQUEUE2_PROTO(FPRFX, PQT, KT, VT)\
00204 PQT * FPRFX ## Create2(ssize_t maxnodes);\
00205 void FPRFX ## Reset2(PQT *queue);\
00206 void FPRFX ## Destroy2(PQT **r_queue);\
00207 size_t FPRFX ## Length2(PQT *queue);\
00208 int FPRFX ## Insert2(PQT *queue, VT node, KT key);\
00209 int FPRFX ## GetTop2(PQT *queue, VT *r_val);\
00210 int FPRFX ## SeeTopVal2(PQT *queue, VT *r_val);\
00211 KT FPRFX ## SeeTopKey2(PQT *queue);\
00212 int FPRFX ## CheckHeap2(PQT *queue);\
00213
00214
00215 #endif
1.5.5