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 }