epan/frame_data_sequence.c

   1 /* frame_data_sequence.c
   2  * Implements a sequence of frame_data structures
   3  *
   4  * Wireshark - Network traffic analyzer
   5  * By Gerald Combs <gerald@wireshark.org>
   6  * Copyright 1998 Gerald Combs
   7  *
   8  * This program is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU General Public License
  10  * as published by the Free Software Foundation; either version 2
  11  * of the License, or (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21  */
  22
  23 #include "config.h"
  24
  25 #include <glib.h>
  26
  27 #include <epan/packet.h>
  28
  29 #include "frame_data_sequence.h"
  30
  31 /*
  32  * We store the frame_data structures in a radix tree, with 1024
  33  * elements per level.  The leaf nodes are arrays of 1024 frame_data
  34  * structures; the nodes above them are arrays of 1024 pointers to
  35  * the nodes below them.  The capture_file structure has a pointer
  36  * to the root node.
  37  *
  38  * As frame numbers are 32 bits, and as 1024 is 2^10, that gives us
  39  * up to 4 levels of tree.
  40  */
  41 #define LOG2_NODES_PER_LEVEL    10
  42 #define NODES_PER_LEVEL         (1<<LOG2_NODES_PER_LEVEL)
  43
  44 struct _frame_data_sequence {
  45   guint32      count;           /* Total number of frames */
  46   void        *ptree_root;      /* Pointer to the root node */
  47 };
  48
  49 /*
  50  * For a given frame number, calculate the indices into a level 3
  51  * node, a level 2 node, a level 1 node, and a leaf node.
  52  */
  53 #define LEVEL_3_INDEX(framenum) \
  54         ((framenum) >> (3*LOG2_NODES_PER_LEVEL))
  55 #define LEVEL_2_INDEX(framenum) \
  56         (((framenum) >> (2*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
  57 #define LEVEL_1_INDEX(framenum) \
  58         (((framenum) >> (1*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
  59 #define LEAF_INDEX(framenum) \
  60         (((framenum) >> (0*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
  61
  62 frame_data_sequence *
  63 new_frame_data_sequence(void)
  64 {
  65   frame_data_sequence *fds;
  66
  67   fds = (frame_data_sequence *)g_malloc(sizeof *fds);
  68   fds->count = 0;
  69   fds->ptree_root = NULL;
  70   return fds;
  71 }
  72
  73 /*
  74  * Add a new frame_data structure to a frame_data_sequence.
  75  */
  76 frame_data *
  77 frame_data_sequence_add(frame_data_sequence *fds, frame_data *fdata)
  78 {
  79   frame_data *leaf;
  80   frame_data **level1;
  81   frame_data ***level2;
  82   frame_data ****level3;
  83   frame_data *node;
  84
  85   /*
  86    * The current value of fds->count is the index value for the new frame,
  87    * because the index value for a frame is the frame number - 1, and
  88    * if we currently have fds->count frames, the the frame number of
  89    * the last frame in the collection is fds->count, so its index value
  90    * is fds->count - 1.
  91    */
  92   if (fds->count == 0) {
  93     /* The tree is empty; allocate the first leaf node, which will be
  94        the root node. */
  95     leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
  96     node = &leaf[0];
  97     fds->ptree_root = leaf;
  98   } else if (fds->count < NODES_PER_LEVEL) {
  99     /* It's a 1-level tree, and is going to stay that way for now. */
 100     leaf = (frame_data *)fds->ptree_root;
 101     node = &leaf[fds->count];
 102   } else if (fds->count == NODES_PER_LEVEL) {
 103     /* It's a 1-level tree that will turn into a 2-level tree. */
 104     level1 = (frame_data **)g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
 105     level1[0] = (frame_data *)fds->ptree_root;
 106     leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
 107     level1[1] = leaf;
 108     node = &leaf[0];
 109     fds->ptree_root = level1;
 110   } else if (fds->count < NODES_PER_LEVEL*NODES_PER_LEVEL) {
 111     /* It's a 2-level tree, and is going to stay that way for now. */
 112     level1 = (frame_data **)fds->ptree_root;
 113     leaf = level1[fds->count >> LOG2_NODES_PER_LEVEL];
 114     if (leaf == NULL) {
 115       leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
 116       level1[fds->count >> LOG2_NODES_PER_LEVEL] = leaf;
 117     }
 118     node = &leaf[LEAF_INDEX(fds->count)];
 119   } else if (fds->count == NODES_PER_LEVEL*NODES_PER_LEVEL) {
 120     /* It's a 2-level tree that will turn into a 3-level tree */
 121     level2 = (frame_data ***)g_malloc0((sizeof *level2)*NODES_PER_LEVEL);
 122     level2[0] = (frame_data **)fds->ptree_root;
 123     level1 = (frame_data **)g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
 124     level2[1] = level1;
 125     leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
 126     level1[0] = leaf;
 127     node = &leaf[0];
 128     fds->ptree_root = level2;
 129   } else if (fds->count < NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
 130     /* It's a 3-level tree, and is going to stay that way for now. */
 131     level2 = (frame_data ***)fds->ptree_root;
 132     level1 = level2[fds->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
 133     if (level1 == NULL) {
 134       level1 = (frame_data **)g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
 135       level2[fds->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)] = level1;
 136     }
 137     leaf = level1[LEVEL_1_INDEX(fds->count)];
 138     if (leaf == NULL) {
 139       leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
 140       level1[LEVEL_1_INDEX(fds->count)] = leaf;
 141     }
 142     node = &leaf[LEAF_INDEX(fds->count)];
 143   } else if (fds->count == NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
 144     /* It's a 3-level tree that will turn into a 4-level tree */
 145     level3 = (frame_data ****)g_malloc0((sizeof *level3)*NODES_PER_LEVEL);
 146     level3[0] = (frame_data ***)fds->ptree_root;
 147     level2 = (frame_data ***)g_malloc0((sizeof *level2)*NODES_PER_LEVEL);
 148     level3[1] = level2;
 149     level1 = (frame_data **)g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
 150     level2[0] = level1;
 151     leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
 152     level1[0] = leaf;
 153     node = &leaf[0];
 154     fds->ptree_root = level3;
 155   } else {
 156     /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
 157        2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
 158        so fds->count is always less < NODES_PER_LEVEL^4.
 159
 160        XXX - we should fail if fds->count is 2^31-1, or should
 161        make the frame numbers 64-bit and just let users run
 162        themselves out of address space or swap space. :-) */
 163     /* It's a 4-level tree, and is going to stay that way forever. */
 164     level3 = (frame_data ****)fds->ptree_root;
 165     level2 = level3[LEVEL_3_INDEX(fds->count)];
 166     if (level2 == NULL) {
 167       level2 = (frame_data ***)g_malloc0((sizeof *level2)*NODES_PER_LEVEL);
 168       level3[LEVEL_3_INDEX(fds->count)] = level2;
 169     }
 170     level1 = level2[LEVEL_2_INDEX(fds->count)];
 171     if (level1 == NULL) {
 172       level1 = (frame_data **)g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
 173       level2[LEVEL_2_INDEX(fds->count)] = level1;
 174     }
 175     leaf = level1[LEVEL_1_INDEX(fds->count)];
 176     if (leaf == NULL) {
 177       leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
 178       level1[LEVEL_1_INDEX(fds->count)] = leaf;
 179     }
 180     node = &leaf[LEAF_INDEX(fds->count)];
 181   }
 182   *node = *fdata;
 183   fds->count++;
 184   return node;
 185 }
 186
 187 /*
 188  * Find the frame_data for the specified frame number.
 189  */
 190 frame_data *
 191 frame_data_sequence_find(frame_data_sequence *fds, guint32 num)
 192 {
 193   frame_data *leaf;
 194   frame_data **level1;
 195   frame_data ***level2;
 196   frame_data ****level3;
 197
 198   if (num == 0) {
 199     /* There is no frame number 0 */
 200     return NULL;
 201   }
 202
 203   /* Convert it into an index number. */
 204   num--;
 205   if (num >= fds->count) {
 206     /* There aren't that many frames. */
 207     return NULL;
 208   }
 209
 210   if (fds->count <= NODES_PER_LEVEL) {
 211     /* It's a 1-level tree. */
 212     leaf = (frame_data *)fds->ptree_root;
 213     return &leaf[num];
 214   }
 215   if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
 216     /* It's a 2-level tree. */
 217     level1 = (frame_data **)fds->ptree_root;
 218     leaf = level1[num >> LOG2_NODES_PER_LEVEL];
 219     return &leaf[LEAF_INDEX(num)];
 220   }
 221   if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
 222     /* It's a 3-level tree. */
 223     level2 = (frame_data ***)fds->ptree_root;
 224     level1 = level2[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
 225     leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)];
 226     return &leaf[LEAF_INDEX(num)];
 227   }
 228   /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
 229      2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
 230      so fds->count is always less < NODES_PER_LEVEL^4. */
 231   /* It's a 4-level tree, and is going to stay that way forever. */
 232   level3 = (frame_data ****)fds->ptree_root;
 233   level2 = level3[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
 234   level1 = level2[(num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1)];
 235   leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)];
 236   return &leaf[LEAF_INDEX(num)];
 237 }
 238
 239 /* recursively frees a frame_data radix level */
 240 static void
 241 free_frame_data_array(void *array, guint count, guint level, gboolean last)
 242 {
 243   guint i, level_count;
 244
 245   if (last) {
 246     /* if we are the last in our given parent's row, we may not have
 247      * exactly a full row, so do the bit twiddling to figure out exactly
 248      * how many fields we have */
 249     level_count = (count >> ((level - 1) * LOG2_NODES_PER_LEVEL)) &
 250                   (NODES_PER_LEVEL - 1);
 251     /* the above calculation rounds down, so make sure we count correctly
 252      * if count is not an even multiple of NODES_PER_LEVEL */
 253     if (count & ((1 << ((level - 1) * LOG2_NODES_PER_LEVEL)) - 1)) {
 254       level_count++;
 255     }
 256   }
 257   else {
 258     /* if we're not the last in our parent, then we're guaranteed to have
 259      * a full array */
 260     level_count = NODES_PER_LEVEL;
 261   }
 262
 263
 264   if (level > 1) {
 265     /* recurse on every sub-array, passing on our own 'last' value
 266      * specially to our last child */
 267     frame_data **real_array = (frame_data **) array;
 268
 269     for (i=0; i < level_count-1; i++) {
 270       free_frame_data_array(real_array[i], count, level-1, FALSE);
 271     }
 272
 273     free_frame_data_array(real_array[level_count-1], count, level-1, last);
 274   }
 275   else if (level == 1) {
 276     /* bottom level, so just clean up all the frame data */
 277     frame_data *real_array = (frame_data *) array;
 278
 279     for (i=0; i < level_count; i++) {
 280       frame_data_destroy(&real_array[i]);
 281     }
 282   }
 283
 284   /* free the array itself */
 285   g_free(array);
 286 }
 287
 288 /*
 289  * Free a frame_data_sequence and all the frame_data structures in it.
 290  */
 291 void
 292 free_frame_data_sequence(frame_data_sequence *fds)
 293 {
 294   guint   levels;
 295
 296   /* calculate how many levels we have */
 297   if (fds->count == 0) {
 298     /* The tree is empty; there are no levels. */
 299     levels = 0;
 300   } else if (fds->count <= NODES_PER_LEVEL) {
 301     /* It's a 1-level tree. */
 302     levels = 1;
 303   } else if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
 304     /* It's a 2-level tree. */
 305     levels = 2;
 306   } else if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
 307     /* It's a 3-level tree. */
 308     levels = 3;
 309   } else {
 310     /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
 311        2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
 312        so fds->count is always less < NODES_PER_LEVEL^4. */
 313     /* It's a 4-level tree. */
 314     levels = 4;
 315   }
 316
 317   /* call the recursive free function */
 318   if (levels > 0) {
 319     free_frame_data_array(fds->ptree_root, fds->count, levels, TRUE);
 320   }
 321
 322   /* free the header struct */
 323   g_free(fds);
 324 }
 325
 326 void
 327 find_and_mark_frame_depended_upon(gpointer data, gpointer user_data)
 328 {
 329   frame_data   *dependent_fd;
 330   guint32       dependent_frame = GPOINTER_TO_UINT(data);
 331   frame_data_sequence *frames   = (frame_data_sequence *)user_data;
 332
 333   if (dependent_frame && frames) {
 334     dependent_fd = frame_data_sequence_find(frames, dependent_frame);
 335     dependent_fd->flags.dependent_of_displayed = 1;
 336   }
 337 }
 338
 339 /*
 340  * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
 341  *
 342  * Local variables:
 343  * c-basic-offset: 2
 344  * tab-width: 8
 345  * indent-tabs-mode: nil
 346  * End:
 347  *
 348  * vi: set shiftwidth=2 tabstop=8 expandtab:
 349  * :indentSize=2:tabSize=8:noTabs=true:
 350  */