← Back to branch summary

~ubuntu-branches/debian/sid/sflphone/sid

« back to all changes in this revision

Viewing changes to daemon/libs/pjproject-2.1.0/pjlib/src/pj/rbtree.c

  • Committer: Package Import Robot
  • Author(s): Mark Purcell
  • Date: 2014-01-28 18:23:36 UTC
  • mfrom: (1.1.11)
  • Revision ID: package-import@ubuntu.com-20140128182336-3xenud1kbnwmf3mz
Tags: 1.3.0-1
http://bugs.debian.org/735846
http://bugs.debian.org/727164
http://bugs.debian.org/718178
http://bugs.debian.org/736583
http://bugs.debian.org/722040
http://bugs.debian.org/736746
* New upstream release 
  - Fixes "New Upstream Release" (Closes: #735846)
  - Fixes "Ringtone does not stop" (Closes: #727164)
  - Fixes "[sflphone-kde] crash on startup" (Closes: #718178)
  - Fixes "sflphone GUI crashes when call is hung up" (Closes: #736583)
* Build-Depends: ensure GnuTLS 2.6
  - libucommon-dev (>= 6.0.7-1.1), libccrtp-dev (>= 2.0.6-3)
  - Fixes "FTBFS Build-Depends libgnutls{26,28}-dev" (Closes: #722040)
* Fix "boost 1.49 is going away" unversioned Build-Depends: (Closes: #736746)
* Add Build-Depends: libsndfile-dev, nepomuk-core-dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
daemon/libs/pjproject-2.1.0/pjlib/src/pj/rbtree.c
 
1
/* $Id: rbtree.c 3553 2011-05-05 06:14:19Z nanang $ */
 
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 <pj/rbtree.h>
 
21
#include <pj/os.h>
 
22
 
 
23
static void left_rotate( pj_rbtree *tree, pj_rbtree_node *node ) 
 
24
{
 
25
    pj_rbtree_node *rnode, *parent;
 
26
 
 
27
    PJ_CHECK_STACK();
 
28
 
 
29
    rnode = node->right;
 
30
    if (rnode == tree->null)
 
31
        return;
 
32
    
 
33
    node->right = rnode->left;
 
34
    if (rnode->left != tree->null)
 
35
        rnode->left->parent = node;
 
36
    parent = node->parent;
 
37
    rnode->parent = parent;
 
38
    if (parent != tree->null) {
 
39
        if (parent->left == node)
 
40
           parent->left = rnode;
 
41
        else
 
42
           parent->right = rnode;
 
43
    } else {
 
44
        tree->root = rnode;
 
45
    }
 
46
    rnode->left = node;
 
47
    node->parent = rnode;
 
48
}
 
49
 
 
50
static void right_rotate( pj_rbtree *tree, pj_rbtree_node *node ) 
 
51
{
 
52
    pj_rbtree_node *lnode, *parent;
 
53
 
 
54
    PJ_CHECK_STACK();
 
55
 
 
56
    lnode = node->left;
 
57
    if (lnode == tree->null)
 
58
        return;
 
59
 
 
60
    node->left = lnode->right;
 
61
    if (lnode->right != tree->null)
 
62
        lnode->right->parent = node;
 
63
    parent = node->parent;
 
64
    lnode->parent = parent;
 
65
 
 
66
    if (parent != tree->null) {
 
67
        if (parent->left == node)
 
68
            parent->left = lnode;
 
69
        else
 
70
            parent->right = lnode;
 
71
    } else {
 
72
        tree->root = lnode;
 
73
    }
 
74
    lnode->right = node;
 
75
    node->parent = lnode;
 
76
}
 
77
 
 
78
static void insert_fixup( pj_rbtree *tree, pj_rbtree_node *node ) 
 
79
{
 
80
    pj_rbtree_node *temp, *parent;
 
81
 
 
82
    PJ_CHECK_STACK();
 
83
 
 
84
    while (node != tree->root && node->parent->color == PJ_RBCOLOR_RED) {
 
85
        parent = node->parent;
 
86
        if (parent == parent->parent->left) {
 
87
            temp = parent->parent->right;
 
88
            if (temp->color == PJ_RBCOLOR_RED) {
 
89
                temp->color = PJ_RBCOLOR_BLACK;
 
90
                node = parent;
 
91
                node->color = PJ_RBCOLOR_BLACK;
 
92
                node = node->parent;
 
93
                node->color = PJ_RBCOLOR_RED;
 
94
            } else {
 
95
                if (node == parent->right) {
 
96
                   node = parent;
 
97
                   left_rotate(tree, node);
 
98
                }
 
99
                temp = node->parent;
 
100
                temp->color = PJ_RBCOLOR_BLACK;
 
101
                temp = temp->parent;
 
102
                temp->color = PJ_RBCOLOR_RED;
 
103
                right_rotate( tree, temp);
 
104
            }
 
105
        } else {
 
106
            temp = parent->parent->left;
 
107
            if (temp->color == PJ_RBCOLOR_RED) {
 
108
                temp->color = PJ_RBCOLOR_BLACK;
 
109
                node = parent;
 
110
                node->color = PJ_RBCOLOR_BLACK;
 
111
                node = node->parent;
 
112
                node->color = PJ_RBCOLOR_RED;
 
113
            } else {
 
114
                if (node == parent->left) {
 
115
                    node = parent;
 
116
                    right_rotate(tree, node);
 
117
                }
 
118
                temp = node->parent;
 
119
                temp->color = PJ_RBCOLOR_BLACK;
 
120
                temp = temp->parent;
 
121
                temp->color = PJ_RBCOLOR_RED;
 
122
                left_rotate(tree, temp);
 
123
           }
 
124
        }
 
125
    }
 
126
        
 
127
    tree->root->color = PJ_RBCOLOR_BLACK;
 
128
}
 
129
 
 
130
 
 
131
static void delete_fixup( pj_rbtree *tree, pj_rbtree_node *node )
 
132
{
 
133
    pj_rbtree_node *temp;
 
134
 
 
135
    PJ_CHECK_STACK();
 
136
 
 
137
    while (node != tree->root && node->color == PJ_RBCOLOR_BLACK) {
 
138
        if (node->parent->left == node) {
 
139
            temp = node->parent->right;
 
140
            if (temp->color == PJ_RBCOLOR_RED) {
 
141
                temp->color = PJ_RBCOLOR_BLACK;
 
142
                node->parent->color = PJ_RBCOLOR_RED;
 
143
                left_rotate(tree, node->parent);
 
144
                temp = node->parent->right;
 
145
            }
 
146
            if (temp->left->color == PJ_RBCOLOR_BLACK && 
 
147
                temp->right->color == PJ_RBCOLOR_BLACK) 
 
148
            {
 
149
                temp->color = PJ_RBCOLOR_RED;
 
150
                node = node->parent;
 
151
            } else {
 
152
                if (temp->right->color == PJ_RBCOLOR_BLACK) {
 
153
                    temp->left->color = PJ_RBCOLOR_BLACK;
 
154
                    temp->color = PJ_RBCOLOR_RED;
 
155
                    right_rotate( tree, temp);
 
156
                    temp = node->parent->right;
 
157
                }
 
158
                temp->color = node->parent->color;
 
159
                temp->right->color = PJ_RBCOLOR_BLACK;
 
160
                node->parent->color = PJ_RBCOLOR_BLACK;
 
161
                left_rotate(tree, node->parent);
 
162
                node = tree->root;
 
163
            }
 
164
        } else {
 
165
            temp = node->parent->left;
 
166
            if (temp->color == PJ_RBCOLOR_RED) {
 
167
                temp->color = PJ_RBCOLOR_BLACK;
 
168
                node->parent->color = PJ_RBCOLOR_RED;
 
169
                right_rotate( tree, node->parent);
 
170
                temp = node->parent->left;
 
171
            }
 
172
            if (temp->right->color == PJ_RBCOLOR_BLACK && 
 
173
                temp->left->color == PJ_RBCOLOR_BLACK) 
 
174
            {
 
175
                temp->color = PJ_RBCOLOR_RED;
 
176
                node = node->parent;
 
177
            } else {
 
178
                if (temp->left->color == PJ_RBCOLOR_BLACK) {
 
179
                    temp->right->color = PJ_RBCOLOR_BLACK;
 
180
                    temp->color = PJ_RBCOLOR_RED;
 
181
                    left_rotate( tree, temp);
 
182
                    temp = node->parent->left;
 
183
                }
 
184
                temp->color = node->parent->color;
 
185
                node->parent->color = PJ_RBCOLOR_BLACK;
 
186
                temp->left->color = PJ_RBCOLOR_BLACK;
 
187
                right_rotate(tree, node->parent);
 
188
                node = tree->root;
 
189
            }
 
190
        }
 
191
    }
 
192
        
 
193
    node->color = PJ_RBCOLOR_BLACK;
 
194
}
 
195
 
 
196
 
 
197
PJ_DEF(void) pj_rbtree_init( pj_rbtree *tree, pj_rbtree_comp *comp )
 
198
{
 
199
    PJ_CHECK_STACK();
 
200
 
 
201
    tree->null = tree->root = &tree->null_node;
 
202
    tree->null->key = NULL;
 
203
    tree->null->user_data = NULL;
 
204
    tree->size = 0;
 
205
    tree->null->left = tree->null->right = tree->null->parent = tree->null;
 
206
    tree->null->color = PJ_RBCOLOR_BLACK;
 
207
    tree->comp = comp;
 
208
}
 
209
 
 
210
PJ_DEF(pj_rbtree_node*) pj_rbtree_first( pj_rbtree *tree )
 
211
{
 
212
    register pj_rbtree_node *node = tree->root;
 
213
    register pj_rbtree_node *null = tree->null;
 
214
    
 
215
    PJ_CHECK_STACK();
 
216
 
 
217
    while (node->left != null)
 
218
        node = node->left;
 
219
    return node != null ? node : NULL;
 
220
}
 
221
 
 
222
PJ_DEF(pj_rbtree_node*) pj_rbtree_last( pj_rbtree *tree )
 
223
{
 
224
    register pj_rbtree_node *node = tree->root;
 
225
    register pj_rbtree_node *null = tree->null;
 
226
    
 
227
    PJ_CHECK_STACK();
 
228
 
 
229
    while (node->right != null)
 
230
        node = node->right;
 
231
    return node != null ? node : NULL;
 
232
}
 
233
 
 
234
PJ_DEF(pj_rbtree_node*) pj_rbtree_next( pj_rbtree *tree, 
 
235
                                        register pj_rbtree_node *node )
 
236
{
 
237
    register pj_rbtree_node *null = tree->null;
 
238
    
 
239
    PJ_CHECK_STACK();
 
240
 
 
241
    if (node->right != null) {
 
242
        for (node=node->right; node->left!=null; node = node->left)
 
243
            /* void */;
 
244
    } else {
 
245
        register pj_rbtree_node *temp = node->parent;
 
246
        while (temp!=null && temp->right==node) {
 
247
            node = temp;
 
248
            temp = temp->parent;
 
249
        }
 
250
        node = temp;
 
251
    }    
 
252
    return node != null ? node : NULL;
 
253
}
 
254
 
 
255
PJ_DEF(pj_rbtree_node*) pj_rbtree_prev( pj_rbtree *tree, 
 
256
                                        register pj_rbtree_node *node )
 
257
{
 
258
    register pj_rbtree_node *null = tree->null;
 
259
    
 
260
    PJ_CHECK_STACK();
 
261
 
 
262
    if (node->left != null) {
 
263
        for (node=node->left; node->right!=null; node=node->right)
 
264
           /* void */;
 
265
    } else {
 
266
        register pj_rbtree_node *temp = node->parent;
 
267
        while (temp!=null && temp->left==node) {
 
268
            node = temp;
 
269
            temp = temp->parent;
 
270
        }
 
271
        node = temp;
 
272
    }    
 
273
    return node != null ? node : NULL;
 
274
}
 
275
 
 
276
PJ_DEF(int) pj_rbtree_insert( pj_rbtree *tree, 
 
277
                              pj_rbtree_node *element )
 
278
{
 
279
    int rv = 0;
 
280
    pj_rbtree_node *node, *parent = tree->null, 
 
281
                   *null = tree->null;
 
282
    pj_rbtree_comp *comp = tree->comp;
 
283
        
 
284
    PJ_CHECK_STACK();
 
285
 
 
286
    node = tree->root;  
 
287
    while (node != null) {
 
288
        rv = (*comp)(element->key, node->key);
 
289
        if (rv == 0) {
 
290
            /* found match, i.e. entry with equal key already exist */
 
291
            return -1;
 
292
        }    
 
293
        parent = node;
 
294
        node = rv < 0 ? node->left : node->right;
 
295
    }
 
296
 
 
297
    element->color = PJ_RBCOLOR_RED;
 
298
    element->left = element->right = null;
 
299
 
 
300
    node = element;
 
301
    if (parent != null) {
 
302
        node->parent = parent;
 
303
        if (rv < 0)
 
304
           parent->left = node;
 
305
        else
 
306
           parent->right = node;
 
307
        insert_fixup( tree, node);
 
308
    } else {
 
309
        tree->root = node;
 
310
        node->parent = null;
 
311
        node->color = PJ_RBCOLOR_BLACK;
 
312
    }
 
313
        
 
314
    ++tree->size;
 
315
    return 0;
 
316
}
 
317
 
 
318
 
 
319
PJ_DEF(pj_rbtree_node*) pj_rbtree_find( pj_rbtree *tree,
 
320
                                        const void *key )
 
321
{
 
322
    int rv;
 
323
    pj_rbtree_node *node = tree->root;
 
324
    pj_rbtree_node *null = tree->null;
 
325
    pj_rbtree_comp *comp = tree->comp;
 
326
    
 
327
    while (node != null) {
 
328
        rv = (*comp)(key, node->key);
 
329
        if (rv == 0)
 
330
            return node;
 
331
        node = rv < 0 ? node->left : node->right;
 
332
    }
 
333
    return node != null ? node : NULL;
 
334
}
 
335
 
 
336
PJ_DEF(pj_rbtree_node*) pj_rbtree_erase( pj_rbtree *tree,
 
337
                                         pj_rbtree_node *node )
 
338
{
 
339
    pj_rbtree_node *succ;
 
340
    pj_rbtree_node *null = tree->null;
 
341
    pj_rbtree_node *child;
 
342
    pj_rbtree_node *parent;
 
343
    
 
344
    PJ_CHECK_STACK();
 
345
 
 
346
    if (node->left == null || node->right == null) {
 
347
        succ = node;
 
348
    } else {
 
349
        for (succ=node->right; succ->left!=null; succ=succ->left)
 
350
           /* void */;
 
351
    }
 
352
 
 
353
    child = succ->left != null ? succ->left : succ->right;
 
354
    parent = succ->parent;
 
355
    child->parent = parent;
 
356
    
 
357
    if (parent != null) {
 
358
        if (parent->left == succ)
 
359
            parent->left = child;
 
360
        else
 
361
           parent->right = child;
 
362
    } else
 
363
        tree->root = child;
 
364
 
 
365
    if (succ != node) {
 
366
        succ->parent = node->parent;
 
367
        succ->left = node->left;
 
368
        succ->right = node->right;
 
369
        succ->color = node->color;
 
370
 
 
371
        parent = node->parent;
 
372
        if (parent != null) {
 
373
           if (parent->left==node)
 
374
                parent->left=succ;
 
375
           else
 
376
                parent->right=succ;
 
377
        }
 
378
        if (node->left != null)
 
379
           node->left->parent = succ;;
 
380
        if (node->right != null)
 
381
            node->right->parent = succ;
 
382
 
 
383
        if (tree->root == node)
 
384
           tree->root = succ;
 
385
    }
 
386
 
 
387
    if (succ->color == PJ_RBCOLOR_BLACK) {
 
388
        if (child != null) 
 
389
            delete_fixup(tree, child);
 
390
        tree->null->color = PJ_RBCOLOR_BLACK;
 
391
    }
 
392
 
 
393
    --tree->size;
 
394
    return node;
 
395
}
 
396
 
 
397
 
 
398
PJ_DEF(unsigned) pj_rbtree_max_height( pj_rbtree *tree,
 
399
                                       pj_rbtree_node *node )
 
400
{
 
401
    unsigned l, r;
 
402
    
 
403
    PJ_CHECK_STACK();
 
404
 
 
405
    if (node==NULL) 
 
406
        node = tree->root;
 
407
    
 
408
    l = node->left != tree->null ? pj_rbtree_max_height(tree,node->left)+1 : 0;
 
409
    r = node->right != tree->null ? pj_rbtree_max_height(tree,node->right)+1 : 0;
 
410
    return l > r ? l : r;
 
411
}
 
412
 
 
413
PJ_DEF(unsigned) pj_rbtree_min_height( pj_rbtree *tree,
 
414
                                       pj_rbtree_node *node )
 
415
{
 
416
    unsigned l, r;
 
417
    
 
418
    PJ_CHECK_STACK();
 
419
 
 
420
    if (node==NULL) 
 
421
        node=tree->root;
 
422
    
 
423
    l = (node->left != tree->null) ? pj_rbtree_max_height(tree,node->left)+1 : 0;
 
424
    r = (node->right != tree->null) ? pj_rbtree_max_height(tree,node->right)+1 : 0;
 
425
    return l > r ? r : l;
 
426
}
 
427
 
 
428