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