lib/pqueue.c

   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 "pqueue.h"
  24
  25 /* priority queue using heap sort */
  26
  27 /* pqueue->cmp() controls the order of sorting (i.e, ascending or
  28    descending). If you want the left node to move upper of the heap
  29    binary tree, make cmp() to return less than 0.  for example, if cmp
  30    (10, 20) returns -1, the sorting is ascending order. if cmp (10,
  31    20) returns 1, the sorting is descending order. if cmp (10, 20)
  32    returns 0, this library does not do sorting (which will not be what
  33    you want).  To be brief, if the contents of cmp_func (left, right)
  34    is left - right, dequeue () returns the smallest node.  Otherwise
  35    (if the contents is right - left), dequeue () returns the largest
  36    node.  */
  37
  38 #define DATA_SIZE (sizeof (void *))
  39 #define PARENT_OF(x) ((x - 1) / 2)
  40 #define LEFT_OF(x)  (2 * x + 1)
  41 #define RIGHT_OF(x) (2 * x + 2)
  42 #define HAVE_CHILD(x,q) (x < (q)->size / 2)
  43
  44 static void
  45 trickle_up (int index, struct pqueue *queue)
  46 {
  47   void *tmp;
  48
  49   /* Save current node as tmp node.  */
  50   tmp = queue->array[index];
  51
  52   /* Continue until the node reaches top or the place where the parent
  53      node should be upper than the tmp node.  */
  54   while (index > 0 &&
  55          (*queue->cmp) (tmp, queue->array[PARENT_OF (index)]) < 0)
  56     {
  57       /* actually trickle up */
  58       queue->array[index] = queue->array[PARENT_OF (index)];
  59       if (queue->update != NULL)
  60         (*queue->update) (queue->array[index], index);
  61       index = PARENT_OF (index);
  62     }
  63
  64   /* Restore the tmp node to appropriate place.  */
  65   queue->array[index] = tmp;
  66   if (queue->update != NULL)
  67     (*queue->update) (tmp, index);
  68 }
  69
  70 void
  71 trickle_down (int index, struct pqueue *queue)
  72 {
  73   void *tmp;
  74   int which;
  75
  76   /* Save current node as tmp node.  */
  77   tmp = queue->array[index];
  78
  79   /* Continue until the node have at least one (left) child.  */
  80   while (HAVE_CHILD (index, queue))
  81     {
  82       /* If right child exists, and if the right child is more proper
  83          to be moved upper.  */
  84       if (RIGHT_OF (index) < queue->size &&
  85           (*queue->cmp) (queue->array[LEFT_OF (index)],
  86                          queue->array[RIGHT_OF (index)]) > 0)
  87         which = RIGHT_OF (index);
  88       else
  89         which = LEFT_OF (index);
  90
  91       /* If the tmp node should be upper than the child, break.  */
  92       if ((*queue->cmp) (queue->array[which], tmp) > 0)
  93         break;
  94
  95       /* Actually trickle down the tmp node.  */
  96       queue->array[index] = queue->array[which];
  97        if (queue->update != NULL)
  98          (*queue->update) (queue->array[index], index);
  99       index = which;
 100     }
 101
 102   /* Restore the tmp node to appropriate place.  */
 103   queue->array[index] = tmp;
 104   if (queue->update != NULL)
 105     (*queue->update) (tmp, index);
 106 }
 107
 108 struct pqueue *
 109 pqueue_create ()
 110 {
 111   struct pqueue *queue;
 112
 113   queue = (struct pqueue *) malloc (sizeof (struct pqueue));
 114   memset (queue, 0, sizeof (struct pqueue));
 115
 116   queue->array = (void **)
 117     malloc (DATA_SIZE * PQUEUE_INIT_ARRAYSIZE);
 118   memset (queue->array, 0, DATA_SIZE * PQUEUE_INIT_ARRAYSIZE);
 119   queue->array_size = PQUEUE_INIT_ARRAYSIZE;
 120
 121   /* By default we want nothing to happen when a node changes. */
 122   queue->update = NULL;
 123   return queue;
 124 }
 125
 126 void
 127 pqueue_delete (struct pqueue *queue)
 128 {
 129   free (queue->array);
 130   free (queue);
 131 }
 132
 133 static int
 134 pqueue_expand (struct pqueue *queue)
 135 {
 136   void **newarray;
 137
 138   newarray = (void **) malloc (queue->array_size * DATA_SIZE * 2);
 139   if (newarray == NULL)
 140     return 0;
 141
 142   memset (newarray, 0, queue->array_size * DATA_SIZE * 2);
 143   memcpy (newarray, queue->array, queue->array_size * DATA_SIZE);
 144
 145   free (queue->array);
 146   queue->array = newarray;
 147   queue->array_size *= 2;
 148
 149   return 1;
 150 }
 151
 152 void
 153 pqueue_enqueue (void *data, struct pqueue *queue)
 154 {
 155   if (queue->size + 2 >= queue->array_size && ! pqueue_expand (queue))
 156     return;
 157
 158   queue->array[queue->size] = data;
 159   if (queue->update != NULL)
 160     (*queue->update) (data, queue->size);
 161   trickle_up (queue->size, queue);
 162   queue->size ++;
 163 }
 164
 165 void *
 166 pqueue_dequeue (struct pqueue *queue)
 167 {
 168   void *data = queue->array[0];
 169   queue->array[0] =  queue->array[--queue->size];
 170   trickle_down (0, queue);
 171   return data;
 172 }