blob: 7b57b2d39a78abc2320b8cf17e6a1de300a81ea5
1 | /* |
2 | * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> |
3 | * |
4 | * This file is part of FFmpeg. |
5 | * |
6 | * FFmpeg is free software; you can redistribute it and/or |
7 | * modify it under the terms of the GNU Lesser General Public |
8 | * License as published by the Free Software Foundation; either |
9 | * version 2.1 of the License, or (at your option) any later version. |
10 | * |
11 | * FFmpeg 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 GNU |
14 | * Lesser General Public License for more details. |
15 | * |
16 | * You should have received a copy of the GNU Lesser General Public |
17 | * License along with FFmpeg; if not, write to the Free Software |
18 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
19 | */ |
20 | |
21 | #include "error.h" |
22 | #include "log.h" |
23 | #include "mem.h" |
24 | #include "tree.h" |
25 | |
26 | typedef struct AVTreeNode { |
27 | struct AVTreeNode *child[2]; |
28 | void *elem; |
29 | int state; |
30 | } AVTreeNode; |
31 | |
32 | const int av_tree_node_size = sizeof(AVTreeNode); |
33 | |
34 | struct AVTreeNode *av_tree_node_alloc(void) |
35 | { |
36 | return av_mallocz(sizeof(struct AVTreeNode)); |
37 | } |
38 | |
39 | void *av_tree_find(const AVTreeNode *t, void *key, |
40 | int (*cmp)(const void *key, const void *b), void *next[2]) |
41 | { |
42 | if (t) { |
43 | unsigned int v = cmp(key, t->elem); |
44 | if (v) { |
45 | if (next) |
46 | next[v >> 31] = t->elem; |
47 | return av_tree_find(t->child[(v >> 31) ^ 1], key, cmp, next); |
48 | } else { |
49 | if (next) { |
50 | av_tree_find(t->child[0], key, cmp, next); |
51 | av_tree_find(t->child[1], key, cmp, next); |
52 | } |
53 | return t->elem; |
54 | } |
55 | } |
56 | return NULL; |
57 | } |
58 | |
59 | void *av_tree_insert(AVTreeNode **tp, void *key, |
60 | int (*cmp)(const void *key, const void *b), AVTreeNode **next) |
61 | { |
62 | AVTreeNode *t = *tp; |
63 | if (t) { |
64 | unsigned int v = cmp(t->elem, key); |
65 | void *ret; |
66 | if (!v) { |
67 | if (*next) |
68 | return t->elem; |
69 | else if (t->child[0] || t->child[1]) { |
70 | int i = !t->child[0]; |
71 | void *next_elem[2]; |
72 | av_tree_find(t->child[i], key, cmp, next_elem); |
73 | key = t->elem = next_elem[i]; |
74 | v = -i; |
75 | } else { |
76 | *next = t; |
77 | *tp = NULL; |
78 | return NULL; |
79 | } |
80 | } |
81 | ret = av_tree_insert(&t->child[v >> 31], key, cmp, next); |
82 | if (!ret) { |
83 | int i = (v >> 31) ^ !!*next; |
84 | AVTreeNode **child = &t->child[i]; |
85 | t->state += 2 * i - 1; |
86 | |
87 | if (!(t->state & 1)) { |
88 | if (t->state) { |
89 | /* The following code is equivalent to |
90 | * if ((*child)->state * 2 == -t->state) |
91 | * rotate(child, i ^ 1); |
92 | * rotate(tp, i); |
93 | * |
94 | * with rotate(): |
95 | * static void rotate(AVTreeNode **tp, int i) |
96 | * { |
97 | * AVTreeNode *t= *tp; |
98 | * |
99 | * *tp = t->child[i]; |
100 | * t->child[i] = t->child[i]->child[i ^ 1]; |
101 | * (*tp)->child[i ^ 1] = t; |
102 | * i = 4 * t->state + 2 * (*tp)->state + 12; |
103 | * t->state = ((0x614586 >> i) & 3) - 1; |
104 | * (*tp)->state = ((0x400EEA >> i) & 3) - 1 + |
105 | * ((*tp)->state >> 1); |
106 | * } |
107 | * but such a rotate function is both bigger and slower |
108 | */ |
109 | if ((*child)->state * 2 == -t->state) { |
110 | *tp = (*child)->child[i ^ 1]; |
111 | (*child)->child[i ^ 1] = (*tp)->child[i]; |
112 | (*tp)->child[i] = *child; |
113 | *child = (*tp)->child[i ^ 1]; |
114 | (*tp)->child[i ^ 1] = t; |
115 | |
116 | (*tp)->child[0]->state = -((*tp)->state > 0); |
117 | (*tp)->child[1]->state = (*tp)->state < 0; |
118 | (*tp)->state = 0; |
119 | } else { |
120 | *tp = *child; |
121 | *child = (*child)->child[i ^ 1]; |
122 | (*tp)->child[i ^ 1] = t; |
123 | if ((*tp)->state) |
124 | t->state = 0; |
125 | else |
126 | t->state >>= 1; |
127 | (*tp)->state = -t->state; |
128 | } |
129 | } |
130 | } |
131 | if (!(*tp)->state ^ !!*next) |
132 | return key; |
133 | } |
134 | return ret; |
135 | } else { |
136 | *tp = *next; |
137 | *next = NULL; |
138 | if (*tp) { |
139 | (*tp)->elem = key; |
140 | return NULL; |
141 | } else |
142 | return key; |
143 | } |
144 | } |
145 | |
146 | void av_tree_destroy(AVTreeNode *t) |
147 | { |
148 | if (t) { |
149 | av_tree_destroy(t->child[0]); |
150 | av_tree_destroy(t->child[1]); |
151 | av_free(t); |
152 | } |
153 | } |
154 | |
155 | void av_tree_enumerate(AVTreeNode *t, void *opaque, |
156 | int (*cmp)(void *opaque, void *elem), |
157 | int (*enu)(void *opaque, void *elem)) |
158 | { |
159 | if (t) { |
160 | int v = cmp ? cmp(opaque, t->elem) : 0; |
161 | if (v >= 0) |
162 | av_tree_enumerate(t->child[0], opaque, cmp, enu); |
163 | if (v == 0) |
164 | enu(opaque, t->elem); |
165 | if (v <= 0) |
166 | av_tree_enumerate(t->child[1], opaque, cmp, enu); |
167 | } |
168 | } |
169 |