release/src/router/zebra/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       index = PARENT_OF (index);
  60     }
  61
  62   /* Restore the tmp node to appropriate place.  */
  63   queue->array[index] = tmp;
  64 }
  65
  66 static void
  67 trickle_down (int index, struct pqueue *queue)
  68 {
  69   void *tmp;
  70   int which;
  71
  72   /* Save current node as tmp node.  */
  73   tmp = queue->array[index];
  74
  75   /* Continue until the node have at least one (left) child.  */
  76   while (HAVE_CHILD (index, queue))
  77     {
  78       /* If right child exists, and if the right child is more proper
  79          to be moved upper.  */
  80       if (RIGHT_OF (index) < queue->size &&
  81           (*queue->cmp) (queue->array[LEFT_OF (index)],
  82                          queue->array[RIGHT_OF (index)]) > 0)
  83         which = RIGHT_OF (index);
  84       else
  85         which = LEFT_OF (index);
  86
  87       /* If the tmp node should be upper than the child, break.  */
  88       if ((*queue->cmp) (queue->array[which], tmp) > 0)
  89         break;
  90
  91       /* Actually trickle down the tmp node.  */
  92       queue->array[index] = queue->array[which];
  93       index = which;
  94     }
  95
  96   /* Restore the tmp node to appropriate place.  */
  97   queue->array[index] = tmp;
  98 }
  99
 100 struct pqueue *
 101 pqueue_create ()
 102 {
 103   struct pqueue *queue;
 104
 105   queue = (struct pqueue *) malloc (sizeof (struct pqueue));
 106   memset (queue, 0, sizeof (struct pqueue));
 107
 108   queue->array = (void **)
 109     malloc (DATA_SIZE * PQUEUE_INIT_ARRAYSIZE);
 110   memset (queue->array, 0, DATA_SIZE * PQUEUE_INIT_ARRAYSIZE);
 111   queue->array_size = PQUEUE_INIT_ARRAYSIZE;
 112
 113   return queue;
 114 }
 115
 116 void
 117 pqueue_delete (struct pqueue *queue)
 118 {
 119   free (queue->array);
 120   free (queue);
 121 }
 122
 123 static int
 124 pqueue_expand (struct pqueue *queue)
 125 {
 126   void **newarray;
 127
 128   newarray = (void **) malloc (queue->array_size * DATA_SIZE * 2);
 129   if (newarray == NULL)
 130     return 0;
 131
 132   memset (newarray, 0, queue->array_size * DATA_SIZE * 2);
 133   memcpy (newarray, queue->array, queue->array_size * DATA_SIZE);
 134
 135   free (queue->array);
 136   queue->array = newarray;
 137   queue->array_size *= 2;
 138
 139   return 1;
 140 }
 141
 142 void
 143 pqueue_enqueue (void *data, struct pqueue *queue)
 144 {
 145   if (queue->size + 2 >= queue->array_size && ! pqueue_expand (queue))
 146     return;
 147
 148   queue->array[queue->size] = data;
 149   trickle_up (queue->size, queue);
 150   queue->size ++;
 151 }
 152
 153 void *
 154 pqueue_dequeue (struct pqueue *queue)
 155 {
 156   void *data = queue->array[0];
 157   queue->array[0] =  queue->array[--queue->size];
 158   trickle_down (0, queue);
 159   return data;
 160 }