1 /* frame_data_sequence.c
2 * Implements a sequence of frame_data structures
6 * Wireshark - Network traffic analyzer
7 * By Gerald Combs <gerald@wireshark.org>
8 * Copyright 1998 Gerald Combs
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version 2
13 * of the License, or (at your option) any later version.
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software
22 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
31 #include <epan/packet.h>
33 #include "frame_data_sequence.h"
36 * We store the frame_data structures in a radix tree, with 1024
37 * elements per level. The leaf nodes are arrays of 1024 frame_data
38 * structures; the nodes above them are arrays of 1024 pointers to
39 * the nodes below them. The capture_file structure has a pointer
42 * As frame numbers are 32 bits, and as 1024 is 2^10, that gives us
43 * up to 4 levels of tree.
45 #define LOG2_NODES_PER_LEVEL 10
46 #define NODES_PER_LEVEL (1<<LOG2_NODES_PER_LEVEL)
48 struct _frame_data_sequence {
49 guint32 count; /* Total number of frames */
50 void *ptree_root; /* Pointer to the root node */
54 * For a given frame number, calculate the indices into a level 3
55 * node, a level 2 node, a level 1 node, and a leaf node.
57 #define LEVEL_3_INDEX(framenum) \
58 ((framenum) >> (3*LOG2_NODES_PER_LEVEL))
59 #define LEVEL_2_INDEX(framenum) \
60 (((framenum) >> (2*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
61 #define LEVEL_1_INDEX(framenum) \
62 (((framenum) >> (1*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
63 #define LEAF_INDEX(framenum) \
64 (((framenum) >> (0*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
67 new_frame_data_sequence(void)
69 frame_data_sequence *fds;
71 fds = g_malloc(sizeof *fds);
73 fds->ptree_root = NULL;
78 * Add a new frame_data structure to a frame_data_sequence.
81 frame_data_sequence_add(frame_data_sequence *fds, frame_data *fdata)
86 frame_data ****level3;
90 * The current value of fds->count is the index value for the new frame,
91 * because the index value for a frame is the frame number - 1, and
92 * if we currently have fds->count frames, the the frame number of
93 * the last frame in the collection is fds->count, so its index value
96 if (fds->count == 0) {
97 /* The tree is empty; allocate the first leaf node, which will be
99 leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
101 fds->ptree_root = leaf;
102 } else if (fds->count < NODES_PER_LEVEL) {
103 /* It's a 1-level tree, and is going to stay that way for now. */
104 leaf = fds->ptree_root;
105 node = &leaf[fds->count];
106 } else if (fds->count == NODES_PER_LEVEL) {
107 /* It's a 1-level tree that will turn into a 2-level tree. */
108 level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
109 memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
110 level1[0] = fds->ptree_root;
111 leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
114 fds->ptree_root = level1;
115 } else if (fds->count < NODES_PER_LEVEL*NODES_PER_LEVEL) {
116 /* It's a 2-level tree, and is going to stay that way for now. */
117 level1 = fds->ptree_root;
118 leaf = level1[fds->count >> LOG2_NODES_PER_LEVEL];
120 leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
121 level1[fds->count >> LOG2_NODES_PER_LEVEL] = leaf;
123 node = &leaf[LEAF_INDEX(fds->count)];
124 } else if (fds->count == NODES_PER_LEVEL*NODES_PER_LEVEL) {
125 /* It's a 2-level tree that will turn into a 3-level tree */
126 level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL);
127 memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL);
128 level2[0] = fds->ptree_root;
129 level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
130 memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
132 leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
135 fds->ptree_root = level2;
136 } else if (fds->count < NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
137 /* It's a 3-level tree, and is going to stay that way for now. */
138 level2 = fds->ptree_root;
139 level1 = level2[fds->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
140 if (level1 == NULL) {
141 level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
142 memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
143 level2[fds->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)] = level1;
145 leaf = level1[LEVEL_1_INDEX(fds->count)];
147 leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
148 level1[LEVEL_1_INDEX(fds->count)] = leaf;
150 node = &leaf[LEAF_INDEX(fds->count)];
151 } else if (fds->count == NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
152 /* It's a 3-level tree that will turn into a 4-level tree */
153 level3 = g_malloc((sizeof *level3)*NODES_PER_LEVEL);
154 memset(level3, 0, (sizeof *level3)*NODES_PER_LEVEL);
155 level3[0] = fds->ptree_root;
156 level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL);
157 memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL);
159 level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
160 memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
162 leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
165 fds->ptree_root = level3;
167 /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
168 2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
169 so fds->count is always less < NODES_PER_LEVEL^4.
171 XXX - we should fail if fds->count is 2^31-1, or should
172 make the frame numbers 64-bit and just let users run
173 themselves out of address space or swap space. :-) */
174 /* It's a 4-level tree, and is going to stay that way forever. */
175 level3 = fds->ptree_root;
176 level2 = level3[LEVEL_3_INDEX(fds->count)];
177 if (level2 == NULL) {
178 level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL);
179 memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL);
180 level3[LEVEL_3_INDEX(fds->count)] = level2;
182 level1 = level2[LEVEL_2_INDEX(fds->count)];
183 if (level1 == NULL) {
184 level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
185 memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
186 level2[LEVEL_2_INDEX(fds->count)] = level1;
188 leaf = level1[LEVEL_1_INDEX(fds->count)];
190 leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
191 level1[LEVEL_1_INDEX(fds->count)] = leaf;
193 node = &leaf[LEAF_INDEX(fds->count)];
201 * Find the frame_data for the specified frame number.
204 frame_data_sequence_find(frame_data_sequence *fds, guint32 num)
208 frame_data ***level2;
209 frame_data ****level3;
212 /* There is no frame number 0 */
216 /* Convert it into an index number. */
218 if (num >= fds->count) {
219 /* There aren't that many frames. */
223 if (fds->count <= NODES_PER_LEVEL) {
224 /* It's a 1-level tree. */
225 leaf = fds->ptree_root;
228 if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
229 /* It's a 2-level tree. */
230 level1 = fds->ptree_root;
231 leaf = level1[num >> LOG2_NODES_PER_LEVEL];
232 return &leaf[LEAF_INDEX(num)];
234 if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
235 /* It's a 3-level tree. */
236 level2 = fds->ptree_root;
237 level1 = level2[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
238 leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)];
239 return &leaf[LEAF_INDEX(num)];
241 /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
242 2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
243 so fds->count is always less < NODES_PER_LEVEL^4. */
244 /* It's a 4-level tree, and is going to stay that way forever. */
245 level3 = fds->ptree_root;
246 level2 = level3[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
247 level1 = level2[(num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1)];
248 leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)];
249 return &leaf[LEAF_INDEX(num)];
253 * Free a frame_data_sequence and all the frame_data structures in it.
256 free_frame_data_sequence(frame_data_sequence *fds)
259 frame_data ***level2;
260 frame_data ****level3;
263 if (fds->count == 0) {
264 /* Nothing to free. */
267 if (fds->count <= NODES_PER_LEVEL) {
268 /* It's a 1-level tree. */
269 g_free(fds->ptree_root);
270 } else if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
271 /* It's a 2-level tree. */
272 level1 = fds->ptree_root;
273 for (i = 0; i < NODES_PER_LEVEL && level1[i] != NULL; i++)
276 } else if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
277 /* It's a 3-level tree. */
278 level2 = fds->ptree_root;
279 for (i = 0; i < NODES_PER_LEVEL && level2[i] != NULL; i++) {
281 for (j = 0; j < NODES_PER_LEVEL && level1[i] != NULL; j++)
288 /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
289 2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
290 so fds->count is always less < NODES_PER_LEVEL^4. */
291 /* It's a 4-level tree, and is going to stay that way forever. */
292 level3 = fds->ptree_root;
293 for (i = 0; i < NODES_PER_LEVEL && level3[i] != NULL; i++) {
295 for (j = 0; j < NODES_PER_LEVEL && level2[i] != NULL; j++) {
297 for (k = 0; k < NODES_PER_LEVEL && level1[k] != NULL; k++)