1/*** 2 This file is part of avahi. 3 4 avahi is free software; you can redistribute it and/or modify it 5 under the terms of the GNU Lesser General Public License as 6 published by the Free Software Foundation; either version 2.1 of the 7 License, or (at your option) any later version. 8 9 avahi is distributed in the hope that it will be useful, but WITHOUT 10 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 11 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General 12 Public License for more details. 13 14 You should have received a copy of the GNU Lesser General Public 15 License along with avahi; if not, write to the Free Software 16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 17 USA. 18***/ 19 20#ifdef HAVE_CONFIG_H 21#include <config.h> 22#endif 23 24#include <time.h> 25#include <stdlib.h> 26#include <stdio.h> 27#include <assert.h> 28 29#include <avahi-common/gccmacro.h> 30 31#include "prioq.h" 32 33#define POINTER_TO_INT(p) ((int) (long) (p)) 34#define INT_TO_POINTER(i) ((void*) (long) (i)) 35 36static int compare_int(const void* a, const void* b) { 37 int i = POINTER_TO_INT(a), j = POINTER_TO_INT(b); 38 39 return i < j ? -1 : (i > j ? 1 : 0); 40} 41 42static int compare_ptr(const void* a, const void* b) { 43 return a < b ? -1 : (a > b ? 1 : 0); 44} 45 46static void rec(AvahiPrioQueueNode *n) { 47 if (!n) 48 return; 49 50 if (n->left) 51 assert(n->left->parent == n); 52 53 if (n->right) 54 assert(n->right->parent == n); 55 56 if (n->parent) { 57 assert(n->parent->left == n || n->parent->right == n); 58 59 if (n->parent->left == n) 60 assert(n->next == n->parent->right); 61 } 62 63 if (!n->next) { 64 assert(n->queue->last == n); 65 66 if (n->parent && n->parent->left == n) 67 assert(n->parent->right == NULL); 68 } 69 70 71 if (n->parent) { 72 int a = POINTER_TO_INT(n->parent->data), b = POINTER_TO_INT(n->data); 73 if (a > b) { 74 printf("%i <= %i: NO\n", a, b); 75 abort(); 76 } 77 } 78 79 rec(n->left); 80 rec(n->right); 81} 82 83int main(AVAHI_GCC_UNUSED int argc, AVAHI_GCC_UNUSED char *argv[]) { 84 AvahiPrioQueue *q, *q2; 85 int i; 86 87 q = avahi_prio_queue_new(compare_int); 88 q2 = avahi_prio_queue_new(compare_ptr); 89 90 srand(time(NULL)); 91 92 for (i = 0; i < 10000; i++) 93 avahi_prio_queue_put(q2, avahi_prio_queue_put(q, INT_TO_POINTER(random() & 0xFFFF))); 94 95 while (q2->root) { 96 rec(q->root); 97 rec(q2->root); 98 99 assert(q->n_nodes == q2->n_nodes); 100 101 printf("%i\n", POINTER_TO_INT(((AvahiPrioQueueNode*)q2->root->data)->data)); 102 103 avahi_prio_queue_remove(q, q2->root->data); 104 avahi_prio_queue_remove(q2, q2->root); 105 } 106 107 108/* prev = 0; */ 109/* while (q->root) { */ 110/* int v = GPOINTER_TO_INT(q->root->data); */ 111/* rec(q->root); */ 112/* printf("%i\n", v); */ 113/* avahi_prio_queue_remove(q, q->root); */ 114/* assert(v >= prev); */ 115/* prev = v; */ 116/* } */ 117 118 avahi_prio_queue_free(q); 119 return 0; 120} 121