Major update

      bgpd/bgp_advertise.c
      bgpd/bgp_advertise.h

        The adj_in and adj_out objects are now put on a list based
        on the peer to whom the route belongs.

	The adj_in and adj_out objects also now point to the bgp_node
	which they are routes for.

        This substantially reduces the work needed to shut down a peer.

      bgpd/bgp_damp.c

        Changes to adj_in and adj_out forced small change to macros
        used in bgp_damp.c to manage its lists.

      bgpd/bgp_debug.c

        Replaced direct access to vty->node by the required vty_get_node().

      bgpd/bgp_dump.c

        Changes to the names of fields in bgp_info structures.

      bgpd/bgp_engine.h

        Modified the debug and trace functions.

      bgpd/bgp_fsm.c

        Make use of sockunion2str() consistent with common usage.

        Improved some documentation.

      bgpd/bgp_main.c

        Use the newly extended qpn_add_hook_function() facility.

      bgpd/bgp_mplsvpn.c

        Changes to the names of fields in bgp_info structures.

      bgpd/bgp_msg_read.c

        Bug fix: correct handling of capability code length.

        Improvement: better casting in calculation of message length.

      bgpd/bgp_msg_write.c

        Bug fix: correct byte ordering of bgp_id in open message.

      bgpd/bgp_network.c

        Bug fix: correct handling of incoming connections.

        Takes advantage of improvements in sockunion.c.

      bgpd/bgp_nexthop.c

        Changes to the names of fields in bgp_info structures.

      bgpd/bgp_open_state.c

        Remove mistaken #include of memtypes.h

      bgpd/bgp_packet.c

        Improvements to handling of withdrawing routes for peers.

      bgpd/bgp_peer.c

        Tidying up the state of peers as they are enabled and disabled.
        Improvements to handling of withdrawing routes for peers.

      bgpd/bgp_peer.h

        Adding list bases for lists of routes originated by the peer.

      bgpd/bgp_peer_index.c

        Bug fix: correct freeing of peer indexes.

      bgpd/bgp_route.c

        Implement lists of bgp_info based in the owning peer.  Adjust
        for name changes to bgp_info fields.

        Reimplemented all the clearing functions to use the lists of
        items that belong to the peer -- rather than searching route
        tables for stuff to withdraw.

        Changed work queue handling for added/changed routes, so
        that queues run through existing items, rather than having
        queues of auxiliary items -- lower memory overhead.

      bgpd/bgp_route.h

        Added fields to bgp_info to allow all bgp_info originated by
        each peer to live on lists based in the peer.  And changed the
        name of existing fields to avoid confusion.

      bgpd/bgp_routemap.c

        Removing redundant code and fixing a memory leak.

      bgpd/bgp_table.h

        Based work queue for added/changed routes directly in the
        table, rather than having auxiliary structures.

      bgpd/bgp_vty.c

        Use vty_get_node() and vty_set_node() rather than direct
        access to the vty field.

      bgpd/bgpd.c

        Implement changes to route clearing.

      bgpd/bgpd.h

        Changes to work queue handling.

      lib/buffer.c

        Changes to allow embedded buffer structures.

      lib/buffer.h

        Moved struct buffer here so that could have embedded buffer
        structurs.

      lib/command.c

        Substantial tidy up and document exercise.

        Restructured the top level command processing and finding
        of descriptions and command completion.

        Removal of unpleasant messing around with the insides of
        vector structures.

        Movement of some command actions to vty.c.

        Uses uty.h to pick up the "private" functions from vty.c
        et al.

      lib/command.h

        Moved the "node" values to node_type.h, so that can use an
        enum node_type in places where cannot include command.h.

      lib/command_queue.c

        Updated to cope with the called command changing the node
        value.

        Improved handling of revoked commands, so the the command
        line handler does not get stuck waiting for a command to
        complete which has been revoked !

      lib/command_queue.h

        Improved message format.

      lib/if.c

        Use vty_set_node().

      lib/keychain.c

        Use vty_set_node().

  new lib/keystroke.c
  new lib/keystroke.h

        New code to implement a keystroke FIFO.

        This moves some complexity out of the command handler.

        The handling of mixtures of escapes and Telnet IACs is
        tightened up.

        It would be possible to extend this to, say, UTF-8.

        Regularises the "stealing" of keystrokes for the "--more--"
        output handling... which was a bit hit and miss.

  new lib/list_util.c
  new lib/list_util.h

        New code to implement various forms of linked list,
        where the list pointers are embedded in structures.

      lib/log.c

        Changed the handling of log messages, so that all types
        of log output (except syslog) use the same message buffer
        scheme, and the message is constructed once and once
        only.

        Changes to the handling of VTY_LOCK() etc.

        Uses uty.h to pick up the "private" functions from vty.c
	et al.

      lib/log.h

        Changes to the buffering of log messages.

  new lib/mem_tracker.c

        New code to track memory allocation/deallocation, for
        debug purposes.

      lib/memory.c
      lib/memory.h

        Updated to allow the use of the mem_tracker.

      lib/memtypes.awk

        Made the memtypes into a named enum MTYPE.

      lib/memtypes.c

        Various new memory types.

      lib/mqueue.c
      lib/mqueue.h

        Add mqueue_finish function for close-down.

      lib/network.c
      lib/network.h

        Added non-blocking read_nb() and write_nb().

  new lib/node_type.h

        As above.

      lib/plist.c

        Remove vty_puts() which wasn't a good idea.

      lib/qlib_init.c

        Added qps_init() to first stage and mqueue_finish to
        finish.

      lib/qpnexus.c
      lib/qpnexus.h

        More flexible hooks for in_thread_init and in_thread_final.

      lib/qpselect.c
      lib/qpselect.h

        Added qps_start_up() to build the required maps once and
        for all.

        Added qdebug to control the debug checks and validation.

        Improved validation and test functions.

  new lib/qstring.c
  new lib/qstring.h

        New code for limited flexible string handling.

      lib/qtimers.c

        Added qdebug to control the debug checks and validation.

      lib/routemap.c

        Use vty_set_node().

      lib/sockunion.c
      lib/sockunion.h

        Tidied up and regularised the handling of sin_len and
        sin6_len.

        Created common function for setting port into socket.

        Created common function for initialisation/allocation of
        new sockunion.

        Reduced various functions by using common sub-functions.
        Rationalised some code.

        Added sockunion_listen() and sockunion_new_sockaddr().
        Renamed sockunion_new() to sockunion_new_prefix().

        Improved some logging messages.

        Added documentation.

  new lib/uty.h

        Functions etc. used only by vty/command/log/vty_io and
        vty_cli.

      lib/vector.c
      lib/vector.h

        Added vector_t type.

        Removed VECTOR_INDEX, vector_only_wrapper_free() and
        vector_only_index_free() -- following improvement of
        code in command.c.

        Added vector_set_min_length(), vector_set_new_min_length()
        and vector_length() functions.

  new lib/vio_fifo.c
  new lib/vio_fifo.h

        New code to manage simple FIFO of indefinite length.

      lib/vty.c
      lib/vty.h

        Reworked.  Broken into vty.c, vty_io.c and vty_cli.c.

  new lib/vty_cli.c
  new lib/vty_cli.h

        CLI handling parts of the vty family.

  new lib/vty_io.c
  new lib/vty_io.h

        I/O parts of the vty family.

      lib/workqueue.h

        Introduced tyedefs for the various call-back entries.

  new tests/test-list_util.c

        Tests for the list-util stuff.

      vtysh/vtysh.c

        Small change to interface for cmd_execute_command()

1 files changed, 729 insertions, 0 deletions

diff --git a/lib/list_util.h b/lib/list_util.h
new file mode 100644
index 00000000..b658c7ce
--- /dev/null
+++ b/lib/list_util.h
@@ -0,0 +1,729 @@
+/* List Utilities -- header
+ * Copyright (C) 2009 Chris Hall (GMCH), Highwayman
+ *
+ * This file is part of GNU Zebra.
+ *
+ * GNU Zebra is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2, or (at your option) any
+ * later version.
+ *
+ * GNU Zebra is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Zebra; see the file COPYING.  If not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ * 02111-1307, USA.
+ */
+
+#ifndef _ZEBRA_LIST_UTIL_H
+#define _ZEBRA_LIST_UTIL_H
+
+#include <stddef.h>
+
+/* Macro in case there are particular compiler issues.    */
+#ifndef Inline
+  #define Inline static inline
+#endif
+
+/*------------------------------------------------------------------------------
+ * Note that the following fell foul of "strict-aliasing":
+ *
+ *    #define ssl_del_head(base, next) \
+ *      ssl_del_head_func_i((void**)&(base), _lu_off(base, next))
+ *
+ *    Inline void*
+ *    ssl_del_head_func_i(void** p_base, size_t link_offset)
+ *    {
+ *      void* item = *p_base ;
+ *
+ *      if (item != NULL)
+ *        *p_base = _sl_next(item, link_offset) ;
+ *
+ *      return item ;
+ *    } ;
+ *
+ * the assignment to *p_base is, apparently, unacceptable.  This works
+ * perfectly well as am ordinary function.  Using a GNUC extension it is
+ * possible to avoid the function call... hence the ugly skips.
+ */
+#ifdef __GNUC__
+#define __GNUC__LIST_UTIL
+#endif
+
+/*==============================================================================
+ * These utilities provide for linked lists of items, where the list pointers
+ * are fields in the items.
+ *
+ * This is a little less general that the linklist stuff, but carries less
+ * overhead.
+ *
+ * The items will be structures of some sort, and are described here as being
+ * of type "struct item".  Pointers to those items will be of type
+ * "struct item*".
+ *
+ * Most of these utilities are implemented as macros.
+ *
+ *------------------------------------------------------------------------------
+ * Links and Bases.
+ *
+ * For a singly linked list, the item declaration is straightforward:
+ *
+ *   struct item
+ *   {
+ *     ....
+ *     struct item*  foo_next ;
+ *     ....
+ *   }
+ *
+ * The item can live on more than one list, all that is required is that each
+ * list has its next pointer.
+ *
+ * For double linked lists, the item may be declared:
+ *
+ *   struct item
+ *   {
+ *     ....
+ *     struct list_pair(struct item*) foo_list ;
+ *     ....
+ *   } ;
+ *
+ * A single base is straighforward:
+ *
+ *   struct item* foo_base ;
+ *
+ * and that may be a variable or a structure field.
+ *
+ * A double base may be declared:
+ *
+ *   struct base_pair(struct item*) foo_base ;
+ *
+ * Various ways to construct structures or structure types:
+ *
+ *   typedef struct list_pair(struct foo*) foo_list ;
+ *
+ *   struct foo_list list_pair(struct foo*) ;
+ *
+ *   struct foo_base base_pair(struct foo*) ;
+ */
+
+#define dl_list_pair(ptr_t)  { ptr_t next ; ptr_t prev ; }
+
+#define dl_base_pair(ptr_t)  { ptr_t head ; ptr_t tail ; }
+
+struct dl_void_list_pair list_pair(void*) ;
+struct dl_void_base_pair base_pair(void*) ;
+
+#define _lu_off(obj, field) ((char*)&((obj)->field) - (char*)(obj))
+
+/*==============================================================================
+ * Single Base, Single Link
+ *
+ * To delete entry must chase down list to find it.
+ *
+ * Supports:
+ *
+ *   ssl_init(base)                 -- initialise base
+ *
+ *     An empty list has a NULL base.
+ *
+ *   ssl_push(base, item, next)     -- add at head of list
+ *
+ *     Treat as void function.  The item may *not* be NULL.
+ *
+ *     Undefined if item is already on any list (including this one).
+ *
+ *   ssl_del(base, item, next)      -- delete from list
+ *
+ *     Treat as function returning int.  Does nothing if the item is NULL.
+ *
+ *     Returns: 0 => OK -- removed item from list (OR item == NULL)
+ *             -1 => item not found on list
+ *
+ *   ssl_del_head(base, next)       -- delete head of list
+ *
+ *     Treat as void function.  Does nothing if the list is empty.
+ *
+ *   ssl_pop(&dst, base, next)      -- pop head of list, if any
+ *
+ *     Treat as function returning void*.
+ *
+ *     Returns old head in dst and as return from "function".
+ *
+ *     Returns NULL and sets dst == NULL if list is empty.
+ *
+ *   ssl_head(base)                 -- return head of list
+ *
+ *     Treat as function returning void*.
+ *
+ *   ssl_next(item, next)           -- step to next item, if any
+ *
+ *     Treat as function returning void*.  Returns NULL if item is NULL.
+ *
+ * Note that ssl_del() and ssl_pop() do NOT affect the item->next pointer.
+ *
+ * Where:
+ *
+ *   "base" to be an r-value of type struct item*
+ *
+ *   "item" to be an l-value of type struct item*
+ *
+ *   "dst"  to be an r-value of type struct item*
+ *
+ *   "next" to be the name of a field in struct item, with type struct item*
+ *
+ *------------------------------------------------------------------------------
+ * For example:
+ *
+ *   struct item                       // definition for list items
+ *   {
+ *     ...
+ *     struct item*  bar_next ;
+ *     ...
+ *   } ;
+ *
+ *   static struct item* bar_base ;    // declaration of the list base
+ *
+ *   // create item and add to list (adds at front)
+ *   struct item* q = calloc(1, sizeof(struct item)) ;
+ *   ssl_push(bar_base, q, bar_next) ;
+ *
+ *   // remove item from list
+ *   ssl_del(bar_base, q, bar_next) ;
+ *
+ *   // walk a list
+ *   struct item* t = ssl_head(bar_base) ;
+ *   while (t != NULL)
+ *     {
+ *       ....
+ *       t = ssl_next(t, bar_next) ;
+ *     }
+ *
+ *   // walk and empty out a list -- removing item before processing
+ *   struct item* t ;
+ *   while (ssl_pop(&t, bar_base, bar_next) != NULL)
+ *     {
+ *       ....  // t points to old head of list
+ *     }
+ *
+ *   // walk and empty out a list -- removing after processing
+ *   struct item* t ;
+ *   while ((t = ssl_head(bar_base) != NULL)
+ *     {
+ *       ....
+ *       ssl_del_head(bar_base, bar_next) ;
+ *     }
+ *
+ * And for example:
+ *
+ *   struct parent_item                 // parent structure containing list
+ *   {
+ *      ....
+ *      struct item* bar_base ;
+ *      ....
+ *   }
+ *
+ *   void footle(struct parent_item* parent, struct item* item)
+ *   {
+ *     ....
+ *     ssl_push(parent->bar_base, item, bar_next) ;
+ *     ....
+ *   }
+ */
+
+#define ssl_init(base)                                          \
+  ((base) = NULL)
+
+#define ssl_push(base, item, next)                              \
+  do { confirm(_lu_off(base, next) == _lu_off(item, next)) ;    \
+       (item)->next = (base) ;                                  \
+       (base) = item ;                                          \
+  } while (0)
+
+extern int ssl_del_func(void** p_this, void* obj, size_t link_offset) ;
+
+#define ssl_del(base, item, next)                               \
+  ssl_del_func((void**)&(base), item, _lu_off(base, next))
+
+#define ssl_del_head(base, next)                                \
+  do { if ((base) != NULL)                                      \
+       (base) = (base)->next ;                                  \
+  } while (0)
+
+#define ssl_pop(dst, base, next)                                \
+  ((*(dst) = (base)) != NULL ? ((base) = (base)->next, *(dst)) : NULL)
+
+#define ssl_head(base) (base)
+
+#define ssl_next(item, next)                                    \
+  ((item) != NULL ? (item)->next : NULL)
+
+/*   _sl_p_next(item, off) -- pointer to next pointer at given offset
+ *   _sl_next(item, off)   -- contents of next pointer at given offset
+ */
+
+#define _sl_p_next(item, off)                                   \
+  ( (void**)( (char*)(item) + (off) ) )
+
+#define _sl_next(item, off)                                     \
+  *_sl_p_next(item, off)
+
+/*==============================================================================
+ * Single Base, Double Link
+ *
+ * Can delete entry directly.
+ *
+ * Supports:
+ *
+ *   sdl_init(base)                 -- initialise base
+ *
+ *     An empty list has a NULL base.
+ *
+ *   sdl_push(base, item, list)     -- add at head of list
+ *
+ *     Treat as void function.  The item may *not* be NULL.
+ *
+ *     Undefined if item is already on any list (including this one).
+ *
+ *   sdl_del(base, item, list)      -- delete from list
+ *
+ *     Treat as void function.  Does nothing if the item is NULL.
+ *
+ *     Undefined if item is not on the list.
+ *
+ *   sdl_del_head(base, next)       -- delete head of list
+ *
+ *     Treat as void function.  Does nothing if the list is empty.
+ *
+ *   sdl_pop(&dst, base, next)      -- pop head of list, if any
+ *
+ *     Treat as function returning void*.
+ *
+ *     Returns old head in dst and as return from "function".
+ *
+ *     Returns NULL and sets dst == NULL if list is empty.
+ *
+ *   sdl_head(base)                 -- return head of list
+ *
+ *     Treat as function returning void*.
+ *
+ *   sdl_next(item, next)           -- step to next item, if any
+ *
+ *     Treat as function returning void*.  Returns NULL if the item is NULL.
+ *
+ *   sdl_prev(item, next)           -- step to prev item, if any
+ *
+ *     Treat as function returning void*.  Returns NULL if the item is NULL.
+ *
+ * Note that sdl_del() and sdl_pop() do NOT affect the item->list.next
+ * or item->list.prev pointers.
+ *
+ * Where:
+ *
+ *   "base" to be an r-value of type: struct base_pair(struct item*)*
+ *
+ *          That is... a variable or field which is a pointer to
+ *
+ *   "item" to be an l-value of type struct item*
+ *
+ *   "dst"  to be an r-value of type struct item*
+ *
+ *   "list" to be the name of a field in struct item
+ *          of type: struct list_pair(struct item*)
+ *
+ *------------------------------------------------------------------------------
+ * For example:
+ *
+ *   struct item                       // definition for list items
+ *   {
+ *     ...
+ *     struct list_pair(struct item*)  bar_list ;
+ *     ...
+ *   } ;
+ *
+ *   static struct base_pair(struct item*) bar_base ;
+ *                                    // declaration of the list base
+ *
+ *   // create item and add to list (adds at front)
+ *   struct item* q = calloc(1, sizeof(struct item)) ;
+ *   sdl_push(bar_base, q, bar_list) ;
+ *
+ *   // remove item from list
+ *   sdl_del(bar_base, q, bar_list) ;
+ *
+ *   // walk a list
+ *   struct item* t = sdl_head(bar_base) ;
+ *   while (t != NULL)
+ *     {
+ *       ....
+ *       t = sdl_next(t, bar_list) ;
+ *     }
+ *
+ *   // walk and empty out a list -- removing item before processing
+ *   struct item* t ;
+ *   while (sdl_pop(&t, bar_base, bar_list) != NULL)
+ *     {
+ *       ....  // t points to old head of list
+ *     }
+ *
+ *   // walk and empty out a list -- removing after processing
+ *   struct item* t ;
+ *   while ((t = sdl_head(bar_base) != NULL)
+ *     {
+ *       ....
+ *       sdl_del_head(bar_base, bar_list) ;
+ *     }
+ *
+ * And for example:
+ *
+ *   struct parent_item                 // parent structure containing list
+ *   {
+ *      ....
+ *      struct base_pair(struct item*) bar_base ;
+ *      ....
+ *   }
+ *
+ *   void footle(struct parent_item* parent, struct item* item)
+ *   {
+ *     ....
+ *     sdl_push(parent->bar_base, item, bar_list) ;
+ *     ....
+ *   }
+ */
+
+#define sdl_init(base)                                                  \
+  ((base) = NULL)
+
+#define sdl_push(base, item, list)                                      \
+  do { confirm(_lu_off(base, list.next) == _lu_off(item, list.next)) ;  \
+       confirm(_lu_off(base, list.prev) == _lu_off(item, list.prev)) ;  \
+       (item)->list.next = (base) ;                                     \
+       (item)->list.prev = NULL ;                                       \
+       if ((base) != NULL)                                              \
+         (base)->list.prev = (item) ;                                   \
+       (base) = (item) ;                                                \
+  } while (0)
+
+#define sdl_del(base, item, list)                                       \
+  do { confirm(_lu_off(base, list.next) == _lu_off(item, list.next)) ;  \
+       confirm(_lu_off(base, list.prev) == _lu_off(item, list.prev)) ;  \
+       if ((item) != NULL)                                              \
+         {                                                              \
+           if ((item)->list.next != NULL)                               \
+             (item)->list.next->list.prev = (item)->list.prev ;         \
+           if ((item)->list.prev != NULL)                               \
+             (item)->list.prev->list.next = (item)->list.next ;         \
+           else                                                         \
+             (base) = (item)->list.next ;                               \
+         } ;                                                            \
+  } while (0)
+
+#define sdl_del_head(base, list)                                        \
+  do { if ((base) != NULL)                                              \
+         {                                                              \
+           (base) = (base)->list.next ;                                 \
+           if ((base) != NULL)                                          \
+             (base)->list.prev = NULL ;                                 \
+         }                                                              \
+  } while (0)
+
+#define sdl_pop(dst, base, list)                                        \
+  ((*(dst) = (base)) != NULL                                            \
+    ? ( ((base) = (base)->list.next) != NULL                            \
+      ? ( (base)->list.prev = NULL, *(dst) ) : *(dst) ) : NULL)
+
+#define sdl_head(base) (base)
+
+#define sdl_next(item, list)                                            \
+  ((item) != NULL ? (item)->list.next : NULL)
+
+#define sdl_prev(item, list)                                            \
+  ((item) != NULL ? (item)->list.prev : NULL)
+
+/*   _dl_p_next(obj, off)   -- pointer to next pointer at given offset
+ *   _dl_next(obj, off)     -- contents of next pointer at given offset
+ *   _dl_p_prev(obj, off)   -- pointer to prev pointer at given offset
+ *   _dl_prev(obj, off)     -- contents of prev pointer at given offset
+ */
+#define _dl_p_next(obj, off)                                            \
+  ( (void**)( (char*)(obj) + (off) + 0 ) )
+
+#define _dl_next(obj, off)                                              \
+  *_dl_p_next(obj, off)
+
+#define _dl_p_prev(obj, off)                                            \
+  ( (void**)( (char*)(obj) + (off) _ sizeof(void*) ) )
+
+#define _dl_prev(obj, off)                                              \
+  *_dl_p_next(obj, off)
+
+/*==============================================================================
+ * Double Base, Double Link
+ *
+ * Can delete entry directly.  Can insert and remove at tail.
+ *
+ * Supports:
+ *
+ *   ddl_init(base)                 -- initialise base
+ *
+ *     An empty list has *both* head and tail pointers NULL.
+ *
+ *     NB: confusion will arise if only one of these pointers is NULL.
+ *
+ *   ddl_push(base, item, list)     -- insert at head of list
+ *
+ *     Treat as void function.  The item may *not* be NULL.
+ *
+ *     Undefined if item is already on any list (including this one).
+ *
+ *   ddl_append(base, item, list)   -- insert at tail of list
+ *
+ *     Treat as void function.  The item may *not* be NULL.
+ *
+ *     Undefined if item is already on any list (including this one).
+ *
+ *   ddl_in_after(after, base, item, list)   -- insert after
+ *
+ *     Treat as void function.  The after & item may *not* be NULL.
+ *
+ *     Undefined if item is already on any list (including this one), or if
+ *     after is not on the list.
+ *
+ *   ddl_in_before(before, base, item, list) -- insert before
+ *
+ *     Treat as void function.  The before & item may *not* be NULL.
+ *
+ *     Undefined if item is already on any list (including this one), or if
+ *     before is not on the list.
+ *
+ *   ddl_pop(&dst, base, next)      -- pop head of list, if any
+ *
+ *     Treat as function returning void*.
+ *
+ *     Returns old head in dst and as return from "function".
+ *
+ *     Returns NULL and sets dst == NULL if list is empty.
+ *
+ *   ddl_crop(&dst, base, next)     -- crop tail of list, if any
+ *
+ *     Treat as function returning void*.
+ *
+ *     Returns old head in dst and as return from "function".
+ *
+ *     Returns NULL and sets dst == NULL if list is empty.
+ *
+ *   ddl_del(base, item, list)      -- delete from list
+ *
+ *     Treat as void function.  Does nothing if the item is NULL.
+ *
+ *     Undefined if item is not on the list.
+ *
+ *   ddl_del_head(base, next)       -- delete head of list
+ *
+ *     Treat as void function.  Does nothing if the list is empty.
+ *
+ *   ddl_del_tail(base, next)       -- delete tail of list
+ *
+ *     Treat as void function.  Does nothing if the list is empty.
+ *
+ *   ddl_head(base)                 -- return head of list
+ *
+ *     Treat as function returning void*.
+ *
+ *   ddl_tail(base)                 -- return tail of list
+ *
+ *     Treat as function returning void*.
+ *
+ *   ddl_next(item, next)           -- step to next item, if any
+ *
+ *     Treat as function returning void*.  Returns NULL if the item is NULL.
+ *
+ *   ddl_prev(item, next)           -- step to prev item, if any
+ *
+ *     Treat as function returning void*.  Returns NULL if the item is NULL.
+ *
+ * Note that ddl_del() and ddl_pop() do NOT affect the item->list.next
+ * or item->list.prev pointers.
+ *
+ * Where:
+ *
+ *   "base" to be an r-value of type: struct base_pair(struct item*)*
+ *
+ *          That is... a variable or field which is a pointer to
+ *
+ *   "item" to be an l-value of type struct item*
+ *
+ *   "dst"  to be an r-value of type struct item*
+ *
+ *   "list" to be the name of a field in struct item
+ *          of type: struct list_pair(struct item*)
+ *
+ *
+ *
+ *------------------------------------------------------------------------------
+ * For example:
+ *
+ *   struct item                       // definition for list items
+ *   {
+ *     ...
+ *     struct list_pair(struct item*)  bar_list ;
+ *     ...
+ *   } ;
+ *
+ *   static struct base_pair(struct item*) bar_base ;
+ *                                    // declaration of the list base
+ *
+ *   // create item and add to list (adds at front)
+ *   struct item* q = calloc(1, sizeof(struct item)) ;
+ *   ddl_push(bar_base, q, bar_list) ;
+ *
+ *   // remove item from list
+ *   ddl_del(bar_base, q, bar_list) ;
+ *
+ *   // walk a list
+ *   struct item* t = ddl_head(bar_base) ;
+ *   while (t != NULL)
+ *     {
+ *       ....
+ *       t = ddl_next(t, bar_list) ;
+ *     }
+ *
+ *   // walk and empty out a list -- removing item before processing
+ *   struct item* t ;
+ *   while (ddl_pop(&t, bar_base, bar_list) != NULL)
+ *     {
+ *       ....  // t points to old head of list
+ *     }
+ *
+ *   // walk and empty out a list -- removing after processing
+ *   struct item* t ;
+ *   while ((t = ddl_head(bar_base) != NULL)
+ *     {
+ *       ....
+ *       ddl_del_head(bar_base, bar_list) ;
+ *     }
+ *
+ * And for example:
+ *
+ *   struct parent_item                 // parent structure containing list
+ *   {
+ *      ....
+ *      struct base_pair(struct item*) bar_base ;
+ *      ....
+ *   }
+ *
+ *   void footle(struct parent_item* parent, struct item* item)
+ *   {
+ *     ....
+ *     ddl_push(parent->bar_base, item, bar_list) ;
+ *     ....
+ *   }
+ */
+
+#define ddl_init(base)                                                  \
+  ((base).head = (base).tail = NULL)
+
+#define ddl_push(base, item, list)                                      \
+  do { (item)->list.next = (base).head ;                                \
+       (item)->list.prev = NULL ;                                       \
+       if ((base).head != NULL)                                         \
+         (base).head->list.prev = (item) ;                              \
+       else                                                             \
+         (base).tail = (item) ;                                         \
+       (base).head = (item) ;                                           \
+  } while (0)
+
+#define ddl_append(base, item, list)                                    \
+  do { (item)->list.next = NULL ;                                       \
+       (item)->list.prev = (base).tail ;                                \
+       if ((base).tail != NULL)                                         \
+         (base).tail->list.next = (item) ;                              \
+       else                                                             \
+         (base).head = (item) ;                                         \
+       (base).tail = (item) ;                                           \
+  } while (0)
+
+#define ddl_in_after(after, base, item, list)                           \
+  do { (item)->list.next = (after)->list.next ;                         \
+       (item)->list.prev = (after) ;                                    \
+       if ((after)->list.next != NULL)                                  \
+         (after)->list.next->list.prev = (item) ;                       \
+       else                                                             \
+         (base).tail = (item) ;                                         \
+       (after)->list.next = (item) ;                                    \
+  } while (0)
+
+#define ddl_in_before(before, base, item, list)                         \
+  do { (item)->list.next = (before) ;                                   \
+       (item)->list.prev = (before)->list.prev ;                        \
+       if ((before)->list.prev != NULL)                                 \
+         (before)->list.prev->list.next = (item) ;                      \
+       else                                                             \
+         (base).head = (item) ;                                         \
+       (before)->list.prev = (item) ;                                   \
+  } while (0)
+
+#define ddl_del(base, item, list)                                       \
+  do { if ((item) != NULL)                                              \
+         {                                                              \
+           if ((item)->list.next != NULL)                               \
+             (item)->list.next->list.prev = (item)->list.prev ;         \
+           else                                                         \
+             (base).tail = (item)->list.prev ;                          \
+           if ((item)->list.prev != NULL)                               \
+             (item)->list.prev->list.next = (item)->list.next ;         \
+           else                                                         \
+             (base).head = (item)->list.next ;                          \
+         } ;                                                            \
+  } while (0)
+
+#define ddl_del_head(base, list)                                        \
+  do { if ((base).head != NULL)                                         \
+         {                                                              \
+           (base).head = (base).head->list.next ;                       \
+           if ((base).head != NULL)                                     \
+             (base).head->list.prev = NULL ;                            \
+           else                                                         \
+             (base).tail = NULL ;                                       \
+         }                                                              \
+  } while (0)
+
+#define ddl_del_tail(base, list)                                        \
+  do { if ((base).tail != NULL)                                         \
+         {                                                              \
+           (base).tail = (base).tail->list.prev ;                       \
+           if ((base).tail != NULL)                                     \
+             (base).tail->list.next = NULL ;                            \
+           else                                                         \
+             (base).head = NULL ;                                       \
+         }                                                              \
+  } while (0)
+
+#define ddl_pop(dst, base, list)                                        \
+  ((*(dst) = (base).head) != NULL                                       \
+    ? ( ((base).head = (base).head->list.next) != NULL                  \
+          ? ( (base).head->list.prev = NULL, *(dst) )                   \
+          : ( (base).tail            = NULL, *(dst) ) )                 \
+    : NULL)
+
+#define ddl_crop(dst, base, list)                                       \
+  ((*(dst) = (base).tail) != NULL                                       \
+    ? ( ((base).tail = (base).tail->list.prev) != NULL                  \
+          ? ( (base).tail->list.next = NULL, *(dst) )                   \
+          : ( (base).head            = NULL, *(dst) ) )                 \
+    : NULL)
+
+#define ddl_head(base) ((base).head)
+
+#define ddl_tail(base) ((base).tail)
+
+#define ddl_next(item, list)                                            \
+  ((item) != NULL ? (item)->list.next : NULL)
+
+#define ddl_prev(item, list)                                            \
+  ((item) != NULL ? (item)->list.prev : NULL)
+
+#endif /* _ZEBRA_LIST_UTIL_H */