Don't use GNodes for the protocol tree, put the sibling pointer, and

pointers to the first *and* last child, in the "proto_node" structure
itself.  That saves us one level of indirection and memory allocation,
and lets us append to a tree by appending to the last child directly,
rather than having to scan through the list of siblings of the first
child to find the end of that list.

svn path=/trunk/; revision=9171

8 files changed, 166 insertions, 74 deletions

diff --git a/epan/proto.c b/epan/proto.c
index 52fb49f5c7..7f5a0a382d 100644
--- a/epan/proto.c
+++ b/epan/proto.c
@@ -1,7 +1,7 @@
 /* proto.c
  * Routines for protocol tree
  *
- * $Id: proto.c,v 1.123 2003/12/03 09:50:40 sahlberg Exp $
+ * $Id: proto.c,v 1.124 2003/12/04 10:59:34 guy Exp $
  *
  * Ethereal - Network traffic analyzer
  * By Gerald Combs <gerald@ethereal.com>
@@ -50,7 +50,7 @@
 #define cVALS(x) (const value_string*)(x)
 
 static gboolean
-proto_tree_free_node(GNode *node, gpointer data);
+proto_tree_free_node(proto_node *node, gpointer data);
 
 static void fill_label_boolean(field_info *fi, gchar *label_str);
 static void fill_label_uint(field_info *fi, gchar *label_str);
@@ -165,7 +165,11 @@ static field_info *field_info_tmp=NULL;
 /* Contains the space for proto_nodes. */
 static proto_node *proto_node_free_list=NULL;
 #define PROTO_NODE_NEW(node)				\
-	SLAB_ALLOC(node, proto_node_free_list)
+	SLAB_ALLOC(node, proto_node_free_list)		\
+	node->first_child = NULL;			\
+	node->last_child = NULL;			\
+	node->next = NULL;
+
 #define PROTO_NODE_FREE(node)				\
 	SLAB_FREE(node, proto_node_free_list)
 
@@ -294,16 +298,101 @@ proto_cleanup(void)
 
 }
 
+typedef gboolean (*proto_tree_traverse_func)(proto_node *, gpointer);
+
+static gboolean
+proto_tree_traverse_pre_order(proto_tree *tree, proto_tree_traverse_func func,
+    gpointer data)
+{
+	proto_node *pnode = tree;
+	proto_node *child;
+	proto_node *current;
+
+	if (func(pnode, data))
+		return TRUE;
+
+	child = pnode->first_child;
+	while (child != NULL) {
+		/*
+		 * The routine we call might modify the child, e.g. by
+		 * freeing it, so we get the child's successor before
+		 * calling that routine.
+		 */
+		current = child;
+		child = current->next;
+		if (proto_tree_traverse_pre_order((proto_tree *)current, func,
+		    data))
+			return TRUE;
+	}
+
+	return FALSE;
+}
+
+static gboolean
+proto_tree_traverse_in_order(proto_tree *tree, proto_tree_traverse_func func,
+    gpointer data)
+{
+	proto_node *pnode = tree;
+	proto_node *child;
+	proto_node *current;
+
+	child = pnode->first_child;
+	if (child != NULL) {
+		/*
+		 * The routine we call might modify the child, e.g. by
+		 * freeing it, so we get the child's successor before
+		 * calling that routine.
+		 */
+		current = child;
+		child = current->next;
+
+		if (proto_tree_traverse_in_order((proto_tree *)current, func,
+		    data))
+			return TRUE;
+
+		if (func(pnode, data))
+			return TRUE;
+
+		while (child != NULL) {
+			/*
+			 * The routine we call might modify the child, e.g. by
+			 * freeing it, so we get the child's successor before
+			 * calling that routine.
+			 */
+			current = child;
+			child = current->next;
+			if (proto_tree_traverse_in_order((proto_tree *)current,
+			    func, data))
+				return TRUE;
+		}
+	} else {
+		if (func(pnode, data))
+			return TRUE;
+	}
+
+	return FALSE;
+}
+
+void
+proto_tree_children_foreach(proto_tree *tree, proto_tree_foreach_func func,
+    gpointer data)
+{
+	proto_node *node = tree;
+	proto_node *current;
+
+	node = node->first_child;
+	while (node != NULL) {
+		current = node;
+		node = current->next;
+		func((proto_tree *)current, data);
+	}
+}
+
 /* frees the resources that the dissection a proto_tree uses */
 void
 proto_tree_free(proto_tree *tree)
 {
-	/* Free all the data pointed to by the tree. */
-	g_node_traverse((GNode*)tree, G_IN_ORDER, G_TRAVERSE_ALL, -1,
-		proto_tree_free_node, NULL);
-
-	/* Then free the tree. */
-	g_node_destroy((GNode*)tree);
+	proto_tree_traverse_in_order(tree, proto_tree_free_node, NULL);
 }
 
 static void
@@ -336,25 +425,25 @@ free_node_tree_data(tree_data_t *tree_data)
 	FIELD_INFO_FREE(finfo);
 
 static gboolean
-proto_tree_free_node(GNode *node, gpointer data _U_)
+proto_tree_free_node(proto_node *node, gpointer data _U_)
 {
 	field_info *finfo = PITEM_FINFO(node);
 
 	if (finfo == NULL) {
-		/* This is the root GNode. Destroy the per-tree data.
+		/* This is the root node. Destroy the per-tree data.
 		 * There is no field_info to destroy. */
 		free_node_tree_data(PTREE_DATA(node));
 	}
 	else {
-		/* This is a child GNode. Don't free the per-tree data, but
+		/* This is a child node. Don't free the per-tree data, but
 		 * do free the field_info data. */
 		FREE_NODE_FIELD_INFO(finfo);
 	}
 
 	/* Free the proto_node. */
-	PROTO_NODE_FREE(GNODE_PNODE(node));
+	PROTO_NODE_FREE(node);
 
-	return FALSE; /* FALSE = do not end traversal of GNode tree */
+	return FALSE; /* FALSE = do not end traversal of protocol tree */
 }
 
 /* Is the parsing being done for a visible proto_tree or an invisible one?
@@ -1740,12 +1829,11 @@ proto_tree_set_int(field_info *fi, gint32 value)
 }
 
 
-/* Add a field_info struct to the proto_tree, encapsulating it in a GNode (proto_item) */
+/* Add a field_info struct to the proto_tree, encapsulating it in a proto_node */
 static proto_item *
 proto_tree_add_node(proto_tree *tree, field_info *fi)
 {
-	GNode *new_gnode;
-	proto_node *pnode, *tnode;
+	proto_node *pnode, *tnode, *sibling;
 	field_info *tfi;
 
 	/*
@@ -1757,7 +1845,7 @@ proto_tree_add_node(proto_tree *tree, field_info *fi)
 	 * so it doesn't need an ett_ value to remember whether it
 	 * was expanded.
 	 */
-	tnode = GNODE_PNODE(tree);
+	tnode = tree;
 	tfi = tnode->finfo;
 	g_assert(tfi == NULL ||
 	    (tfi->tree_type >= 0 && tfi->tree_type < num_tree_types));
@@ -1766,10 +1854,15 @@ proto_tree_add_node(proto_tree *tree, field_info *fi)
 	pnode->finfo = fi;
 	pnode->tree_data = PTREE_DATA(tree);
 
-	new_gnode = g_node_new(pnode);
-	g_node_append((GNode*)tree, new_gnode);
+	if (tnode->last_child != NULL) {
+		sibling = tnode->last_child;
+		g_assert(sibling->next == NULL);
+		sibling->next = pnode;
+	} else
+		tnode->first_child = pnode;
+	tnode->last_child = pnode;
 
-	return (proto_item*) new_gnode;
+	return (proto_item*)pnode;
 }
 
 
@@ -2030,7 +2123,7 @@ proto_tree_create_root(void)
 	 * changed, then we'll find out very quickly. */
 	pnode->tree_data->visible = FALSE;
 
-	return (proto_tree*) g_node_new(pnode);
+	return (proto_tree*) pnode;
 }
 
 
@@ -3224,7 +3317,7 @@ typedef struct {
 } offset_search_t;
 
 static gboolean
-check_for_offset(GNode *node, gpointer data)
+check_for_offset(proto_node *node, gpointer data)
 {
 	field_info          *fi = PITEM_FINFO(node);
 	offset_search_t		*offsearch = data;
@@ -3258,8 +3351,7 @@ proto_find_field_from_offset(proto_tree *tree, guint offset, tvbuff_t *tvb)
 	offsearch.finfo = NULL;
 	offsearch.tvb = tvb;
 
-	g_node_traverse((GNode*)tree, G_PRE_ORDER, G_TRAVERSE_ALL, -1,
-			check_for_offset, &offsearch);
+	proto_tree_traverse_pre_order(tree, check_for_offset, &offsearch);
 
 	return offsearch.finfo;
 }
diff --git a/epan/proto.h b/epan/proto.h
index 9c0d3fa55e..7422945748 100644
--- a/epan/proto.h
+++ b/epan/proto.h
@@ -1,7 +1,7 @@
 /* proto.h
  * Definitions for protocol display
  *
- * $Id: proto.h,v 1.51 2003/12/03 09:28:22 guy Exp $
+ * $Id: proto.h,v 1.52 2003/12/04 10:59:34 guy Exp $
  *
  * Ethereal - Network traffic analyzer
  * By Gerald Combs <gerald@ethereal.com>
@@ -126,24 +126,28 @@ typedef struct {
     gboolean    visible;
 } tree_data_t;
 
-/* Each GNode (proto_tree, proto_item) points to one of
- * these. */
+/* Each proto_tree, proto_item is one of these. */
 typedef struct _proto_node {
+	struct _proto_node *first_child;
+	struct _proto_node *last_child;
+	struct _proto_node *next;
 	field_info  *finfo;
 	tree_data_t *tree_data;
 } proto_node;
 
-typedef GNode proto_tree;
-typedef GNode proto_item;
+typedef proto_node proto_tree;
+typedef proto_node proto_item;
 
-/* Retrieve the proto_node from a GNode. */
-#define GNODE_PNODE(t)  ((proto_node*)((GNode*)(t))->data)
+typedef void (*proto_tree_foreach_func)(proto_node *, gpointer);
+
+extern void proto_tree_children_foreach(proto_tree *tree,
+    proto_tree_foreach_func func, gpointer data);
 
 /* Retrieve the field_info from a proto_item */
-#define PITEM_FINFO(t)  (GNODE_PNODE(t)->finfo)
+#define PITEM_FINFO(t)  ((t)->finfo)
 
 /* Retrieve the tree_data_t from a proto_tree */
-#define PTREE_DATA(t)   (GNODE_PNODE(t)->tree_data)
+#define PTREE_DATA(t)   ((t)->tree_data)
 
 /* Sets up memory used by proto routines. Called at program startup */
 extern void proto_init(const char *plugin_dir,
diff --git a/file.c b/file.c
index 19253ed686..fef4ed5c50 100644
--- a/file.c
+++ b/file.c
@@ -1,7 +1,7 @@
 /* file.c
  * File I/O routines
  *
- * $Id: file.c,v 1.325 2003/12/02 23:14:30 guy Exp $
+ * $Id: file.c,v 1.326 2003/12/04 10:59:33 guy Exp $
  *
  * Ethereal - Network traffic analyzer
  * By Gerald Combs <gerald@ethereal.com>
@@ -96,7 +96,7 @@ static void rescan_packets(capture_file *cf, const char *action, const char *act
 
 static gboolean match_protocol_tree(capture_file *cf, frame_data *fdata,
 	void *criterion);
-static void match_subtree_text(GNode *node, gpointer data);
+static void match_subtree_text(proto_node *node, gpointer data);
 static gboolean match_summary_line(capture_file *cf, frame_data *fdata,
 	void *criterion);
 static gboolean match_ascii_and_unicode(capture_file *cf, frame_data *fdata,
@@ -1623,14 +1623,13 @@ match_protocol_tree(capture_file *cf, frame_data *fdata, void *criterion)
   /* Iterate through all the nodes, seeing if they have text that matches. */
   mdata->cf = cf;
   mdata->frame_matched = FALSE;
-  g_node_children_foreach((GNode*) edt->tree, G_TRAVERSE_ALL,
-			  match_subtree_text, mdata);
+  proto_tree_children_foreach(edt->tree, match_subtree_text, mdata);
   epan_dissect_free(edt);
   return mdata->frame_matched;
 }
 
 static void
-match_subtree_text(GNode *node, gpointer data)
+match_subtree_text(proto_node *node, gpointer data)
 {
   match_data	*mdata = (match_data*) data;
   const gchar	*string = mdata->string;
@@ -1680,8 +1679,8 @@ match_subtree_text(GNode *node, gpointer data)
   }
   
   /* Recurse into the subtree, if it exists */
-  if (g_node_n_children(node) > 0)
-    g_node_children_foreach(node, G_TRAVERSE_ALL, match_subtree_text, mdata);
+  if (node->first_child != NULL)
+    proto_tree_children_foreach(node, match_subtree_text, mdata);
 }
 
 gboolean
diff --git a/gtk/proto_draw.c b/gtk/proto_draw.c
index a580b79a0a..90b168c722 100644
--- a/gtk/proto_draw.c
+++ b/gtk/proto_draw.c
@@ -1,7 +1,7 @@
 /* proto_draw.c
  * Routines for GTK+ packet display
  *
- * $Id: proto_draw.c,v 1.70 2003/12/01 02:01:56 guy Exp $
+ * $Id: proto_draw.c,v 1.71 2003/12/04 10:59:34 guy Exp $
  *
  * Ethereal - Network traffic analyzer
  * By Gerald Combs <gerald@ethereal.com>
@@ -116,7 +116,7 @@ add_byte_tab(GtkWidget *byte_nb, const char *name, tvbuff_t *tvb,
     proto_tree *tree, GtkWidget *tree_view);
 
 static void
-proto_tree_draw_node(GNode *node, gpointer data);
+proto_tree_draw_node(proto_node *node, gpointer data);
 
 /* Get the current text window for the notebook. */
 GtkWidget *
@@ -1603,8 +1603,7 @@ proto_tree_draw(proto_tree *protocol_tree, GtkWidget *tree_view)
     gtk_tree_store_clear(store);
 #endif
 
-    g_node_children_foreach((GNode*) protocol_tree, G_TRAVERSE_ALL,
-                            proto_tree_draw_node, &info);
+    proto_tree_children_foreach(protocol_tree, proto_tree_draw_node, &info);
 
 #if GTK_MAJOR_VERSION < 2
     gtk_clist_thaw(GTK_CLIST(tree_view));
@@ -1612,7 +1611,7 @@ proto_tree_draw(proto_tree *protocol_tree, GtkWidget *tree_view)
 }
 
 static void
-proto_tree_draw_node(GNode *node, gpointer data)
+proto_tree_draw_node(proto_node *node, gpointer data)
 {
     struct proto_tree_draw_info	info;
     struct proto_tree_draw_info	*parent_info = (struct proto_tree_draw_info*) data;
@@ -1641,7 +1640,7 @@ proto_tree_draw_node(GNode *node, gpointer data)
         proto_item_fill_label(fi, label_str);
     }
 
-    if (g_node_n_children(node) > 0) {
+    if (node->first_child != NULL) {
         is_leaf = FALSE;
         g_assert(fi->tree_type >= 0 && fi->tree_type < num_tree_types);
         if (tree_is_expanded[fi->tree_type]) {
@@ -1676,8 +1675,7 @@ proto_tree_draw_node(GNode *node, gpointer data)
 #else
         info.iter = &iter;
 #endif
-        g_node_children_foreach(node, G_TRAVERSE_ALL,
-                                proto_tree_draw_node, &info);
+        proto_tree_children_foreach(node, proto_tree_draw_node, &info);
 #if GTK_MAJOR_VERSION >= 2
         path = gtk_tree_model_get_path(GTK_TREE_MODEL(store), &iter);
         if (is_expanded)
diff --git a/gtk/rtp_analysis.c b/gtk/rtp_analysis.c
index de4b0d8ecf..03257a9468 100644
--- a/gtk/rtp_analysis.c
+++ b/gtk/rtp_analysis.c
@@ -1,7 +1,7 @@
 /* rtp_analysis.c
  * RTP analysis addition for ethereal
  *
- * $Id: rtp_analysis.c,v 1.12 2003/12/03 09:28:26 guy Exp $
+ * $Id: rtp_analysis.c,v 1.13 2003/12/04 10:59:34 guy Exp $
  *
  * Copyright 2003, Alcatel Business Systems
  * By Lars Ruoff <lars.ruoff@gmx.net>
@@ -1770,11 +1770,11 @@ void create_rtp_dialog(user_data_t* user_data)
 
 
 /****************************************************************************/
-static gboolean process_node(proto_item *ptree_node, header_field_info *hfinformation,
+static gboolean process_node(proto_node *ptree_node, header_field_info *hfinformation,
 							const gchar* proto_field, guint32* p_result)
 {
 	field_info            *finfo;
-	proto_item            *proto_sibling_node;
+	proto_node            *proto_sibling_node;
 	header_field_info     *hfssrc;
 	ipv4_addr             *ipv4;
 
@@ -1784,8 +1784,8 @@ static gboolean process_node(proto_item *ptree_node, header_field_info *hfinform
 		hfssrc = proto_registrar_get_byname((gchar*) proto_field);
 		if (hfssrc == NULL)
 			return FALSE;
-		for(ptree_node=g_node_first_child(ptree_node); ptree_node!=NULL; 
-					ptree_node=g_node_next_sibling(ptree_node)) {
+		for(ptree_node=ptree_node->first_child; ptree_node!=NULL; 
+					ptree_node=ptree_node->next) {
 			finfo=PITEM_FINFO(ptree_node);
 			if (hfssrc==finfo->hfinfo) {
 				if (hfinformation->type==FT_IPv4) {
@@ -1800,7 +1800,7 @@ static gboolean process_node(proto_item *ptree_node, header_field_info *hfinform
 		}
 	}
 
-	proto_sibling_node = g_node_next_sibling(ptree_node);
+	proto_sibling_node = ptree_node->next;
 
 	if (proto_sibling_node) {
 		return process_node(proto_sibling_node, hfinformation, proto_field, p_result);
@@ -1815,14 +1815,14 @@ static gboolean get_int_value_from_proto_tree(proto_tree *protocol_tree,
 											 const gchar* proto_field,
 											 guint32* p_result)
 {
-	proto_item      *ptree_node;
+	proto_node      *ptree_node;
 	header_field_info     *hfinformation;
 
 	hfinformation = proto_registrar_get_byname((gchar*) proto_name);
 	if (hfinformation == NULL)
 		return FALSE;
 
-	ptree_node = g_node_first_child(protocol_tree);
+	ptree_node = ((proto_node *)protocol_tree)->first_child;
 	if (!ptree_node)
 		return FALSE;
 
diff --git a/print.c b/print.c
index 553febb42b..07ab81d628 100644
--- a/print.c
+++ b/print.c
@@ -1,7 +1,7 @@
 /* print.c
  * Routines for printing packet analysis trees.
  *
- * $Id: print.c,v 1.62 2003/12/03 09:28:19 guy Exp $
+ * $Id: print.c,v 1.63 2003/12/04 10:59:33 guy Exp $
  *
  * Gilbert Ramirez <gram@alumni.rice.edu>
  *
@@ -41,7 +41,7 @@
 #include "util.h"
 #include "packet-data.h"
 
-static void proto_tree_print_node(GNode *node, gpointer data);
+static void proto_tree_print_node(proto_node *node, gpointer data);
 static void print_hex_data_buffer(FILE *fh, register const guchar *cp,
     register guint length, char_enc encoding, gint format);
 static void ps_clean_string(unsigned char *out, const unsigned char *in,
@@ -95,8 +95,7 @@ void proto_tree_print(print_args_t *print_args, epan_dissect_t *edt,
 	       print uninterpreted data fields in hex as well. */
 	data.format = print_args->format;
 
-	g_node_children_foreach((GNode*) edt->tree, G_TRAVERSE_ALL,
-		proto_tree_print_node, &data);
+	proto_tree_children_foreach(edt->tree, proto_tree_print_node, &data);
 }
 
 /*
@@ -130,7 +129,7 @@ get_field_data(GSList *src_list, field_info *fi)
 
 /* Print a tree's data, and any child nodes. */
 static
-void proto_tree_print_node(GNode *node, gpointer data)
+void proto_tree_print_node(proto_node *node, gpointer data)
 {
 	field_info	*fi = PITEM_FINFO(node);
 	print_data	*pdata = (print_data*) data;
@@ -170,9 +169,9 @@ void proto_tree_print_node(GNode *node, gpointer data)
 	g_assert(fi->tree_type >= -1 && fi->tree_type < num_tree_types);
 	if (pdata->print_all_levels ||
 	    (fi->tree_type >= 0 && tree_is_expanded[fi->tree_type])) {
-		if (g_node_n_children(node) > 0) {
+		if (node->first_child != NULL) {
 			pdata->level++;
-			g_node_children_foreach(node, G_TRAVERSE_ALL,
+			proto_tree_children_foreach(node,
 				proto_tree_print_node, pdata);
 			pdata->level--;
 		}
diff --git a/proto_hier_stats.c b/proto_hier_stats.c
index 266c7dd070..641ee0d24c 100644
--- a/proto_hier_stats.c
+++ b/proto_hier_stats.c
@@ -1,7 +1,7 @@
 /* proto_hier_stats.c
  * Routines for calculating statistics based on protocol.
  *
- * $Id: proto_hier_stats.c,v 1.19 2003/12/03 09:28:19 guy Exp $
+ * $Id: proto_hier_stats.c,v 1.20 2003/12/04 10:59:33 guy Exp $
  *
  * Ethereal - Network traffic analyzer
  * By Gerald Combs <gerald@ethereal.com>
@@ -76,11 +76,11 @@ find_stat_node(GNode *parent_stat_node, header_field_info *needle_hfinfo)
 
 
 static void
-process_node(proto_item *ptree_node, GNode *parent_stat_node, ph_stats_t *ps, guint pkt_len)
+process_node(proto_node *ptree_node, GNode *parent_stat_node, ph_stats_t *ps, guint pkt_len)
 {
 	field_info		*finfo;
-	ph_stats_node_t	*stats;
-	proto_item		*proto_sibling_node;
+	ph_stats_node_t		*stats;
+	proto_node		*proto_sibling_node;
 	GNode			*stat_node;
 
 	finfo = PITEM_FINFO(ptree_node);
@@ -95,7 +95,7 @@ process_node(proto_item *ptree_node, GNode *parent_stat_node, ph_stats_t *ps, gu
 	stats->num_pkts_total++;
 	stats->num_bytes_total += pkt_len;
 
-	proto_sibling_node = g_node_next_sibling(ptree_node);
+	proto_sibling_node = ptree_node->next;
 
 	if (proto_sibling_node) {
 		process_node(proto_sibling_node, stat_node, ps, pkt_len);
@@ -111,9 +111,9 @@ process_node(proto_item *ptree_node, GNode *parent_stat_node, ph_stats_t *ps, gu
 static void
 process_tree(proto_tree *protocol_tree, ph_stats_t* ps, guint pkt_len)
 {
-	proto_item	*ptree_node;
+	proto_node	*ptree_node;
 
-	ptree_node = g_node_first_child(protocol_tree);
+	ptree_node = ((proto_node *)protocol_tree)->first_child;
 	if (!ptree_node) {
 		return;
 	}
diff --git a/tap-protohierstat.c b/tap-protohierstat.c
index dfe6481705..532ebcc343 100644
--- a/tap-protohierstat.c
+++ b/tap-protohierstat.c
@@ -1,7 +1,7 @@
 /* tap-protohierstat.c
  * protohierstat   2002 Ronnie Sahlberg
  *
- * $Id: tap-protohierstat.c,v 1.5 2003/12/03 09:28:19 guy Exp $
+ * $Id: tap-protohierstat.c,v 1.6 2003/12/04 10:59:33 guy Exp $
  *
  * Ethereal - Network traffic analyzer
  * By Gerald Combs <gerald@ethereal.com>
@@ -84,11 +84,11 @@ protohierstat_packet(void *prs, packet_info *pinfo, epan_dissect_t *edt, void *d
 	if(!edt->tree){
 		return 0;
 	}
-	if(!edt->tree->children){
+	if(!edt->tree->first_child){
 		return 0;
 	}
 
-	for(tree=edt->tree->children;tree;tree=tree->next){
+	for(tree=edt->tree->first_child;tree;tree=tree->next){
 		fi=PITEM_FINFO(tree);
 
 		/* first time we saw a protocol at this leaf */