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, 222 insertions, 62 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;
 }