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

11 files changed, 334 insertions, 205 deletions

diff --git a/cfile.c b/cfile.c
index d993e7ab84..2249c77512 100644
--- a/cfile.c
+++ b/cfile.c
@@ -37,8 +37,7 @@ void
 cap_file_init(capture_file *cf)
 {
   /* Initialize the capture file struct */
-  cf->plist_start    = NULL;
-  cf->plist_end      = NULL;
+  cf->ptree_root     = NULL;
   cf->wth            = NULL;
   cf->filename       = NULL;
   cf->source         = NULL;
@@ -49,88 +48,249 @@ cap_file_init(capture_file *cf)
   cf->has_snap       = FALSE;
   cf->snap           = WTAP_MAX_PACKET_SIZE;
   cf->count          = 0;
-  cf->last_found_num = 0;
-  cf->last_found_fd  = NULL;
   cf->redissecting   = FALSE;
 }
 
-void
+/*
+ * 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 *plist_end = cf->plist_end;
-  fdata->prev = plist_end;
-  if (plist_end != NULL)
-    plist_end->next = fdata;
-  else
-    cf->plist_start = fdata;
-  cf->plist_end = 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.
- * Do some caching to make this work reasonably fast for
- * forward and backward sequential passes through the packets.
  */
 frame_data *
 cap_file_find_fdata(capture_file *cf, guint32 num)
 {
-  frame_data *fdata;
+  frame_data *leaf;
+  frame_data **level1;
+  frame_data ***level2;
+  frame_data ****level3;
 
   if (num == 0) {
     /* There is no frame number 0 */
     return NULL;
   }
 
-  /*
-   * Did we remember a frame number from a sequential pass through
-   * the frames?
-   */
-  if (cf->last_found_num != 0) {
-    /*
-     * Yes.  Is this that frame?
-     */
-    if (num == cf->last_found_num) {
-      /* Yes - return it. */
-      return cf->last_found_fd;
-    }
+  /* Convert it into an index number. */
+  num--;
+  if (num >= cf->count) {
+    /* There aren't that many frames. */
+    return NULL;
+  }
 
-    /*
-     * No.  Is it the frame just after that frame?
-     */
-    if (num == cf->last_found_num + 1) {
-      /*
-       * Yes - if there is such a frame, remember it and return it.
-       */
-      fdata = cf->last_found_fd->next;
-      if (fdata != NULL) {
-        cf->last_found_num = num;
-        cf->last_found_fd = fdata;
-      }
-      return fdata;	/* could be null, if there is no such frame */
-    }
+  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)];
+}
 
-    /*
-     * No.  Is it the frame just before that frame?
-     */
-    if (num == cf->last_found_num - 1) {
-      /*
-       * Yes - if there is such a frame, remember it and return it.
-       */
-      fdata = cf->last_found_fd->prev;
-      if (fdata != NULL) {
-        cf->last_found_num = num;
-        cf->last_found_fd = fdata;
+/*
+ * 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]);
       }
-      return fdata;	/* could be null, if there is no such frame */
+      g_free(level2);
     }
+    g_free(level3);
   }
-
-  for (fdata = cf->plist_start; fdata != NULL && fdata->num < num;
-       fdata = fdata->next)
-    ;
-  if (fdata != NULL) {
-    cf->last_found_num = num;
-    cf->last_found_fd = fdata;
-  }
-  return fdata;
+  cf->ptree_root = NULL;
+  cf->count = 0;
 }
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 */
diff --git a/epan/dissectors/packet-tcp.c b/epan/dissectors/packet-tcp.c
index 7e99f9af6f..abd12a9dd2 100644
--- a/epan/dissectors/packet-tcp.c
+++ b/epan/dissectors/packet-tcp.c
@@ -2112,21 +2112,30 @@ tcp_dissect_pdus(tvbuff_t *tvb, packet_info *pinfo, proto_tree *tree,
 
         /*
          * Do not display the the PDU length if it crosses the boundary of the
-         * packet and no more packets are available
+         * packet and no more packets are available.
+         *
+         * XXX - we don't necessarily know whether more packets are
+         * available; we might be doing a one-pass read through the
+         * capture in TShark, or we might be doing a live capture in
+         * Wireshark.
          */
-        if (length_remaining >= plen || pinfo->fd->next != NULL)
+#if 0
+        if (length_remaining >= plen || there are more packets)
         {
+#endif
                 /*
                  * Display the PDU length as a field
                  */
                 item=proto_tree_add_uint(pinfo->tcp_tree, hf_tcp_pdu_size,
                                          tvb, offset, plen, plen);
                 PROTO_ITEM_SET_GENERATED(item);
+#if 0
         } else {
                 item = proto_tree_add_text(pinfo->tcp_tree, tvb, offset, -1,
                     "PDU Size: %u cut short at %u",plen,length_remaining);
                 PROTO_ITEM_SET_GENERATED(item);
         }
+#endif
 
 
         /* give a hint to TCP where the next PDU starts
diff --git a/epan/frame_data.c b/epan/frame_data.c
index b07681b1d9..b9b32c69cb 100644
--- a/epan/frame_data.c
+++ b/epan/frame_data.c
@@ -189,8 +189,6 @@ frame_data_init(frame_data *fdata, guint32 num,
                 const struct wtap_pkthdr *phdr, gint64 offset,
                 guint32 cum_bytes)
 {
-  fdata->next = NULL;
-  fdata->prev = NULL;
   fdata->pfd = NULL;
   fdata->num = num;
   fdata->pkt_len = phdr->len;
diff --git a/epan/frame_data.h b/epan/frame_data.h
index 2165278216..bf1a7ca95e 100644
--- a/epan/frame_data.h
+++ b/epan/frame_data.h
@@ -40,8 +40,6 @@
    it's 1-origin.  In various contexts, 0 as a frame number means "frame
    number unknown". */
 typedef struct _frame_data {
-  struct _frame_data *next; /**< Next element in list */
-  struct _frame_data *prev; /**< Previous element in list */
   GSList      *pfd;         /**< Per frame proto data */
   guint32      num;         /**< Frame number */
   guint32      pkt_len;     /**< Packet length */
diff --git a/file.c b/file.c
index a1697e7a94..33f663f0d9 100644
--- a/file.c
+++ b/file.c
@@ -399,28 +399,15 @@ cf_reset_state(capture_file *cf)
   /* ...which means we have nothing to save. */
   cf->user_saved = FALSE;
 
-#if GLIB_CHECK_VERSION(2,10,0)
-  if (cf->plist_start != NULL)
-    g_slice_free_chain(frame_data, cf->plist_start, next);
-#else
-  /* memory chunks have been deprecated in favor of the slice allocator,
-   * which has been added in 2.10
-   */
-  if (cf->plist_chunk != NULL) {
-    g_mem_chunk_destroy(cf->plist_chunk);
-    cf->plist_chunk = NULL;
-  }
-#endif
   dfilter_free(cf->rfcode);
   cf->rfcode = NULL;
-  cf->plist_start = NULL;
-  cf->plist_end = NULL;
+  cap_file_free_frames(cf);
   cf_unselect_packet(cf);   /* nothing to select */
-  cf->first_displayed = NULL;
-  cf->last_displayed = NULL;
+  cf->first_displayed = 0;
+  cf->last_displayed = 0;
 
   /* No frame selected, no field in that frame selected. */
-  cf->current_frame = NULL;
+  cf->current_frame = 0;
   cf->current_row = 0;
   cf->finfo_selected = NULL;
 
@@ -430,7 +417,6 @@ cf_reset_state(capture_file *cf)
   new_packet_list_thaw();
 
   cf->f_datalen = 0;
-  cf->count = 0;
   nstime_set_zero(&cf->elapsed_time);
 
   reset_tap_listeners();
@@ -605,7 +591,7 @@ cf_read(capture_file *cf, gboolean from_save)
           /* (on smaller files the display update takes longer than reading the file) */
 #ifdef HAVE_LIBPCAP
           if (progbar_quantum > 500000 || displayed_once == 0) {
-            if ((auto_scroll_live || displayed_once == 0 || cf->displayed_count < 1000) && cf->plist_end != NULL) {
+            if ((auto_scroll_live || displayed_once == 0 || cf->displayed_count < 1000) && cf->count != 0) {
               displayed_once = 1;
               new_packet_list_thaw();
               if (auto_scroll_live)
@@ -683,7 +669,7 @@ cf_read(capture_file *cf, gboolean from_save)
      WTAP_ENCAP_PER_PACKET). */
   cf->lnk_t = wtap_file_encap(cf->wth);
 
-  cf->current_frame = cf->first_displayed;
+  cf->current_frame = cap_file_find_fdata(cf, cf->first_displayed);
   cf->current_row = 0;
 
   new_packet_list_thaw();
@@ -694,7 +680,7 @@ cf_read(capture_file *cf, gboolean from_save)
 
   /* If we have any displayed packets to select, select the first of those
      packets by making the first row the selected row. */
-  if (cf->first_displayed != NULL){
+  if (cf->first_displayed != 0){
     new_packet_list_select_first_row();
   }
 
@@ -869,7 +855,7 @@ cf_continue_tail(capture_file *cf, volatile int to_read, int *err)
 
   /* moving to the end of the packet list - if the user requested so and
      we have some new packets. */
-  if (newly_displayed_packets && auto_scroll_live && cf->plist_end != NULL)
+  if (newly_displayed_packets && auto_scroll_live && cf->count != 0)
       new_packet_list_moveto_end();
 
   if (cf->state == FILE_READ_ABORTED) {
@@ -955,7 +941,7 @@ cf_finish_tail(capture_file *cf, int *err)
     return CF_READ_ABORTED;
   }
 
-  if (auto_scroll_live && cf->plist_end != NULL)
+  if (auto_scroll_live && cf->count != 0)
     new_packet_list_moveto_end();
 
   /* We're done reading sequentially through the file. */
@@ -1163,11 +1149,11 @@ add_packet_to_packet_list(frame_data *fdata, capture_file *cf,
        We thus need to leave behind bread crumbs so that
        "cf_select_packet()" can find this frame.  See the comment
        in "cf_select_packet()". */
-    if (cf->first_displayed == NULL)
-      cf->first_displayed = fdata;
+    if (cf->first_displayed == 0)
+      cf->first_displayed = fdata->num;
 
     /* This is the last frame we've seen so far. */
-    cf->last_displayed = fdata;
+    cf->last_displayed = fdata->num;
   }
 
   epan_dissect_cleanup(&edt);
@@ -1193,65 +1179,45 @@ read_packet(capture_file *cf, dfilter_t *dfcode,
   const struct wtap_pkthdr *phdr = wtap_phdr(cf->wth);
   union wtap_pseudo_header *pseudo_header = wtap_pseudoheader(cf->wth);
   const guchar *buf = wtap_buf_ptr(cf->wth);
+  frame_data    fdlocal;
+  guint32       framenum;
   frame_data   *fdata;
   int           passed;
   int           row = -1;
 
-  cf->count++;
+  /* The frame number of this packet is one more than the count of
+     frames in this packet. */
+  framenum = cf->count + 1;
 
-  /* Allocate the next list entry, and add it to the list.
-   * 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)
-  fdata = g_slice_new(frame_data);
-#else
-  fdata = g_mem_chunk_alloc(cf->plist_chunk);
-#endif
-
-  frame_data_init(fdata, cf->count, phdr, offset, cum_bytes);
-  init_col_text(fdata, cf->cinfo.num_cols);
+  frame_data_init(&fdlocal, framenum, phdr, offset, cum_bytes);
+  /* Note - if the packet doesn't pass the read filter, and is thus
+     not added to the capture_file's collection of packets, the
+     column text arrays aren't free; they're alocated with
+     se_alloc0(), so they eventually get freed when we close the
+     file. */
+  init_col_text(&fdlocal, cf->cinfo.num_cols);
 
   passed = TRUE;
   if (cf->rfcode) {
     epan_dissect_t edt;
     epan_dissect_init(&edt, TRUE, FALSE);
     epan_dissect_prime_dfilter(&edt, cf->rfcode);
-    epan_dissect_run(&edt, pseudo_header, buf, fdata, NULL);
+    epan_dissect_run(&edt, pseudo_header, buf, &fdlocal, NULL);
     passed = dfilter_apply_edt(cf->rfcode, &edt);
     epan_dissect_cleanup(&edt);
   }
 
   if (passed) {
-    cap_file_add_fdata(cf, fdata);
+    /* This does a shallow copy of fdlocal, which is good enough. */
+    fdata = cap_file_add_fdata(cf, &fdlocal);
 
-    cf->f_datalen = offset + fdata->cap_len;
+    cf->f_datalen = offset + fdlocal.cap_len;
 
     if (!cf->redissecting) {
       row = add_packet_to_packet_list(fdata, cf, dfcode,
                                       filtering_tap_listeners, tap_flags,
                                       pseudo_header, buf, TRUE, TRUE);
     }
-  } else {
-    /* We didn't pass read filter so roll back count */
-    cf->count--;
-
-    /* XXX - if we didn't have read filters, or if we could avoid
-       allocating the "frame_data" structure until we knew whether
-       the frame passed the read filter, we could use a G_ALLOC_ONLY
-       memory chunk...
-
-       ...but, at least in one test I did, where I just made the chunk
-       a G_ALLOC_ONLY chunk and read in a huge capture file, it didn't
-       seem to save a noticeable amount of time or space. */
-#if GLIB_CHECK_VERSION(2,10,0)
-  /* memory chunks have been deprecated in favor of the slice allocator,
-   * which has been added in 2.10
-   */
-    g_slice_free(frame_data,fdata);
-#else
-    g_mem_chunk_free(cf->plist_chunk, fdata);
-#endif
   }
 
   return row;
@@ -1705,8 +1671,8 @@ rescan_packets(capture_file *cf, const char *action, const char *action_item,
   }
 
   /* We don't yet know which will be the first and last frames displayed. */
-  cf->first_displayed = NULL;
-  cf->last_displayed = NULL;
+  cf->first_displayed = 0;
+  cf->last_displayed = 0;
 
   /* We currently don't display any packets */
   cf->displayed_count = 0;
@@ -3502,7 +3468,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 = cf->first_displayed;
+         fdata = cap_file_find_fdata(cf, cf->first_displayed);
   }
 
   /* If fdata _still_ isn't set simply give up. */
diff --git a/gtk/new_packet_list.c b/gtk/new_packet_list.c
index 74c08f5d4b..3be4d98a04 100644
--- a/gtk/new_packet_list.c
+++ b/gtk/new_packet_list.c
@@ -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 = cfile.first_displayed;
+		fdata = cap_file_find_fdata(&cfile, cfile.first_displayed);
 		if (fdata->flags.ignored==TRUE) {
 			ignore_all_displayed_frames(FALSE);
 		} else {
diff --git a/packet-range.c b/packet-range.c
index e6838f62f7..6e561fb0cb 100644
--- a/packet-range.c
+++ b/packet-range.c
@@ -43,7 +43,7 @@
 
 /* (re-)calculate the packet counts (except the user specified range) */
 static void packet_range_calc(packet_range_t *range) {
-  guint32       current_count;
+  guint32       framenum;
   guint32       mark_low;
   guint32       mark_high;
   guint32       displayed_mark_low;
@@ -79,11 +79,11 @@ static void packet_range_calc(packet_range_t *range) {
    * data must be entered in the widget by the user.
    */
 
-  current_count = 0;
-  for(packet = cfile.plist_start; packet != NULL; packet = packet->next) {
-      current_count++;
+  for(framenum = 1; framenum <= cfile.count; framenum++) {
+      packet = cap_file_find_fdata(&cfile, framenum);
+
       if (cfile.current_frame == packet) {
-          range->selected_packet = current_count;
+          range->selected_packet = framenum;
       }
       if (packet->flags.passed_dfilter) {
           range->displayed_cnt++;
@@ -98,18 +98,18 @@ static void packet_range_calc(packet_range_t *range) {
                     range->displayed_ignored_marked_cnt++;
                 }
                 if (displayed_mark_low == 0) {
-                   displayed_mark_low = current_count;
+                   displayed_mark_low = framenum;
                 }
-                if (current_count > displayed_mark_high) {
-                   displayed_mark_high = current_count;
+                if (framenum > displayed_mark_high) {
+                   displayed_mark_high = framenum;
                 }
             }
 
             if (mark_low == 0) {
-               mark_low = current_count;
+               mark_low = framenum;
             }
-            if (current_count > mark_high) {
-               mark_high = current_count;
+            if (framenum > mark_high) {
+               mark_high = framenum;
             }
       }
       if (packet->flags.ignored) {
@@ -120,12 +120,11 @@ static void packet_range_calc(packet_range_t *range) {
       }
   }
 
-  current_count = 0;
-  for(packet = cfile.plist_start; packet != NULL; packet = packet->next) {
-      current_count++;
+  for(framenum = 1; framenum <= cfile.count; framenum++) {
+      packet = cap_file_find_fdata(&cfile, framenum);
 
-      if (current_count >= mark_low &&
-          current_count <= mark_high)
+      if (framenum >= mark_low &&
+          framenum <= mark_high)
       {
           range->mark_range_cnt++;
           if (packet->flags.ignored) {
@@ -133,8 +132,8 @@ static void packet_range_calc(packet_range_t *range) {
           }
       }
 
-      if (current_count >= displayed_mark_low &&
-          current_count <= displayed_mark_high)
+      if (framenum >= displayed_mark_low &&
+          framenum <= displayed_mark_high)
       {
           if (packet->flags.passed_dfilter) {
             range->displayed_mark_range_cnt++;
@@ -159,7 +158,7 @@ static void packet_range_calc(packet_range_t *range) {
 
 /* (re-)calculate the user specified packet range counts */
 static void packet_range_calc_user(packet_range_t *range) {
-  guint32       current_count;
+  guint32       framenum;
   frame_data    *packet;
 
   range->user_range_cnt             = 0L;
@@ -167,11 +166,10 @@ static void packet_range_calc_user(packet_range_t *range) {
   range->displayed_user_range_cnt   = 0L;
   range->displayed_ignored_user_range_cnt = 0L;
 
-  current_count = 0;
-  for(packet = cfile.plist_start; packet != NULL; packet = packet->next) {
-      current_count++;
+  for(framenum = 1; framenum <= cfile.count; framenum++) {
+      packet = cap_file_find_fdata(&cfile, framenum);
 
-      if (value_is_in_range(range->user_range, current_count)) {
+      if (value_is_in_range(range->user_range, framenum)) {
           range->user_range_cnt++;
           if (packet->flags.ignored) {
               range->ignored_user_range_cnt++;
diff --git a/proto_hier_stats.c b/proto_hier_stats.c
index 4f95d9837c..4a7c2d6591 100644
--- a/proto_hier_stats.c
+++ b/proto_hier_stats.c
@@ -177,6 +177,7 @@ ph_stats_t*
 ph_stats_new(void)
 {
 	ph_stats_t	*ps;
+	guint32		framenum;
 	frame_data	*frame;
 	guint		tot_packets, tot_bytes;
 	progdlg_t	*progbar = NULL;
@@ -212,7 +213,9 @@ ph_stats_new(void)
 	tot_packets = 0;
 	tot_bytes = 0;
 
-	for (frame = cfile.plist_start; frame != NULL; frame = frame->next) {
+	for (framenum = 1; framenum <= cfile.count; framenum++) {
+		frame = cap_file_find_fdata(&cfile, framenum);
+
 		/* Create the progress bar if necessary.
 		   We check on every iteration of the loop, so that
 		   it takes no longer than the standard time to create
diff --git a/summary.c b/summary.c
index cda290289a..36a59e0e30 100644
--- a/summary.c
+++ b/summary.c
@@ -92,8 +92,7 @@ summary_fill_in(capture_file *cf, summary_tally *st)
 {
 
   frame_data    *first_frame, *cur_frame;
-  guint32        i;
-  frame_data    *cur_glist;
+  guint32        framenum;
 
   st->start_time = 0;
   st->stop_time = 0;
@@ -109,16 +108,14 @@ summary_fill_in(capture_file *cf, summary_tally *st)
   st->ignored_count = 0;
 
   /* initialize the tally */
-  if (cf->plist_start != NULL) {
-    first_frame = cf->plist_start;
-    st->start_time 	= nstime_to_sec(&first_frame->abs_ts);
+  if (cf->count != 0) {
+    first_frame = cap_file_find_fdata(cf, 1);
+    st->start_time = nstime_to_sec(&first_frame->abs_ts);
     st->stop_time = nstime_to_sec(&first_frame->abs_ts);
-    cur_glist = cf->plist_start;
 
-    for (i = 0; i < cf->count; i++) {
-      cur_frame = cur_glist;
+    for (framenum = 1; framenum <= cf->count; framenum++) {
+      cur_frame = cap_file_find_fdata(cf, framenum);
       tally_frame_data(cur_frame, st);
-      cur_glist = cur_glist->next;
     }
   }
 
diff --git a/tshark.c b/tshark.c
index 856304bc2f..528d6e801a 100644
--- a/tshark.c
+++ b/tshark.c
@@ -1202,11 +1202,9 @@ main(int argc, char *argv[])
       arg_error = TRUE;
 #endif
       break;
-#if GLIB_CHECK_VERSION(2,10,0)
     case 'P':        /* Perform two pass analysis */
       perform_two_pass_analysis = TRUE;
       break;
-#endif
     case 'n':        /* No name resolution */
       gbl_resolv_flags = RESOLV_NONE;
       break;
@@ -1818,10 +1816,7 @@ main(int argc, char *argv[])
 
   g_free(cf_name);
 
-#if GLIB_CHECK_VERSION(2,10,0)
-  if (cfile.plist_start != NULL)
-    g_slice_free_chain(frame_data, cfile.plist_start, next);
-#endif
+  cap_file_free_frames(&cfile);
 
   draw_tap_listeners(TRUE);
   funnel_dump_all_text_windows();
@@ -2387,25 +2382,26 @@ capture_cleanup(int signum _U_)
 #endif /* _WIN32 */
 #endif /* HAVE_LIBPCAP */
 
-#if GLIB_CHECK_VERSION(2,10,0)
 static gboolean
 process_packet_first_pass(capture_file *cf,
                gint64 offset, const struct wtap_pkthdr *whdr,
                union wtap_pseudo_header *pseudo_header, const guchar *pd)
 {
-  frame_data *fdata = g_slice_new(frame_data);
+  frame_data fdlocal;
+  guint32 framenum;
   epan_dissect_t edt;
   gboolean passed;
 
-  /* Count this packet. */
-  cf->count++;
+  /* The frame number of this packet is one more than the count of
+     frames in this packet. */
+  framenum = cf->count + 1;
 
   /* If we're not running a display filter and we're not printing any
      packet information, we don't need to do a dissection. This means
      that all packets can be marked as 'passed'. */
   passed = TRUE;
 
-  frame_data_init(fdata, cf->count, whdr, offset, cum_bytes);
+  frame_data_init(&fdlocal, framenum, whdr, offset, cum_bytes);
 
   /* If we're going to print packet information, or we're going to
      run a read filter, or we're going to process taps, set up to
@@ -2426,10 +2422,10 @@ process_packet_first_pass(capture_file *cf,
     if (cf->rfcode)
       epan_dissect_prime_dfilter(&edt, cf->rfcode);
 
-    frame_data_set_before_dissect(fdata, &cf->elapsed_time,
+    frame_data_set_before_dissect(&fdlocal, &cf->elapsed_time,
                                   &first_ts, &prev_dis_ts, &prev_cap_ts);
 
-    epan_dissect_run(&edt, pseudo_header, pd, fdata, NULL);
+    epan_dissect_run(&edt, pseudo_header, pd, &fdlocal, NULL);
 
     /* Run the read filter if we have one. */
     if (cf->rfcode)
@@ -2437,11 +2433,9 @@ process_packet_first_pass(capture_file *cf,
   }
 
   if (passed) {
-    frame_data_set_after_dissect(fdata, &cum_bytes, &prev_dis_ts);
-    cap_file_add_fdata(cf, fdata);
+    frame_data_set_after_dissect(&fdlocal, &cum_bytes, &prev_dis_ts);
+    cap_file_add_fdata(cf, &fdlocal);
   }
-  else
-    g_slice_free(frame_data, fdata);
 
   if (do_dissection)
     epan_dissect_cleanup(&edt);
@@ -2560,7 +2554,6 @@ process_packet_second_pass(capture_file *cf, frame_data *fdata,
   }
   return passed;
 }
-#endif
 
 static int
 load_cap_file(capture_file *cf, char *save_file, int out_file_type,
@@ -2646,7 +2639,7 @@ load_cap_file(capture_file *cf, char *save_file, int out_file_type,
   tap_flags = union_of_tap_listener_flags();
 
   if (perform_two_pass_analysis) {
-#if GLIB_CHECK_VERSION(2,10,0)
+    guint32 framenum;
     frame_data *fdata;
     int old_max_packet_count = max_packet_count;
 
@@ -2674,7 +2667,8 @@ load_cap_file(capture_file *cf, char *save_file, int out_file_type,
 
     max_packet_count = old_max_packet_count;
 
-    for (fdata = cf->plist_start; err == 0 && fdata != NULL; fdata = fdata->next) {
+    for (framenum = 1; err == 0 && framenum <= cf->count; framenum++) {
+      fdata = cap_file_find_fdata(cf, 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,
@@ -2705,7 +2699,6 @@ load_cap_file(capture_file *cf, char *save_file, int out_file_type,
         }
       }
     }
-#endif
   }
   else {
     while (wtap_read(cf->wth, &err, &err_info, &data_offset)) {