Return to pqueue.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / lib

quagga

    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: }