Store the frame_data structures in a tree, rather than a linked list.

This lets us get rid of the per-frame_data-structure prev and next
pointers, saving memory (at least according to Activity Monitor's report
of the virtual address space size on my Snow Leopard machine, it's a
noticeable saving), and lets us look up frame_data structures by frame
number in O(log2(number of frames)) time rather than O(number of frames)
time.  It seems to take more CPU time when reading in the file, but
seems to go from "finished reading in all the packets" to "displaying
the packets" faster and seems to free up the frame_data structures
faster when closing the file.

It *is* doing more copying, currently, as we now don't allocate the
frame_data structure until after the packet has passed the read filter,
so that might account for the additional CPU time.

(Oh, and, for what it's worth, on an LP64 platform, a frame_data
structure is exactly 128 bytes long.  However, there's more stuff to
remove, so the power-of-2 size is not guaranteed to remain, and it's not
a power-of-2 size on an ILP32 platform.)

It also means we don't need GLib 2.10 or later for the two-pass mode in
TShark.

It also means some code in the TCP dissector that was checking
pinfo->fd->next to see if it's NULL, in order to see if this is the last
packet in the file, no longer works, but that wasn't guaranteed to work
anyway:

	we might be doing a one-pass read through the capture in TShark;

	we might be dissecting the frame while we're reading in the
	packets for the first time in Wireshark;

	we might be doing a live capture in Wireshark;

in which case packets might be prematurely considered "the last packet".
#if 0 the no-longer-working tests, pending figuring out a better way of
doing it.

svn path=/trunk/; revision=36849

1 files changed, 24 insertions, 17 deletions

diff --git a/cfile.h b/cfile.h
index 06bdc4e120..a14accc9e1 100644
--- a/cfile.h
+++ b/cfile.h
@@ -46,6 +46,19 @@ typedef enum {
   SD_BACKWARD
 } search_direction;
 
+/*
+ * 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 _capture_file {
   file_state   state;           /* Current state of capture file */
   gchar       *filename;        /* Name of capture file */
@@ -84,21 +97,10 @@ typedef struct _capture_file {
   /* packet data */
   union wtap_pseudo_header pseudo_header; /* Packet pseudo_header */
   guint8       pd[WTAP_MAX_PACKET_SIZE];  /* Packet data */
-  /* memory chunks have been deprecated in favor of the slice allocator,
-   * which has been added in 2.10
-   */
-#if GLIB_CHECK_VERSION(2,10,0)
-
-#else
-  GMemChunk   *plist_chunk;     /* Memory chunk for frame_data structures */
-#endif
-  frame_data  *plist_start;     /* Packet list */
-  frame_data  *plist_end;       /* Last packet in list */
-  frame_data  *first_displayed; /* First frame displayed */
-  frame_data  *last_displayed;  /* Last frame displayed */
-  /* The next two are used to speed up frame number -> frame data searches */
-  guint32      last_found_num;  /* Frame number we last found */
-  frame_data  *last_found_fd;   /* The corresponding frame_data */
+  /* frames */
+  void        *ptree_root;      /* Pointer to the root node */
+  guint32      first_displayed; /* Frame number of first frame displayed */
+  guint32      last_displayed;  /* Frame number of last frame displayed */
   column_info  cinfo;           /* Column formatting information */
   frame_data  *current_frame;   /* Frame data for current frame */
   gint         current_row;     /* Row number for current frame */
@@ -106,9 +108,9 @@ typedef struct _capture_file {
   field_info  *finfo_selected;	/* Field info for currently selected field */
 } capture_file;
 
-void cap_file_init(capture_file *cf);
+extern void cap_file_init(capture_file *cf);
 
-void cap_file_add_fdata(capture_file *cf, frame_data *fdata);
+extern frame_data *cap_file_add_fdata(capture_file *cf, frame_data *fdata);
 
 /*
  * Find the frame_data for the specified frame number.
@@ -117,4 +119,9 @@ void cap_file_add_fdata(capture_file *cf, frame_data *fdata);
  */
 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 */