pqueue.c 5.1 KB

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