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 = 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 = 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 = 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 = g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
 107     level1[0] = fds->ptree_root;
 108     leaf = 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 = fds->ptree_root;
 115     leaf = level1[fds->count >> LOG2_NODES_PER_LEVEL];
 116     if (leaf == NULL) {
 117       leaf = 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 = g_malloc0((sizeof *level2)*NODES_PER_LEVEL);
 124     level2[0] = fds->ptree_root;
 125     level1 = g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
 126     level2[1] = level1;
 127     leaf = 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 = fds->ptree_root;
 134     level1 = level2[fds->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
 135     if (level1 == NULL) {
 136       level1 = 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 = 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 = g_malloc0((sizeof *level3)*NODES_PER_LEVEL);
 148     level3[0] = fds->ptree_root;
 149     level2 = g_malloc0((sizeof *level2)*NODES_PER_LEVEL);
 150     level3[1] = level2;
 151     level1 = g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
 152     level2[0] = level1;
 153     leaf = 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 = fds->ptree_root;
 167     level2 = level3[LEVEL_3_INDEX(fds->count)];
 168     if (level2 == NULL) {
 169       level2 = 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 = 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 = 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 = 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 = 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 = 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 = 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 /*
 242  * Free a frame_data_sequence and all the frame_data structures in it.
 243  */
 244 void
 245 free_frame_data_sequence(frame_data_sequence *fds)
 246 {
 247   frame_data **level1;
 248   frame_data ***level2;
 249   frame_data ****level3;
 250   guint i, j, k;
 251
 252   if (fds->count == 0) {
 253     /* Nothing to free. */
 254     return;
 255   }
 256   if (fds->count <= NODES_PER_LEVEL) {
 257     /* It's a 1-level tree. */
 258     g_free(fds->ptree_root);
 259   } else if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
 260     /* It's a 2-level tree. */
 261     level1 = fds->ptree_root;
 262     for (i = 0; i < NODES_PER_LEVEL && level1[i] != NULL; i++)
 263       g_free(level1[i]);
 264     g_free(level1);
 265   } else if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
 266     /* It's a 3-level tree. */
 267     level2 = fds->ptree_root;
 268     for (i = 0; i < NODES_PER_LEVEL && level2[i] != NULL; i++) {
 269       level1 = level2[i];
 270       for (j = 0; j < NODES_PER_LEVEL && level1[i] != NULL; j++)
 271         g_free(level1[j]);
 272       g_free(level1);
 273     }
 274     g_free(level2);
 275     return;
 276   } else {
 277     /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
 278        2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
 279        so fds->count is always less < NODES_PER_LEVEL^4. */
 280     /* It's a 4-level tree, and is going to stay that way forever. */
 281     level3 = fds->ptree_root;
 282     for (i = 0; i < NODES_PER_LEVEL && level3[i] != NULL; i++) {
 283       level2 = level3[i];
 284       for (j = 0; j < NODES_PER_LEVEL && level2[i] != NULL; j++) {
 285         level1 = level2[j];
 286         for (k = 0; k < NODES_PER_LEVEL && level1[k] != NULL; k++)
 287           g_free(level1[k]);
 288       }
 289       g_free(level2);
 290     }
 291     g_free(level3);
 292   }
 293   g_free(fds);
 294 }