FFmpeg
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
tree.c
Go to the documentation of this file.
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 "log.h"
22 #include "mem.h"
23 #include "tree.h"
24 
25 typedef struct AVTreeNode {
26  struct AVTreeNode *child[2];
27  void *elem;
28  int state;
29 } AVTreeNode;
30 
31 const int av_tree_node_size = sizeof(AVTreeNode);
32 
34 {
35  return av_mallocz(sizeof(struct AVTreeNode));
36 }
37 
38 void *av_tree_find(const AVTreeNode *t, void *key,
39  int (*cmp)(void *key, const void *b), void *next[2])
40 {
41  if (t) {
42  unsigned int v = cmp(key, t->elem);
43  if (v) {
44  if (next) next[v >> 31] = t->elem;
45  return av_tree_find(t->child[(v >> 31) ^ 1], key, cmp, next);
46  } else {
47  if (next) {
48  av_tree_find(t->child[0], key, cmp, next);
49  av_tree_find(t->child[1], key, cmp, next);
50  }
51  return t->elem;
52  }
53  }
54  return NULL;
55 }
56 
57 void *av_tree_insert(AVTreeNode **tp, void *key,
58  int (*cmp)(void *key, const void *b), AVTreeNode **next)
59 {
60  AVTreeNode *t = *tp;
61  if (t) {
62  unsigned int v = cmp(t->elem, key);
63  void *ret;
64  if (!v) {
65  if (*next)
66  return t->elem;
67  else if (t->child[0] || t->child[1]) {
68  int i = !t->child[0];
69  void *next_elem[2];
70  av_tree_find(t->child[i], key, cmp, next_elem);
71  key = t->elem = next_elem[i];
72  v = -i;
73  } else {
74  *next = t;
75  *tp = NULL;
76  return NULL;
77  }
78  }
79  ret = av_tree_insert(&t->child[v >> 31], key, cmp, next);
80  if (!ret) {
81  int i = (v >> 31) ^ !!*next;
82  AVTreeNode **child = &t->child[i];
83  t->state += 2 * i - 1;
84 
85  if (!(t->state & 1)) {
86  if (t->state) {
87  /* The following code is equivalent to
88  if((*child)->state*2 == -t->state)
89  rotate(child, i^1);
90  rotate(tp, i);
91 
92  with rotate():
93  static void rotate(AVTreeNode **tp, int i) {
94  AVTreeNode *t= *tp;
95 
96  *tp= t->child[i];
97  t->child[i]= t->child[i]->child[i^1];
98  (*tp)->child[i^1]= t;
99  i= 4*t->state + 2*(*tp)->state + 12;
100  t ->state= ((0x614586 >> i) & 3)-1;
101  (*tp)->state= ((*tp)->state>>1) + ((0x400EEA >> i) & 3)-1;
102  }
103  but such a rotate function is both bigger and slower
104  */
105  if (( *child )->state * 2 == -t->state) {
106  *tp = (*child)->child[i ^ 1];
107  (*child)->child[i ^ 1] = (*tp)->child[i];
108  (*tp)->child[i] = *child;
109  *child = ( *tp )->child[i ^ 1];
110  (*tp)->child[i ^ 1] = t;
111 
112  (*tp)->child[0]->state = -((*tp)->state > 0);
113  (*tp)->child[1]->state = (*tp)->state < 0;
114  (*tp)->state = 0;
115  } else {
116  *tp = *child;
117  *child = (*child)->child[i ^ 1];
118  (*tp)->child[i ^ 1] = t;
119  if ((*tp)->state) t->state = 0;
120  else t->state >>= 1;
121  (*tp)->state = -t->state;
122  }
123  }
124  }
125  if (!(*tp)->state ^ !!*next)
126  return key;
127  }
128  return ret;
129  } else {
130  *tp = *next;
131  *next = NULL;
132  if (*tp) {
133  (*tp)->elem = key;
134  return NULL;
135  } else
136  return key;
137  }
138 }
139 
141 {
142  if (t) {
143  av_tree_destroy(t->child[0]);
144  av_tree_destroy(t->child[1]);
145  av_free(t);
146  }
147 }
148 
149 void av_tree_enumerate(AVTreeNode *t, void *opaque,
150  int (*cmp)(void *opaque, void *elem),
151  int (*enu)(void *opaque, void *elem))
152 {
153  if (t) {
154  int v = cmp ? cmp(opaque, t->elem) : 0;
155  if (v >= 0)
156  av_tree_enumerate(t->child[0], opaque, cmp, enu);
157  if (v == 0)
158  enu(opaque, t->elem);
159  if (v <= 0)
160  av_tree_enumerate(t->child[1], opaque, cmp, enu);
161  }
162 }
163 
164 #ifdef TEST
165 
166 #include "common.h"
167 #include "lfg.h"
168 
169 static int check(AVTreeNode *t)
170 {
171  if (t) {
172  int left = check(t->child[0]);
173  int right = check(t->child[1]);
174 
175  if (left>999 || right>999)
176  return 1000;
177  if (right - left != t->state)
178  return 1000;
179  if (t->state>1 || t->state<-1)
180  return 1000;
181  return FFMAX(left, right) + 1;
182  }
183  return 0;
184 }
185 
186 static void print(AVTreeNode *t, int depth)
187 {
188  int i;
189  for (i = 0; i < depth * 4; i++) av_log(NULL, AV_LOG_ERROR, " ");
190  if (t) {
191  av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem);
192  print(t->child[0], depth + 1);
193  print(t->child[1], depth + 1);
194  } else
195  av_log(NULL, AV_LOG_ERROR, "NULL\n");
196 }
197 
198 static int cmp(void *a, const void *b)
199 {
200  return (uint8_t *) a - (const uint8_t *) b;
201 }
202 
203 int main (void)
204 {
205  int i;
206  void *k;
207  AVTreeNode *root = NULL, *node = NULL;
208  AVLFG prng;
209 
210  av_lfg_init(&prng, 1);
211 
212  for (i = 0; i < 10000; i++) {
213  intptr_t j = av_lfg_get(&prng) % 86294;
214  if (check(root) > 999) {
215  av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
216  print(root, 0);
217  return -1;
218  }
219  av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", (int)j);
220  if (!node)
221  node = av_tree_node_alloc();
222  av_tree_insert(&root, (void *) (j + 1), cmp, &node);
223 
224  j = av_lfg_get(&prng) % 86294;
225  {
226  AVTreeNode *node2 = NULL;
227  av_log(NULL, AV_LOG_ERROR, "removing %4d\n", (int)j);
228  av_tree_insert(&root, (void *) (j + 1), cmp, &node2);
229  k = av_tree_find(root, (void *) (j + 1), cmp, NULL);
230  if (k)
231  av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i);
232  }
233  }
234  return 0;
235 }
236 #endif