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 "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 trickle_up (int index, struct pqueue *queue)
  47 {
  48   void *tmp;
  49
  50   /* Save current node as tmp node.  */
  51   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   while (index > 0 &&
  56          (*queue->cmp) (tmp, queue->array[PARENT_OF (index)]) < 0)
  57     {
  58       /* actually trickle up */
  59       queue->array[index] = queue->array[PARENT_OF (index)];
  60       if (queue->update != NULL)
  61         (*queue->update) (queue->array[index], index);
  62       index = PARENT_OF (index);
  63     }
  64
  65   /* Restore the tmp node to appropriate place.  */
  66   queue->array[index] = tmp;
  67   if (queue->update != NULL)
  68     (*queue->update) (tmp, index);
  69 }
  70
  71 void
  72 trickle_down (int index, struct pqueue *queue)
  73 {
  74   void *tmp;
  75   int which;
  76
  77   /* Save current node as tmp node.  */
  78   tmp = queue->array[index];
  79
  80   /* Continue until the node have at least one (left) child.  */
  81   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       if (RIGHT_OF (index) < queue->size &&
  86           (*queue->cmp) (queue->array[LEFT_OF (index)],
  87                          queue->array[RIGHT_OF (index)]) > 0)
  88         which = RIGHT_OF (index);
  89       else
  90         which = LEFT_OF (index);
  91
  92       /* If the tmp node should be upper than the child, break.  */
  93       if ((*queue->cmp) (queue->array[which], tmp) > 0)
  94         break;
  95
  96       /* Actually trickle down the tmp node.  */
  97       queue->array[index] = queue->array[which];
  98        if (queue->update != NULL)
  99          (*queue->update) (queue->array[index], index);
 100       index = which;
 101     }
 102
 103   /* Restore the tmp node to appropriate place.  */
 104   queue->array[index] = tmp;
 105   if (queue->update != NULL)
 106     (*queue->update) (tmp, index);
 107 }
 108
 109 struct pqueue *
 110 pqueue_create (void)
 111 {
 112   struct pqueue *queue;
 113
 114   queue = XCALLOC (MTYPE_PQUEUE, sizeof (struct pqueue));
 115
 116   queue->array = XCALLOC (MTYPE_PQUEUE_DATA,
 117                           DATA_SIZE * PQUEUE_INIT_ARRAYSIZE);
 118   queue->array_size = PQUEUE_INIT_ARRAYSIZE;
 119
 120   /* By default we want nothing to happen when a node changes. */
 121   queue->update = NULL;
 122   return queue;
 123 }
 124
 125 void
 126 pqueue_delete (struct pqueue *queue)
 127 {
 128   XFREE (MTYPE_PQUEUE_DATA, queue->array);
 129   XFREE (MTYPE_PQUEUE, queue);
 130 }
 131
 132 static int
 133 pqueue_expand (struct pqueue *queue)
 134 {
 135   void **newarray;
 136
 137   newarray = XCALLOC (MTYPE_PQUEUE_DATA, queue->array_size * DATA_SIZE * 2);
 138   if (newarray == NULL)
 139     return 0;
 140
 141   memcpy (newarray, queue->array, queue->array_size * DATA_SIZE);
 142
 143   XFREE (MTYPE_PQUEUE_DATA, queue->array);
 144   queue->array = newarray;
 145   queue->array_size *= 2;
 146
 147   return 1;
 148 }
 149
 150 void
 151 pqueue_enqueue (void *data, struct pqueue *queue)
 152 {
 153   if (queue->size + 2 >= queue->array_size && ! pqueue_expand (queue))
 154     return;
 155
 156   queue->array[queue->size] = data;
 157   if (queue->update != NULL)
 158     (*queue->update) (data, queue->size);
 159   trickle_up (queue->size, queue);
 160   queue->size ++;
 161 }
 162
 163 void *
 164 pqueue_dequeue (struct pqueue *queue)
 165 {
 166   void *data = queue->array[0];
 167   queue->array[0] =  queue->array[--queue->size];
 168   trickle_down (0, queue);
 169   return data;
 170 }
 171
 172 void
 173 pqueue_remove_at (int index, struct pqueue *queue)
 174 {
 175   queue->array[index] = queue->array[--queue->size];
 176
 177   if (index > 0
 178       && (*queue->cmp) (queue->array[index],
 179                         queue->array[PARENT_OF(index)]) < 0)
 180     {
 181       trickle_up (index, queue);
 182     }
 183   else
 184     {
 185       trickle_down (index, queue);
 186     }
 187 }