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