Add support for ICE/STUN/TURN in res_rtp_asterisk and chan_sip.
[asterisk/asterisk.git] / res / pjproject / pjlib / src / pjlib-test / rbtree.c
1 /* $Id$ */
2 /* 
3  * Copyright (C) 2008-2011 Teluu Inc. (http://www.teluu.com)
4  * Copyright (C) 2003-2008 Benny Prijono <benny@prijono.org>
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
19  */
20 #include "test.h"
21
22 #if INCLUDE_RBTREE_TEST
23
24 #include <pjlib.h>
25
26 #define LOOP        32
27 #define MIN_COUNT   64
28 #define MAX_COUNT   (LOOP * MIN_COUNT)
29 #define STRSIZE     16
30 #define THIS_FILE   "rbtree_test"
31
32 typedef struct node_key
33 {
34     pj_uint32_t hash;
35     char str[STRSIZE];
36 } node_key;
37
38 static int compare_node(const node_key *k1, const node_key *k2)
39 {
40     if (k1->hash == k2->hash) {
41         return strcmp(k1->str, k2->str);
42     } else {
43         return k1->hash < k2->hash ? -1 : 1;
44     }
45 }
46
47 void randomize_string(char *str, int len)
48 {
49     int i;
50     for (i=0; i<len-1; ++i)
51         str[i] = (char)('a' + pj_rand() % 26);
52     str[len-1] = '\0';
53 }
54
55 static int test(void)
56 {
57     pj_rbtree rb;
58     node_key *key;
59     pj_rbtree_node *node;
60     pj_pool_t *pool;
61     int err=0;
62     int count = MIN_COUNT;
63     int i;
64     unsigned size;
65
66     pj_rbtree_init(&rb, (pj_rbtree_comp*)&compare_node);
67     size = MAX_COUNT*(sizeof(*key)+PJ_RBTREE_NODE_SIZE) + 
68                            PJ_RBTREE_SIZE + PJ_POOL_SIZE;
69     pool = pj_pool_create( mem, "pool", size, 0, NULL);
70     if (!pool) {
71         PJ_LOG(3,("test", "...error: creating pool of %u bytes", size));
72         return -10;
73     }
74
75     key = (node_key *)pj_pool_alloc(pool, MAX_COUNT*sizeof(*key));
76     if (!key)
77         return -20;
78
79     node = (pj_rbtree_node*)pj_pool_alloc(pool, MAX_COUNT*sizeof(*node));
80     if (!node)
81         return -30;
82
83     for (i=0; i<LOOP; ++i) {
84         int j;
85         pj_rbtree_node *prev, *it;
86         pj_timestamp t1, t2, t_setup, t_insert, t_search, t_erase;
87
88         pj_assert(rb.size == 0);
89
90         t_setup.u32.lo = t_insert.u32.lo = t_search.u32.lo = t_erase.u32.lo = 0;
91
92         for (j=0; j<count; j++) {
93             randomize_string(key[j].str, STRSIZE);
94
95             pj_get_timestamp(&t1);
96             node[j].key = &key[j];
97             node[j].user_data = key[j].str;
98             key[j].hash = pj_hash_calc(0, key[j].str, PJ_HASH_KEY_STRING);
99             pj_get_timestamp(&t2);
100             t_setup.u32.lo += (t2.u32.lo - t1.u32.lo);
101
102             pj_get_timestamp(&t1);
103             pj_rbtree_insert(&rb, &node[j]);
104             pj_get_timestamp(&t2);
105             t_insert.u32.lo += (t2.u32.lo - t1.u32.lo);
106         }
107
108         pj_assert(rb.size == (unsigned)count);
109
110         // Iterate key, make sure they're sorted.
111         prev = NULL;
112         it = pj_rbtree_first(&rb);
113         while (it) {
114             if (prev) {
115                 if (compare_node((node_key*)prev->key,(node_key*)it->key)>=0) {
116                     ++err;
117                     PJ_LOG(3, (THIS_FILE, "Error: %s >= %s", 
118                                (char*)prev->user_data, (char*)it->user_data));
119                 }
120             }
121             prev = it;
122             it = pj_rbtree_next(&rb, it);
123         }
124
125         // Search.
126         for (j=0; j<count; j++) {
127             pj_get_timestamp(&t1);
128             it = pj_rbtree_find(&rb, &key[j]);
129             pj_get_timestamp(&t2);
130             t_search.u32.lo += (t2.u32.lo - t1.u32.lo);
131
132             pj_assert(it != NULL);
133             if (it == NULL)
134                 ++err;
135         }
136
137         // Erase node.
138         for (j=0; j<count; j++) {
139             pj_get_timestamp(&t1);
140             it = pj_rbtree_erase(&rb, &node[j]);
141             pj_get_timestamp(&t2);
142             t_erase.u32.lo += (t2.u32.lo - t1.u32.lo);
143         }
144
145         PJ_LOG(4, (THIS_FILE, 
146                 "...count:%d, setup:%d, insert:%d, search:%d, erase:%d",
147                 count,
148                 t_setup.u32.lo / count, t_insert.u32.lo / count,
149                 t_search.u32.lo / count, t_erase.u32.lo / count));
150
151         count = 2 * count;
152         if (count > MAX_COUNT)
153             break;
154     }
155
156     pj_pool_release(pool);
157     return err;
158 }
159
160
161 int rbtree_test()
162 {
163     return test();
164 }
165
166 #endif  /* INCLUDE_RBTREE_TEST */
167
168