← Back to branch summary

~ubuntu-branches/ubuntu/wily/sflphone/wily

« back to all changes in this revision

Viewing changes to daemon/libs/pjproject-2.0.1/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)
  • mto: This revision was merged to the branch mainline in revision 24.
  • Revision ID: package-import@ubuntu.com-20140128182336-3xenud1kbnwmf3mz
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.0.1/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
 
}