srcs/toolbox/pqueue.c

00001 /*
00002  * Copyright (c) 2005-2012 by KoanLogic s.r.l.
00003  */ 
00004 
00005 #include <toolbox/carpal.h>
00006 #include <toolbox/misc.h>
00007 #include <toolbox/pqueue.h>
00008 
00009 typedef struct u_pq_item_s
00010 {
00011     double key;
00012     void *val;
00013 } u_pq_item_t;
00014 
00015 struct u_pq_s
00016 {
00017     size_t nelems, nitems;
00018     u_pq_item_t *q;
00019 };
00020 
00021 static int pq_item_comp (u_pq_item_t *pi, u_pq_item_t *pj);
00022 static void pq_item_swap (u_pq_item_t *pi, u_pq_item_t *pj);
00023 static void bubble_up (u_pq_item_t *pi, size_t k);
00024 static void bubble_down (u_pq_item_t *pi, size_t k, size_t n);
00025 
00089 int u_pq_create (size_t nitems, u_pq_t **ppq)
00090 {
00091     u_pq_t *pq = NULL;
00092 
00093     dbg_return_if (ppq == NULL, ~0);
00094     dbg_return_if (nitems < 2, ~0); /* Expect at least 2 elements. */
00095 
00096     /* Make room for both the queue head and items' array. */
00097     dbg_err_sif ((pq = u_zalloc(sizeof *pq)) == NULL);
00098     dbg_err_sif ((pq->q = u_calloc(nitems + 1, sizeof(u_pq_item_t))) == NULL);
00099 
00100     /* Init the index of last element in array: valid elements are stored 
00101      * at index'es [1..nitems]. */
00102     pq->nelems = 0;
00103     pq->nitems = nitems;
00104 
00105     *ppq = pq;
00106 
00107     return 0;
00108 err:
00109     u_pq_free(pq);
00110     return ~0;
00111 }
00112 
00120 int u_pq_empty (u_pq_t *pq)
00121 {
00122     return (pq->nelems == 0);
00123 }
00124 
00132 int u_pq_full (u_pq_t *pq)
00133 {
00134     return (pq->nelems == pq->nitems);
00135 }
00136 
00146 void u_pq_free (u_pq_t *pq)
00147 {
00148     dbg_return_if (pq == NULL, );
00149 
00150     if (pq->q)
00151         u_free(pq->q);
00152     u_free(pq);
00153 
00154     return;
00155 }
00156 
00171 int u_pq_push (u_pq_t *pq, double key, const void *val)
00172 {
00173     u_pq_item_t *pi;
00174 
00175     dbg_return_if (pq == NULL, -1);
00176 
00177     /* Queue full, would overflow. */
00178     if (u_pq_full(pq))
00179         return -2;
00180 
00181     pq->nelems += 1;
00182 
00183     /* Get next free slot (from heap bottom). */
00184     pi = &pq->q[pq->nelems];
00185 
00186     /* Assign element. */
00187     pi->key = key;
00188     memcpy(&pi->val, &val, sizeof(void **));
00189 
00190     /* Fix heap condition bottom-up. */
00191     bubble_up(pq->q, pq->nelems);
00192 
00193     return 0;
00194 }
00195 
00206 void *u_pq_peekmax (u_pq_t *pq, double *pkey)
00207 {
00208     u_pq_item_t *pmax = &pq->q[1];
00209 
00210     if (pkey)
00211         *pkey = pmax->key;
00212 
00213     return pmax->val;
00214 }
00215 
00226 void *u_pq_delmax (u_pq_t *pq, double *pkey) 
00227 {
00228     u_pq_item_t *pmax;
00229 
00230     dbg_return_if (pq == NULL, NULL);
00231 
00232     /* Empty queue. XXX NULL is legitimate ... */
00233     if (pq->nelems == 0)
00234         return NULL;
00235 
00236     /* Exchange top and bottom items. */
00237     pq_item_swap(&pq->q[1], &pq->q[pq->nelems]);
00238 
00239     /* Fix heap condition top-down excluding the evicted item. */
00240     bubble_down(pq->q, 1, pq->nelems - 1);
00241 
00242     pmax = &pq->q[pq->nelems];
00243 
00244     pq->nelems -= 1;
00245 
00246     /* Copy out the deleted key if requested. */
00247     if (pkey)
00248         *pkey = pmax->key;
00249 
00250     return pmax->val;
00251 }
00252 
00257 static void pq_item_swap (u_pq_item_t *pi, u_pq_item_t *pj)
00258 {
00259     void *tmpval = pi->val;
00260     double tmpkey = pi->key;
00261 
00262     pi->key = pj->key;
00263     pi->val = pj->val;
00264 
00265     pj->key = tmpkey;
00266     pj->val = tmpval;
00267 
00268     return;
00269 }
00270 
00271 static int pq_item_comp (u_pq_item_t *pi, u_pq_item_t *pj)
00272 {
00273     return (pi->key < pj->key);
00274 }
00275 
00276 static void bubble_up (u_pq_item_t *pi, size_t k)
00277 {
00278     /* Move from bottom to top exchanging child with its parent node until
00279      * child is higher than parent, or we've reached the top. */
00280     while (k > 1 && pq_item_comp(&pi[k / 2], &pi[k]))
00281     {
00282         pq_item_swap(&pi[k], &pi[k / 2]);
00283         k = k / 2;
00284     }
00285 
00286     return;
00287 }
00288 
00289 static void bubble_down (u_pq_item_t *pi, size_t k, size_t n)
00290 {
00291     size_t j;
00292 
00293     /* Move from top to bottom exchanging the parent node with the highest
00294      * of its children, until the "moving" node is higher then both of them -
00295      * or we've reached the bottom. */
00296     while (2 * k <= n)
00297     {
00298         j = 2 * k;
00299 
00300         /* Choose to go left or right depending on who's bigger. */
00301         if (j < n && pq_item_comp(&pi[j], &pi[j + 1]))
00302             j++;
00303 
00304         if (!pq_item_comp(&pi[k], &pi[j]))
00305             break;
00306 
00307         pq_item_swap(&pi[k], &pi[j]);
00308 
00309         k = j;
00310     }
00311 
00312     return;
00313 }

←Products
© 2005-2012 - KoanLogic S.r.l. - All rights reserved