LCOV - code coverage report
Current view: top level - lib - pqueue.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 41 70 58.6 %
Date: 2015-11-19 Functions: 6 8 75.0 %

          Line data    Source code
       1             : /* Priority queue functions.
       2             :    Copyright (C) 2003 Yasuhiro Ohara
       3             : 
       4             : This file is part of GNU Zebra.
       5             : 
       6             : GNU Zebra is free software; you can redistribute it and/or modify
       7             : it under the terms of the GNU General Public License as published
       8             : by the Free Software Foundation; either version 2, or (at your
       9             : option) any later version.
      10             : 
      11             : GNU Zebra is distributed in the hope that it will be useful, but
      12             : WITHOUT ANY WARRANTY; without even the implied warranty of
      13             : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      14             : General Public License for more details.
      15             : 
      16             : You should have received a copy of the GNU General Public License
      17             : along with GNU Zebra; see the file COPYING.  If not, write to the
      18             : Free Software Foundation, Inc., 59 Temple Place - Suite 330,
      19             : Boston, MA 02111-1307, USA.  */
      20             : 
      21             : #include <zebra.h>
      22             : 
      23             : #include "memory.h"
      24             : #include "pqueue.h"
      25             : 
      26             : /* priority queue using heap sort */
      27             : 
      28             : /* pqueue->cmp() controls the order of sorting (i.e, ascending or
      29             :    descending). If you want the left node to move upper of the heap
      30             :    binary tree, make cmp() to return less than 0.  for example, if cmp
      31             :    (10, 20) returns -1, the sorting is ascending order. if cmp (10,
      32             :    20) returns 1, the sorting is descending order. if cmp (10, 20)
      33             :    returns 0, this library does not do sorting (which will not be what
      34             :    you want).  To be brief, if the contents of cmp_func (left, right)
      35             :    is left - right, dequeue () returns the smallest node.  Otherwise
      36             :    (if the contents is right - left), dequeue () returns the largest
      37             :    node.  */
      38             : 
      39             : #define DATA_SIZE (sizeof (void *))
      40             : #define PARENT_OF(x) ((x - 1) / 2)
      41             : #define LEFT_OF(x)  (2 * x + 1)
      42             : #define RIGHT_OF(x) (2 * x + 2)
      43             : #define HAVE_CHILD(x,q) (x < (q)->size / 2)
      44             : 
      45             : void
      46         763 : trickle_up (int index, struct pqueue *queue)
      47             : {
      48             :   void *tmp;
      49             : 
      50             :   /* Save current node as tmp node.  */
      51         763 :   tmp = queue->array[index];
      52             : 
      53             :   /* Continue until the node reaches top or the place where the parent
      54             :      node should be upper than the tmp node.  */
      55        1706 :   while (index > 0 &&
      56          90 :          (*queue->cmp) (tmp, queue->array[PARENT_OF (index)]) < 0)
      57             :     {
      58             :       /* actually trickle up */
      59          90 :       queue->array[index] = queue->array[PARENT_OF (index)];
      60          90 :       if (queue->update != NULL)
      61          90 :         (*queue->update) (queue->array[index], index);
      62          90 :       index = PARENT_OF (index);
      63             :     }
      64             : 
      65             :   /* Restore the tmp node to appropriate place.  */
      66         763 :   queue->array[index] = tmp;
      67         763 :   if (queue->update != NULL)
      68         763 :     (*queue->update) (tmp, index);
      69         763 : }
      70             : 
      71             : void
      72         665 : trickle_down (int index, struct pqueue *queue)
      73             : {
      74             :   void *tmp;
      75             :   int which;
      76             : 
      77             :   /* Save current node as tmp node.  */
      78         665 :   tmp = queue->array[index];
      79             : 
      80             :   /* Continue until the node have at least one (left) child.  */
      81        1330 :   while (HAVE_CHILD (index, queue))
      82             :     {
      83             :       /* If right child exists, and if the right child is more proper
      84             :          to be moved upper.  */
      85           0 :       if (RIGHT_OF (index) < queue->size &&
      86           0 :           (*queue->cmp) (queue->array[LEFT_OF (index)],
      87           0 :                          queue->array[RIGHT_OF (index)]) > 0)
      88           0 :         which = RIGHT_OF (index);
      89             :       else
      90           0 :         which = LEFT_OF (index);
      91             : 
      92             :       /* If the tmp node should be upper than the child, break.  */
      93           0 :       if ((*queue->cmp) (queue->array[which], tmp) > 0)
      94           0 :         break;
      95             : 
      96             :       /* Actually trickle down the tmp node.  */
      97           0 :       queue->array[index] = queue->array[which];
      98           0 :        if (queue->update != NULL)
      99           0 :          (*queue->update) (queue->array[index], index);
     100           0 :       index = which;
     101             :     }
     102             : 
     103             :   /* Restore the tmp node to appropriate place.  */
     104         665 :   queue->array[index] = tmp;
     105         665 :   if (queue->update != NULL)
     106         665 :     (*queue->update) (tmp, index);
     107         665 : }
     108             : 
     109             : struct pqueue *
     110         104 : pqueue_create (void)
     111             : {
     112             :   struct pqueue *queue;
     113             : 
     114         104 :   queue = XCALLOC (MTYPE_PQUEUE, sizeof (struct pqueue));
     115             : 
     116         104 :   queue->array = XCALLOC (MTYPE_PQUEUE_DATA, 
     117             :                           DATA_SIZE * PQUEUE_INIT_ARRAYSIZE);
     118         104 :   queue->array_size = PQUEUE_INIT_ARRAYSIZE;
     119             : 
     120             :   /* By default we want nothing to happen when a node changes. */
     121         104 :   queue->update = NULL;
     122         104 :   return queue;
     123             : }
     124             : 
     125             : void
     126           2 : pqueue_delete (struct pqueue *queue)
     127             : {
     128           2 :   XFREE (MTYPE_PQUEUE_DATA, queue->array);
     129           2 :   XFREE (MTYPE_PQUEUE, queue);
     130           2 : }
     131             : 
     132             : static int
     133           0 : pqueue_expand (struct pqueue *queue)
     134             : {
     135             :   void **newarray;
     136             : 
     137           0 :   newarray = XCALLOC (MTYPE_PQUEUE_DATA, queue->array_size * DATA_SIZE * 2);
     138           0 :   if (newarray == NULL)
     139           0 :     return 0;
     140             : 
     141           0 :   memcpy (newarray, queue->array, queue->array_size * DATA_SIZE);
     142             : 
     143           0 :   XFREE (MTYPE_PQUEUE_DATA, queue->array);
     144           0 :   queue->array = newarray;
     145           0 :   queue->array_size *= 2;
     146             : 
     147           0 :   return 1;
     148             : }
     149             : 
     150             : void
     151         763 : pqueue_enqueue (void *data, struct pqueue *queue)
     152             : {
     153         763 :   if (queue->size + 2 >= queue->array_size && ! pqueue_expand (queue))
     154           0 :     return;
     155             : 
     156         763 :   queue->array[queue->size] = data;
     157         763 :   if (queue->update != NULL)
     158         763 :     (*queue->update) (data, queue->size);
     159         763 :   trickle_up (queue->size, queue);
     160         763 :   queue->size ++;
     161             : }
     162             : 
     163             : void *
     164         665 : pqueue_dequeue (struct pqueue *queue)
     165             : {
     166         665 :   void *data = queue->array[0];
     167         665 :   queue->array[0] =  queue->array[--queue->size];
     168         665 :   trickle_down (0, queue);
     169         665 :   return data;
     170             : }
     171             : 
     172             : void
     173           0 : pqueue_remove_at (int index, struct pqueue *queue)
     174             : {
     175           0 :   queue->array[index] = queue->array[--queue->size];
     176             : 
     177           0 :   if (index > 0
     178           0 :       && (*queue->cmp) (queue->array[index],
     179           0 :                         queue->array[PARENT_OF(index)]) < 0)
     180             :     {
     181           0 :       trickle_up (index, queue);
     182             :     }
     183             :   else
     184             :     {
     185           0 :       trickle_down (index, queue);
     186             :     }
     187           0 : }

Generated by: LCOV version 1.10