Mercurial > libavutil.hg
annotate tree.c @ 413:a54e20281de9 libavutil
Move *malloc() out of tree.c, that way the code can be used with
flat arrays which have lower overhead than millions of mallocd() elements.
author | michael |
---|---|
date | Fri, 04 Jan 2008 17:52:16 +0000 |
parents | 357ac44f4720 |
children | a30cad55db8b |
rev | line source |
---|---|
136 | 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 "common.h" | |
22 #include "log.h" | |
23 #include "tree.h" | |
24 | |
25 typedef struct AVTreeNode{ | |
26 struct AVTreeNode *child[2]; | |
27 void *elem; | |
28 int state; | |
29 }AVTreeNode; | |
30 | |
413
a54e20281de9
Move *malloc() out of tree.c, that way the code can be used with
michael
parents:
412
diff
changeset
|
31 const int av_tree_node_size = sizeof(AVTreeNode); |
a54e20281de9
Move *malloc() out of tree.c, that way the code can be used with
michael
parents:
412
diff
changeset
|
32 |
136 | 33 void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){ |
34 if(t){ | |
35 unsigned int v= cmp(t->elem, key); | |
36 if(v){ | |
37 if(next) next[(v>>31)^1]= t->elem; | |
38 return av_tree_find(t->child[v>>31], key, cmp, next); | |
39 }else{ | |
412
357ac44f4720
Always set next correctly, even if a matching element is found (that is
michael
parents:
404
diff
changeset
|
40 if(next){ |
357ac44f4720
Always set next correctly, even if a matching element is found (that is
michael
parents:
404
diff
changeset
|
41 av_tree_find(t->child[0], key, cmp, next); |
357ac44f4720
Always set next correctly, even if a matching element is found (that is
michael
parents:
404
diff
changeset
|
42 av_tree_find(t->child[1], key, cmp, next); |
357ac44f4720
Always set next correctly, even if a matching element is found (that is
michael
parents:
404
diff
changeset
|
43 } |
136 | 44 return t->elem; |
45 } | |
46 } | |
47 return NULL; | |
48 } | |
49 | |
413
a54e20281de9
Move *malloc() out of tree.c, that way the code can be used with
michael
parents:
412
diff
changeset
|
50 void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){ |
136 | 51 AVTreeNode *t= *tp; |
52 if(t){ | |
53 unsigned int v= cmp(t->elem, key); | |
54 if(v){ | |
55 int i= v>>31; | |
56 AVTreeNode **child= &t->child[i]; | |
413
a54e20281de9
Move *malloc() out of tree.c, that way the code can be used with
michael
parents:
412
diff
changeset
|
57 void *ret= av_tree_insert(child, key, cmp, next); |
136 | 58 if(!ret){ |
59 t->state -= ((int)v>>31)|1; | |
60 if(!(t->state&1)){ | |
61 if(t->state){ | |
62 if((*child)->state*2 == t->state){ | |
63 *tp= *child; | |
64 *child= (*child)->child[i^1]; | |
65 (*tp)->child[i^1]= t; | |
66 t->state= 0; | |
67 }else{ | |
68 *tp= (*child)->child[i^1]; | |
69 (*child)->child[i^1]= (*tp)->child[i]; | |
70 (*tp)->child[i]= *child; | |
71 *child= (*tp)->child[i^1]; | |
72 (*tp)->child[i^1]= t; | |
73 | |
74 i= (*tp)->state > 0; | |
75 (*tp)->child[i ]->state= 0; | |
76 (*tp)->child[i^1]->state= -(*tp)->state; | |
77 } | |
78 (*tp)->state=0; | |
79 } | |
80 return key; | |
81 } | |
82 } | |
83 return ret; | |
84 }else{ | |
85 return t->elem; | |
86 } | |
87 }else{ | |
413
a54e20281de9
Move *malloc() out of tree.c, that way the code can be used with
michael
parents:
412
diff
changeset
|
88 *tp= *next; *next= NULL; |
136 | 89 (*tp)->elem= key; |
90 return NULL; | |
91 } | |
92 } | |
93 | |
94 void av_tree_destroy(AVTreeNode *t){ | |
95 av_tree_destroy(t->child[0]); | |
96 av_tree_destroy(t->child[1]); | |
97 av_free(t); | |
98 } | |
99 | |
100 #if 0 | |
101 void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){ | |
137
dbcf66639764
improve enumerate so arbitrary ranges can be enumerated quickly
michael
parents:
136
diff
changeset
|
102 int v= f(opaque, t->elem); |
dbcf66639764
improve enumerate so arbitrary ranges can be enumerated quickly
michael
parents:
136
diff
changeset
|
103 if(v>=0) av_tree_enumerate(t->child[0], opaque, f); |
dbcf66639764
improve enumerate so arbitrary ranges can be enumerated quickly
michael
parents:
136
diff
changeset
|
104 if(v<=0) av_tree_enumerate(t->child[1], opaque, f); |
136 | 105 } |
106 #endif | |
107 | |
108 #ifdef TEST | |
109 | |
110 static int check(AVTreeNode *t){ | |
111 if(t){ | |
112 int left= check(t->child[0]); | |
113 int right= check(t->child[1]); | |
114 | |
115 if(left>999 || right>999) | |
116 return 1000; | |
117 if(right - left != t->state) | |
118 return 1000; | |
119 if(t->state>1 || t->state<-1) | |
120 return 1000; | |
121 return FFMAX(left, right)+1; | |
122 } | |
123 return 0; | |
124 } | |
125 | |
126 static void print(AVTreeNode *t, int depth){ | |
127 int i; | |
128 for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " "); | |
129 if(t){ | |
130 av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem); | |
131 print(t->child[0], depth+1); | |
132 print(t->child[1], depth+1); | |
133 }else | |
134 av_log(NULL, AV_LOG_ERROR, "NULL\n"); | |
135 } | |
136 | |
137 int cmp(const void *a, const void *b){ | |
138 return a-b; | |
139 } | |
140 | |
404 | 141 int main(void){ |
136 | 142 int i,j,k; |
141 | 143 AVTreeNode *root= NULL; |
136 | 144 |
145 for(i=0; i<10000; i++){ | |
146 int j= (random()%863294); | |
147 if(check(root) > 999){ | |
148 av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i); | |
149 print(root, 0); | |
150 return -1; | |
151 } | |
152 av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j); | |
153 av_tree_insert(&root, (void*)(j+1), cmp); | |
154 } | |
155 return 0; | |
156 } | |
157 #endif |