From Colin O'Flynn:
[obnox/wireshark/wip.git] / frame_data_sequence.c
1 /* frame_data_sequence.c
2  * Implements a sequence of frame_data structures
3  *
4  * $Id$
5  *
6  * Wireshark - Network traffic analyzer
7  * By Gerald Combs <gerald@wireshark.org>
8  * Copyright 1998 Gerald Combs
9  *
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.
14  *
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.
19  *
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.
23  */
24
25 #ifdef HAVE_CONFIG_H
26 # include "config.h"
27 #endif
28
29 #include <glib.h>
30
31 #include <epan/packet.h>
32
33 #include "frame_data_sequence.h"
34
35 /*
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
40  * to the root node.
41  *
42  * As frame numbers are 32 bits, and as 1024 is 2^10, that gives us
43  * up to 4 levels of tree.
44  */
45 #define LOG2_NODES_PER_LEVEL    10
46 #define NODES_PER_LEVEL         (1<<LOG2_NODES_PER_LEVEL)
47
48 struct _frame_data_sequence {
49   guint32      count;           /* Total number of frames */
50   void        *ptree_root;      /* Pointer to the root node */
51 };
52
53 /*
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.
56  */
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))
65
66 frame_data_sequence *
67 new_frame_data_sequence(void)
68 {
69         frame_data_sequence *fds;
70
71         fds = g_malloc(sizeof *fds);
72         fds->count = 0;
73         fds->ptree_root = NULL;
74         return fds;
75 }
76
77 /*
78  * Add a new frame_data structure to a frame_data_sequence.
79  */
80 frame_data *
81 frame_data_sequence_add(frame_data_sequence *fds, frame_data *fdata)
82 {
83   frame_data *leaf;
84   frame_data **level1;
85   frame_data ***level2;
86   frame_data ****level3;
87   frame_data *node;
88
89   /*
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
94    * is fds->count - 1.
95    */
96   if (fds->count == 0) {
97     /* The tree is empty; allocate the first leaf node, which will be
98        the root node. */
99     leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
100     node = &leaf[0];
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);
112     level1[1] = leaf;
113     node = &leaf[0];
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];
119     if (leaf == NULL) {
120       leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
121       level1[fds->count >> LOG2_NODES_PER_LEVEL] = leaf;
122     }
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);
131     level2[1] = level1;
132     leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
133     level1[0] = leaf;
134     node = &leaf[0];
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;
144     }
145     leaf = level1[LEVEL_1_INDEX(fds->count)];
146     if (leaf == NULL) {
147       leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
148       level1[LEVEL_1_INDEX(fds->count)] = leaf;
149     }
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);
158     level3[1] = level2;
159     level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
160     memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
161     level2[0] = level1;
162     leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
163     level1[0] = leaf;
164     node = &leaf[0];
165     fds->ptree_root = level3;
166   } else {
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.
170
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;
181     }
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;
187     }
188     leaf = level1[LEVEL_1_INDEX(fds->count)];
189     if (leaf == NULL) {
190       leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
191       level1[LEVEL_1_INDEX(fds->count)] = leaf;
192     }
193     node = &leaf[LEAF_INDEX(fds->count)];
194   }
195   *node = *fdata;
196   fds->count++;
197   return node;
198 }
199
200 /*
201  * Find the frame_data for the specified frame number.
202  */
203 frame_data *
204 frame_data_sequence_find(frame_data_sequence *fds, guint32 num)
205 {
206   frame_data *leaf;
207   frame_data **level1;
208   frame_data ***level2;
209   frame_data ****level3;
210
211   if (num == 0) {
212     /* There is no frame number 0 */
213     return NULL;
214   }
215
216   /* Convert it into an index number. */
217   num--;
218   if (num >= fds->count) {
219     /* There aren't that many frames. */
220     return NULL;
221   }
222
223   if (fds->count <= NODES_PER_LEVEL) {
224     /* It's a 1-level tree. */
225     leaf = fds->ptree_root;
226     return &leaf[num];
227   }
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)];
233   }
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)];
240   }
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)];
250 }
251
252 /*
253  * Free a frame_data_sequence and all the frame_data structures in it.
254  */
255 void
256 free_frame_data_sequence(frame_data_sequence *fds)
257 {
258   frame_data **level1;
259   frame_data ***level2;
260   frame_data ****level3;
261   guint i, j, k;
262
263   if (fds->count == 0) {
264     /* Nothing to free. */
265     return;
266   }
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++)
274       g_free(level1[i]);
275     g_free(level1);
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++) {
280       level1 = level2[i];
281       for (j = 0; j < NODES_PER_LEVEL && level1[i] != NULL; j++)
282         g_free(level1[j]);
283       g_free(level1);
284     }
285     g_free(level2);
286     return;
287   } else {
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++) {
294       level2 = level3[i];
295       for (j = 0; j < NODES_PER_LEVEL && level2[i] != NULL; j++) {
296         level1 = level2[j];
297         for (k = 0; k < NODES_PER_LEVEL && level1[k] != NULL; k++)
298           g_free(level1[k]);
299       }
300       g_free(level2);
301     }
302     g_free(level3);
303   }
304   g_free(fds);
305 }