Create a new frame_data_sequence data type; it represents a dense
authorguy <guy@f5534014-38df-0310-8fa8-9805f1628bb7>
Wed, 27 Apr 2011 02:54:44 +0000 (02:54 +0000)
committerguy <guy@f5534014-38df-0310-8fa8-9805f1628bb7>
Wed, 27 Apr 2011 02:54:44 +0000 (02:54 +0000)
sequence of frame_data structures, indexed by the frame number.  Extract
the relevant bits of the capture_file data structure and move them to
the frame_data_sequence, and move the relevant code from cfile.c and
tweak it to handle frame_data_sequence structures.

Have a possibly-null pointer to a frame_data_sequence structure in the
capture_file structure; if it's null, we aren't keeping a sequence of
frame_data structures (we don't keep that sequence when we're doing
one-pass processing in TShark).

Nothing in libwireshark should care about a capture_file structure; get
rid of some unnecessary includes of cfile.h.

git-svn-id: http://anonsvn.wireshark.org/wireshark/trunk@36881 f5534014-38df-0310-8fa8-9805f1628bb7

13 files changed:
Makefile.common
cfile.c
cfile.h
epan/frame_data.c
epan/prefs.c
file.c
frame_data_sequence.c [new file with mode: 0644]
frame_data_sequence.h [new file with mode: 0644]
gtk/new_packet_list.c
packet-range.c
proto_hier_stats.c
summary.c
tshark.c

index 9767b94..f702bae 100644 (file)
@@ -51,6 +51,7 @@ WIRESHARK_COMMON_SRC =        \
        cfile.c \
        clopts_common.c \
        disabled_protos.c       \
+       frame_data_sequence.c   \
        packet-range.c  \
        print.c \
        ps.c    \
@@ -74,6 +75,7 @@ WIRESHARK_COMMON_INCLUDES =   \
        disabled_protos.h       \
        file.h  \
        fileset.h       \
+       frame_data_sequence.h   \
        isprint.h       \
        packet-range.h  \
        print.h \
diff --git a/cfile.c b/cfile.c
index 2249c77..3463c1d 100644 (file)
--- a/cfile.c
+++ b/cfile.c
@@ -37,260 +37,16 @@ void
 cap_file_init(capture_file *cf)
 {
   /* Initialize the capture file struct */
-  cf->ptree_root     = NULL;
-  cf->wth            = NULL;
-  cf->filename       = NULL;
-  cf->source         = NULL;
-  cf->user_saved     = FALSE;
-  cf->is_tempfile    = FALSE;
-  cf->rfcode         = NULL;
-  cf->dfilter        = NULL;
-  cf->has_snap       = FALSE;
-  cf->snap           = WTAP_MAX_PACKET_SIZE;
-  cf->count          = 0;
-  cf->redissecting   = FALSE;
-}
-
-/*
- * For a given frame number, calculate the indices into a level 3
- * node, a level 2 node, a level 1 node, and a leaf node.
- */
-#define LEVEL_3_INDEX(framenum) \
-       ((framenum) >> (3*LOG2_NODES_PER_LEVEL))
-#define LEVEL_2_INDEX(framenum) \
-       (((framenum) >> (2*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
-#define LEVEL_1_INDEX(framenum) \
-       (((framenum) >> (1*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
-#define LEAF_INDEX(framenum) \
-       (((framenum) >> (0*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
-
-/*
- * Add a new frame_data structure to the capture_file's collection.
- */
-frame_data *
-cap_file_add_fdata(capture_file *cf, frame_data *fdata)
-{
-  frame_data *leaf;
-  frame_data **level1;
-  frame_data ***level2;
-  frame_data ****level3;
-  frame_data *node;
-
-  /*
-   * The current value of cf->count is the index value for the new frame,
-   * because the index value for a frame is the frame number - 1, and
-   * if we currently have cf->count frames, the the frame number of
-   * the last frame in the collection is cf->count, so its index value
-   * is cf->count - 1.
-   */
-  if (cf->count == 0) {
-    /* The tree is empty; allocate the first leaf node, which will be
-       the root node. */
-    leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
-    node = &leaf[0];
-    cf->ptree_root = leaf;
-  } else if (cf->count < NODES_PER_LEVEL) {
-    /* It's a 1-level tree, and is going to stay that way for now. */
-    leaf = cf->ptree_root;
-    node = &leaf[cf->count];
-  } else if (cf->count == NODES_PER_LEVEL) {
-    /* It's a 1-level tree that will turn into a 2-level tree. */
-    level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
-    memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
-    level1[0] = cf->ptree_root;
-    leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
-    level1[1] = leaf;
-    node = &leaf[0];
-    cf->ptree_root = level1;
-  } else if (cf->count < NODES_PER_LEVEL*NODES_PER_LEVEL) {
-    /* It's a 2-level tree, and is going to stay that way for now. */
-    level1 = cf->ptree_root;
-    leaf = level1[cf->count >> LOG2_NODES_PER_LEVEL];
-    if (leaf == NULL) {
-      leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
-      level1[cf->count >> LOG2_NODES_PER_LEVEL] = leaf;
-    }
-    node = &leaf[LEAF_INDEX(cf->count)];
-  } else if (cf->count == NODES_PER_LEVEL*NODES_PER_LEVEL) {
-    /* It's a 2-level tree that will turn into a 3-level tree */
-    level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL);
-    memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL);
-    level2[0] = cf->ptree_root;
-    level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
-    memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
-    level2[1] = level1;
-    leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
-    level1[0] = leaf;
-    node = &leaf[0];
-    cf->ptree_root = level2;
-  } else if (cf->count < NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
-    /* It's a 3-level tree, and is going to stay that way for now. */
-    level2 = cf->ptree_root;
-    level1 = level2[cf->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
-    if (level1 == NULL) {
-      level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
-      memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
-      level2[cf->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)] = level1;
-    }
-    leaf = level1[LEVEL_1_INDEX(cf->count)];
-    if (leaf == NULL) {
-      leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
-      level1[LEVEL_1_INDEX(cf->count)] = leaf;
-    }
-    node = &leaf[LEAF_INDEX(cf->count)];
-  } else if (cf->count == NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
-    /* It's a 3-level tree that will turn into a 4-level tree */
-    level3 = g_malloc((sizeof *level3)*NODES_PER_LEVEL);
-    memset(level3, 0, (sizeof *level3)*NODES_PER_LEVEL);
-    level3[0] = cf->ptree_root;
-    level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL);
-    memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL);
-    level3[1] = level2;
-    level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
-    memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
-    level2[0] = level1;
-    leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
-    level1[0] = leaf;
-    node = &leaf[0];
-    cf->ptree_root = level3;
-  } else {
-    /* cf->count is 2^32-1 at most, and NODES_PER_LEVEL^4
-       2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
-       so cf->count is always less < NODES_PER_LEVEL^4.
-
-       XXX - we should fail if cf->count is 2^31-1, or should
-       make the frame numbers 64-bit and just let users run
-       themselves out of address space or swap space. :-) */
-    /* It's a 4-level tree, and is going to stay that way forever. */
-    level3 = cf->ptree_root;
-    level2 = level3[LEVEL_3_INDEX(cf->count)];
-    if (level2 == NULL) {
-      level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL);
-      memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL);
-      level3[LEVEL_3_INDEX(cf->count)] = level2;
-    }
-    level1 = level2[LEVEL_2_INDEX(cf->count)];
-    if (level1 == NULL) {
-      level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
-      memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
-      level2[LEVEL_2_INDEX(cf->count)] = level1;
-    }
-    leaf = level1[LEVEL_1_INDEX(cf->count)];
-    if (leaf == NULL) {
-      leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
-      level1[LEVEL_1_INDEX(cf->count)] = leaf;
-    }
-    node = &leaf[LEAF_INDEX(cf->count)];
-  }
-  *node = *fdata;
-  cf->count++;
-  return node;
-}
-
-/*
- * Find the frame_data for the specified frame number.
- */
-frame_data *
-cap_file_find_fdata(capture_file *cf, guint32 num)
-{
-  frame_data *leaf;
-  frame_data **level1;
-  frame_data ***level2;
-  frame_data ****level3;
-
-  if (num == 0) {
-    /* There is no frame number 0 */
-    return NULL;
-  }
-
-  /* Convert it into an index number. */
-  num--;
-  if (num >= cf->count) {
-    /* There aren't that many frames. */
-    return NULL;
-  }
-
-  if (cf->count <= NODES_PER_LEVEL) {
-    /* It's a 1-level tree. */
-    leaf = cf->ptree_root;
-    return &leaf[num];
-  }
-  if (cf->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
-    /* It's a 2-level tree. */
-    level1 = cf->ptree_root;
-    leaf = level1[num >> LOG2_NODES_PER_LEVEL];
-    return &leaf[LEAF_INDEX(num)];
-  }
-  if (cf->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
-    /* It's a 3-level tree. */
-    level2 = cf->ptree_root;
-    level1 = level2[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
-    leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)];
-    return &leaf[LEAF_INDEX(num)];
-  }
-  /* cf->count is 2^32-1 at most, and NODES_PER_LEVEL^4
-     2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
-     so cf->count is always less < NODES_PER_LEVEL^4. */
-  /* It's a 4-level tree, and is going to stay that way forever. */
-  level3 = cf->ptree_root;
-  level2 = level3[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
-  level1 = level2[(num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1)];
-  leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)];
-  return &leaf[LEAF_INDEX(num)];
-}
-
-/*
- * Free up all the frame information for a capture file.
- */
-void
-cap_file_free_frames(capture_file *cf)
-{
-  frame_data **level1;
-  frame_data ***level2;
-  frame_data ****level3;
-  guint i, j, k;
-
-  if (cf->count == 0) {
-    /* Nothing to free. */
-    return;
-  }
-  if (cf->count <= NODES_PER_LEVEL) {
-    /* It's a 1-level tree. */
-    g_free(cf->ptree_root);
-  } else if (cf->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
-    /* It's a 2-level tree. */
-    level1 = cf->ptree_root;
-    for (i = 0; i < NODES_PER_LEVEL && level1[i] != NULL; i++)
-      g_free(level1[i]);
-    g_free(level1);
-  } else if (cf->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
-    /* It's a 3-level tree. */
-    level2 = cf->ptree_root;
-    for (i = 0; i < NODES_PER_LEVEL && level2[i] != NULL; i++) {
-      level1 = level2[i];
-      for (j = 0; j < NODES_PER_LEVEL && level1[i] != NULL; j++)
-        g_free(level1[j]);
-      g_free(level1);
-    }
-    g_free(level2);
-    return;
-  } else {
-    /* cf->count is 2^32-1 at most, and NODES_PER_LEVEL^4
-       2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
-       so cf->count is always less < NODES_PER_LEVEL^4. */
-    /* It's a 4-level tree, and is going to stay that way forever. */
-    level3 = cf->ptree_root;
-    for (i = 0; i < NODES_PER_LEVEL && level3[i] != NULL; i++) {
-      level2 = level3[i];
-      for (j = 0; j < NODES_PER_LEVEL && level2[i] != NULL; j++) {
-        level1 = level2[j];
-        for (k = 0; k < NODES_PER_LEVEL && level1[k] != NULL; k++)
-          g_free(level1[k]);
-      }
-      g_free(level2);
-    }
-    g_free(level3);
-  }
-  cf->ptree_root = NULL;
-  cf->count = 0;
+  cf->filename      = NULL;
+  cf->source        = NULL;
+  cf->is_tempfile   = FALSE;
+  cf->user_saved    = FALSE;
+  cf->count         = 0;
+  cf->has_snap      = FALSE;
+  cf->snap          = WTAP_MAX_PACKET_SIZE;
+  cf->wth           = NULL;
+  cf->rfcode        = NULL;
+  cf->dfilter       = NULL;
+  cf->redissecting  = FALSE;
+  cf->frames        = NULL;
 }
diff --git a/cfile.h b/cfile.h
index a14accc..83d2309 100644 (file)
--- a/cfile.h
+++ b/cfile.h
@@ -25,6 +25,8 @@
 #ifndef __CFILE_H__
 #define __CFILE_H__
 
+#include "frame_data_sequence.h"
+
 /* Current state of file. */
 typedef enum {
   FILE_CLOSED,                 /* No file open */
@@ -98,7 +100,7 @@ typedef struct _capture_file {
   union wtap_pseudo_header pseudo_header; /* Packet pseudo_header */
   guint8       pd[WTAP_MAX_PACKET_SIZE];  /* Packet data */
   /* frames */
-  void        *ptree_root;      /* Pointer to the root node */
+  frame_data_sequence *frames;  /* Sequence of frames, if we're keeping that information */
   guint32      first_displayed; /* Frame number of first frame displayed */
   guint32      last_displayed;  /* Frame number of last frame displayed */
   column_info  cinfo;           /* Column formatting information */
@@ -110,18 +112,4 @@ typedef struct _capture_file {
 
 extern void cap_file_init(capture_file *cf);
 
-extern frame_data *cap_file_add_fdata(capture_file *cf, frame_data *fdata);
-
-/*
- * Find the frame_data for the specified frame number.
- * Do some caching to make this work reasonably fast for
- * forward and backward sequential passes through the packets.
- */
-extern frame_data *cap_file_find_fdata(capture_file *cf, guint32 num);
-
-/*
- * Free up all the frame information for a capture file.
- */
-extern void cap_file_free_frames(capture_file *cf);
-
 #endif /* cfile.h */
index b9b32c6..5b4f775 100644 (file)
@@ -32,7 +32,6 @@
 #include <epan/packet.h>
 #include <epan/emem.h>
 #include <epan/timestamp.h>
-#include "cfile.h"
 
 #include <glib.h>
 
index a52e486..a713f9f 100644 (file)
@@ -46,7 +46,6 @@
 #include <epan/prefs.h>
 #include <epan/proto.h>
 #include <epan/strutil.h>
-#include "cfile.h"
 #include <epan/column.h>
 #include "print.h"
 #include <wsutil/file_util.h>
diff --git a/file.c b/file.c
index 7cb4762..7c089c9 100644 (file)
--- a/file.c
+++ b/file.c
@@ -331,6 +331,9 @@ cf_open(capture_file *cf, const char *fname, gboolean is_tempfile, int *err)
   } else
     cf->has_snap = TRUE;
 
+  /* Allocate a frame_data_sequence for the frames in this file */
+  cf->frames = new_frame_data_sequence();
+
   nstime_set_zero(&cf->elapsed_time);
   nstime_set_unset(&first_ts);
   nstime_set_unset(&prev_dis_ts);
@@ -389,7 +392,8 @@ cf_reset_state(capture_file *cf)
 
   dfilter_free(cf->rfcode);
   cf->rfcode = NULL;
-  cap_file_free_frames(cf);
+  free_frame_data_sequence(cf->frames);
+  cf->frames = NULL;
   cf_unselect_packet(cf);   /* nothing to select */
   cf->first_displayed = 0;
   cf->last_displayed = 0;
@@ -642,7 +646,7 @@ cf_read(capture_file *cf, gboolean from_save)
      WTAP_ENCAP_PER_PACKET). */
   cf->lnk_t = wtap_file_encap(cf->wth);
 
-  cf->current_frame = cap_file_find_fdata(cf, cf->first_displayed);
+  cf->current_frame = frame_data_sequence_find(cf->frames, cf->first_displayed);
   cf->current_row = 0;
 
   new_packet_list_thaw();
@@ -1182,8 +1186,9 @@ read_packet(capture_file *cf, dfilter_t *dfcode,
 
   if (passed) {
     /* This does a shallow copy of fdlocal, which is good enough. */
-    fdata = cap_file_add_fdata(cf, &fdlocal);
+    fdata = frame_data_sequence_add(cf->frames, &fdlocal);
 
+    cf->count++;
     cf->f_datalen = offset + fdlocal.cap_len;
 
     if (!cf->redissecting) {
@@ -1683,7 +1688,7 @@ rescan_packets(capture_file *cf, const char *action, const char *action_item,
   selected_frame_seen = FALSE;
 
   for (framenum = 1; framenum <= cf->count; framenum++) {
-    fdata = cap_file_find_fdata(cf, framenum);
+    fdata = frame_data_sequence_find(cf->frames, framenum);
 
     /* Create the progress bar if necessary.
        We check on every iteration of the loop, so that it takes no
@@ -1798,7 +1803,7 @@ rescan_packets(capture_file *cf, const char *action, const char *action_item,
        would leave the user stuck with an Wireshark grinding on
        until it finishes.  Should we just stick them with that? */
     for (; framenum <= cf->count; framenum++) {
-      fdata = cap_file_find_fdata(cf, framenum);
+      fdata = frame_data_sequence_find(cf->frames, framenum);
       fdata->flags.visited = 0;
       frame_data_cleanup(fdata);
     }
@@ -1899,7 +1904,7 @@ ref_time_packets(capture_file *cf)
   cum_bytes = 0;
 
   for (framenum = 1; framenum <= cf->count; framenum++) {
-    fdata = cap_file_find_fdata(cf, framenum);
+    fdata = frame_data_sequence_find(cf->frames, framenum);
 
     /* just add some value here until we know if it is being displayed or not */
     fdata->cum_bytes = cum_bytes + fdata->pkt_len;
@@ -2011,7 +2016,7 @@ process_specified_packets(capture_file *cf, packet_range_t *range,
   /* Iterate through all the packets, printing the packets that
      were selected by the current display filter.  */
   for (framenum = 1; framenum <= cf->count; framenum++) {
-    fdata = cap_file_find_fdata(cf, framenum);
+    fdata = frame_data_sequence_find(cf->frames, framenum);
 
     /* Create the progress bar if necessary.
        We check on every iteration of the loop, so that it takes no
@@ -3280,7 +3285,7 @@ find_packet(capture_file *cf,
         } else
           framenum++;
       }
-      fdata = cap_file_find_fdata(cf, framenum);
+      fdata = frame_data_sequence_find(cf->frames, framenum);
 
       count++;
 
@@ -3339,7 +3344,7 @@ cf_goto_frame(capture_file *cf, guint fnumber)
 {
   frame_data *fdata;
 
-  fdata = cap_file_find_fdata(cf, fnumber);
+  fdata = frame_data_sequence_find(cf->frames, fnumber);
 
   if (fdata == NULL) {
     /* we didn't find a packet with that packet number */
@@ -3441,7 +3446,7 @@ cf_select_packet(capture_file *cf, int row)
        GtkCList; see the comment in "add_packet_to_packet_list()". */
 
        if (row == 0 && cf->first_displayed == cf->last_displayed)
-         fdata = cap_file_find_fdata(cf, cf->first_displayed);
+         fdata = frame_data_sequence_find(cf->frames, cf->first_displayed);
   }
 
   /* If fdata _still_ isn't set simply give up. */
diff --git a/frame_data_sequence.c b/frame_data_sequence.c
new file mode 100644 (file)
index 0000000..ed1cb74
--- /dev/null
@@ -0,0 +1,287 @@
+/* frame_data_sequence.c
+ * Implements a sequence of frame_data structures
+ *
+ * $Id$
+ *
+ * Wireshark - Network traffic analyzer
+ * By Gerald Combs <gerald@wireshark.org>
+ * Copyright 1998 Gerald Combs
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <glib.h>
+
+#include <epan/packet.h>
+
+#include "frame_data_sequence.h"
+
+frame_data_sequence *
+new_frame_data_sequence(void)
+{
+       frame_data_sequence *fds;
+
+       fds = g_malloc(sizeof *fds);
+       fds->count = 0;
+       fds->ptree_root = NULL;
+       return fds;
+}
+
+/*
+ * For a given frame number, calculate the indices into a level 3
+ * node, a level 2 node, a level 1 node, and a leaf node.
+ */
+#define LEVEL_3_INDEX(framenum) \
+       ((framenum) >> (3*LOG2_NODES_PER_LEVEL))
+#define LEVEL_2_INDEX(framenum) \
+       (((framenum) >> (2*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
+#define LEVEL_1_INDEX(framenum) \
+       (((framenum) >> (1*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
+#define LEAF_INDEX(framenum) \
+       (((framenum) >> (0*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
+
+/*
+ * Add a new frame_data structure to a frame_data_sequence.
+ */
+frame_data *
+frame_data_sequence_add(frame_data_sequence *fds, frame_data *fdata)
+{
+  frame_data *leaf;
+  frame_data **level1;
+  frame_data ***level2;
+  frame_data ****level3;
+  frame_data *node;
+
+  /*
+   * The current value of fds->count is the index value for the new frame,
+   * because the index value for a frame is the frame number - 1, and
+   * if we currently have fds->count frames, the the frame number of
+   * the last frame in the collection is fds->count, so its index value
+   * is fds->count - 1.
+   */
+  if (fds->count == 0) {
+    /* The tree is empty; allocate the first leaf node, which will be
+       the root node. */
+    leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
+    node = &leaf[0];
+    fds->ptree_root = leaf;
+  } else if (fds->count < NODES_PER_LEVEL) {
+    /* It's a 1-level tree, and is going to stay that way for now. */
+    leaf = fds->ptree_root;
+    node = &leaf[fds->count];
+  } else if (fds->count == NODES_PER_LEVEL) {
+    /* It's a 1-level tree that will turn into a 2-level tree. */
+    level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
+    memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
+    level1[0] = fds->ptree_root;
+    leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
+    level1[1] = leaf;
+    node = &leaf[0];
+    fds->ptree_root = level1;
+  } else if (fds->count < NODES_PER_LEVEL*NODES_PER_LEVEL) {
+    /* It's a 2-level tree, and is going to stay that way for now. */
+    level1 = fds->ptree_root;
+    leaf = level1[fds->count >> LOG2_NODES_PER_LEVEL];
+    if (leaf == NULL) {
+      leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
+      level1[fds->count >> LOG2_NODES_PER_LEVEL] = leaf;
+    }
+    node = &leaf[LEAF_INDEX(fds->count)];
+  } else if (fds->count == NODES_PER_LEVEL*NODES_PER_LEVEL) {
+    /* It's a 2-level tree that will turn into a 3-level tree */
+    level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL);
+    memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL);
+    level2[0] = fds->ptree_root;
+    level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
+    memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
+    level2[1] = level1;
+    leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
+    level1[0] = leaf;
+    node = &leaf[0];
+    fds->ptree_root = level2;
+  } else if (fds->count < NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
+    /* It's a 3-level tree, and is going to stay that way for now. */
+    level2 = fds->ptree_root;
+    level1 = level2[fds->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
+    if (level1 == NULL) {
+      level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
+      memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
+      level2[fds->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)] = level1;
+    }
+    leaf = level1[LEVEL_1_INDEX(fds->count)];
+    if (leaf == NULL) {
+      leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
+      level1[LEVEL_1_INDEX(fds->count)] = leaf;
+    }
+    node = &leaf[LEAF_INDEX(fds->count)];
+  } else if (fds->count == NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
+    /* It's a 3-level tree that will turn into a 4-level tree */
+    level3 = g_malloc((sizeof *level3)*NODES_PER_LEVEL);
+    memset(level3, 0, (sizeof *level3)*NODES_PER_LEVEL);
+    level3[0] = fds->ptree_root;
+    level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL);
+    memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL);
+    level3[1] = level2;
+    level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
+    memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
+    level2[0] = level1;
+    leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
+    level1[0] = leaf;
+    node = &leaf[0];
+    fds->ptree_root = level3;
+  } else {
+    /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
+       2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
+       so fds->count is always less < NODES_PER_LEVEL^4.
+
+       XXX - we should fail if fds->count is 2^31-1, or should
+       make the frame numbers 64-bit and just let users run
+       themselves out of address space or swap space. :-) */
+    /* It's a 4-level tree, and is going to stay that way forever. */
+    level3 = fds->ptree_root;
+    level2 = level3[LEVEL_3_INDEX(fds->count)];
+    if (level2 == NULL) {
+      level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL);
+      memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL);
+      level3[LEVEL_3_INDEX(fds->count)] = level2;
+    }
+    level1 = level2[LEVEL_2_INDEX(fds->count)];
+    if (level1 == NULL) {
+      level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
+      memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
+      level2[LEVEL_2_INDEX(fds->count)] = level1;
+    }
+    leaf = level1[LEVEL_1_INDEX(fds->count)];
+    if (leaf == NULL) {
+      leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
+      level1[LEVEL_1_INDEX(fds->count)] = leaf;
+    }
+    node = &leaf[LEAF_INDEX(fds->count)];
+  }
+  *node = *fdata;
+  fds->count++;
+  return node;
+}
+
+/*
+ * Find the frame_data for the specified frame number.
+ */
+frame_data *
+frame_data_sequence_find(frame_data_sequence *fds, guint32 num)
+{
+  frame_data *leaf;
+  frame_data **level1;
+  frame_data ***level2;
+  frame_data ****level3;
+
+  if (num == 0) {
+    /* There is no frame number 0 */
+    return NULL;
+  }
+
+  /* Convert it into an index number. */
+  num--;
+  if (num >= fds->count) {
+    /* There aren't that many frames. */
+    return NULL;
+  }
+
+  if (fds->count <= NODES_PER_LEVEL) {
+    /* It's a 1-level tree. */
+    leaf = fds->ptree_root;
+    return &leaf[num];
+  }
+  if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
+    /* It's a 2-level tree. */
+    level1 = fds->ptree_root;
+    leaf = level1[num >> LOG2_NODES_PER_LEVEL];
+    return &leaf[LEAF_INDEX(num)];
+  }
+  if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
+    /* It's a 3-level tree. */
+    level2 = fds->ptree_root;
+    level1 = level2[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
+    leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)];
+    return &leaf[LEAF_INDEX(num)];
+  }
+  /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
+     2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
+     so fds->count is always less < NODES_PER_LEVEL^4. */
+  /* It's a 4-level tree, and is going to stay that way forever. */
+  level3 = fds->ptree_root;
+  level2 = level3[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
+  level1 = level2[(num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1)];
+  leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)];
+  return &leaf[LEAF_INDEX(num)];
+}
+
+/*
+ * Free a frame_data_sequence and all the frame_data structures in it.
+ */
+void
+free_frame_data_sequence(frame_data_sequence *fds)
+{
+  frame_data **level1;
+  frame_data ***level2;
+  frame_data ****level3;
+  guint i, j, k;
+
+  if (fds->count == 0) {
+    /* Nothing to free. */
+    return;
+  }
+  if (fds->count <= NODES_PER_LEVEL) {
+    /* It's a 1-level tree. */
+    g_free(fds->ptree_root);
+  } else if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
+    /* It's a 2-level tree. */
+    level1 = fds->ptree_root;
+    for (i = 0; i < NODES_PER_LEVEL && level1[i] != NULL; i++)
+      g_free(level1[i]);
+    g_free(level1);
+  } else if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
+    /* It's a 3-level tree. */
+    level2 = fds->ptree_root;
+    for (i = 0; i < NODES_PER_LEVEL && level2[i] != NULL; i++) {
+      level1 = level2[i];
+      for (j = 0; j < NODES_PER_LEVEL && level1[i] != NULL; j++)
+        g_free(level1[j]);
+      g_free(level1);
+    }
+    g_free(level2);
+    return;
+  } else {
+    /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
+       2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
+       so fds->count is always less < NODES_PER_LEVEL^4. */
+    /* It's a 4-level tree, and is going to stay that way forever. */
+    level3 = fds->ptree_root;
+    for (i = 0; i < NODES_PER_LEVEL && level3[i] != NULL; i++) {
+      level2 = level3[i];
+      for (j = 0; j < NODES_PER_LEVEL && level2[i] != NULL; j++) {
+        level1 = level2[j];
+        for (k = 0; k < NODES_PER_LEVEL && level1[k] != NULL; k++)
+          g_free(level1[k]);
+      }
+      g_free(level2);
+    }
+    g_free(level3);
+  }
+  g_free(fds);
+}
diff --git a/frame_data_sequence.h b/frame_data_sequence.h
new file mode 100644 (file)
index 0000000..8f59cdb
--- /dev/null
@@ -0,0 +1,62 @@
+/* frame_data_sequence.h
+ * Implements a sequence of frame_data structures
+ *
+ * $Id$
+ *
+ * Wireshark - Network traffic analyzer
+ * By Gerald Combs <gerald@wireshark.org>
+ * Copyright 1998 Gerald Combs
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ */
+
+#ifndef __FRAME_DATA_SEQUENCE_H__
+#define __FRAME_DATA_SEQUENCE_H__
+
+/*
+ * We store the frame_data structures in a radix tree, with 1024
+ * elements per level.  The leaf nodes are arrays of 1024 frame_data
+ * structures; the nodes above them are arrays of 1024 pointers to
+ * the nodes below them.  The capture_file structure has a pointer
+ * to the root node.
+ *
+ * As frame numbers are 32 bits, and as 1024 is 2^10, that gives us
+ * up to 4 levels of tree.
+ */
+#define LOG2_NODES_PER_LEVEL   10
+#define NODES_PER_LEVEL                (1<<LOG2_NODES_PER_LEVEL)
+
+typedef struct {
+  guint32      count;           /* Total number of frames */
+  void        *ptree_root;      /* Pointer to the root node */
+} frame_data_sequence;
+
+extern frame_data_sequence *new_frame_data_sequence(void);
+
+extern frame_data *frame_data_sequence_add(frame_data_sequence *fds,
+    frame_data *fdata);
+
+/*
+ * Find the frame_data for the specified frame number.
+ */
+extern frame_data *frame_data_sequence_find(frame_data_sequence *fds,
+    guint32 num);
+
+/*
+ * Free a frame_data_sequence and all the frame_data structures in it.
+ */
+extern void free_frame_data_sequence(frame_data_sequence *fds);
+
+#endif /* frame_data_sequence.h */
index 3be4d98..d95a454 100644 (file)
@@ -1495,7 +1495,7 @@ mark_all_displayed_frames(gboolean set)
        guint32 framenum;
        frame_data *fdata;
        for (framenum = 1; framenum <= cfile.count; framenum++) {
-               fdata = cap_file_find_fdata(&cfile, framenum);
+               fdata = frame_data_sequence_find(cfile.frames, framenum);
                if( fdata->flags.passed_dfilter )
                        set_frame_mark(set, fdata);
        }
@@ -1522,7 +1522,7 @@ toggle_mark_all_displayed_frames()
        guint32 framenum;
        frame_data *fdata;
        for (framenum = 1; framenum <= cfile.count; framenum++) {
-               fdata = cap_file_find_fdata(&cfile, framenum);
+               fdata = frame_data_sequence_find(cfile.frames, framenum);
                if( fdata->flags.passed_dfilter )
                        set_frame_mark(!fdata->flags.marked, fdata);
        }
@@ -1571,7 +1571,7 @@ ignore_all_displayed_frames(gboolean set)
 
        /* XXX: we might need a progressbar here */
        for (framenum = 1; framenum <= cfile.count; framenum++) {
-               fdata = cap_file_find_fdata(&cfile, framenum);
+               fdata = frame_data_sequence_find(cfile.frames, framenum);
                if( fdata->flags.passed_dfilter )
                        set_frame_ignore(set, fdata);
        }
@@ -1586,7 +1586,7 @@ new_packet_list_ignore_all_displayed_frames_cb(GtkWidget *w _U_, gpointer data _
                /* Due to performance impact with large captures, don't check the filtered list for
                an ignored frame; just check the first. If a ignored frame exists but isn't first and
                the user wants to unignore all the displayed frames, they will just re-exec the shortcut. */
-               fdata = cap_file_find_fdata(&cfile, cfile.first_displayed);
+               fdata = frame_data_sequence_find(cfile.frames, cfile.first_displayed);
                if (fdata->flags.ignored==TRUE) {
                        ignore_all_displayed_frames(FALSE);
                } else {
@@ -1603,7 +1603,7 @@ unignore_all_frames(void)
 
        /* XXX: we might need a progressbar here */
        for (framenum = 1; framenum <= cfile.count; framenum++) {
-               fdata = cap_file_find_fdata(&cfile, framenum);
+               fdata = frame_data_sequence_find(cfile.frames, framenum);
                set_frame_ignore(FALSE, fdata);
        }
        redissect_packets();
@@ -1623,7 +1623,7 @@ untime_reference_all_frames()
        guint32 framenum;
        frame_data *fdata;
        for (framenum = 1; framenum <= cfile.count && cfile.ref_time_count > 0; framenum++) {
-               fdata = cap_file_find_fdata(&cfile, framenum);
+               fdata = frame_data_sequence_find(cfile.frames, framenum);
                if (fdata->flags.ref_time == 1) {
                        set_frame_reftime(FALSE, fdata, cfile.current_row);
                }
index aed5d29..ed9955e 100644 (file)
@@ -76,7 +76,7 @@ static void packet_range_calc(packet_range_t *range) {
      * for example, the case when TShark is doing a one-pass
      * read of a file or a live capture.
      */
-    if (cfile.ptree_root != NULL) {
+    if (cfile.frames != NULL) {
         /* The next for-loop is used to obtain the amount of packets
          * to be processed and is used to present the information in
          * the Save/Print As widget.
@@ -87,7 +87,7 @@ static void packet_range_calc(packet_range_t *range) {
          */
 
         for(framenum = 1; framenum <= cfile.count; framenum++) {
-            packet = cap_file_find_fdata(&cfile, framenum);
+            packet = frame_data_sequence_find(cfile.frames, framenum);
 
             if (cfile.current_frame == packet) {
                 range->selected_packet = framenum;
@@ -128,7 +128,7 @@ static void packet_range_calc(packet_range_t *range) {
         }
 
         for(framenum = 1; framenum <= cfile.count; framenum++) {
-            packet = cap_file_find_fdata(&cfile, framenum);
+            packet = frame_data_sequence_find(cfile.frames, framenum);
 
             if (framenum >= mark_low &&
                 framenum <= mark_high)
@@ -181,9 +181,9 @@ static void packet_range_calc_user(packet_range_t *range) {
      * for example, the case when TShark is doing a one-pass
      * read of a file or a live capture.
      */
-    if (cfile.ptree_root != NULL) {
+    if (cfile.frames != NULL) {
         for(framenum = 1; framenum <= cfile.count; framenum++) {
-            packet = cap_file_find_fdata(&cfile, framenum);
+            packet = frame_data_sequence_find(cfile.frames, framenum);
 
             if (value_is_in_range(range->user_range, framenum)) {
                 range->user_range_cnt++;
index 4a7c2d6..420e725 100644 (file)
@@ -214,7 +214,7 @@ ph_stats_new(void)
        tot_bytes = 0;
 
        for (framenum = 1; framenum <= cfile.count; framenum++) {
-               frame = cap_file_find_fdata(&cfile, framenum);
+               frame = frame_data_sequence_find(cfile.frames, framenum);
 
                /* Create the progress bar if necessary.
                   We check on every iteration of the loop, so that
index 36a59e0..7686e04 100644 (file)
--- a/summary.c
+++ b/summary.c
@@ -109,12 +109,12 @@ summary_fill_in(capture_file *cf, summary_tally *st)
 
   /* initialize the tally */
   if (cf->count != 0) {
-    first_frame = cap_file_find_fdata(cf, 1);
+    first_frame = frame_data_sequence_find(cf->frames, 1);
     st->start_time = nstime_to_sec(&first_frame->abs_ts);
     st->stop_time = nstime_to_sec(&first_frame->abs_ts);
 
     for (framenum = 1; framenum <= cf->count; framenum++) {
-      cur_frame = cap_file_find_fdata(cf, framenum);
+      cur_frame = frame_data_sequence_find(cf->frames, framenum);
       tally_frame_data(cur_frame, st);
     }
   }
index 4310740..a20f125 100644 (file)
--- a/tshark.c
+++ b/tshark.c
@@ -1816,14 +1816,10 @@ main(int argc, char *argv[])
 
   g_free(cf_name);
 
-  /* XXX - hack to avoid a crash in one-pass mode, where we update
-     cfile.count but don't allocate any frame_data structures.
-     We may want to more cleanly separate the "capture file" and
-     "collection of frames" stuff, to handle cases such as TShark
-     one-pass mode where we care about the former but don't care
-     about the latter. */
-  if (cfile.ptree_root != NULL)
-    cap_file_free_frames(&cfile);
+  if (cfile.frames != NULL) {
+    free_frame_data_sequence(cfile.frames);
+    cfile.frames = NULL;
+  }
 
   draw_tap_listeners(TRUE);
   funnel_dump_all_text_windows();
@@ -2441,7 +2437,8 @@ process_packet_first_pass(capture_file *cf,
 
   if (passed) {
     frame_data_set_after_dissect(&fdlocal, &cum_bytes, &prev_dis_ts);
-    cap_file_add_fdata(cf, &fdlocal);
+    frame_data_sequence_add(cf->frames, &fdlocal);
+    cf->count++;
   }
 
   if (do_dissection)
@@ -2650,6 +2647,9 @@ load_cap_file(capture_file *cf, char *save_file, int out_file_type,
     frame_data *fdata;
     int old_max_packet_count = max_packet_count;
 
+    /* Allocate a frame_data_sequence for all the frames. */
+    cf->frames = new_frame_data_sequence();
+
     while (wtap_read(cf->wth, &err, &err_info, &data_offset)) {
       if (process_packet_first_pass(cf, data_offset, wtap_phdr(cf->wth),
                          wtap_pseudoheader(cf->wth), wtap_buf_ptr(cf->wth))) {
@@ -2675,7 +2675,7 @@ load_cap_file(capture_file *cf, char *save_file, int out_file_type,
     max_packet_count = old_max_packet_count;
 
     for (framenum = 1; err == 0 && framenum <= cf->count; framenum++) {
-      fdata = cap_file_find_fdata(cf, framenum);
+      fdata = frame_data_sequence_find(cf->frames, framenum);
       if (wtap_seek_read(cf->wth, fdata->file_off, &cf->pseudo_header,
           cf->pd, fdata->cap_len, &err, &err_info)) {
         if (process_packet_second_pass(cf, fdata,