2005-09-10 Paul Jakma <paul.jakma@sun.com>

	* Makefile.am: bgpd shouldn't list libgp's sources as its own.
	  Use LDADD.
	* bgp_aspath.h:
	  (struct assegment) New struct, abstract representation of a
	  list of AS_PATH segments and the contained ASNs.
	  (struct aspath) Remove the raw-data related
	  fields, reference the abstract struct assegment instead.
	  Remove several other computed fields, it's just a
	  headache to maintain them and they're cheap to compute from
	  struct assegment.
	  (aspath_parse) parse a stream, not a pointer to raw data.
	  (aspath_count_{hops,confeds,size}) helpers to access
	  information formerly directly contained in struct aspath.
	  (aspath_snmp_pathseg) Helper for SNMP, BGP MIB wants
	  to be able to output hex representation of raw data.
	* bgp_aspath.c: (general) partial-rewrite. Store aspath data
	  as an abstract singly-linked list of abstract segments,
          rather than storing the raw data, and parsing it each and
	  every time. Remove several count/size fields which are cheap
	  to compute from the abstract segment structure.
	  (global) Include stream.h, needed for aspath_parse, and
	  others. Couple of helper macros added.
	  (struct assegment_header) Just the header, and only the
	  header.
	  (assegment_data_{new,free}) convenience functions for
	  AS_SEG_DATA allocation, the dynamic, per-segment array of
	  ASNs.
	  (assegment_{new,free,free_all,dup,dup_all}) convenience
	  functions for creating struct assegments. The _all forms will
	  follow the entire chain of segments from the given segment.
	  (assegment_prepend_asns) new function, prepend an ASN N times
	  to segment.
 	  (assegment_append_asns) Append a list (array) of ASNs to
	  segment.
	  (int_cmp) convenience function for the aspath hash.
	  (assegment_normalise) new function. Normalise the given
	  segment chain to meet expectations of Quagga, and to
	  eliminate differing raw representations of the same paths.
	  Merge 'runs' of SEQUENCEs into one segment as our internal
	  segment is not limited by the protocol AS_PATH segment
	  length. Sort ASNs in SETs.
	  (aspath_new) Take void argument to quell warnings. Use the
	  assegment convenience functions.
	  (assegment_count_{asns,confeds,hops}) new functions to
	  compute at runtime values previously held in struct aspath.
	  (aspath_size) ditto.
	  (aspath_make_str_count) rewritten to stringify new
	  representation, and to be slightly easier to understand
	  hopefully.
	  (aspath_str_update) convenience function, update the aspath
	  str. Should investigate removing maintained string from
	  struct aspath, just run-time compute it, as per other fields.
	  It's just a maintenance headache, would save noticeable
	  amount of RAM with possibly not much extra run-time cost.
	  (aspath_dup) use the assegment dup functions.
	  (aspath_hash_alloc) Take void * argument to satisfy gcc. Use
	  the proper helper functions to dup data.
	  (assegments_parse) new function. parse raw AS_PATH data into
	  struct assegments. Normalise and return the head of the list.
	  (aspath_parse) Parse a stream, not pointer to raw data and
	  use assegments_parse to do it.
	  (assegment_data_put) Write out a single segment data in protocol
	  form to stream.
	  (assegment_header_put) ditto but for segment header.
	  (aspath_put) new function. As per previous but for an entire
	  struct aspath.
	  (aspath_snmp_pathseg) wrapper around aspath_put for
	  bgp_snmp.c. Uses a static buffer sadly.
	  (aspath_aggregate_as_set_add) rewritten to use assegments.
	  (aspath_aggregate) ditto
	  (aspath_{firstas,loop,private_as}_check) ditto
	  (aspath_{merge,prepend,add_one_as}) ditto
	  (aspath_cmp_left{_confed}) ditto
	  (aspath_delete_confed_seq) ditto, plus fixed to properly
	  delete all leading confed segments.
	  (aspath_as_add) Just use assegment_append_asns.
	  (aspath_segment_add) updated to use assegments.
	  (enum as_token) Add values for confeds
	  (aspath_gettoken) Add support for confeds
	  (aspath_str2aspath) ditto
	  (aspath_key_make) updated to use as_segments. Also, add
	  segment type into the hash value as appropriate.
	  (aspath_cmp) updated to use as_segments.
	  (aspath_print) don't segfault on NULL argument.
	* bgp_attr.c: (bgp_attr_aspath) aspath_parse wants the stream
	  now. No need for manual forwarding of stream.
	  (bgp_packet_attribute) empty aspath is now denoted by NULL
	  segment field, length is gone.
	  Use aspath_size() to determine size.
	  (bgp_attr_init) Fix declaration, explicitely specify void
	  arg.
	  (bgp_dump_routes_attr) Use aspath_size() to determine size.
	* bgp_route.c: (bgp_info_cmp) use the aspath_count_* functions.
	  (bgp_rib_withdraw) remove unused variable. Use
	  aspath_count_hops.
	* bgp_snmp.c: (bgp4PathAttrTable) raw data is gone, use
	  aspath_snmp_pathseg to get the representation.

1 files changed, 832 insertions, 511 deletions

diff --git a/bgpd/bgp_aspath.c b/bgpd/bgp_aspath.c
index d13ed186..7f85ea10 100644
--- a/bgpd/bgp_aspath.c
+++ b/bgpd/bgp_aspath.c
@@ -1,5 +1,6 @@
 /* AS path management routines.
    Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro
+   Copyright (C) 2005 Sun Microsystems, Inc.
 
 This file is part of GNU Zebra.
 
@@ -26,6 +27,7 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 #include "vty.h"
 #include "str.h"
 #include "log.h"
+#include "stream.h"
 
 #include "bgpd/bgpd.h"
 #include "bgpd/bgp_aspath.h"
@@ -36,22 +38,255 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 /* Two octet is used for AS value. */
 #define AS_VALUE_SIZE         sizeof (as_t)
 
-/* AS segment octet length. */
-#define ASSEGMENT_LEN(X)  ((X)->length * AS_VALUE_SIZE + AS_HEADER_SIZE)
+/* Maximum protocol segment length value */
+#define AS_SEGMENT_MAX		255
+
+/* The following length and size macros relate specifically to Quagga's
+ * internal representation of AS-Segments, not per se to the on-wire
+ * sizes and lengths.  At present (200508) they sort of match, however
+ * the ONLY functions which should now about the on-wire syntax are
+ * aspath_put, assegment_put and assegment_parse.
+ */
+
+/* Calculated size in bytes of ASN segment data to hold N ASN's */
+#define ASSEGMENT_DATA_SIZE(N) ((N) * AS_VALUE_SIZE)
 
-/* To fetch and store as segment value. */
-struct assegment
+/* Calculated size of segment struct to hold N ASN's */
+#define ASSEGMENT_SIZE(N)  (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N))
+
+/* AS segment octet length. */
+#define ASSEGMENT_LEN(X) ASSEGMENT_SIZE((X)->length)
+
+/* AS_SEQUENCE segments can be packed together */
+/* Can the types of X and Y be considered for packing? */
+#define ASSEGMENT_TYPES_PACKABLE(X,Y) \
+  ( ((X)->type == (Y)->type) \
+   && ((X)->type == AS_SEQUENCE))
+/* Types and length of X,Y suitable for packing? */
+#define ASSEGMENTS_PACKABLE(X,Y) \
+  ( ASSEGMENT_TYPES_PACKABLE( (X), (Y)) \
+   && ( ((X)->length + (Y)->length) <= AS_SEGMENT_MAX ) )
+
+/* As segment header - the on-wire representation 
+ * NOT the internal representation!
+ */
+struct assegment_header
 {
   u_char type;
   u_char length;
-  as_t asval[1];
 };
 
 /* Hash for aspath.  This is the top level structure of AS path. */
 struct hash *ashash;
 
+static inline as_t *
+assegment_data_new (int num)
+{
+  return (XCALLOC (MTYPE_AS_SEG_DATA, ASSEGMENT_DATA_SIZE (num)));
+}
+
+static inline void
+assegment_data_free (as_t *asdata)
+{
+  XFREE (MTYPE_AS_SEG_DATA,asdata);
+}
+
+/* Get a new segment. Note that 0 is an allowed length,
+ * and will result in a segment with no allocated data segment.
+ * the caller should immediately assign data to the segment, as the segment
+ * otherwise is not generally valid
+ */
+static struct assegment *
+assegment_new (u_char type, u_short length)
+{
+  struct assegment *new;
+  
+  new = XCALLOC (MTYPE_AS_SEG, sizeof (struct assegment));
+  
+  if (length)
+    new->as = assegment_data_new (length);
+  
+  new->length = length;
+  new->type = type;
+  
+  return new;
+}
+
+static void
+assegment_free (struct assegment *seg)
+{
+  if (!seg)
+    return;
+  
+  if (seg->as)
+    XFREE (MTYPE_AS_SEG_DATA, seg->as);
+  memset (seg, 0xfe, sizeof(struct assegment));
+  XFREE (MTYPE_AS_SEG, seg);
+  
+  return;
+}
+
+/* free entire chain of segments */
+static void
+assegment_free_all (struct assegment *seg)
+{
+  struct assegment *prev;
+  
+  while (seg)
+    {
+      prev = seg;
+      seg = seg->next;
+      assegment_free (prev);
+    }
+}
+
+/* Duplicate just the given assegment and its data */
+static struct assegment *
+assegment_dup (struct assegment *seg)
+{
+  struct assegment *new;
+  
+  new = assegment_new (seg->type, seg->length);
+  memcpy (new->as, seg->as, ASSEGMENT_DATA_SIZE (new->length) );
+    
+  return new;
+}
+
+/* Duplicate entire chain of assegments, return the head */
+static struct assegment *
+assegment_dup_all (struct assegment *seg)
+{
+  struct assegment *new = NULL;
+  struct assegment *head = NULL;
+  
+  while (seg)
+    {
+      if (head)
+        {
+          new->next = assegment_dup (seg);
+          new = new->next;
+        }
+      else
+        head = new = assegment_dup (seg);
+      
+      seg = seg->next;
+    }
+  return head;
+}
+
+/* prepend the as number to given segment, given num of times */
+static struct assegment *
+assegment_prepend_asns (struct assegment *seg, as_t asnum, int num)
+{
+  as_t *newas;
+  
+  if (!num)
+    return seg;
+  
+  if (num >= AS_SEGMENT_MAX)
+    return seg; /* we don't do huge prepends */
+  
+  newas = assegment_data_new (seg->length + num);
+  
+  if (newas)
+    {
+      int i;
+      for (i = 0; i < num; i++)
+        newas[i] = asnum;
+      
+      memcpy (newas + num, seg->as, ASSEGMENT_DATA_SIZE (seg->length));
+      XFREE (MTYPE_AS_SEG_DATA, seg->as);
+      seg->as = newas; 
+      seg->length += num;
+      return seg;
+    }
+
+  assegment_free_all (seg);
+  return NULL;
+}
+
+/* append given array of as numbers to the segment */
+static struct assegment *
+assegment_append_asns (struct assegment *seg, as_t *asnos, int num)
+{
+  seg->as = XREALLOC (MTYPE_AS_SEG_DATA, seg->as,
+		      ASSEGMENT_DATA_SIZE (seg->length + num));
+
+  if (seg->as)
+    {
+      memcpy (seg->as + seg->length, asnos, ASSEGMENT_DATA_SIZE(num));
+      seg->length += num;
+      return seg;
+    }
+
+  assegment_free_all (seg);
+  return NULL;
+}
+
+static int
+int_cmp (const void *p1, const void *p2)
+{
+  const as_t *as1 = p1;
+  const as_t *as2 = p2;
+  
+  return (*as1 == *as2) 
+          ? 0 : ( (*as1 > *as2) ? 1 : -1);
+}
+
+/* normalise the segment.
+ * In particular, merge runs of AS_SEQUENCEs into one segment
+ * Internally, we do not care about the wire segment length limit, and
+ * we want each distinct AS_PATHs to have the exact same internal
+ * representation - eg, so that our hashing actually works..
+ */
+static struct assegment *
+assegment_normalise (struct assegment *head)
+{
+  struct assegment *seg = head, *pin;
+  struct assegment *tmp;
+  
+  if (!head)
+    return head;
+  
+  while (seg)
+    {
+      pin = seg;
+      
+      /* Sort values SET segments, for determinism in paths to aid
+       * creation of hash values / path comparisons
+       * and because it helps other lesser implementations ;)
+       */
+      if (seg->type == AS_SET || seg->type == AS_CONFED_SET)
+        qsort (seg->as, seg->length, sizeof(as_t), int_cmp);
+
+      /* read ahead from the current, pinned segment while the segments
+       * are packable/mergeable. Append all following packable segments
+       * to the segment we have pinned and remove these appended
+       * segments.
+       */      
+      while (pin->next && ASSEGMENT_TYPES_PACKABLE(pin, pin->next))
+        {
+          tmp = pin->next;
+          seg = pin->next;
+          
+          /* append the next sequence to the pinned sequence */
+          pin = assegment_append_asns (pin, seg->as, seg->length);
+          
+          /* bypass the next sequence */
+          pin->next = seg->next;
+          
+          /* get rid of the now referenceless segment */
+          assegment_free (tmp);
+          
+        }
+
+      seg = pin->next;
+    }
+  return head;
+}
+
 static struct aspath *
-aspath_new ()
+aspath_new (void)
 {
   struct aspath *aspath;
 
@@ -66,8 +301,8 @@ aspath_free (struct aspath *aspath)
 {
   if (!aspath)
     return;
-  if (aspath->data)
-    XFREE (MTYPE_AS_SEG, aspath->data);
+  if (aspath->segments)
+    assegment_free_all (aspath->segments);
   if (aspath->str)
     XFREE (MTYPE_AS_STR, aspath->str);
   XFREE (MTYPE_AS_PATH, aspath);
@@ -106,7 +341,6 @@ aspath_delimiter_char (u_char type, u_char which)
   } aspath_delim_char [] =
     {
       { AS_SET,             '{', '}' },
-      { AS_SEQUENCE,        ' ', ' ' },
       { AS_CONFED_SET,      '[', ']' },
       { AS_CONFED_SEQUENCE, '(', ')' },
       { 0 }
@@ -125,142 +359,179 @@ aspath_delimiter_char (u_char type, u_char which)
   return ' ';
 }
 
+/* countup asns from this segment and index onward */
+static int
+assegment_count_asns (struct assegment *seg, int from)
+{
+  int count = 0;
+  while (seg)
+    {
+      if (!from)
+        count += seg->length;
+      else
+        {
+          count += (seg->length - from);
+          from = 0;
+        }
+      seg = seg->next;
+    }
+  return count;
+}
+
+unsigned int
+aspath_count_confeds (struct aspath *aspath)
+{
+  int count = 0;
+  struct assegment *seg = aspath->segments;
+  
+  while (seg)
+    {
+      if (seg->type == AS_CONFED_SEQUENCE)
+        count += seg->length;
+      else if (seg->type == AS_CONFED_SET)
+        count++;
+      
+      seg = seg->next;
+    }
+  return count;
+}
+
+unsigned int
+aspath_count_hops (struct aspath *aspath)
+{
+  int count = 0;
+  struct assegment *seg = aspath->segments;
+  
+  while (seg)
+    {
+      if (seg->type == AS_SEQUENCE)
+        count += seg->length;
+      else if (seg->type == AS_SET)
+        count++;
+      
+      seg = seg->next;
+    }
+  return count;
+}
+
+unsigned int
+aspath_size (struct aspath *aspath)
+{
+  int size = 0;
+  struct assegment *seg = aspath->segments;
+  
+  while (seg)
+    {
+      size += ASSEGMENT_SIZE(seg->length);
+      seg = seg->next;
+    }
+  return size;
+}
+
 /* Convert aspath structure to string expression. */
 static char *
 aspath_make_str_count (struct aspath *as)
 {
-  int space;
-  u_char type;
-  caddr_t pnt;
-  caddr_t end;
-  struct assegment *assegment;
-  int str_size = ASPATH_STR_DEFAULT_LEN;
-  int str_pnt;
+  struct assegment *seg;
+  int str_size;
+  int len = 0;
   char *str_buf;
-  int count = 0;
-  int confed_count = 0;
 
   /* Empty aspath. */
-  if (as->length == 0)
+  if (!as->segments)
     {
       str_buf = XMALLOC (MTYPE_AS_STR, 1);
       str_buf[0] = '\0';
-      as->count = count;
-      as->confed_count = confed_count;
       return str_buf;
     }
-
-  /* Set default value. */
-  space = 0;
-  type = AS_SEQUENCE;
-
-  /* Set initial pointer. */
-  pnt = as->data;
-  end = pnt + as->length;
-
+  
+  seg = as->segments;
+  
+  /* ASN takes 5 chars at least, plus seperator, see below.
+   * If there is one differing segment type, we need an additional
+   * 2 chars for segment delimiters, and the final '\0'.
+   * Hopefully this is large enough to avoid hitting the realloc
+   * code below for most common sequences.
+   */
+#define ASN_STR_LEN (5 + 1)
+  str_size = MAX (assegment_count_asns (seg, 0) * ASN_STR_LEN + 2 + 1,
+                  ASPATH_STR_DEFAULT_LEN);
   str_buf = XMALLOC (MTYPE_AS_STR, str_size);
-  str_pnt = 0;
-
-  assegment = (struct assegment *) pnt;
 
-  while (pnt < end)
+  while (seg)
     {
       int i;
-      int estimate_len;
-
-      /* For fetch value. */
-      assegment = (struct assegment *) pnt;
-
-      /* Check AS type validity. */
-      if ((assegment->type != AS_SET) && 
-	  (assegment->type != AS_SEQUENCE) &&
-	  (assegment->type != AS_CONFED_SET) && 
-	  (assegment->type != AS_CONFED_SEQUENCE))
-	{
-	  XFREE (MTYPE_AS_STR, str_buf);
-	  return NULL;
-	}
-
-      /* Check AS length. */
-      if ((pnt + (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE) > end)
-	{
-	  XFREE (MTYPE_AS_STR, str_buf);
-	  return NULL;
-	}
-
-      /* Buffer length check. */
-      estimate_len = ((assegment->length * 6) + 4);
+      char seperator;
       
-      /* String length check. */
-      while (str_pnt + estimate_len >= str_size)
-	{
-	  str_size *= 2;
-	  str_buf = XREALLOC (MTYPE_AS_STR, str_buf, str_size);
-	}
-
-      /* If assegment type is changed, print previous type's end
-         character. */
-      if (type != AS_SEQUENCE)
-	str_buf[str_pnt++] = aspath_delimiter_char (type, AS_SEG_END);
-      if (space)
-	str_buf[str_pnt++] = ' ';
-
-      if (assegment->type != AS_SEQUENCE)
-	str_buf[str_pnt++] = aspath_delimiter_char (assegment->type, AS_SEG_START);
-
-      space = 0;
-
-      /* Increment counts */
-      switch (assegment->type)
-	{
-	case AS_SEQUENCE:
-	  count += assegment->length;
-	  break;
-	case AS_SET:
-	  count++;
-	  break;
-	case AS_CONFED_SEQUENCE:
-	  confed_count += assegment->length;
-	  break;
-	case AS_CONFED_SET:
-	  confed_count++;
-	  break;
-	}
-
-      for (i = 0; i < assegment->length; i++)
-	{
-	  int len;
-
-	  if (space)
-	    {
-	      if (assegment->type == AS_SET
-		  || assegment->type == AS_CONFED_SET)
-		str_buf[str_pnt++] = ',';
-	      else
-		str_buf[str_pnt++] = ' ';
-	    }
-	  else
-	    space = 1;
-
-	  len = sprintf (str_buf + str_pnt, "%d", ntohs (assegment->asval[i]));
-	  str_pnt += len;
-	}
-
-      type = assegment->type;
-      pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
+      /* Check AS type validity. Set seperator for segment */
+      switch (seg->type)
+        {
+          case AS_SET:
+          case AS_CONFED_SET:
+            seperator = ',';
+            break;
+          case AS_SEQUENCE:
+          case AS_CONFED_SEQUENCE:
+            seperator = ' ';
+            break;
+          default:
+            XFREE (MTYPE_AS_STR, str_buf);
+            return NULL;
+        }
+      
+      /* We might need to increase str_buf, particularly if path has
+       * differing segments types, our initial guesstimate above will
+       * have been wrong.  need 5 chars for ASN, a seperator each and
+       * potentially two segment delimiters, plus a space between each
+       * segment and trailing zero.
+       */
+#define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
+      if ( (len + SEGMENT_STR_LEN(seg)) > str_size)
+        {
+          str_size = len + SEGMENT_STR_LEN(seg);
+          str_buf = XREALLOC (MTYPE_AS_STR, str_buf, str_size);
+        }
+#undef ASN_STR_LEN
+#undef SEGMENT_STR_LEN
+      
+      if (seg->type != AS_SEQUENCE)
+        len += snprintf (str_buf + len, str_size - len, 
+			 "%c", 
+                         aspath_delimiter_char (seg->type, AS_SEG_START));
+      
+      /* write out the ASNs, with their seperators, bar the last one*/
+      for (i = 0; i < seg->length; i++)
+        {
+          len += snprintf (str_buf + len, str_size - len, "%u", seg->as[i]);
+          
+          if (i < (seg->length - 1))
+            len += snprintf (str_buf + len, str_size - len, "%c", seperator);
+        }
+      
+      if (seg->type != AS_SEQUENCE)
+        len += snprintf (str_buf + len, str_size - len, "%c", 
+                        aspath_delimiter_char (seg->type, AS_SEG_END));
+      if (seg->next)
+        len += snprintf (str_buf + len, str_size - len, " ");
+      
+      seg = seg->next;
     }
-
-  if (assegment->type != AS_SEQUENCE)
-    str_buf[str_pnt++] = aspath_delimiter_char (assegment->type, AS_SEG_END);
-
-  str_buf[str_pnt] = '\0';
-
-  as->count = count;
-  as->confed_count = confed_count;
+  
+  assert (len < str_size);
+  
+  str_buf[len] = '\0';
 
   return str_buf;
 }
 
+static void
+aspath_str_update (struct aspath *as)
+{
+  if (as->str)
+    XFREE (MTYPE_AS_STR, as->str);
+  as->str = aspath_make_str_count (as);
+}
+
 /* Intern allocated AS path. */
 struct aspath *
 aspath_intern (struct aspath *aspath)
@@ -274,7 +545,7 @@ aspath_intern (struct aspath *aspath)
   find = hash_get (ashash, aspath, hash_alloc_intern);
 
   if (find != aspath)
-      aspath_free (aspath);
+    aspath_free (aspath);
 
   find->refcnt++;
 
@@ -291,43 +562,26 @@ aspath_dup (struct aspath *aspath)
 {
   struct aspath *new;
 
-  new = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
-  memset (new, 0, sizeof (struct aspath));
+  new = XCALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
 
-  new->length = aspath->length;
-
-  if (new->length)
-    {
-      new->data = XMALLOC (MTYPE_AS_SEG, aspath->length);
-      memcpy (new->data, aspath->data, aspath->length);
-    }
+  if (aspath->segments)
+    new->segments = assegment_dup_all (aspath->segments);
   else
-    new->data = NULL;
+    new->segments = NULL;
 
-  /* new->str = aspath_make_str_count (aspath); */
+  new->str = aspath_make_str_count (aspath);
 
   return new;
 }
 
 static void *
-aspath_hash_alloc (struct aspath *arg)
+aspath_hash_alloc (void *arg)
 {
   struct aspath *aspath;
 
   /* New aspath strucutre is needed. */
-  aspath = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
-  memset ((void *) aspath, 0, sizeof (struct aspath));
-  aspath->length = arg->length;
-
-  /* In case of IBGP connection aspath's length can be zero. */
-  if (arg->length)
-    {
-      aspath->data = XMALLOC (MTYPE_AS_SEG, arg->length);
-      memcpy (aspath->data, arg->data, arg->length);
-    }
-  else
-    aspath->data = NULL;
-
+  aspath = aspath_dup (arg);
+  
   /* Make AS path string. */
   aspath->str = aspath_make_str_count (aspath);
 
@@ -341,23 +595,79 @@ aspath_hash_alloc (struct aspath *arg)
   return aspath;
 }
 
+/* parse as-segment byte stream in struct assegment */
+struct assegment *
+assegments_parse (struct stream *s, size_t length)
+{
+  struct assegment_header segh;
+  struct assegment *seg, *prev = NULL, *head = NULL;
+  size_t bytes = 0;
+  
+  /* empty aspath (ie iBGP or somesuch) */
+  if (length == 0)
+    return NULL;
+  
+  /* basic checks */
+  if ( (STREAM_READABLE(s) < length)
+      || (STREAM_READABLE(s) < AS_HEADER_SIZE) 
+      || (length % AS_VALUE_SIZE))
+    return NULL;
+  
+  while ( (STREAM_READABLE(s) > AS_HEADER_SIZE)
+         && (bytes < length))
+    {
+      int i;
+      
+      /* softly softly, get the header first on its own */
+      segh.type = stream_getc (s);
+      segh.length = stream_getc (s);
+      
+      /* check it.. */
+      if ( ((bytes + ASSEGMENT_SIZE(segh.length)) > length)
+          /* 1771bis 4.3b: seg length contains one or more */
+          || (segh.length == 0) 
+          /* Paranoia in case someone changes type of segment length */
+          || ((sizeof segh.length > 1) && segh.length > AS_SEGMENT_MAX))
+        {
+          if (head)
+            assegment_free_all (head);
+          return NULL;
+        }
+      
+      /* now its safe to trust lengths */
+      seg = assegment_new (segh.type, segh.length);
+      
+      if (head)
+        prev->next = seg;
+      else /* it's the first segment */
+        head = prev = seg;
+      
+      for (i = 0; i < segh.length; i++)
+        seg->as[i] = stream_getw (s);
+      
+      bytes += ASSEGMENT_SIZE(segh.length);
+      
+      prev = seg;
+    }
+ 
+  return assegment_normalise (head);
+}
+
 /* AS path parse function.  pnt is a pointer to byte stream and length
    is length of byte stream.  If there is same AS path in the the AS
    path hash then return it else make new AS path structure. */
 struct aspath *
-aspath_parse (caddr_t pnt, int length)
+aspath_parse (struct stream *s, size_t length)
 {
   struct aspath as;
   struct aspath *find;
 
   /* If length is odd it's malformed AS path. */
-  if (length % 2)
+  if (length % AS_VALUE_SIZE)
     return NULL;
 
-  /* Looking up aspath hash entry. */
-  as.data = pnt;
-  as.length = length;
-
+  as.segments = assegments_parse (s, length);
+  
   /* If already same aspath exist then return it. */
   find = hash_get (ashash, &as, aspath_hash_alloc);
   if (! find)
@@ -367,36 +677,111 @@ aspath_parse (caddr_t pnt, int length)
   return find;
 }
 
-#define min(A,B) ((A) < (B) ? (A) : (B))
-
-#define ASSEGMENT_SIZE(N)  (AS_HEADER_SIZE + ((N) * AS_VALUE_SIZE))
+static inline void
+assegment_data_put (struct stream *s, as_t *as, int num)
+{
+  int i;
+  assert (num <= AS_SEGMENT_MAX);
+  
+  for (i = 0; i < num; i++)
+    stream_putw (s, as[i]);
+}
 
-static struct aspath *
-aspath_aggregate_segment_copy (struct aspath *aspath, struct assegment *seg,
-			       int i)
+static inline size_t
+assegment_header_put (struct stream *s, u_char type, int length)
 {
-  struct assegment *newseg;
+  size_t lenp;
+  assert (length <= AS_SEGMENT_MAX);
+  stream_putc (s, type);
+  lenp = stream_get_endp (s);
+  stream_putc (s, length);
+  return lenp;
+}
 
-  if (! aspath->data)
+/* write aspath data to stream */
+void
+aspath_put (struct stream *s, struct aspath *as)
+{
+  struct assegment *seg = as->segments;
+  
+  if (!seg || seg->length == 0)
+    return;
+  
+  if (seg)
     {
-      aspath->data = XMALLOC (MTYPE_AS_SEG, ASSEGMENT_SIZE (i));
-      newseg = (struct assegment *) aspath->data;
-      aspath->length = ASSEGMENT_SIZE (i);
+      while (seg && (ASSEGMENT_LEN (seg) <= STREAM_WRITEABLE(s)))
+        {
+          int written = 0;
+          size_t lenp;
+          
+          /* Overlength segments have to be split up */
+          while ( (seg->length - written) > AS_SEGMENT_MAX)
+            {
+              assegment_header_put (s, seg->type, AS_SEGMENT_MAX);
+              assegment_data_put (s, seg->as, AS_SEGMENT_MAX);
+              written += AS_SEGMENT_MAX;
+            }
+          
+          /* write the final segment, probably is also the first */
+          lenp = assegment_header_put (s, seg->type, seg->length - written);
+          assegment_data_put (s, (seg->as + written), seg->length - written);
+          
+          /* Sequence-type segments can be 'packed' together
+           * Case of a segment which was overlength and split up
+           * will be missed here, but that doesn't matter.
+           */
+          if (seg->next && ASSEGMENTS_PACKABLE (seg, seg->next))
+            {
+              /* NB: We should never normally get here given we
+               * normalise aspath data when parse them. However, better
+               * safe than sorry. We potentially could call
+               * assegment_normalise here instead, but it's cheaper and
+               * easier to do it on the fly here rather than go through
+               * the segment list twice every time we write out
+               * aspath's.
+               */
+              
+              /* Next segment's data can fit in this one */
+              assegment_data_put (s, seg->next->as, seg->next->length);
+              
+              /* update the length of the segment header */
+	      stream_putc_at (s, lenp, 
+	                      seg->length - written + seg->next->length);
+	      seg = seg->next->next; /* skip to past next */
+	    }
+          else
+            seg = seg->next;
+        }
     }
+}
+
+/* This is for SNMP BGP4PATHATTRASPATHSEGMENT
+ * We have no way to manage the storage, so we use a static stream
+ * wrapper around aspath_put.
+ */
+u_char *
+aspath_snmp_pathseg (struct aspath *as, size_t *varlen)
+{
+#define SNMP_PATHSEG_MAX 1024
+  static struct stream *s = NULL;
+  
+  if (!s)
+    s = stream_new (SNMP_PATHSEG_MAX);
   else
+    stream_reset (s);
+  
+  if (!as)
     {
-      aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
-			       aspath->length + ASSEGMENT_SIZE (i));
-      newseg = (struct assegment *) (aspath->data + aspath->length);
-      aspath->length += ASSEGMENT_SIZE (i);
+      *varlen = 0;
+      return NULL;
     }
-
-  newseg->type = seg->type;
-  newseg->length = i;
-  memcpy (newseg->asval, seg->asval, (i * AS_VALUE_SIZE));
-
-  return aspath;
+  aspath_put (s, as);
+  
+  *varlen = stream_get_endp (s);
+  return stream_pnt(s);
 }
+      
+#define min(A,B) ((A) < (B) ? (A) : (B))
 
 static struct assegment *
 aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset,
@@ -407,41 +792,33 @@ aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset,
   /* If this is first AS set member, create new as-set segment. */
   if (asset == NULL)
     {
-      if (! aspath->data)
-	{
-	  aspath->data = XMALLOC (MTYPE_AS_SEG, ASSEGMENT_SIZE (1));
-	  asset = (struct assegment *) aspath->data;
-	  aspath->length = ASSEGMENT_SIZE (1);
-	}
+      asset = assegment_new (AS_SET, 1);
+      if (! aspath->segments)
+	aspath->segments = asset;
       else
-	{
-	  aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
-				   aspath->length + ASSEGMENT_SIZE (1));
-	  asset = (struct assegment *) (aspath->data + aspath->length);
-	  aspath->length += ASSEGMENT_SIZE (1);
-	}
+        {
+          struct assegment *seg = aspath->segments;
+          while (seg->next)
+            seg = seg->next;
+          seg->next = asset;
+        }
       asset->type = AS_SET;
       asset->length = 1;
-      asset->asval[0] = as;
+      asset->as[0] = as;
     }
   else
     {
-      size_t offset;
-
       /* Check this AS value already exists or not. */
       for (i = 0; i < asset->length; i++)
-	if (asset->asval[i] == as)
+	if (asset->as[i] == as)
 	  return asset;
-
-      offset = (caddr_t) asset - (caddr_t) aspath->data;
-      aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
-			       aspath->length + AS_VALUE_SIZE);
-
-      asset = (struct assegment *) (aspath->data + offset);
-      aspath->length += AS_VALUE_SIZE;
-      asset->asval[asset->length] = as;
+      
       asset->length++;
+      asset->as = XREALLOC (MTYPE_AS_SEG_DATA, asset->as, 
+                            asset->length * AS_VALUE_SIZE);
+      asset->as[asset->length - 1] = as;
     }
+  
 
   return asset;
 }
@@ -453,14 +830,9 @@ aspath_aggregate (struct aspath *as1, struct aspath *as2)
   int i;
   int minlen;
   int match;
-  int match1;
-  int match2;
-  caddr_t cp1;
-  caddr_t cp2;
-  caddr_t end1;
-  caddr_t end2;
-  struct assegment *seg1;
-  struct assegment *seg2;
+  int from;
+  struct assegment *seg1 = as1->segments;
+  struct assegment *seg2 = as2->segments;
   struct aspath *aspath;
   struct assegment *asset;
 
@@ -468,16 +840,9 @@ aspath_aggregate (struct aspath *as1, struct aspath *as2)
   minlen = 0;
   aspath = NULL;
   asset = NULL;
-  cp1 = as1->data;
-  end1 = as1->data + as1->length;
-  cp2 = as2->data;
-  end2 = as2->data + as2->length;
-
-  seg1 = (struct assegment *) cp1;
-  seg2 = (struct assegment *) cp2;
 
   /* First of all check common leading sequence. */
-  while ((cp1 < end1) && (cp2 < end2))
+  while (seg1 && seg2)
     {
       /* Check segment type. */
       if (seg1->type != seg2->type)
@@ -487,55 +852,52 @@ aspath_aggregate (struct aspath *as1, struct aspath *as2)
       minlen = min (seg1->length, seg2->length);
 
       for (match = 0; match < minlen; match++)
-	if (seg1->asval[match] != seg2->asval[match])
+	if (seg1->as[match] != seg2->as[match])
 	  break;
 
       if (match)
 	{
 	  if (! aspath)
-	    aspath = aspath_new();
-	  aspath = aspath_aggregate_segment_copy (aspath, seg1, match);
+	    aspath = aspath_new ();
+	  aspath->segments = assegment_new (seg1->type, 0);
+	  aspath->segments = assegment_append_asns (aspath->segments, 
+	                                            seg1->as, match);
 	}
 
       if (match != minlen || match != seg1->length 
 	  || seg1->length != seg2->length)
 	break;
-
-      cp1 += ((seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
-      cp2 += ((seg2->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
-
-      seg1 = (struct assegment *) cp1;
-      seg2 = (struct assegment *) cp2;
+      
+      seg1 = seg1->next;
+      seg2 = seg2->next;
     }
 
   if (! aspath)
     aspath = aspath_new();
 
   /* Make as-set using rest of all information. */
-  match1 = match;
-  while (cp1 < end1)
+  from = match;
+  while (seg1)
     {
-      seg1 = (struct assegment *) cp1;
-
-      for (i = match1; i < seg1->length; i++)
-	asset = aspath_aggregate_as_set_add (aspath, asset, seg1->asval[i]);
-
-      match1 = 0;
-      cp1 += ((seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
+      for (i = from; i < seg1->length; i++)
+	asset = aspath_aggregate_as_set_add (aspath, asset, seg1->as[i]);
+      
+      from = 0;
+      seg1 = seg1->next;
     }
 
-  match2 = match;
-  while (cp2 < end2)
+  from = match;
+  while (seg2)
     {
-      seg2 = (struct assegment *) cp2;
+      for (i = from; i < seg2->length; i++)
+	asset = aspath_aggregate_as_set_add (aspath, asset, seg2->as[i]);
 
-      for (i = match2; i < seg2->length; i++)
-	asset = aspath_aggregate_as_set_add (aspath, asset, seg2->asval[i]);
-
-      match2 = 0;
-      cp2 += ((seg2->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
+      from = 0;
+      seg2 = seg2->next;
     }
-
+  
+  assegment_normalise (aspath->segments);
+  aspath_str_update (aspath);
   return aspath;
 }
 
@@ -545,18 +907,12 @@ aspath_aggregate (struct aspath *as1, struct aspath *as2)
 int
 aspath_firstas_check (struct aspath *aspath, as_t asno)
 {
-  caddr_t pnt;
-  struct assegment *assegment;
-
-  if (aspath == NULL)
+  if ( (aspath == NULL) || (aspath->segments == NULL) )
     return 0;
-
-  pnt = aspath->data;
-  assegment = (struct assegment *) pnt;
-
-  if (assegment
-      && assegment->type == AS_SEQUENCE
-      && assegment->asval[0] == htons (asno))
+  
+  if (aspath->segments
+      && (aspath->segments->type == AS_SEQUENCE)
+      && (aspath->segments->as[0] == asno ))
     return 1;
 
   return 0;
@@ -566,27 +922,23 @@ aspath_firstas_check (struct aspath *aspath, as_t asno)
 int
 aspath_loop_check (struct aspath *aspath, as_t asno)
 {
-  caddr_t pnt;
-  caddr_t end;
-  struct assegment *assegment;
+  struct assegment *seg;
   int count = 0;
 
-  if (aspath == NULL)
+  if ( (aspath == NULL) || (aspath->segments) )
     return 0;
-
-  pnt = aspath->data;
-  end = aspath->data + aspath->length;
-
-  while (pnt < end)
+  
+  seg = aspath->segments;
+  
+  while (seg)
     {
       int i;
-      assegment = (struct assegment *) pnt;
       
-      for (i = 0; i < assegment->length; i++)
-	if (assegment->asval[i] == htons (asno))
+      for (i = 0; i < seg->length; i++)
+	if (seg->as[i] == asno)
 	  count++;
-
-      pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
+      
+      seg = seg->next;
     }
   return count;
 }
@@ -595,31 +947,24 @@ aspath_loop_check (struct aspath *aspath, as_t asno)
 int
 aspath_private_as_check (struct aspath *aspath)
 {
-  caddr_t pnt;
-  caddr_t end;
-  struct assegment *assegment;
-
-  if (aspath == NULL)
-    return 0;
-
-  if (aspath->length == 0)
+  struct assegment *seg;
+  
+  if ( !(aspath && aspath->segments) )
     return 0;
+    
+  seg = aspath->segments;
 
-  pnt = aspath->data;
-  end = aspath->data + aspath->length;
-
-  while (pnt < end)
+  while (seg)
     {
       int i;
-      assegment = (struct assegment *) pnt;
       
-      for (i = 0; i < assegment->length; i++)
+      for (i = 0; i < seg->length; i++)
 	{
-	  if (ntohs (assegment->asval[i]) < BGP_PRIVATE_AS_MIN
-	      || ntohs (assegment->asval[i]) > BGP_PRIVATE_AS_MAX)
+	  if ( (seg->as[i] < BGP_PRIVATE_AS_MIN)
+	      || (seg->as[i] > BGP_PRIVATE_AS_MAX) )
 	    return 0;
 	}
-      pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
+      seg = seg->next;
     }
   return 1;
 }
@@ -628,19 +973,20 @@ aspath_private_as_check (struct aspath *aspath)
 static struct aspath *
 aspath_merge (struct aspath *as1, struct aspath *as2)
 {
-  caddr_t data;
+  struct assegment *last, *new;
 
   if (! as1 || ! as2)
     return NULL;
 
-  data = XMALLOC (MTYPE_AS_SEG, as1->length + as2->length);
-  memcpy (data, as1->data, as1->length);
-  memcpy (data + as1->length, as2->data, as2->length);
-
-  XFREE (MTYPE_AS_SEG, as2->data);
-  as2->data = data;
-  as2->length += as1->length;
-  as2->count += as1->count;
+  last = new = assegment_dup_all (as1->segments);
+  
+  /* find the last valid segment */
+  while (last && last->next)
+    last = last->next;
+  
+  last->next = as2->segments;
+  as2->segments = new;
+  aspath_str_update (as2);
   return as2;
 }
 
@@ -648,38 +994,30 @@ aspath_merge (struct aspath *as1, struct aspath *as2)
 struct aspath *
 aspath_prepend (struct aspath *as1, struct aspath *as2)
 {
-  caddr_t pnt;
-  caddr_t end;
-  struct assegment *seg1 = NULL;
-  struct assegment *seg2 = NULL;
+  struct assegment *seg1;
+  struct assegment *seg2;
 
   if (! as1 || ! as2)
     return NULL;
-
-  seg2 = (struct assegment *) as2->data;
-
-  /* In case of as2 is empty AS. */
+  
+  seg1 = as1->segments;
+  seg2 = as2->segments;
+  
+  /* If as2 is empty, only need to dupe as1's chain onto as2 */
   if (seg2 == NULL)
     {
-      as2->length = as1->length;
-      as2->data = XMALLOC (MTYPE_AS_SEG, as1->length);
-      as2->count = as1->count;
-      memcpy (as2->data, as1->data, as1->length);
+      as2->segments = assegment_dup_all (as1->segments);
+      aspath_str_update (as2);
       return as2;
     }
-
-  /* assegment points last segment of as1. */
-  pnt = as1->data;
-  end = as1->data + as1->length;
-  while (pnt < end)
-    {
-      seg1 = (struct assegment *) pnt;
-      pnt += (seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
-    }
-
-  /* In case of as1 is empty AS. */
+  
+  /* If as1 is empty AS, no prepending to do. */
   if (seg1 == NULL)
     return as2;
+  
+  /* find the tail as1's segment chain. */
+  while (seg1 && seg1->next)
+    seg1 = seg1->next;
 
   /* Compare last segment type of as1 and first segment type of as2. */
   if (seg1->type != seg2->type)
@@ -687,22 +1025,37 @@ aspath_prepend (struct aspath *as1, struct aspath *as2)
 
   if (seg1->type == AS_SEQUENCE)
     {
-      caddr_t newdata;
-      struct assegment *seg = NULL;
+      /* We have two chains of segments, as1->segments and seg2, 
+       * and we have to attach them together, merging the attaching
+       * segments together into one.
+       * 
+       * 1. dupe as1->segments onto head of as2
+       * 2. merge seg2's asns onto last segment of this new chain
+       * 3. attach chain after seg2
+       */
       
-      newdata = XMALLOC (MTYPE_AS_SEG, 
-			 as1->length + as2->length - AS_HEADER_SIZE);
-      memcpy (newdata, as1->data, as1->length);
-      seg = (struct assegment *) (newdata + ((caddr_t)seg1 - as1->data));
-      seg->length += seg2->length;
-      memcpy (newdata + as1->length, as2->data + AS_HEADER_SIZE,
-	      as2->length - AS_HEADER_SIZE);
-
-      XFREE (MTYPE_AS_SEG, as2->data);
-      as2->data = newdata;
-      as2->length += (as1->length - AS_HEADER_SIZE);
-      as2->count += as1->count;
-
+      /* dupe as1 onto as2's head */
+      seg1 = as2->segments = assegment_dup_all (as1->segments);
+      
+      /* refind the tail of as2, reusing seg1 */
+      while (seg1 && seg1->next)
+        seg1 = seg1->next;
+      
+      /* merge the old head, seg2, into tail, seg1 */
+      seg1 = assegment_append_asns (seg1, seg2->as, seg2->length);
+      
+      /* bypass the merged seg2, and attach any chain after it to
+       * chain descending from as2's head
+       */
+      seg1->next = seg2->next;
+      
+      /* seg2 is now referenceless and useless*/
+      assegment_free (seg2);
+      
+      /* we've now prepended as1's segment chain to as2, merging
+       * the inbetween AS_SEQUENCE of seg2 in the process 
+       */
+      aspath_str_update (as2);
       return as2;
     }
   else
@@ -710,7 +1063,8 @@ aspath_prepend (struct aspath *as1, struct aspath *as2)
       /* AS_SET merge code is needed at here. */
       return aspath_merge (as1, as2);
     }
-
+  /* XXX: Ermmm, what if as1 has multiple segments?? */
+  
   /* Not reached */
 }
 
@@ -718,67 +1072,34 @@ aspath_prepend (struct aspath *as1, struct aspath *as2)
 static struct aspath *
 aspath_add_one_as (struct aspath *aspath, as_t asno, u_char type)
 {
-  struct assegment *assegment;
-
-  assegment = (struct assegment *) aspath->data;
+  struct assegment *assegment = aspath->segments;
 
   /* In case of empty aspath. */
   if (assegment == NULL || assegment->length == 0)
     {
-      aspath->length = AS_HEADER_SIZE + AS_VALUE_SIZE;
-
+      aspath->segments = assegment_new (type, 1);
+      aspath->segments->as[0] = asno;
+      
       if (assegment)
-	aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, aspath->length);
-      else
-	aspath->data = XMALLOC (MTYPE_AS_SEG, aspath->length);
-
-      assegment = (struct assegment *) aspath->data;
-      assegment->type = type;
-      assegment->length = 1;
-      assegment->asval[0] = htons (asno);
+	assegment_free (assegment);
 
       return aspath;
     }
 
   if (assegment->type == type)
+    aspath->segments = assegment_prepend_asns (aspath->segments, asno, 1);
+  else 
     {
-      caddr_t newdata;
-      struct assegment *newsegment;
-
-      newdata = XMALLOC (MTYPE_AS_SEG, aspath->length + AS_VALUE_SIZE);
-      newsegment = (struct assegment *) newdata;
-
-      newsegment->type = type;
-      newsegment->length = assegment->length + 1;
-      newsegment->asval[0] = htons (asno);
-
-      memcpy (newdata + AS_HEADER_SIZE + AS_VALUE_SIZE,
-	      aspath->data + AS_HEADER_SIZE, 
-	      aspath->length - AS_HEADER_SIZE);
-
-      XFREE (MTYPE_AS_SEG, aspath->data);
-
-      aspath->data = newdata;
-      aspath->length += AS_VALUE_SIZE;
-    } else {
-      caddr_t newdata;
+      /* create new segment
+       * push it onto head of aspath's segment chain 
+       */
       struct assegment *newsegment;
-
-      newdata = XMALLOC (MTYPE_AS_SEG, aspath->length + AS_VALUE_SIZE + AS_HEADER_SIZE);
-      newsegment = (struct assegment *) newdata;
-
-      newsegment->type = type;
-      newsegment->length = 1;
-      newsegment->asval[0] = htons (asno);
-
-      memcpy (newdata + AS_HEADER_SIZE + AS_VALUE_SIZE,
-	      aspath->data,
-	      aspath->length);
-
-      XFREE (MTYPE_AS_SEG, aspath->data);
-
-      aspath->data = newdata;
-      aspath->length += AS_HEADER_SIZE + AS_VALUE_SIZE;
+      
+      newsegment = assegment_new (type, 1);
+      newsegment->as[0] = asno;
+      
+      newsegment->next = assegment;
+      aspath->segments = newsegment;
     }
 
   return aspath;
@@ -796,31 +1117,30 @@ aspath_add_seq (struct aspath *aspath, as_t asno)
 int
 aspath_cmp_left (struct aspath *aspath1, struct aspath *aspath2)
 {
-  struct assegment *seg1;
-  struct assegment *seg2;
-  as_t as1;
-  as_t as2;
+  struct assegment *seg1 = NULL;
+  struct assegment *seg2 = NULL;
 
-  seg1 = (struct assegment *) aspath1->data;
-  seg2 = (struct assegment *) aspath2->data;
+  if (!(aspath1 && aspath2))
+    return 0;
 
-  while (seg1 && seg1->length 
-	 && (seg1->type == AS_CONFED_SEQUENCE || seg1->type == AS_CONFED_SET))
-    seg1 = (struct assegment *) ((caddr_t) seg1 + ASSEGMENT_LEN (seg1));
-  while (seg2 && seg2->length 
-	 && (seg2->type == AS_CONFED_SEQUENCE || seg2->type == AS_CONFED_SET))
-    seg2 = (struct assegment *) ((caddr_t) seg2 + ASSEGMENT_LEN (seg2));
+  seg1 = aspath1->segments;
+  seg2 = aspath2->segments;
 
-  /* Check as1's */
-  if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_SEQUENCE)
-    return 0;
-  as1 = seg1->asval[0];
+  /* find first non-confed segments for each */
+  while (seg1 && ((seg1->type == AS_CONFED_SEQUENCE)
+		  || (seg1->type == AS_CONFED_SET)))
+    seg1 = seg1->next;
 
-  if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_SEQUENCE)
-    return 0;
-  as2 = seg2->asval[0];
+  while (seg2 && ((seg2->type == AS_CONFED_SEQUENCE)
+		  || (seg2->type == AS_CONFED_SET)))
+    seg2 = seg2->next;
 
-  if (as1 == as2)
+  /* Check as1's */
+  if (!(seg1 && seg2
+	&& (seg1->type == AS_SEQUENCE) && (seg2->type == AS_SEQUENCE)))
+    return 0;
+  
+  if (seg1->as[0] == seg2->as[0])
     return 1;
 
   return 0;
@@ -832,70 +1152,49 @@ aspath_cmp_left (struct aspath *aspath1, struct aspath *aspath2)
 int
 aspath_cmp_left_confed (struct aspath *aspath1, struct aspath *aspath2)
 {
-  struct assegment *seg1;
-  struct assegment *seg2;
-
-  as_t as1;
-  as_t as2;
-
-  if (aspath1->count || aspath2->count) 
-    return 0;
-
-  seg1 = (struct assegment *) aspath1->data;
-  seg2 = (struct assegment *) aspath2->data;
-
-  /* Check as1's */
-  if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_CONFED_SEQUENCE)
+  if (! (aspath1 && aspath2) )
     return 0;
-  as1 = seg1->asval[0];
-
-  /* Check as2's */
-  if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_CONFED_SEQUENCE)
+  
+  if ( (aspath1->segments->type != AS_CONFED_SEQUENCE)
+      || (aspath2->segments->type != AS_CONFED_SEQUENCE) )
     return 0;
-  as2 = seg2->asval[0];
-
-  if (as1 == as2)
+  
+  if (aspath1->segments->as[0] == aspath2->segments->as[0])
     return 1;
 
   return 0;
 }
 
-/* Delete first sequential AS_CONFED_SEQUENCE from aspath.  */
+/* Delete all leading AS_CONFED_SEQUENCE/SET segments from aspath.
+ * See RFC3065, 6.1 c1 */
 struct aspath *
 aspath_delete_confed_seq (struct aspath *aspath)
 {
-  int seglen;
-  struct assegment *assegment;
+  struct assegment *seg;
 
-  if (! aspath)
+  if (!(aspath && aspath->segments))
     return aspath;
 
-  assegment = (struct assegment *) aspath->data;
+  seg = aspath->segments;
+  
+  /* "if the first path segment of the AS_PATH is 
+   *  of type AS_CONFED_SEQUENCE,"
+   */
+  if (aspath->segments->type != AS_CONFED_SEQUENCE)
+    return aspath;
 
-  while (assegment)
+  /* "... that segment and any immediately following segments 
+   *  of the type AS_CONFED_SET or AS_CONFED_SEQUENCE are removed 
+   *  from the AS_PATH attribute,"
+   */
+  while (seg && 
+         (seg->type == AS_CONFED_SEQUENCE || seg->type == AS_CONFED_SET))
     {
-      if (assegment->type != AS_CONFED_SEQUENCE)
-	return aspath;
-
-      seglen = ASSEGMENT_LEN (assegment);
-
-      if (seglen == aspath->length)
-	{
-	  XFREE (MTYPE_AS_SEG, aspath->data);
-	  aspath->data = NULL;
-	  aspath->length = 0;
-	}
-      else
-	{
-	  memcpy (aspath->data, aspath->data + seglen,
-		  aspath->length - seglen);
-	  aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
-				   aspath->length - seglen);
-	  aspath->length -= seglen;
-	}
-
-      assegment = (struct assegment *) aspath->data;
+      aspath->segments = seg->next;
+      assegment_free (seg);
+      seg = aspath->segments;
     }
+  aspath_str_update (aspath);
   return aspath;
 }
 
@@ -911,53 +1210,32 @@ aspath_add_confed_seq (struct aspath *aspath, as_t asno)
 static void
 aspath_as_add (struct aspath *as, as_t asno)
 {
-  caddr_t pnt;
-  caddr_t end;
-  struct assegment *assegment;
-
-  /* Increase as->data for new as value. */
-  as->data = XREALLOC (MTYPE_AS_SEG, as->data, as->length + 2);
-  as->length += 2;
-
-  pnt = as->data;
-  end = as->data + as->length;
-  assegment = (struct assegment *) pnt;
+  struct assegment *seg = as->segments;
 
   /* Last segment search procedure. */
-  while (pnt + 2 < end)
-    {
-      assegment = (struct assegment *) pnt;
-
-      /* We add 2 for segment_type and segment_length and segment
-         value assegment->length * 2. */
-      pnt += (AS_HEADER_SIZE + (assegment->length * AS_VALUE_SIZE));
-    }
-
-  assegment->asval[assegment->length] = htons (asno);
-  assegment->length++;
+  while (seg && seg->next)
+    seg = seg->next;
+  
+  if (!seg)
+    return;
+  
+  assegment_append_asns (seg, &asno, 1);
 }
 
 /* Add new as segment to the as path. */
 static void
 aspath_segment_add (struct aspath *as, int type)
 {
-  struct assegment *assegment;
+  struct assegment *seg = as->segments;
+  struct assegment *new = assegment_new (type, 0);
 
-  if (as->data == NULL)
-    {
-      as->data = XMALLOC (MTYPE_AS_SEG, 2);
-      assegment = (struct assegment *) as->data;
-      as->length = 2;
-    }
+  while (seg && seg->next)
+    seg = seg->next;
+  
+  if (seg == NULL)
+    as->segments = new;
   else
-    {
-      as->data = XREALLOC (MTYPE_AS_SEG, as->data, as->length + 2);
-      assegment = (struct assegment *) (as->data + as->length);
-      as->length += 2;
-    }
-
-  assegment->type = type;
-  assegment->length = 0;
+    seg->next = new;
 }
 
 struct aspath *
@@ -977,7 +1255,7 @@ aspath_empty_get (void)
 }
 
 unsigned long
-aspath_count ()
+aspath_count (void)
 {
   return ashash->count;
 }     
@@ -997,8 +1275,10 @@ enum as_token
   as_token_asval,
   as_token_set_start,
   as_token_set_end,
-  as_token_confed_start,
-  as_token_confed_end,
+  as_token_confed_seq_start,
+  as_token_confed_seq_end,
+  as_token_confed_set_start,
+  as_token_confed_set_end,
   as_token_unknown
 };
 
@@ -1008,8 +1288,8 @@ aspath_gettoken (const char *buf, enum as_token *token, u_short *asno)
 {
   const char *p = buf;
 
-  /* Skip space. */
-  while (isspace ((int) *p))
+  /* Skip seperators (space for sequences, ',' for sets). */
+  while (isspace ((int) *p) || *p == ',')
     p++;
 
   /* Check the end of the string and type specify characters
@@ -1030,12 +1310,22 @@ aspath_gettoken (const char *buf, enum as_token *token, u_short *asno)
       return p;
       break;
     case '(':
-      *token = as_token_confed_start;
+      *token = as_token_confed_seq_start;
       p++;
       return p;
       break;
     case ')':
-      *token = as_token_confed_end;
+      *token = as_token_confed_seq_end;
+      p++;
+      return p;
+      break;
+    case '[':
+      *token = as_token_confed_set_start;
+      p++;
+      return p;
+      break;
+    case ']':
+      *token = as_token_confed_set_end;
       p++;
       return p;
       break;
@@ -1100,17 +1390,27 @@ aspath_str2aspath (const char *str)
 	  as_type = AS_SEQUENCE;
 	  needtype = 1;
 	  break;
-	case as_token_confed_start:
+	case as_token_confed_seq_start:
 	  as_type = AS_CONFED_SEQUENCE;
 	  aspath_segment_add (aspath, as_type);
 	  needtype = 0;
 	  break;
-	case as_token_confed_end:
+	case as_token_confed_seq_end:
+	  as_type = AS_SEQUENCE;
+	  needtype = 1;
+	  break;
+	case as_token_confed_set_start:
+	  as_type = AS_CONFED_SET;
+	  aspath_segment_add (aspath, as_type);
+	  needtype = 0;
+	  break;
+	case as_token_confed_set_end:
 	  as_type = AS_SEQUENCE;
 	  needtype = 1;
 	  break;
 	case as_token_unknown:
 	default:
+	  aspath_free (aspath);
 	  return NULL;
 	  break;
 	}
@@ -1126,16 +1426,23 @@ unsigned int
 aspath_key_make (struct aspath *aspath)
 {
   unsigned int key = 0;
-  int length;
-  unsigned short *pnt;
-
-  length = aspath->length / 2;
-  pnt = (unsigned short *) aspath->data;
+  unsigned int i;
+  struct assegment *seg = aspath->segments;
+  struct assegment *prev = NULL;
 
-  while (length)
+  while (seg)
     {
-      key += *pnt++;
-      length--;
+      /* segment types should be part of the hash
+       * otherwise seq(1) and set(1) will hash to same value
+       */
+      if (!(prev && seg->type == AS_SEQUENCE && seg->type == prev->type))
+        key += seg->type;
+      
+      for (i = 0; i < seg->length; i++)
+	key += seg->as[i];
+      
+      prev = seg;
+      seg = seg->next;
     }
 
   return key;
@@ -1143,13 +1450,27 @@ aspath_key_make (struct aspath *aspath)
 
 /* If two aspath have same value then return 1 else return 0 */
 static int
-aspath_cmp (struct aspath *as1, struct aspath *as2)
+aspath_cmp (void *arg1, void *arg2)
 {
-  if (as1->length == as2->length 
-      && !memcmp (as1->data, as2->data, as1->length))
-    return 1;
-  else
-    return 0;
+  struct assegment *seg1 = ((struct aspath *)arg1)->segments;
+  struct assegment *seg2 = ((struct aspath *)arg2)->segments;
+  
+  while (seg1 || seg2)
+    {
+      int i;
+      if ((!seg1 && seg2) || (seg1 && !seg2))
+	return 0;
+      if (seg1->type != seg2->type)
+        return 0;      
+      if (seg1->length != seg2->length)
+        return 0;
+      for (i = 0; i < seg1->length; i++)
+        if (seg1->as[i] != seg2->as[i])
+          return 0;
+      seg1 = seg1->next;
+      seg2 = seg2->next;
+    }
+  return 1;
 }
 
 /* AS path hash initialize. */
@@ -1163,7 +1484,7 @@ aspath_init (void)
 const char *
 aspath_print (struct aspath *as)
 {
-  return as->str;
+  return (as ? as->str : NULL);
 }
 
 /* Printing functions */