You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

223 lines
5.6KB

  1. /*
  2. Generic queue utilities.
  3. Copyright (C) 2002 Robert Lipe, robertlipe+source@gpsbabel.org
  4. This program is free software; you can redistribute it and/or modify
  5. it under the terms of the GNU General Public License as published by
  6. the Free Software Foundation; either version 2 of the License, or
  7. (at your option) any later version.
  8. This program is distributed in the hope that it will be useful,
  9. but WITHOUT ANY WARRANTY; without even the implied warranty of
  10. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11. GNU General Public License for more details.
  12. You should have received a copy of the GNU General Public License
  13. along with this program; if not, write to the Free Software
  14. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111 USA
  15. */
  16. #include "queue.h"
  17. #include <stddef.h>
  18. void
  19. enqueue(queue* new_el, queue* old)
  20. {
  21. new_el->next = old->next;
  22. new_el->prev = old;
  23. old->next->prev = new_el;
  24. old->next = new_el;
  25. }
  26. queue*
  27. dequeue(queue* element)
  28. {
  29. queue* prev = element->prev;
  30. queue* next = element->next;
  31. next->prev = prev;
  32. prev->next = next;
  33. QUEUE_INIT(element);
  34. return element;
  35. }
  36. /*
  37. * The following sorting code was derived from linked-list mergesort
  38. * sample code by Simon Tatham, code obtained from:
  39. * http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
  40. * Modified for use with gpsbabel's queues by Paul Fox, October 2006.
  41. *
  42. * Original description and copyright messages follow...
  43. */
  44. /*
  45. * Demonstration code for sorting a linked list.
  46. *
  47. * The algorithm used is Mergesort, because that works really well
  48. * on linked lists, without requiring the O(N) extra space it needs
  49. * when you do it on arrays.
  50. *
  51. * ...
  52. */
  53. /*
  54. * This file is copyright 2001 Simon Tatham.
  55. *
  56. * Permission is hereby granted, free of charge, to any person
  57. * obtaining a copy of this software and associated documentation
  58. * files (the "Software"), to deal in the Software without
  59. * restriction, including without limitation the rights to use,
  60. * copy, modify, merge, publish, distribute, sublicense, and/or
  61. * sell copies of the Software, and to permit persons to whom the
  62. * Software is furnished to do so, subject to the following
  63. * conditions:
  64. *
  65. * The above copyright notice and this permission notice shall be
  66. * included in all copies or substantial portions of the Software.
  67. *
  68. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  69. * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  70. * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  71. * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
  72. * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
  73. * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  74. * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  75. * SOFTWARE.
  76. */
  77. void
  78. sortqueue(queue* qh, int (*cmp)(const queue*, const queue*))
  79. {
  80. queue* p, *q, *e, *tail, *oldhead, *list;
  81. int insize, nmerges, psize, qsize, i;
  82. /*
  83. * Special case: if `list' is empty, we're done.
  84. */
  85. if (QUEUE_EMPTY(qh)) {
  86. return;
  87. }
  88. /*
  89. * The algorithm doesn't really want the extra list head
  90. * element. So remove the list head for now. Put it back later.
  91. */
  92. list = QUEUE_FIRST(qh);
  93. dequeue(qh);
  94. insize = 1;
  95. while (1) {
  96. p = list;
  97. oldhead = list; /* only used for circular linkage */
  98. list = NULL;
  99. tail = NULL;
  100. nmerges = 0; /* count number of merges we do in this pass */
  101. while (p) {
  102. nmerges++; /* there exists a merge to be done */
  103. /* step `insize' places along from p */
  104. q = p;
  105. psize = 0;
  106. for (i = 0; i < insize; i++) {
  107. psize++;
  108. q = (q->next == oldhead ? NULL : q->next);
  109. if (!q) {
  110. break;
  111. }
  112. }
  113. /* if q hasn't fallen off end, we have
  114. * two lists to merge */
  115. qsize = insize;
  116. /* now we have two lists; merge them */
  117. while (psize > 0 || (qsize > 0 && q)) {
  118. /* decide whether next element of
  119. * merge comes from p or q
  120. */
  121. if (psize == 0) {
  122. /* p is empty; e must come from q. */
  123. e = q;
  124. q = q->next;
  125. qsize--;
  126. if (q == oldhead) {
  127. q = NULL;
  128. }
  129. } else if (qsize == 0 || !q) {
  130. /* q is empty; e must come from p. */
  131. e = p;
  132. p = p->next;
  133. psize--;
  134. if (p == oldhead) {
  135. p = NULL;
  136. }
  137. } else if (cmp(p,q) <= 0) {
  138. /* First element of p is
  139. * lower (or same); e must
  140. * come from p.
  141. */
  142. e = p;
  143. p = p->next;
  144. psize--;
  145. if (p == oldhead) {
  146. p = NULL;
  147. }
  148. } else {
  149. /* First element of q is
  150. * lower; e must come from
  151. * q.
  152. */
  153. e = q;
  154. q = q->next;
  155. qsize--;
  156. if (q == oldhead) {
  157. q = NULL;
  158. }
  159. }
  160. /* add the next element to the merged list */
  161. if (tail) {
  162. tail->next = e;
  163. } else {
  164. list = e;
  165. }
  166. /* Maintain reverse pointers in a
  167. * doubly linked list. */
  168. e->prev = tail;
  169. tail = e;
  170. }
  171. /* now p has stepped `insize' places
  172. * along, and q has too */
  173. p = q;
  174. }
  175. tail->next = list;
  176. list->prev = tail;
  177. /* If we have done only one merge, we're finished.
  178. * Allow for nmerges==0, the empty list case.
  179. */
  180. if (nmerges <= 1) {
  181. /* Put the list head back at the start of the list */
  182. ENQUEUE_TAIL(list, qh);
  183. return;
  184. }
  185. /* Otherwise repeat, merging lists twice the size */
  186. insize *= 2;
  187. }
  188. }