File: mrtprogrammer.html

package info (click to toggle)
mrt 2.2.2a-6
links: PTS
area: main
in suites: etch, etch-m68k
size: 3,140 kB
ctags: 4,853
sloc: ansic: 56,465; sh: 2,801; perl: 1,065; makefile: 321
file content (1686 lines) | stat: -rw-r--r-- 111,970 bytes
parent folder | download | duplicates (4)
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=windows-1252">
<META NAME="Generator" CONTENT="Microsoft Word 97">
<TITLE>MRT User's Guide Overview</TITLE>
</HEAD>
<BODY LINK="#0000ff" VLINK="#800080" BGCOLOR="#ffffff">

<FONT FACE="Arial" SIZE=7><P ALIGN="CENTER">&nbsp;</P>
<B><P ALIGN="CENTER">&nbsp;</P>
<P ALIGN="CENTER">&nbsp;</P>
<P ALIGN="CENTER">&nbsp;</P>
<P ALIGN="CENTER">MRT Programmer's Guide</P>
</FONT><I><FONT FACE="Arial" SIZE=6><P ALIGN="CENTER">Version 2.0.0 Alpha</P>
</B></FONT><FONT FACE="Arial" SIZE=4><STRONG><P ALIGN="CENTER">(Draft 11/5/99</P>
<P ALIGN="CENTER">&nbsp;</P>
</I></FONT></STRONG><B><FONT FACE="Arial" SIZE=5><P ALIGN="CENTER">&nbsp;</P>
<P ALIGN="CENTER">&nbsp;</P>
</FONT><FONT SIZE=5><P>Table of Contents</P>
</B></FONT><P>Introduction&#9;<A HREF="#_Toc412283878">*</A><DIR>

<P>1. Overview&#9;<A HREF="#_Toc412283879">*</A></P>
<P>2.  MRT Base Library&#9;<A HREF="#_Toc412283880">*</A></P>
<P>3.  Select Library&#9;<A HREF="#_Toc412283881">*</A></P>
<P>4.  Gateways and Prefixes&#9;<A HREF="#_Toc412283882">*</A></P>
<P>5.  Timer Library&#9;<A HREF="#_Toc412283883">*</A></P>
<P>6.  Trace Library&#9;<A HREF="#_Toc412283884">*</A></P>
<P>7.  User Interactive Interface (UII)&#9;<A HREF="#_Toc412283885">*</A></P>
<P>8.  Interface Library&#9;<A HREF="#_Toc412283886">*</A></P>
<P>9.  I/O Library&#9;<A HREF="#_Toc412283887">*</A></P>
<P>10.  linked_list.a Library&#9;<A HREF="#_Toc412283888">*</A></P>
<P>11.  hash.a Library&#9;<A HREF="#_Toc412283889">*</A></P>
<P>12. Packet Formats&#9;<A HREF="#_Toc412283890">*</A></P>
<P>&nbsp;</P></DIR>
</P>
<B><FONT SIZE=5><P><A NAME="_Toc410609076">Copyright (c) 1997, 1998</P>
</B></FONT><FONT FACE="Courier" SIZE=3><P>&nbsp;</P>
<P>&nbsp;</P>
<P>The Regents of the University of Michigan ("The Regents") and Merit Network, Inc.  All rights reserved.<BR>
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:</P>
<P>1.  Redistributions of source code must retain the above <BR>
    copyright notice, this list of conditions and the <BR>
    following disclaimer.</P>
<P>2.  Redistributions in binary form must reproduce the above <BR>
    copyright notice, this list of conditions and the <BR>
    following disclaimer in the documentation and/or other <BR>
    materials provided with the distribution.</P>
<P>3.  All advertising materials mentioning features or use of <BR>
    this software must display the following acknowledgement:</P><DIR>
<DIR>

<P>This product includes software developed by the University of Michigan, Merit Network, Inc., and their contributors.</P></DIR>
</DIR>

<P>4.  Neither the name of the University, Merit Network, nor the<BR>
    names of their contributors may be used to endorse or <BR>
    promote products derived from this software without <BR>
    specific prior written permission.</P>
<P>THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. </P>
</FONT><FONT FACE="Courier New"><P ALIGN="JUSTIFY"></A></P>
</FONT><H2><A NAME="_Toc412283840"><A NAME="_Toc412283878">Introduction</A></A></H2>
<P>This chapter introduces the <I>MRT Programmers Guide</I> and explains how to obtain further information about MRT.</P>
<H3>Document Conventions</H3>
<P>The following document conventions are used in the <I>Programmer's Guide:</P>

<UL>
</I><LI>Commands and keywords are in <B>boldface</B>.</LI>
<LI>User-supplied variables are enclosed in &lt;angle brackets&gt;.</LI>
<LI>Optional elements are shown in [square brackets].</LI>
<LI>Alternative but required keywords are grouped in {braces} and separated by a vertical bar.</LI></UL>

<H3>Related MRT Manuals</H3>
<P>The following documentation is also available for MRT users (see http://www.merit.edu/~mrt/mrt_doc/):</P>

<UL>
<I><LI>Installation Guide </LI>
<LI>Programmer's Manual</LI>
</I><LI>Tutorial (in preparation)</LI></UL>

<P>The MRT web site will also have the most up-to-date documentation and code.</P>
<H3>Getting Help</H3>
<P>For more information about MRT, send mail to mrt-support@merit.edu. </P>
<P>The MRT and IPMA development teams are available to answer questions and provide configuration advice.  We are also very interested in bug reports, feature requests, and general feedback.</P>
<P>A mailing list, mrt-discuss-request@merit.edu is also available for MRT users to share advice and experiences with the toolkit.</P>
<H3>Notes</H3>
<B><P>NOTE:</B> The MRT libraries may undergo significant changes prior to the 2.0 release of MRT. After the 2.0 public release, we expect the library API will remain stable. </P>
<H3>Credits</H3>
<P>MRT was developed by Merit Network, Inc., under National Science Foundation grant NCR-9318902, "Experimentation with Routing Technology to be Used for Inter-Domain Routing in the Internet." The current research is supported by the National Science Foundation (NCR-9710176) and a gift from Intel Corporation. </P>
<P>The design and ideas behind many of the MRT libraries draws heavily on the architecture pioneered in the GateD routing daemon. </P>
<P>The University of Michigan/Merit Network MRT development team includes: Craig Labovitz, Masaki Hirabaru, Farnam Jahanian, Susan Hares and Susan Rebecca Harris. Additional code and architecture ideas were supplied by Marc Unangst and John Scudder. </P>
<P>Francis Dupont developed the initial BGP4+ code. </P>
<P>The public domain Struct C-library of linked list, hash table and memory allocation routines was developed by Jonathan Dekock &lt;dekock@cadence.com&gt;.</P>
<P>David Ward &lt;dward@netstar.com&gt; provided bug fixes and helpful suggestions.</P>
<P>Pedro Roque developed the first port to Linux IPv6, and wrote many of the interface routines to the Linux kernel.</P>
<P>We would also like to thank our other colleagues in Japan, Portugal, the Netherlands, the UK, and the US for their many contributions to the MRT development effort. </P>
<H2><A NAME="_Toc412283841"><A NAME="_Toc412283879">1. Overview</A></A></H2>
<P>The Multi-threaded Routing Toolkit provides researchers and application developers with a powerful collection of routing protocol libraries and services.</P>
<H3>1.1 Libraries</H3>
<P>The MRT libraries fall into two main categories:</P>

<UL>
<LI>Lower-level services and support routines (timer, interface, socket routines, etc.)</LI>
<LI>Protocol modules (BGP, RIPng, routing table support, etc.) </LI></UL>

<H4>Service Libraries</H4>
<P>The lower-level service libraries provide routines common to most routing protocol implementations. For example, most protocols have periodic processes, such as sending out KeepAlive packets or timing out routing table entries. The MRT timer library includes routines for multiplexing the Unix signal timer over multiple protocols. Similarly, most routing implementations have a need for receiving packets and buffering outbound packets. The MRT select library provides routines for handling network I/O. Other libraries, including the trace and UII libraries, provide routines to facilitate logging of trace information and the User Interactive Interface.</P>
<H4>Routing Libraries</H4>
<P>The MRT libraries also include high-level interfaces into routing protocols. These interfaces include access to BGP, RIPng and other protocol communications, as well as access to the kernel's routing table and interface management. For example, initiating a BGP peering session with a remote router can be as simple as linking in the MRT BGP library and calling Add_BGP_Peer (hostname, AS). </P>
<H3>1.2 Modules</H3>
<P>MRT provides an object-oriented, multi-threaded programming environment. Under the MRT architecture, functional entities, such as routing protocols and other application-level services, are modeled as <B>modules</B>, or objects. Each module is associated with its own thread of control. On threads-capable multiprocessor machines, modules run on top of native kernel threads. On operating systems lacking threads support, MRT modules run on top of emulated threads. </P>
<P>Modules maintain control of their own private resources, which may include buffers, file descriptors, and network sockets. Modules provide public methods, or call routines, for accessing the data and services supplied by the module. For example, a BGP module may provide public routines for initiating a peering session, trapping BGP packets, and providing event notification.</P>
<P>Each MRT object maintains a queue of pending events, which we will refer to as tasks. Other objects and services may schedule events by calling one of the object's public methods. For example, the BGP module might call <I>RIP.route_change_notify()</I> to alert the RIP module that some external BGP routes have changed, and RIP should begin announcing these new routes.</P>
<H3></H3>
<B><P ALIGN="CENTER">Figure 1 - MRT Pending Events</P>
</B><H3>1.3 Services</H3>
<P>The MRT architecture also includes specialized threads of control called <B>services. </B>Services generally perform specialized, narrowly focused tasks such as I/O multiplexing or timer notification. These threads only schedule events with other modules and do not maintain event queues, nor conduct any event scheduling or processing of their own. Examples of services include a timer and I/O monitor service.</P>
<P>The current implementation of MRT includes the following modules and services: timer, select, BGP, RIP, RIPng, user-interface, and a main controlling thread. Since most UNIX implementations only associate a single timer per process, the MRT timer thread is used to multiplex the single process timer over multiple threads. Objects like BGP and RIP schedule alarms by calling the timer scheduler method and providing both an interval and an absolute time, and a callback method. The timer thread maintains a sorted queue of time-based events, which associate pending alarms with objects and their callback methods. The timer service also includes mechanisms for one-time alarms and adding jitter to timer intervals.</P>
<P>The select service performs synchronous I/O multiplexing on behalf of MRT modules. Since modules already block while waiting for the scheduling of new events, the objects require another mechanism for learning of pending I/O. The select thread monitors object socket descriptors for pending read, write and exception events. Objects register an interest in socket by calling a select service method. Once the select service detects an I/O event, the service invokes the callback method of an object and stops monitoring the socket. After an object completes processing of a socket, it notifies the select thread to once again begin monitoring.</P>
<P>&nbsp;</P>
<H3><A NAME="mrt"></H3>
<H3>1.4  Getting Started</H3>
<P>A basic MRT program looks like the following:</P><DIR>
<DIR>

<CODE><H3>cc [flag ...] file... [library...] -lmrt </H3>
<H3>&nbsp;</H3>
<H3>#include &lt;mrt.h&gt;</H3>
<H3>main (int argc, char *argv[]) {</H3>
<H3>  init_mrt (NULL);</H3>
<H3>}</H3>
<H3>&nbsp;</H3></DIR>
</DIR>

<P>This program is the bare minimum needed to make use of any MRT services. Of course, this program does not do anything even remotely interesting  yet</P>
<H4>Adding Timers</H4>
<P>Lets suppose that we were writing a new routing protocol, LPF (longest path first). The RFC for LPF specifies that it must send out a KeepAlive packet every 30 seconds. Although we are not sure how to build a LPF KeepAlive packet yet, we can begin by at least constructing the framework for a routine that would send the KeepAlive at the appropriate times. We use the MRT timer routines:</P>
<P>&#9;#include &lt;mrt.h&gt;</P>
<P>void <B>send__lpf_keepalive</B> (void) {</P>
<PRE>&#9;  /* send keep alive when we figure that much out */</PRE>
<P>      }</P>
<P>&nbsp;</P><DIR>
<DIR>

<P>main (argc, arv) {</P>
<P>mtimer_t *keep_alive_timer;</P>
<P>  init_mrt (NULL);</P>
</CODE><FONT FACE="Courier New" SIZE=2><P>  keep_alive_timer = <B>New_Timer</B> (send_lpr_keep_alive, 30, </P>
<P>&quot;LPF Keep Alive Timer&quot;, NULL);</P></DIR>
</DIR>

<P>  </P><DIR>
<DIR>

<P>   <B>Timer_Turn_ON</B> (keep_alive_timer);</P>
<P>}</P></DIR>
</DIR>

</FONT><P>The above code calls <B>New_Timer</B> to create an MRT timer that calls the keepalive callback routine every 30 seconds. The first argument of New_Timer specifies the stub callback function, send_lpf_keepalive, which we will eventually get around to writing. The second argument to New_Timer is the callback interval, or the time to wait between calls to send_lpf_keepalive. Finally, the fourth argument is a text string used for debugging, and the final argument (NULL) is a pointer to data that will be passed to our send_lpf_keepalive routine. After creating a timer, we turn it on by a call to Timer_Turn_ON to begin the initial 30-second interval.</P>
<H4>&nbsp;</H4>
<H4>Dealing with I/O</H4>
<P>Now that we know how to send keepalives, we turn our attention to how we can receive them. MRT provides a select library to facilitate the multiplexing of I/O.  The select library is really a wrapper around the standard UNIX select system call.</P><DIR>
<DIR>

<CODE><P>void recv_lpf_packet (void) {</P>
<P>&#9;<I>/* process lpf packet */</P>
<P>&#9;</I><B>select_enable_fd</B> (lpf_fd);</P>
<P>}</P>
<P>&nbsp;</P>
<P>main (argc, argv) {</P>
<P>&#9;int lpf_fd;</P>
<P>&nbsp;</P>
<P>fd = create_lpf_socket ();</P>
<P>&nbsp;</P>
<B><P>select_add_fd </B>(lpf_fd, SELECT_READ, recv_lpf_packet, NULL);<B> </P>
<P>&nbsp;</P>
</B><I><P>/* start our main program loop */</P>
</I><P>main_loop ();</P></DIR>
</DIR>

<P>}</P>
<P>&nbsp;</P>
<P>Assuming the socket was created and initialized in the user routine create_lpf_socket, we can tell MRT to call recv_lpf_packet each time there is new data to read on the lpf socket.  We add the lpf socket by calling select_add_fd.  We need to call select_enable_fd after processing the packet in recv_lpf_packet to notify MRT that we have read the data. By default, MRT will ignore a socket after receiving data on the socket (and invoking the callback routine) until the program re-asserts an interest in the socket by calling select_enable_fd.</P>
<P>&nbsp;</P>
<H3>Going Multi-threaded</H3>
<P>Until now, our programs have used a single module with an associated thread of control. If we have multiple protocols, say OSPF running in combination with LPF, we will probably want to design LPF as a separate module with its own thread of control. We begin by creating a <B>schedule</B> for LPF. Schedules are the basic building block of modules in MRT. All communication between protocols and modules or services occurs by scheduling, or adding events, to a module's schedule queue.</P>
<P>A call to New_Schedule creates a new schedule queue structure. This schedule structure is used by other modules to queue events .</P><DIR>
<DIR>

<P>#include &lt;mrt.h&gt;</P>
<P>schedule_t *lpf_schedule;</P>
<P>&nbsp;</P>
<P>void lpf_thread () {</P>
<P>   /* we are now a module !*/</P>
<P>&nbsp;</P>
<P>   /* Wait around for things to happen (like packets</P>
<P>    * arriving and timers firing</P>
<P>    */</P>
<P>    <B>schedule_wait_for_event</B> (lpf_schedule); </P>
<P>}</P>
<P>&nbsp;</P></DIR>
</DIR>

<P>void <B>send_lpf_keepalive</B> (void) {</P>
<P>   /* we are a method called by a different module. Since we</P><DIR>
<DIR>

<P>    * don't have access to any of LPF's resources, we need</P>
<P>    * to schedule the sending of a lpf packet with the LPF</P>
<P>    * module.</P></DIR>
</DIR>

<P>&#9;    */</P><DIR>
<DIR>

<B><P>schedule_event</B> (lpf_schedule, _send_lpf_schedule, NULL); </P><DIR>
<DIR>

<PRE>return;</PRE></DIR>
</DIR>
</DIR>
</DIR>

<P>      }</P>
<P>&nbsp;</P>
<P>&nbsp;</P><DIR>
<DIR>

<P>main () {</P>
<P>&nbsp;</P>
<P>lpf_schedule = <B>New_Schedule</B> ("LPF Schedule", NULL);</P>
<P> &#9;<B>mrt_thread_create</B> ("LPF Thread", lpf_schedule, lpf_thread, NULL);</P>
<P>&nbsp;</P></DIR>
</DIR>

<P>&#9;&#9;/* main loop */</P><DIR>
<DIR>

<P>}</P>
<P>&nbsp;</P>
<P>&nbsp;</P></DIR>
</DIR>

<P>In <FONT FACE="Courier" SIZE=3>main</FONT>, we first create a schedule structure by calling <B>New_Schedule</B>. We provide New_Schedule with a string used for debugging, "LPF Schedule." We then create a new MRT thread/module by calling <B>mrt_thread_create</B>. This routine creates a new thread of control and begins running the thread with the specified function -- lpf_thread in the above example.</P>
<P>Once MRT creates a thread of control, and begins execution of lpf_thread, the lpf module calls schedule_wait_for_event to wait for other modules and services to schedule events.</P>
</CODE><H2><A NAME="_Toc412283842"><A NAME="_Toc412283880">2.  MRT Base Library</A></A></H2>
<P>The MRT base library provides basic routines for initializing MRT services and managing modules and threads of control.</P>
<H3>Synopsis</H3>
<CODE><P>cc [flag ...] file... [library...] -lmrt </P>
<P>#include &lt;mrt.h&gt; </P>
<P>&nbsp;</P>
<P>int init_mrt(trace_t* trace); </P>
<P>mrt_thread_t* mrt_thread_create (char *name, schedule_t *schedule, void (*call_fn) (), void *arg); </P>
<P>schedule_t *New_Schedule (char *description, trace_t *trace); </P>
<P>int schedule_event (schedule_t *schedule, void (*call_fn)(), int narg, ...); </P>
<P>int schedule_wait_for_event (schedule_t *schedule); </P>
<P>void Delete_Event (event_t *event) </P>
<P>int clear_schedule (schedule_t *schedule); </P>
<P>int mrt_thread_exit (mrt_thread_t *thread); </P>
<P>&nbsp;</P>
</CODE><H3>Description</H3>
<P>All MRT programs must call init_mrt(). This function initializes memory, bookkeeping functions and lower level library routines. </P>
<P>An MRT module is created by calling mrt_thread_create. This function creates a new thread of control and begins execution of  this thread by calling the function pointed to by the call_fn argument. The procedure mrt_thread_create also takes a name character string used for debugging,  a pointer to a schedule, and a argument which will be passed to call_fn. On thread-capable operating systems, mrt_thread_create is layered on top of pthread_create(1).</P>
<P>new_schedule  returns a pointer to a schedule_t data structure. This structure maintains the queue of pending events for a module.  In most cases, programs will need to maintain the pointer to a schedule as a global variable. Other MRT libraries and routines will need this schedule pointer to access the methods and data of the module owning the schedule.</P>
<P>Once an MRT module, or thread, has been launched from mrt_thread_create, the new module may perform some initialization functions and then usually waits for pending events by calling schedule_wait_for_event. This procedure blocks the thread until another module or service notifies the blocked module that there are new events pending. </P>
<CODE><P>Other modules and services, such as the timer or select service, access another modules data and procedures by calling the modules schedule methods to schedule the processing of new events. schedule_event takes a point to a modules schedule structure, the name of the method to be scheduled, narg number of arguments to be passed, and a variable list of void pointers to the arguments.</P>
<P>After a module has returned from processing an event dispatched from schedule_wait_for_event, the event is removed from the schedule queue, and the module needs to explicitly delete the event before returning.</P>
</CODE><H2><A NAME="_Toc412283843"><A NAME="_Toc412283881">3.  Select Library</A></A></H2>
<P>The select library provides a collection of utilities built on top of the Unix select(1) function call for multiplexing I/O data.</P>
<H3>Synopsis</H3>
<CODE><P>cc [flag ...] file... [library...] -lmrt </P>
<PRE>#include &lt;mrt.h&gt; </PRE>
<P>&nbsp;</P>
<P>int select_disable_fd (int fd); </P>
<P>int select_enable_fd (int fd);</P>
<P>int select_delete_fd (int fd); </P>
<P>int select_add_fd (int fd, int type_mask, void (*call_fn)(), void *arg);<B> </P>
</B></CODE><H3>Description</H3>
<P>After creating a socket, a module can request to receive notification of events (socket ready to read, socket ready t write, exceptions), by calling select_add_fd. The fd argument is the socket, the type_mask is SELECT_READ, SELECT_WRITE, SELECT_EXCEPTION, and the call_fn is the callback routing to call whenever one of the selected events occurs.</P>
<P>When one of the conditions occurrs, MRT will invoke the callback function. The module can then process socket by reading, writing data or closing the socket. After the module is done with processing, it must call select_enable_fd to reregister and interest in the socket with the MRT select service.</P>
<H2><A NAME="_Toc412283844"><A NAME="_Toc412283882">4.  Gateways and Prefixes</A></A></H2>
<P>MRT provides a number of convenience routines for handling network addresses. A MRT prefix is similar to the Unix sockaddr structure with a number of important differences  a prefix maintains information about the mask, or number of important bit positions in an address, and a prefix can contain either an IPv4 or IPv6 address.</P>
<P>A gateway structure maintains an Autonomous System number (AS) with an associated prefix address.</P>
<H3>Synopsis</H3>
<CODE><P>cc [flag ...] file... [library...] -lmrt </P>
<PRE>#include &lt;mrt.h&gt; </PRE>
<P>&nbsp;</P>
<PRE>gateway_t *New_Gateway (prefix_t *prefix, int AS); </PRE>
<P>char *gateway_toa (char *tmp, gateway_t *gateway); </P>
<P>gateway_t *find_gateway (prefix_t *prefix, int AS, interface_t *interface); </P>
<P>prefix_t *New_Prefix (int family, u_char *dest, int bitlen); </P>
<P>void Delete_Prefix (prefix_t *prefix); </P>
</CODE><FONT FACE="Courier New" SIZE=2><P>prefix_t *ascii_toprefix(char *string, trace_t *trace);</P>
</FONT><CODE><P>char *prefix_toa (prefix_t *prefix); </P>
<P>char *prefix_toa2 (prefix_t *prefix, char *tmp); </P>
<P>u_char *prefix_tochar (prefix_t *prefix); </P>
<P>int prefix_compare (prefix_t *p1, prefix_t *p2); </P>
</CODE><H3>Description</H3>
<P>The function New_Prefix creates a new prefix_t structure. The arguments to New_Prefix are an address family (either AF_INET or AF_INET6), a pointer to a 4 byte (IPv4) or 128 byte (IPv6) address, and the mask or number of significant bits. Like New_Prefix, ascii2prefix creates a new prefix structure. The ascii2prefix structure takes a string of the form &quot;x.x.x.x/x&quot; or the ASCII DNS hostname of a machine.</P>
<P>Several routings convert prefix information to character strings for logging and debugging. Prefix_toa returns a prefix address in the form &quot;x.x.x.x&quot;. Prefix_toax includes &quot;/x&quot; mask information.</P>
<P>prefix_compare compares two prefixes returning 1 if they are the same and 1 if they are different.</P>
<H2><A NAME="_Toc412283845"><A NAME="_Toc412283883">5.  Timer Library</A></A></H2>
<P>SunOS associates a single timer per process. Unfortunately, a single timer is usually insufficient for most routing protocols. Protocols like RIP, BGP and IDRP require multiple timers to schedule events like sending KeepAlive packets, timing out dead peers, and retrying the opening of peering sessions. The MRT timer library provides an easy-to-use programming interface to multiplex Unix alarm signals. </P>
<P>The MRT Timer libary provides easy programming interfaces to create, destrory, set nad manuipulate timers. </P>
<H3>Synopsis</H3>
<PRE>
  cc [flag...] file... -lmrt [library...]
  #include &lt;timer.h&gt;

  void init_timer_master();

  Timer *New_Timer (void (*call_fn)(), int interval, char *name, void *arg);

  void Timer_Turn_ON (Timer *timer);

  void Timer_Turn_OFF (Timer *timer);

  void Timer_Reset_Time (Timer *timer);</PRE>
<H3>Description</H3>
<P>All programs making use of the MRT timer library <U>MUST</U> call <B>init_timer_master()</B> before calling any timer routines. Failure to call init_timer_master will result in unitialized timer structures and lead to segment faults </P>
<P>After initializing the master timer information, individual timers are created by calling <B>New_Timer ()</B>. The <B>New_Timer ()</B> function intitializes a new timer that calls the user-defined <I>call_fn</I> function after the timer fires every <I>interval</I> number of seconds. After the call_fn is executed, the timer automatically resets to expire <I>interval</I> seconds in the future. The <I>name</I> argument is a descriptive string used in logging timer events. New_Timer returns a pointer to a Timer data structure. The <I>call_fn</I> is called with two arguments, a pointer to the Timer data structure that fired, and a pointer to the user-defined data pointer <I>arg</I>. The user-defined call function has the form: </P>
<PRE>
void my_call_fn (Timer *timer, void *my_data);</PRE>
<P>New_Timer returns a NULL pointer upon failure. </P>
<P>All timers are intially created in the OFF state. In this state, the timer is not scheduled, and the call_fn will not execute. To turn a timer ON, you must call the function <B>Timer_Turn_ON ()</B>. </P>
<P>Similarly, if a timer is no longer needed, <B>Timer_Turn_OFF ()</B> will remove <I>timer</I> from the timer queue and prevent the timer from firing in the future. </P>
<P>The <B>Timer_Reset_Time</B> function resets the <I>timer</I> to fire after the timer's original interval number of seconds expires. This function is used by protocols like BGP which need to reset KeepAlive timers after receiving a KeepAlive from a peer. If a <I>timer</I> is OFF, the Timer_Reset_Time call will turn the <I>timer</I> on. <B>Timer_Set_Time</B> changes the interval value of an initialized <I>timer</I>. After calling Timer_Set_Time, <I>timer</I> will fire after every <I>interval</I> seconds. If a <I>timer</I> is OFF, the Timer_Set_Time call will turn the <I>timer</I> on. </P>
<P>Finally, a protocol that no longer has need of any timer may clear all memory associated with timers by calling <B>Destroy_Timer_Master</B>. Most protocols will not make use of this function. Protocols MUST not call other timer library routines after invoking <B>Destroy_Timer_Master</B>. </P>
<H3>Code Examples: </H3>
<PRE>
#include &lt;stdio.h&gt; 
#include &lt;timer.h&gt;

void my_timer_fire1() {  printf("10 I have fired\n"); }
void my_timer_fire2() {  printf("60 I have fired\n"); }


main() {
        mtimer_t *timer1, *timer2;
 
        init_timer();
 
        timer1 = New_Timer (my_timer_fire1, 60, "timer1");
        timer2 = New_Timer (my_timer_fire2, 10, "timer2");
 
        Timer_Turn_ON (timer1);
        Timer_Turn_ON (timer2);
 
        while (1) mrt_alarm();
}</PRE>
<H3>Makefile Example: </H3>
<PRE>
  INCDIR=-I$(HOME)/mrt/include
  LIBDIR=-L$(HOME)/mrt/lib
  LIBS=-lstruct -lutil -ltimer 

  all: my_file

  my_file: my_file.o
      $(CC) -o my_file $(LIBDIR) $(LIBS)

  my_file.0: my_file.c
      $(CC) $(INCDIR) -c my_file.c</PRE>
<PRE></PRE>
<H2> <A NAME="_Toc412283846"><A NAME="_Toc412283884">6.  Trace Library</A></A></H2>
<P>The MRT Trace library provides simple programming interface for programs and protocols to log trace information either to disk, or to the console. </P>
<H3>Synopsis</H3>
<PRE>
  cc [flag...] file... -ltrace [library...]
  #include &lt;trace.h&gt;

  void trace (int severity, Trace_Struct *trace_struct, ...);

  Trace_Struct *New_Trace_Struct (int first, ...);

  int Set_Trace_Struct (Trace_Struct *tmp, int first, ...)</PRE>
<H3>&nbsp;</H3>
<H3>Description </H3>
<P>Protocols making use of the MRT Trace library must first call <B>New_Trace_Struct</B> to allocate memory and initalize the trace information. As argumets, New_Trace_Struct takes a null terminated list of option flag, option value pairs. Possible options, their associated type of argument, and their default value include: </P>
<PRE>
  TR_LOG_FILE&#9;char*&#9;&#9;"/tmp/mrt.log"
  TR_FLAGS&#9;int&#9;&#9;NORM
  TR_APPEND&#9;boolean&#9;&#9;TRUE
  TR_FLOCK&#9;boolean&#9;&#9;TRUE</PRE>
<I><P>TR_LOG_FILE</I> specifies the name of the file to which trace calls will write logging information. If this flag is followed by an argument of "stdout", trace calls will write to standard out. </P>
<P>The <I>TR_FLAGS</I> argument specifies the level, or verbosity, of tracing information that will be generated. Possible arguments include: </P>
<PRE>
  FATAL&#9;&#9;/* fatal error -- die after receiving */
  TRACE&#9;&#9;/* verbose tracing, like keepalives */
  NORM&#9;&#9;/* normal events to trace */

  TR_PARSE&#9;/* trace parsing of config files */
  TR_PACKET&#9;/* trace packet comming and goings */
  TR_STATE&#9;/* trace state changes and events */
  TR_TIMER&#9;/* trace timer changes and events */
  TR_POLICY&#9;/* trace policy changes and events */

  TR_ALL&#9;/* trace everything */</PRE>
<I><P>TR_APPEND</I> specifies whether the trace library should append (argument of TRUE) new tracing information onto the end of an existent file, or overwrite an existent file (argument of FALSE). </P>
<I><P>TR_FLOCK</I> controls whether the trace library uses the flock library (see flock(2)). </P>
<P>The <B>trace</B> function writes logging information of <I>severity</I> to disk. The <I>trace_struct</I> arguments specified as a format string followed by format. </P>
<H3>Code Examples: </H3>
<PRE>

#include &lt;stdio.h
#include &lt;trace.h
#include &lt;version.h


main () {
   Trace_Struct *protocol_trace;

   protocol_trace = New_Trace_Struct (TRACE_LOGFILE, "/tmp/my_logfile", 
                                      TRACE_FLAGS, NORM, 
                                      NULL);
   
   trace (NORM, protocol_trace, "This is a trace message");
   trace (TR_POLICY, protocol_trace, "This will not show up");

   Set_Trace_Struct (protocol_trace, 
                     TRACE_FLAGS, TR_ALL, 
                     TRACE_LOGFILE, "stdout",
                     NULL);

   trace (TR_POLICY, protocol_trace, "This will show up on the console");

   trace (FATAL, protocol_trace, 
&#9;  "Now I will die... (this shows up in syslog)");
}</PRE>
<H2><A NAME="_Toc412283847"><A NAME="_Toc412283885">7.  User Interactive Interface (UII)</A></A></H2>
<P>The User Interactive Interface provides support for creating telnet vtty management and configuration sessions.</P>
<H3>Synopsis</H3>
<PRE>
cc [flag...] file... -lmrt [library...]
#include &lt;timer.h&gt;
</PRE><DIR>
<DIR>

<CODE><P>int uii_add_command (int state, char *string, int *call_fn); </P>
<P>int parse_line (u_char *line, char *format, ...); </P>
<P>set_uii (uii_t *tmp, int first, ...); </P>
<P>int uii_send_data (uii_connection_t *uii, ...); </P>
<P>int uii_destroy_connection (uii_connection_t *connection); </P></DIR>
</DIR>

</CODE><H3>Description </H3>
<P>The function set_uii can be used to configure uii options:</P>
<P>set_uii (UII_PASSWORD, char *password)</P>
<P>set_uii (UII_ACCESS_LIST, int num)</P>
<P>set_uii (UII_PORT, int port_num)</P>
<P>set_uii (UII_PROMT, state, char *prompt)</P>
<P>The function Parse_line is a utility for scanning and parsing a character string.  Like the Unix scanf function, Parse_line takes a format string and variable arguments.  Supported format arguments include:</P>
<P>&#9;%p&#9;IPv4 prefix</P>
<P>&#9;%P&#9;IPv6 prefix</P>
<P>&#9;%M&#9;either IPv4 or IPv6</P>
<P>&#9;%d&#9;int</P>
<P>&#9;%s&#9;string</P>
<P>&#9;%S&#9;to end of line</P>
<P>&#9;%a&#9;IPv4 prefix with no bitmask (no |)</P>
<P>&#9;%A&#9;IPv6 prefix with no bitmask (no |)</P>
<P>&#9;%n&#9;ASCII name</P>
<P>&#9;%D&#9;integer (| ... max list)</P>
<P>&#9;%m&#9;IPv4 prefix</P>
<H2><A NAME="_Toc412283848"><A NAME="_Toc412283886">8.  Interface Library</A></A></H2>
<H3>Synopsis</H3><DIR>
<DIR>

<CODE><P>cc [flag ...] file... [library...] -lnterface -lmrt </P>
<P>#include &lt;mrt.h&gt; </P>
<P>#include &lt;interface.h&gt; </P>
<P>&nbsp;</P>
<P>int init_interfaces (trace_t *ltrace); </P>
<P>interface_t *find_interface (prefix_t *prefix); </P>
<P>interface_t *find_interface_byname (char *name); </P>
<P>LINKED_LIST *find_network (prefix_t *prefix); </P>
<P>interface_t *find_interface_local (prefix_t *prefix); </P>
<P>int local_interface (int family, u_char *cp); </P>
<P>interface_t *interface_iter (interface_iter_t **iter); </P></DIR>
</DIR>

</CODE><H3>Description </H3>
<P>Description goes here.</P>
<P>&nbsp;</P>
<CODE><P> </P>
<P>&nbsp;</P>
<P>&nbsp;</P>
</CODE><H2><A NAME="io"></H2>
<H2><A NAME="_Toc412283849"><A NAME="_Toc412283887">9.  I/O Library</A></A></H2>
<P>Because MRT is structured as a number of separate processes (BGP peers, MRS, etc.), it is necessary to provide a way for these processes to communicate. Solaris provides several different methods for programs to communicate (IPC methods), but the interface to these IPC methods is not standardized, and some amount of support code is invariably necessary to provide services which MRT requires but the Solaris IPC methods do not provide. </P>
<P>The I/O library provides an easy-to-use, standardized abstract interface to IPC. Several different IPC methods (file, stdin/stdout, and System V message queues) are supported. A message-queue key registry is provided, to allow processes to communicate without knowledge of each other's keys. </P>
<H3>Synopsis</H3>
<CODE><P>cc [flag ...] file... [library...] -lio -lstruct -lmrt </P>
<P>#include &lt;mrt.h&gt; #include &lt;io.h&gt; </P>
<P>int io_init(); </P>
<P>int io_set(int key, int val, ...); </P>
<P>int io_write(long tstamp, short type, short subtype, int length, char *value); </P>
<P>MRT_MSG_STRUCT *io_read(void); </P>
</CODE><H3>Description</H3>
<P>All programs using the I/O library must call <CODE>io_init</CODE> and <CODE>io_set</CODE> before any <CODE>io_write</CODE> or <CODE>io_read</CODE> calls are performed. In addition, the key registry server (<CMD>msgserver</CMD>) must be running in order for the <CODE>IO_INMSGQ</CODE> and <CODE>IO_OUTMSGQ</CODE> I/O types to work. </P>
<CODE><P>io_set</CODE> is used to set up the input and output channels for the I/O library. The arguments to <CODE>io_set</CODE> are a sequence of key-value pairs, with the key being an I/O attribute, and the value being attribute-specific. Available keys are specified in <A HREF="file:///C:/WINNT/Profiles/labovit/DESKTOP/io.html#attr_table">table 1</A>. </P>
<P><A NAME="attr_table"></P>
<B><CODE><P>&nbsp;</P>
</CODE><P> </P></B>
<P ALIGN="CENTER"><CENTER><TABLE BORDER CELLSPACING=1 WIDTH=464>
<TR><TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<P ALIGN="CENTER"><B>Attribute </B></TD>
<TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<B><P ALIGN="CENTER">Value </B></TD>
</TR>
<TR><TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<CODE><P>IO_INNONE</CODE> </TD>
<TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<P>  (char *) NULL </TD>
</TR>
<TR><TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<CODE><P>IO_OUTNONE</CODE> </TD>
<TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<P>  (char *) NULL </TD>
</TR>
<TR><TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<CODE><P>IO_OUTFILE</CODE> </TD>
<TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<P>  filename (string) </TD>
</TR>
<TR><TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<CODE><P>IO_OUTAPPEND</CODE> </TD>
<TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<P>  filename (string)</TD>
</TR>
<TR><TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<CODE><P>IO_INFILE</CODE> </TD>
<TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<P>  filename (string)</TD>
</TR>
<TR><TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<CODE><P>IO_INMSGQ</CODE> </TD>
<TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<P>  client-ID (string)</TD>
</TR>
<TR><TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<CODE><P>IO_OUTMSGQ</CODE> </TD>
<TD WIDTH="50%" VALIGN="MIDDLE" HEIGHT=58>
<P>  client-ID (string)</TD>
</TR>
</TABLE>
</CENTER></P>

<B><CODE><P ALIGN="CENTER"></A></P>
<P ALIGN="CENTER">Table 1:  io_set</CODE> Attributes</P>
</B><P ALIGN="CENTER">&nbsp;</P>
<P>After <CODE>io_set</CODE> has been used to configure the I/O channels, <CODE>io_read</CODE> and <CODE>io_write</CODE> can be used to read and write data, respectively. </P>
<H3>Examples</H3>
<P>See the <KBD>src/progams/msgserver/testio.c</KBD> program for an example of a program that does I/O with message queues. </P>
<H3>Bugs</H3>

<UL>
<LI>Each process can only have one input and one output channel. </LI></UL>

<P>&nbsp;</P>
<P><A NAME="timer"></P>
<H2><A NAME="_Toc412283850"><A NAME="_Toc412283888">10.  linked_list.a Library</A></A></H2>
<B><P>Synopsis</P><DIR>

</B><P>The linked_list.a library provides a generic set of operations for maintaining a linked list.  The library is designed to free the user from maintaining the pointers required in a linked list.  This library supports both intrusive and container style doubly linked lists and the lists may be automatically sorted by the insertion procedures.  Functions and macros are also provided for iteration, processing, sorting, and conversion to other types of data structures.</P></DIR>

<B><P>Data and Function Types</P><DIR>

</B><FONT FACE="Courier New" SIZE=1><P>#include &lt;linked_list.h&gt;</P>
<P>LINKED_LIST&#9;-&#9;</FONT><FONT SIZE=2>Structure containing information about a linked list.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>LL_CONTAINER&#9;-&#9;</FONT><FONT SIZE=2>Structure used as a container for a non-intrusive linked list.</P><DIR>
<DIR>
<DIR>
<DIR>
<DIR>
<DIR>

</FONT><FONT FACE="Courier New" SIZE=1><P>LL_POINTERS&#9;-&#9;</FONT><FONT SIZE=2>Structure which may be used to define the intrusive pointers <BR>
in a structure to be held on a linked list.</P></DIR>
</DIR>
</DIR>
</DIR>
</DIR>
</DIR>

</FONT><FONT FACE="Courier New" SIZE=1><P>enum LL_ATTR&#9;-&#9;</FONT><FONT SIZE=2>Enumeration of attributes possible on a linked list.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>enum LL_ERROR&#9;-&#9;</FONT><FONT SIZE=2>Enumeration of errors possible in a linked list operation.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>LL_DestroyProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function which destroys an item of data.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;void ()(DATA_PTR data);</P>
<P>LL_CompareProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function which compares two items of data.<BR>
&#9;&#9;It should return &lt;0 if d1 &lt; d2, 0 if d1 == d2, and &gt;0 if d1 &gt; d2.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;int ()(DATA_PTR d1, DATA_PTR d2);</P>
<P>LL_FindProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function which compares an item of data to a key.<BR>
&#9;&#9;It should return False (0) if data != key, and True (1) if data == key.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;int ()(DATA_PTR data, DATA_PTR key);</P>
<P>LL_ProcessProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function which processes an item of data.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;void ()(DATA_PTR data);</P>
<P>LL_ProcessPlusProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function which processes an item of data relative to a second argument.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;void ()(DATA_PTR data, DATA_PTR arg2);</P>
<P>LL_SortProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function which sorts a linked list.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;void ()(LINKED_LIST *ll, LL_CompareProc compare);</P>
<P>LL_ErrorProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function which handles/reports linked list errors.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;void ()(LINKED_LIST *ll, enum LL_ERROR error_num, char *function);</P></DIR>

</FONT><B><P>Attribute Description</P><DIR>

</B><P>The linked lists maintained by this library are doubly-linked terminating lists, i.e. the library does not support singly-linked lists or circular lists.  Within these bounds a number of attributes may be set to define the operation of the list.  Such attributes include whether the list is intrusive or container style, whether the list is automatically sorted, what information is reported to stdout with the debug library and various functions used to find, compare, and destroy items contained on the list.  The most important difference is whether the list is intrusive or container style as shown in Figure 1.  The full list of attributes and their default values is shown in Table 1.</P></DIR>

<P ALIGN="CENTER"><IMG SRC="Image4.gif" WIDTH=656 HEIGHT=387></P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P ALIGN="CENTER"><CENTER><TABLE BORDER CELLSPACING=2 CELLPADDING=9 WIDTH=570>
<TR><TD WIDTH="37%" VALIGN="TOP" HEIGHT=40><DIR>

<B><P>Attribute</DIR>
</B></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<B><P>Type</DIR>
</B></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<B><P>Default</DIR>
</B></TD>
</TR>
<TR><TD WIDTH="37%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_Intrusive</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>int</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>False</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="37%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_AutoSort</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>int</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>False</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="37%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_ReportChange</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>int</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>False</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="37%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_ReportAccess</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>int</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>False</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="37%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_NextOffset</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>unsigned short</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>0</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="37%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_PrevOffset</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>unsigned short</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>sizeof(DATA_PTR)</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="37%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_FindFunction</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_FindProc</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>NULL</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="37%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_CompareFunction</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_CompareProc</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>NULL</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="37%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_DestroyFunction</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_DestroyProc</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>NULL</DIR>
</FONT></TD>
</TR>
</TABLE>
</CENTER></P>

<B><FONT SIZE=1><P>&nbsp;</P><DIR>
<DIR>
<DIR>
<DIR>
<DIR>
<DIR>

</FONT><P>Table 1: Attribute Definitions and Default Values</P>
</B><P>&nbsp;</P></DIR>
</DIR>
</DIR>
</DIR>
</DIR>

<P>The LL_Intrusive attribute has the synonym attribute LL_NoContainer, and the antonyms LL_NonIntrusive and LL_Container.  Any of there may be used to define the intrusive attribute.</P>
<P>Linked lists with the LL_AutoSorted attribute set will automatically insert new items in sorted order according to the attribute function LL_CompareFunction with each call to either LL_Add() or LL_InsertSorted().</P>
<P>When the debug library is in use (see Debugging for more info.) the attributes LL_ReportChange and LL_ReportAccess determine (on a list by list basis) what information to report to stdout on each function call.</P>
<P>Offset values for the attributes LL_NextOffset and LL_PrevOffset can be calculated by the macro LL_Offset(address, address).  LL_Offset() takes the address of a structure to be stored on a list and the address of the next (prev) pointer in the strucuture and calculates the offset of the pointer.  The order of the addresses is not important, i.e. <FONT FACE="Courier New" SIZE=1>LL_Offset(&amp;my_struct, &amp;my_struct.next)</FONT> is equivalent to <FONT FACE="Courier New" SIZE=1>LL_Offset(&amp;my_struct.next, &amp;my_struct)</FONT>.  For convenience, the attribute LL_PointersOffset may be used to declare the offset of the struct LL_POINTERS within the user structure, this attribute sets both the next and prev offsets to the appropriate values.  NOTE:  If any offset is set, it automatically declares the list to be intrusive, thus the LL_Intrusive attribute does not necessarily need to be set.</P>
<P>Three functions may be installed as attributes on the linked list.  The LL_FindFunction attribute is the function which will automatically be used when a call to LL_Find() or its derivatives is made.  The LL_CompareFunction attribute is the function which will be used to compare two items of data when the list is being sorted or an element is being inserted into an auto-sorted list.  The LL_DestroyFunction attribute is the function to be called to destroy (free) a single element when LL_Remove() or its derivatives is called.</P>
<P>Note:  The Attributes LL_Intrusive and LL_&lt;type&gt;Offset can not be modified if there are already items on the linked list.  The debug library checks for this case, but the optimized library does not and may result in a segment fault or loss of data if these attributes are modified.</P></DIR>

<B><P>Functions and Procedures</P><DIR>

</B><U><P>Creation, Modification, and Destruction</P>
</U><FONT FACE="Courier New" SIZE=1><P>LINKED_LIST*&#9;LL_Create(&lt;argument list&gt;);</P>
<P>void&#9;LL_Destroy(LINKED_LIST *ll);</P>
<P>void&#9;LL_SetAttribute(LINKED_LIST *ll, enum LL_ATTR attr, type value);</P>
<P>void&#9;LL_GetAttribute(LINKED_LIST *ll, enum LL_ATTR attr, type* value);</P>
</FONT><U><P>Data Entry and Removal</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR&#9;LL_Append(LINKED_LIST *ll, DATA_PTR data);</P>
<P>DATA_PTR&#9;LL_Prepend(LINKED_LIST *ll, DATA_PTR data);</P>
<P>DATA_PTR&#9;LL_InsertSorted(LINKED_LIST *ll, DATA_PTR data, LL_CompareProc comp);</P>
<P>DATA_PTR&#9;LL_Add(LINKED_LIST *ll, DATA_PTR data);</P>
<P>void&#9;LL_Remove(LINKED_LIST *ll, DATA_PTR data);</P>
</FONT><U><P>Data Retrieval</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR&#9;LL_GetHead(LINKED_LIST *ll);</P>
<P>DATA_PTR&#9;LL_GetTail(LINKED_LIST *ll);</P>
<P>DATA_PTR&#9;LL_GetNext(LINKED_LIST *ll, DATA_PTR current);</P>
<P>DATA_PTR&#9;LL_GetPrev(LINKED_LIST *ll, DATA_PTR current);</P>
<P>DATA_PTR&#9;LL_Find(LINKED_LIST *ll, DATA_PTR key, LL_FindProc comp);</P>
<P>DATA_PTR&#9;LL_FindNext(LINKED_LIST *ll, DATA_PTR key, DATA_PTR cur, LL_FindProc comp);</P>
</FONT><U><P>Sorting</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR&#9;LL_Sort(LINKED_LIST *ll, LL_CompareProc comp);</P>
<P>DATA_PTR&#9;LL_ReSort(LINKED_LIST *ll, DATA_PTR data);</P>
</FONT><U><P>Processing and Iteration</P>
</U><FONT FACE="Courier New" SIZE=1><P>void&#9;LL_Process(LINKED_LIST *ll, LL_ProcessProc process);</P>
<P>void&#9;LL_ProcessPlus(LINKED_LIST *ll, LL_ProcessPlusProc process, DATA_PTR arg2);</P>
<P>MACRO&#9;LL_Iterate(LINKED_LIST *ll, DATA_PTR data)</P>
</FONT><U><P>Error Handling</P>
</U><FONT FACE="Courier New" SIZE=1><P>LL_ErrorProc&#9;Set_LL_Handler(LL_ErrorProc handler);</P>
</FONT><U><P>Notes</P>
</U><FONT FACE="Courier New" SIZE=1><P> <I>&lt;argument list&gt;</I> is a NULL terminated attribute-value pair list.</P>
<P> <I>comp</I> is an optional argument, see descriptions for more information.</P>
<P> <I>MACRO</I> indicates that the procedure is a convenience macro emulating a for-loop.</P>
<P>&nbsp;</P></DIR>

</FONT><H4>Description</H4><DIR>

<P>LL_Create() creates a linked list, initializes its attributes to the default values, sets the attributes defined in the <I>&lt;argument list&gt;</I> and returns a pointer to the linked list.</P>
<P>LL_Destroy() destroys a linked list and all the memory retained by the linked list.  This is done by first calling LL_Clear() to remove each item from the list via a call to LL_Remove().  If the LL_DestroyFunction attribute is set, the destructor function will be called for each item on the list.  Once the list is empty, the memory retained for the linked list structure is freed via a call to Delete().</P>
<P>LL_SetAttribute() sets a single attribute in the linked list.  The argument <I>attr</I> should be one of the linked list attributes, and its <I>value</I> should be of the appropriate type for that attribute.  LL_GetAttribute() retrieves the value of a single attribute from a linked list.  The argument <I>value</I> should be a pointer to an item of the appropriate type for <I>attr</I>.  The value of the attribute will be placed into the item pointed to by <I>value</I>.</P>
<P>LL_Append() appends <I>data</I> onto the tail of the linked list.  LL_Prepend() prepends <I>data</I> onto the head of the linked list.  LL_InsertSorted() inserts <I>data</I> into a sorted list.  The argument <I>comp</I> is an optional argument, if the LL_CompareFunction attribute is set, this function will be used regardless of value of <I>comp</I>, however if the attribute is not set, the argument <I>comp</I> must exist.  LL_Add() adds data onto the linked list by either using LL_InsertSorted() or LL_Append() depending on whether the list is auto-sorted or not.  Each of these functions returns the <I>data</I> added onto the list.  If an error occurs during the addition, they return NULL.</P>
<P>LL_Remove() removes <I>data</I> from a linked list.  LL_Remove() first unlinks <I>data</I> from the list and then if the LL_DestroyFunction attribute is set the destructor function is called to destroy (free) <I>data</I>.</P>
<P>LL_GetHead() returns the item of data on the head of the list.  LL_GetTail() returns the item of data on the tail of the list.  LL_GetNext() returns the next item of data, i.e. <I>data</I>-&gt;next.  LL_GetPrev() returns the previous item of data, i.e. <I>data</I>-&gt;prev.  For LL_GetNext() and LL_GetPrev() <I>data</I> must be either NULL or an item of data on the list.  If <I>data</I> is NULL LL_GetNext() returns the head and LL_GetPrev() returns the tail.  If data is not on the list the function is likely to segment fault (the debug library calls the error handler with the error LL_NoMember and returns NULL).</P>
<P>LL_Find() iterates through the list beginning at the head until an item of data is found matching <I>key</I> according to the function <I>comp</I>.  LL_FindNext() iterates through the list beginning at <I>cur</I>-&gt;next until an item of data is found matching <I>key</I> according to the function <I>comp</I>.  If an item is found it is returned, however if no matching items are found the function returns NULL.  The argument <I>comp</I> is an optional argument, i.e. you may call either LL_Find(list, key) or LL_Find(list, key, comp).  If the LL_FindFunction attribute is set, this function will be used regardless of the value of <I>comp</I>, however if the attribute is not set the argument <I>comp</I> must exist.</P>
<P>LL_Sort() sorts a linked list according to the function <I>comp</I>.   The argument <I>comp</I> is an optional argument, i.e. you may either call LL_Sort(list) or LL_Sort(list, comp).  If the LL_CompareFunction attribute is set, this comparison function is used regardless of the value of <I>comp</I>, however, if the attribute is not set, the argument <I>comp</I> must exist.</P>
<P>LL_ReSort() resorts a single element <I>data</I> after it has changed such that it is longer in sorted order.</P>
<P>LL_Process() iterates through the linked list running the function <I>process</I>(data) on each item of data in the list.  LL_ProcessPlus() iterates through the linked list running the function <I>process</I>(data, <I>arg2</I>) on each item of data in the list.  LL_Iterate() is a convenience macro which expands to a for loop of the type:  </P>
<FONT FACE="Courier New" SIZE=1><P>for(<I>data</I> = LL_GetHead(<I>ll</I>); <I>data</I>; <I>data</I> = LL_GetNext(<I>ll</I>, <I>data</I>))</FONT>.</P>
<P>Note:  It is inadvisable to change the argument <I>data</I>'s next or prev pointers or to delete the argument data from the list within any of these iteration loops as this may cause the loop to terminate early, never terminate, or segment fault.  At the very least, at the end of each loop <I>data</I> must be either NULL or an item of data on the list.  i.e. the following code is permissible:</P><DIR>

<FONT FACE="Courier New" SIZE=1><P>LL_Iterate(ll, data) {</P>
<P>&#9;if (some condition) {</P>
<P>&#9;&#9;DATA_PTR tmp = LL_GetPrev(ll, data);</P>
<P>&#9;&#9;LL_Remove(ll, data);</P>
<P>&#9;&#9;data = tmp;  /* ensure that data points to a real value */</P>
<P>&#9;}</P>
<P>}</P></DIR>

</FONT><P>Set_LL_Handler() installs the function <I>handler</I> as the error handler and returns the previously installed handler.  The default error handler reports the error that occurred to stderr (stdout in the debug library).</P></DIR>

<B><P>Extended Functions and Procedures</P><DIR>

</B><U><P>Modification</P>
</U><FONT FACE="Courier New" SIZE=1><P>void&#9;LL_Clear(LINKED_LIST *ll);</P>
<P>void&#9;LL_SetAttributes(LINKED_LIST *ll, &lt;argument list&gt;);</P>
<P>void&#9;LL_GetAttributes(LINKED_LIST *ll, &lt;argument list&gt;);</P>
</FONT><U><P>Data Insertion</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR&#9;LL_InsertAfter(LINKED_LIST *ll, DATA_PTR data, DATA_PTR relative_to);</P>
<P>DATA_PTR&#9;LL_InsertBefore(LINKED_LIST *ll, DATA_PTR data, DATA_PTR relative_to);</P>
</FONT><U><P>Data Retrieval</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR&#9;LL_FindFromTail(LINKED_LIST *ll, DATA_PTR key, LL_FindProc comp);</P>
<P>DATA_PTR&#9;LL_FindPrev(LINKED_LIST *ll, DATA_PTR key, DATA_PTR cur, LL_FindProc comp);</P>
</FONT><U><P>Sorting</P>
</U><FONT FACE="Courier New" SIZE=1><P>void&#9;LL_BubbleSort(LINKED_LIST *ll, LL_CompareProc compare);</P>
<P>void&#9;LL_QuickSort(LINKED_LIST *ll, LL_CompareProc compare);</P>
<P>void&#9;LL_MergeSort(LINKED_LIST *ll, LL_CompareProc compare);</P>
<P>LL_SortProc&#9;Set_LL_Sorter(LL_SortProc sort_fn)</P>
</FONT><U><P>Iteration</P>
</U><FONT FACE="Courier New" SIZE=1><P>MACRO&#9;LL_IterateFind(LINKED_LIST *ll, DATA_PTR key, DATA_PTR data)</P>
</FONT><U><P>Conversion</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR*&#9;LL_ToArray(LINKED_LIST *ll, DATA_PTR *array, int *nel);</P>
<P>LINKED_LIST*&#9;LL_FromArray(LINKED_LIST *ll, DATA_PTR *array, int nel);</P>
</FONT><U><P>&nbsp;</P>
<P>&nbsp;</P>
<P>Misc.</P>
</U><FONT FACE="Courier New" SIZE=1><P>unsigned&#9;LL_GetCount(LINKED_LIST *ll);</P>
</FONT><U><P>Notes</P>
</U><FONT FACE="Courier New" SIZE=1><P> <I>&lt;argument list&gt;</I> is a NULL terminated attribute-value pair list.</P>
<P> <I>comp</I> is an optional argument, see descriptions for more information.</P>
<P> <I>MACRO</I> indicates that the procedure is a convenience macro emulating a for-loop.</P>
</FONT><B><P>&nbsp;</P></DIR>

</B><H4>Extended Function Description</H4><DIR>

<P>LL_Clear() clears all data from a linked list via calls to the function LL_Remove().  If the attribute LL_DestroyFunction is set the destructor will be called to destroy (free) each item of data on the list.  The LL_Clear() function leaves the list's attributes intact, i.e. intrusive, auto-sorted etc..</P>
<P>LL_SetAttributes() sets a number of attributes on the linked list.  The <I>&lt;argument list&gt;</I> is a NULL terminated list of attribute-value pairs.  Each value argument should match the type designated for its attribute.  LL_GetAttributes() retrieves a number of attributes from the linked list.  The <I>&lt;argument list&gt;</I> is a NULL terminated list of attribute-value pointer pairs.  Each value argument should be a pointer to an item of the appropriate type for the attribute where the function will return the attribute's value.</P>
<P>LL_InsertAfter() inserts <I>data</I> after the item <I>relative_to</I>.  LL_InsertBefore inserts <I>data</I> before the item <I>relative_to</I>.  Both functions return the item of <I>data</I> inserted onto the list.  The argument <I>relative_to</I> must either be NULL or an item of data on the list.  If <I>relative_to</I> is NULL, LL_InsertAfter() inserts the item on the head and LL_InsertBefore() inserts the item on the tail.  If <I>relative_to</I> is not on the list, the error handler will be called with the error LL_NoMember() and the function will return NULL.</P>
<P>LL_FindFromTail() and LL_FindPrev() operate in the same manner as LL_Find() and LL_FindNext() except that they search backwards through the list for a matching item.</P>
<P>LL_BubbleSort(), LL_QuickSort(), and LL_MergeSort() provide three different methods of sorting a linked list.  LL_BubbleSort() sorts the list in place, requiring no additional memory.  LL_QuickSort() and LL_MergeSort() first converts the list to an array, then calls ARRAY_&lt;type&gt;Sort() to perform the actual sorting, and finally converts the result back into the linked list.</P>
<P>LL_IterateFind() is a convenience macro which searches for an item of data matching <I>key</I> using the installed attribute LL_FindFunction as the comparison function.  This macro is restricted by all the  restrictions placed on both the LL_Iterate functions and the LL_Find functions.</P>
<P>LL_ToArray() converts a linked list to an array and returns a pointer of type DATA_PTR* to the first item on the list.  The argument <I>array</I> must be a pointer to an array of sufficient size to hold the data on the list or NULL in which case an array of the appropriate size is allocated.  The argument <I>nel</I> is a pointer used to return the number of elements in the array (it may be NULL in which case the size is not returned).  If an array pointer is given, but the array is of insufficient size, it is likely that the function will segment fault while adding data onto the array.</P>
<P>LL_FromArray() converts an array to a linked list and returns a pointer to the linked list.  The argument <I>array</I> must be a pointer to the first element of an array of pointers and <I>nel</I> must be the number of elements in the array.  The argument <I>ll</I> is a pointer to the linked list to fill.  If <I>ll</I> is NULL a default linked list will be created otherwise all the data on the list <I>ll</I> will be ignored (removed without calling the destructor function), but the attributes will remain intact.</P>
<P>LL_GetCount() returns the number of items currently held in the linked list.  It may be used to allocate sufficient space to hold an array prior to the LL_ToArray() conversion.</P></DIR>

<B><P>Fast Functions and Procedures</P><DIR>

</B><U><P>Intrusive Style Lists</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR&#9;LL_IntrGetHead(LINKED_LIST *ll);</P>
<P>DATA_PTR&#9;LL_IntrGetTail(LINKED_LIST *ll);</P>
<P>DATA_PTR&#9;LL_IntrGetNext(LINKED_LIST *ll, DATA_PTR current);</P>
<P>DATA_PTR&#9;LL_IntrGetPrev(LINKED_LIST *ll, DATA_PTR current);</P>
<P>MACRO&#9;LL_IntrIterate(LINKED_LIST *ll, DATA_PTR data)</P>
</FONT><U><P>Container Style Lists</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR&#9;LL_ContGetHead(LINKED_LIST *ll);</P>
<P>DATA_PTR&#9;LL_ContGetTail(LINKED_LIST *ll);</P>
<P>DATA_PTR&#9;LL_ContGetNext(LINKED_LIST *ll, DATA_PTR current);</P>
<P>DATA_PTR&#9;LL_ContGetPrev(LINKED_LIST *ll, DATA_PTR current);</P>
<P>MACRO&#9;LL_ContIterate(LINKED_LIST *ll, DATA_PTR data)</P>
</FONT><U><P>Note</P>
</U><FONT FACE="Courier New" SIZE=1><P> <I>MACRO</I> indicates that the procedure is a convenience macro emulating a for-loop.</P></DIR>

</FONT><B><P>Fast Function and Macro Description</P><DIR>

</B><P>The fast functions are macro expansions which will in general operate faster then the generic functions.  This is mostly due to a decrease in the size of the macro expansion by approximately half, and the removal of a comparison to determine which style of list to retrieve the data from.  All the restrictions placed on these functions are the same as their generic counterparts plus the LL_Intr&lt;&gt;() functions can only be used on intrusive lists while LL_Cont&lt;&gt;() functions can only be used on container style lists.</P>
<B><P>&nbsp;</P>
<P>&nbsp;</P></DIR>

<P>Override Functions and Procedures</P><DIR>

</B><U><P>Destruction and Removal</P>
</U><FONT FACE="Courier New" SIZE=1><P>void&#9;LL_ClearFn(LINKED_LIST *ll, LL_DestroyProc destroy);</P>
<P>void&#9;LL_DestroyFn(LINKED_LIST *ll, LL_DestroyProc destroy);</P>
<P>void&#9;LL_RemoveFn(LINKED_LIST *ll, LL_DestroyProc destroy);</P>
</FONT><U><P>Data Insertion</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR&#9;LL_InsertSortedFn(LINKED_LIST *ll, DATA_PTR data, LL_CompareProc compare);</P>
</FONT><U><P>Data Retrieval</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR&#9;LL_FindFn(LINKED_LIST *ll, DATA_PTR key, LL_FindProc compare);</P>
<P>DATA_PTR&#9;LL_FindFromTailFn(LINKED_LIST *ll, DATA_PTR key, LL_FindProc compare);</P>
<P>DATA_PTR&#9;LL_FindNextFn(LINKED_LIST *ll, DATA_PTR key, DATA_PTR cur, LL_FindProc compare);</P>
<P>DATA_PTR&#9;LL_FindPrevFn(LINKED_LIST *ll, DATA_PTR key, DATA_PTR cur, LL_FindProc compare);</P>
</FONT><U><P>Sorting</P>
</U><FONT FACE="Courier New" SIZE=1><P>void&#9;LL_SortFn(LINKED_LIST *ll, LL_CompareProc compare);</P>
</FONT><U><P>Iteration</P>
</U><FONT FACE="Courier New" SIZE=1><P>MACRO&#9;LL_IterateFindFn(LINKED_LIST *ll, DATA_PTR key, DATA_PTR data, LL_FindProc compare)</P>
</FONT><U><P>Note</P>
</U><FONT FACE="Courier New" SIZE=1><P> <I>MACRO</I> indicates that the procedure is a convenience macro emulating a for-loop.</P></DIR>

</FONT><B><P>Override Function Description</P><DIR>

</B><P>The override functions provide the same operation as their generic counterparts with the exception that they override the function attributes installed on the linked list.  i.e. The function <I>destroy</I> or <I>compare</I> is used rather then the built in attributes LL_DestroyFunction, LL_FindFunction, and LL_CompareFunction.</P></DIR>

<B><P>Debugging Functions</P><DIR>

</B><FONT FACE="Courier New" SIZE=1><P>int&#9;LL_Verify(LINKED_LIST *ll);</P>
<P>void&#9;LL_Print(LINKED_LIST *ll, LL_ProcessProc print);</P>
<P>LL_CONTAINER*&#9;LL_GetContainer(LINKED_LIST *ll, DATA_PTR data);</P></DIR>

</FONT><B><P>Debugging Function Description</P><DIR>

</B><P>LL_Verify() verifies the linked list by ensuring that (1) the attribute set is valid, (2) that the head and tail are actually the head and tail of the list, (3) for each item verify that data-&gt;next-&gt;prev == data, (4) on an auto-sorted list verify that the list is in sorted order, and (5) that the count is equal to the number of items.</P>
<P>LL_Print() first verifies the list, and then calls the function <I>print</I> on each item of data on the list to print it out.  If <I>print</I> is NULL the default printer function will be used which prints the data's address to stdout.</P>
<P>LL_GetContainer() retrieves data's container on a container style linked list.  </P></DIR>

<B><P>Debugging </P><DIR>

</B><P>Linked list operations can be debugged by defining either LL_DEBUG or STRUCT_DEBUG in any ".c" file prior to the inclusion of the &lt;linked_list.h&gt; header file and by using the list_debug.a library in place of the linked_list.a library at compile time.  Defining LL_DEBUG causes each macro to be expanded to force a function call to the library (rather than the optimized expansion).  The debug library makes additional checks to verify the call's arguments and the correctness of internal variables used.  In addition, the attributes LL_ReportAccess and LL_ReportChange may be set on a list whereby each function call will report the operation performed to stdout.</P></DIR>

<B><P>Notes</P><DIR>

</B><P>This library relies on the array.a library to perform the LL_QuickSort() and LL_MergeSort() operations which also rely on the stack.a library.  This library also relies on the New.a library to allocate and deallocate memory for the linked list structure, the container structures, and the arrays in the conversion operations.</P>
<P>The call New(LINKED_LIST) should not be used to create a linked list as the internal data may not be initialized correctly, thus always use LL_Create() to create a linked list.</P>
<P>It is extremely important that within iterations and processing calls, the current item of data neither has its pointers changed nor is removed.  Doing so may cause unpredictable results.  This also applies to any function installed on the linked list or passed as an argument to one of the functions (with the obvious exception of the destructor function).  </P></DIR>

<B><P>Errors</P><DIR>

</B><P>Any of the functions or procedures in this library may fail as a result of the errors described below.  At the occurrence of such a failure, the linked list error handler is called to report the error to the user.  The global variable <FONT FACE="Courier New" SIZE=1>char *LL_errlist[]</FONT> provides a short description of the error which occurred (see the examples for information on how to use the <FONT FACE="Courier New" SIZE=1>*LL_errlist[]</FONT> variable).</P>
<FONT FACE="Courier New" SIZE=1><P>LL_UnknownErr</FONT>&#9;-&#9;<FONT SIZE=2>Undocumented or unknown error.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>LL_MemoryErr</FONT>&#9;-&#9;<FONT SIZE=2>Unable to allocate the necessary space to complete the operation.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>LL_NoMember</FONT>&#9;-&#9;<FONT SIZE=2>One of the data arguments passed to the function is not a member of the list.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>LL_ListNotEmpty</FONT>&#9;-&#9;<FONT SIZE=2>Attempt to set an attribute defining the list on an non-empty list.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>LL_ListCorrupted</FONT>&#9;-&#9;<FONT SIZE=2>The data in the list structure does not match the information held on the list.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>LL_BadOperation</FONT>&#9;-&#9;<FONT SIZE=2>Attempt to perform an operation on a list which is not of the appropriate type.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>LL_BadAttributes</FONT>&#9;-&#9;<FONT SIZE=2>The set of attributes is invalid.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>LL_BadArgument</FONT>&#9;-&#9;<FONT SIZE=2>One of the arguments passed to the function is invalid.</P></DIR>

</FONT><B><P>Examples</P>
</B><U><FONT FACE="Courier" SIZE=2><P>Example Makefile</P><DIR>

</U></FONT><FONT FACE="Courier New" SIZE=1><P>INCDIR=-I$(HOME)/struct/include</P>
<P>LIBDIR=-L$(HOME)/struct/lib</P>
<P>LIBS=-llinked_list -larray -lstack -lNew</P>
<P>&nbsp;</P>
<P>all: my_file</P>
<P>&nbsp;</P>
<P>my_file: my_file.o</P>
<P>&#9;$(CC) -o my_file myfile.o $(LIBDIR) $(LIBS)</P>
<P>&nbsp;</P>
<P>my_file.o: my_file.c</P>
<P>&#9;$(CC) -O $(INCDIR) -c my_file.c</P>
<P>&nbsp;</P>
</FONT><U><FONT SIZE=2><P>Example Use #1:  Container Style List</P>
</U></FONT><FONT FACE="Courier New" SIZE=1><P>#include &lt;linked_list.h&gt;</P>
<P>#include &lt;New.h&gt;      /* used for New()      */</P>
<P>#include &lt;stdio.h&gt;    /* used for printing   */</P>
<P>#include &lt;string.h&gt;   /* used for comparison */</P>
<P>&nbsp;</P>
<P>typedef struct blee {</P>
<P>&#9;char *name;</P>
<P>&#9;int   val;</P>
<P>} BLEE;</P>
<P>&nbsp;</P>
<P>#define SIZE 10</P>
<P>const struct blee array[SIZE] = { </P>
<P>&#9;{"Joe",    0}, {"Frank",  1}, {"Buddy",  2}, {"Jim",    3}, {"George", 4},</P>
<P>&#9;{"Jane",   5}, {"Jay",    6}, {"Laura",  7}, {"Craig",  8}, {"Bill",   9},</P>
<P>};</P>
<P>&nbsp;</P>
<P>int  Compare (BLEE *b1, BLEE *b2)  { return(strcmp(b1-&gt;name, b2-&gt;name)); }</P>
<P>int  Find    (BLEE *b,  char *key) { return(!strcmp(b-&gt;name, key));      }</P>
<P>void Destroy (BLEE *b)      { Delete(b-&gt;name); Delete(b);                      }</P>
<P>void Print   (BLEE *b)      { printf("0x%.8x = %s, %d\n", b, b-&gt;name, b-&gt;val); }</P>
<P>&nbsp;</P>
<P>main () {</P><DIR>

<P>LINKED_LIST *list1, *list2;</P>
<P>BLEE        *b;</P>
<P>int          i;</P>
<P>&nbsp;</P>
<P>list1 = LL_Create(NULL);                   </P>
<P>list2 = LL_Create(LL_AutoSort, True, LL_CompareFunction, Compare, NULL);</P>
<P>&nbsp;</P>
<P>for (i = 0; i &lt; SIZE; i++) {</P><DIR>

<P>b = New(BLEE);</P>
<P>b-&gt;name = strdup(array[i].name);</P>
<P>b-&gt;val  = array[i].val;</P>
<P>LL_Add(list1, b);   /* Add it onto list 1        */</P>
<P>LL_Add(list2, b);   /* Add it sorted into list 2 */</P></DIR>

<P>}</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>LL_Print(list1, Print);</P>
<P>LL_Print(list2, Print);</P>
<P>&nbsp;</P>
<P>b = LL_Find(list1, "Joe", Find);</P>
<P>LL_Remove(list1, b);      /* Remove Joe from the list */</P>
<P>&nbsp;</P>
<P>LL_SetAttribute(list2, LL_FindFunction, Find);</P>
<P>LL_SetAttribute(list2, LL_DestroyFunction, Destroy);</P>
<P>&nbsp;</P>
<P>b = LL_Find(list2, "Joe");</P>
<P>LL_Remove(list2, b);      /* Remove and Destroy "Joe" */</P>
<P>&nbsp;</P>
<P>LL_Destroy(list1);</P>
<P>LL_Destroy(list2);</P></DIR>

<P>}</P>
</FONT><U><FONT SIZE=2><P>&nbsp;</P>
<P>Example Use #2:  Intrusive Style List</P>
</U></FONT><FONT FACE="Courier New" SIZE=1><P>#include &lt;linked_list.h&gt;</P>
<P>#include &lt;New.h&gt;      /* used for New()      */</P>
<P>#include &lt;stdio.h&gt;    /* used for printing   */</P>
<P>#include &lt;string.h&gt;   /* used for comparison */</P>
<P>&nbsp;</P>
<P>typedef struct blee {</P>
<P>&#9;char *name; int val;</P>
<P>} BLEE;</P>
<P>&nbsp;</P>
<P>typedef struct blee_on_list1 {</P>
<P>&#9;char *name; int val;</P>
<P>&#9;struct blee_on_list1 *next, *prev;</P>
<P>} BLEE_1;</P>
<P>&nbsp;</P>
<P>typedef struct blee_on_list2 {</P>
<P>&#9;char *name; int val;</P>
<P>&#9;LL_POINTERS ptrs;</P>
<P>} BLEE_2;</P>
<P>&nbsp;</P>
<P>#define SIZE 10</P>
<P>const struct blee array[SIZE] = { </P>
<P>&#9;{"Joe",    0}, {"Frank",  1}, {"Buddy",  2}, {"Jim",    3}, {"George", 4},</P>
<P>&#9;{"Jane",   5}, {"Jay",    6}, {"Laura",  7}, {"Craig",  8}, {"Bill",   9},</P>
<P>};</P>
<P>&nbsp;</P>
<P>int  Compare  (BLEE_2 *b1, BLEE_2 *b2)  { return(strcmp(b1-&gt;name, b2-&gt;name)); }</P>
<P>int  Find     (BLEE_2 *b,  char *key)   { return(!strcmp(b-&gt;name, key));      }</P>
<P>void Destroy1 (BLEE_1 *b)  { Delete(b-&gt;name); Delete(b);                      }</P>
<P>void Destroy2 (BLEE_2 *b)  { Delete(b-&gt;name); Delete(b);                      }</P>
<P>void Print1   (BLEE_1 *b)  { printf("0x%.8x = %s, %d\n", b, b-&gt;name, b-&gt;val); }</P>
<P>void MyHandler(LINKED_LIST *ll, enum LL_ERROR error_num, char *fn) {</P><DIR>

<P>printf("Error in list 0x%.8x function %s error %d = \"%s\"\n", </P>
<P>  &#9; ll, fn, error_num, LL_errlist[error_num]);</P></DIR>

<P>}</P>
<P>&nbsp;</P>
<P>main () {</P><DIR>

<P>LINKED_LIST *list1, *list2;</P>
<P>BLEE_1      *b1, tmp1;</P>
<P>BLEE_2      *b2, tmp2;</P>
<P>int          i;</P>
<P>LL_ErrorProc old_handler;</P>
<P>&nbsp;</P>
<P>old_handler = Set_LL_Handler(MyHandler);</P>
<P>list1 = LL_Create(LL_Intrusive, True, LL_NextOffset, LL_Offset(&amp;tmp1, &amp;tmp1.next),</P>
<P>                  LL_PrevOffset, LL_Offset(&amp;tmp1, &amp;tmp1.prev), </P>
<P>                  LL_DestroyFunction, Destroy1, NULL);                 </P>
<P>  </P>
<P>list2 = LL_Create(LL_Intrusive, True, LL_PointersOffset, LL_Offset(&amp;tmp1, &amp;tmp2.ptrs),</P>
<P>                  LL_AutoSort, True, LL_CompareFunction, Compare, </P>
<P>                  LL_DestroyFunction, Destroy2, LL_FindFunction, Find, NULL);</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>for (i = 0; i &lt; SIZE; i++) {</P><DIR>

<P>b1 = New(BLEE_1);                  b2 = New(BLEE_2);</P>
<P>b1-&gt;name = strdup(array[i].name);  b2-&gt;name = strdup(array[i].name);</P>
<P>b1-&gt;val  = array[i].val;           b2.val   = array[i].val;</P>
<P>LL_Add(list1, b1);   /* Add it onto list 1        */</P>
<P>LL_Add(list2, b2);   /* Add it sorted into list 2 */</P></DIR>

<P>}</P>
<P>&nbsp;</P>
<P>b2 = LL_Find(list2, "Joe");</P>
<P>LL_Remove(list2, b2);              /* Remove and Destroy "Joe" */</P>
<P>LL_FindNext(list2, "Laura", b2);   /* ERROR: No such member: b2 (it was removed) */</P>
<P>/*  Note: The optimized library may not catch this error, it may segment fault, or</P>
<P>          it may find "Laura".  The debug library will always catch the error. */</P>
<P>&nbsp;</P>
<P>LL_Iterate(list2, b2) {</P>
<P>&#9;printf("Hi, I am at %s, %d\n", b2-&gt;name, b2-&gt;val);</P>
<P>}</P>
<P>LL_Destroy(list1); LL_Destroy(list2);</P></DIR>

<P>}</P></DIR>

</FONT><H4>Author</H4><DIR>

<P>Jonathan L. DeKock  </P></DIR>

<H2><A NAME="_Toc412283851"><A NAME="_Toc412283889">11.  hash.a Library</A></A></H2>
<B><P>Synopsis</P><DIR>

</B><P>The hash.a library provides a generic set of operations for maintaining a hash table.  The library is designed to free the user from maintaining the hash array and pointers.  Functions and macros are provided to create and destroy hash tables, to convert hash tables to/from other types, and to insert, remove, lookup, iterate through and process items of data on a hash table.</P></DIR>

<B><P>Data and Function Types</P><DIR>

</B><FONT FACE="Courier New" SIZE=1><P>#include &lt;hash.h&gt;</P>
<P>HASH_TABLE&#9;-&#9;</FONT><FONT SIZE=2>Structure containing information about a hash table.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>HASH_CONTAINER&#9;-&#9;</FONT><FONT SIZE=2>Structure used as a container on a container style hash table.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>enum HASH_ATTR&#9;-&#9;</FONT><FONT SIZE=2>Enumeration of attributes possible on a hash table.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>enum HASH_ERROR&#9;-&#9;</FONT><FONT SIZE=2>Enumeration of errors possible in a hash table function.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>HASH_HashProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function to convert a key to a hash index.<BR>
</FONT><FONT FACE="Courier New" SIZE=2>&#9;&#9;</FONT><FONT SIZE=2>It should return a value in the range [0:size-1].<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;unsigned ()(DATA_PTR key, unsigned size);</P>
<P>HASH_LookupProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function to compare two keys.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;</FONT><FONT SIZE=2>It should return False (0) if data_key != key and True (1) if data_key == key.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;int ()(DATA_PTR data_key, DATA_PTR key);</P>
<P>HASH_DestroyProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function which destroys an item of data.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;void ()(DATA_PTR data);</P>
<P>HASH_ProcessProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function which processes an item of data.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;void ()(DATA_PTR data);</P>
<P>HASH_ProcessPlusProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function which processes an item of data relative to a 2nd argument.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;void ()(DATA_PTR data, DATA_PTR arg2);</P>
<P>HASH_ErrorProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function which handles/reports hash table errors.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;void ()(HASH_TABLE *h, enum HASH_ERROR error_num, char *fn);</P>
<P>HASH_PrintProc&#9;-&#9;</FONT><FONT SIZE=2>Pointer to a function which prints out an item of data.<BR>
</FONT><FONT FACE="Courier New" SIZE=1>&#9;&#9;void ()(unsigned index, DATA_PTR data, DATA_PTR key);</P></DIR>

</FONT><B><P>Attribute Description</P><DIR>

</B><P>The hash tables maintained by this library are link-style hash tables which allow more than one item of data to be hashed to a single index.  The linked lists used for this purpose are singly linked lists (not the generic lists provided by the linked_list.a library) and are optimized for fast lookup of data in the list.  A number of attributes may be set to define the operation of the hash table including information about how the structures are to be hashed and functions for hashing, lookup, destruction.  The attributes are defined in Table 1.</P>
<P>&nbsp;</P>
<P>&nbsp;</P></DIR>

<P ALIGN="CENTER"><CENTER><TABLE BORDER CELLSPACING=2 CELLPADDING=9 WIDTH=660>
<TR><TD WIDTH="36%" VALIGN="TOP" HEIGHT=40><DIR>

<B><P>Attribute</DIR>
</B></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<B><P>Type</DIR>
</B></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<B><P>Default</DIR>
</B></TD>
</TR>
<TR><TD WIDTH="36%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_EmbeddedKey</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>int</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>False</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="36%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_Intrusive</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>int</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>False</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="36%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_ReportChange</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>int</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>False</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="36%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_ReportAccess</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>int</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>False</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="36%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_DynamicResize</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>unsigned</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>False (0)</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="36%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_KeyOffset</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>unsigned short</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>0</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="36%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_NextOffset</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>unsigned short</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>sizeof(DATA_PTR)</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="36%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_HashFunction</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_HashProc</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>(See Descr.)</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="36%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_LookupFunction</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_LookupProc</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>(See Descr.)</DIR>
</FONT></TD>
</TR>
<TR><TD WIDTH="36%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_DestroyFunction</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>HASH_DestroyProc</DIR>
</FONT></TD>
<TD WIDTH="32%" VALIGN="TOP" HEIGHT=40><DIR>

<FONT FACE="Courier New" SIZE=1><P>NULL</DIR>
</FONT></TD>
</TR>
</TABLE>
</CENTER></P>

<B><FONT SIZE=1><P>&nbsp;</P><DIR>
<DIR>
<DIR>
<DIR>
<DIR>
<DIR>

</FONT><P>Table 1: Attribute Definitions and Default Values</P></DIR>
</DIR>
</DIR>
</DIR>
</DIR>

</B><P>Each structure on a hash table must retain a key by which it is hashed.  This key may be either a pointer or embedded into the structure as defined by the HASH_EmbeddedKey attribute.  By default, the hash table assumes that the key is a pointer to a NULL terminated character string.  Either way, the hashing and lookup functions receive a pointer to the key.</P><DIR>
<DIR>

<FONT SIZE=2><P>   <U>Non-Embedded Key (default)</U>&#9;     <U>Embedded Key</P>
</U></FONT><FONT FACE="Courier New" SIZE=1><P>struct my_struct {&#9;struct my_struct {</P>
<P>&#9;...&#9;&#9;...</P>
<P>&#9;char *name; /* key */&#9;&#9;char name[100]; /* key */</P>
<P>&#9;...&#9;&#9;...</P>
<P>};&#9;&#9;};</P></DIR>
</DIR>

</FONT><P>The HASH_Intrusive attribute determines if the hash table's lists will be intrusively linked or linked by containers.  By default the lists are container style.  However, intrusive lists are more optimal in both time and space.  This attribute has the synonym HASH_NoContainer and the antonyms HASH_NonInstrusive and HASH_Container.  Any of these may be used to define the intrusive attribute.</P>
<P>When the debug library is in use (see Debugging for more info.) the attributes HASH_ReportChange and HASH_ReportAccess determine (on a hash table by hash table basis) what information to report to stdout after each function call.</P>
<P>The HASH_DynamicResize attribute is used to define when (if ever) to resize the hash table to make the hashing more optimal.  On an insertion, if the hash table's Count/Size ratio is greater than this value, the hash table will double in size and re-hash all the items into the new table.  By default resizing is turned off (0).</P>
<P>The offsets HASH_KeyOffset and HASH_NextOffset are used to determine the locations of the key and intrusive next pointer in the structure to be hashed.  A key offset must always be provided while a next offset is only necessary on intrusive tables.  The table is automatically made intrusive if the next offset attribute is set.  The macro HASH_Offset may be used to calculate the offset of the items in the table.  This macro takes the addresses of a structure and the item in it and calculates the offset.   The order of the parameters is not important to the macro, i.e. <FONT FACE="Courier New" SIZE=1>HASH_Offset(&amp;my_struct, &amp;my_struct.name)</FONT> is equivalent to <FONT FACE="Courier New" SIZE=1>HASH_Offset(&amp;my_struct.name, &amp;my_struct)</FONT>.</P>
<P>The attribute HASH_HashFunction defines the hashing function to use.  The value returned must be in the interval [0:<I>size</I>-1], indices out of this range may result in a call to the error handler or a segment fault.  The default hash function hashes NULL terminated character strings into a relatively random distribution.</P>
<P>The attribute HASH_LookupFunction defines the function to use to when scanning through a linked list on a given hash index.  The function compares two keys and True (1) if they are a match and False (0) if they are not.  The default lookup function compares NULL terminated character strings for an exact match.</P>
<P>The attribute HASH_DestroyFunction defines the function to use when an item of data is removed from a hash table.  The purpose of this function is to free (release) the memory allocated for the structure on the hash table.</P></DIR>

<B><P>Functions and Procedures</P><DIR>

</B><U><P>Creation and Destruction and Modification</P>
</U><FONT FACE="Courier New" SIZE=1><P>HAST_TABLE*&#9;HASH_Create(unsigned size, &lt;argument list&gt;);</P>
<P>void&#9;HASH_Destroy(HASH_TABLE *h);</P>
<P>void &#9;HASH_SetAttribute(HASH_TABLE *h, enum HASH_ATTR attr, type value);</P>
<P>void &#9;HASH_GetAttribute(HASH_TABLE *h, enum HASH_ATTR attr, type *value);</P>
</FONT><U><P>Insertion and Removal</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR&#9;HASH_Insert(HASH_TABLE *h, DATA_PTR data);</P>
<P>void&#9;HASH_Remove(HASH_TABLE *h, DATA_PTR data);</P>
<P>void&#9;HASH_RemoveByKey(HASH_TABLE *h, DATA_PTR key);</P>
<P>DATA_PTR&#9;HASH_ReHash(HASH_TABLE *h, DATA_PTR data, DATA_PTR old_key);</P>
</FONT><U><P>Data Retrieval</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR&#9;HASH_Lookup(HASH_TABLE *h, DATA_PTR key);</P>
</FONT><U><P>Processing and Iteration</P>
</U><FONT FACE="Courier New" SIZE=1><P>void&#9;HASH_Process(HASH_TABLE *h, HASH_ProcessProc process);</P>
<P>void&#9;HASH_ProcessPlus(HASH_TABLE *h, HASH_ProcessPlusProc process, DATA_PTR arg2);</P>
<P>MACRO&#9;HASH_Iterate(HASH_TABLE *h, DATA_PTR data)</P>
</FONT><U><P>Error Handling</P>
</U><FONT FACE="Courier New" SIZE=1><P>HASH_ErrorProc&#9;Set_HASH_Handler(HASH_ErrorProc handler);</P>
</FONT><U><P>&nbsp;</P>
<P>Notes</P>
</U><FONT FACE="Courier New" SIZE=1><P> <I>&lt;argument list&gt;</I> is a NULL terminated attribute-value pair list.</P>
<P> <I>MACRO</I> indicates that the procedure is a convenience macro emulating a for-loop.</P>
<P>&nbsp;</P></DIR>

</FONT><B><P>Description</P><DIR>

</B><P>HASH_Create() creates a hash table with <I>size</I> indices, initializes its attributes to the default values, sets the attributes defined in the <I>&lt;argument list&gt;</I>, and returns a pointer to the new hash table.</P>
<P>HASH_Destroy() destroys a hash table and all the information retained by the hash table.  This is done by first calling HASH_Clear() to remove each item from the table via calls to HASH_Remove().  If the HASH_DestoryFunction attribute is set the destructor function is called to free the item of data.  Once the table is empty, the table and the hash-index array are freed via calls to Delete().</P>
<P>HASH_SetAttribute() sets a single attribute in the hash table.  The argument <I>attr</I> should be one of the hash table attributes, and its <I>value</I> should be of the appropriate type for that attribute. HASH_GetAttribute() retrieves the value of a single attribute from a linked list.  The argument <I>value</I> should be a pointer to an item of the appropriate type for <I>attr</I>.  The value of the attribute will be placed into the item pointed to by <I>value</I>.</P>
<P>HASH_Insert() inserts an item into the hash table.  HASH_Remove() removes an item from a hash table.  HASH_RemoveByKey() finds the item matching <I>key</I> and removes it from the table.  </P>
<P>HASH_ReHash() rehashes an item of data after the key has changed.  The argument old_key must have the value of the previous key in it so that the item can be found on the hash table.  This function finds the item on the table, does a quick remove (without the destructor function) and re-inserts into the hash table.  </P>
<P>HASH_Lookup() finds an item of data in the table which matches the argument key and returns a pointer to the data.  If no such item exists the function returns NULL.</P>
<P>HASH_Process() and HASH_ProcessPlus() are used for running a function <I>process</I> across every item in a hash table.  HASH_ProcessPlus() takes a second argument <I>arg2</I> which is passed to each function call so that the processing function can process the data relative to <I>arg2</I>.  HASH_Iterate() is a convenience macro which expands to a for loop to iterate through all items of data in the hash table.  It is inadvisable to change the argument <I>data</I>'s key or pointers while in an iteration or process loop  It is especially important that the item <I>data</I> is not removed from the hash table during such a loop.  Doing so may cause the loop to terminate early, never terminate, or segment fault.</P>
<P>Set_HASH_Handler() installs the function handler as the error handler for all hash tables and returns the previously installed handler.  The default handler reports the error to stderr (stdout with the debug library).</P></DIR>

<B><P>Extended Functions and Procedures</P><DIR>

</B><U><P>Destruction and Modification</P>
</U><FONT FACE="Courier New" SIZE=1><P>void&#9;HASH_Clear(HASH_TABLE *h);</P>
<P>void&#9;HASH_ChangeSize(HASH_TABLE *h, unsigned size);</P>
<P>void&#9;HASH_SetAttributes(HASH_TABLE *h, &lt;argument list&gt;);</P>
<P>void &#9;HASH_GetAttributes(HASH_TABLE *h, &lt;argument list&gt;);</P>
</FONT><U><P>Conversion</P>
</U><FONT FACE="Courier New" SIZE=1><P>DATA_PTR*&#9;HASH_ToArray(HASH_TABLE *h, DATA_PTR *array, unsigned *nel);</P>
<P>HASH_TABLE*&#9;HASH_FromArray(HASH_TABLE *h, DATA_PTR *array, unsigned nel, <BR>
&#9;&#9;unsigned offset, int embedded);</P>
<P>LINKED_LIST*&#9;HASH_ToLinkedList(HASH_TABLE *h, LINKED_LIST *ll);</P>
<P>HASH_TABLE*&#9;HASH_FromLinkedList(HASH_TABLE *h, LINKED_LIST *ll, <BR>
&#9;unsigned offset, int embedded);</P>
</FONT><U><P>Misc.</P>
</U><FONT FACE="Courier New" SIZE=1><P>unsigned&#9;HASH_GetCount(HASH_TABLE *h);</P>
<P>unsigned&#9;HASH_GetSize(HASH_TABLE *h);</P>
</FONT><U><P>Notes</P>
</U><FONT FACE="Courier New" SIZE=1><P> <I>&lt;argument list&gt;</I> is a NULL terminated attribute-value pair list.</P>
<P> <I>offset </I>and<I> embedded</I> are an optional argument, see descriptions for more information.</P></DIR>

</FONT><B><P>Extended Function Description</P><DIR>

</B><P>HASH_Clear() removes all data from a hash table via calls to the function HASH_Remove().  If the attribute HASH_DestroyFunction is set, the destructor function will be called to destroy (free) each item of data on the list.  The HASH_Clear() function leaves the table's attributes intact, i.e. embedded key, intrusive, etc..</P>
<P>HASH_SetAttributes() and HASH_GetAttributes() perform the same operation as their singular forms with the exception that they take a variable number of attributes.  The <I>&lt;argument list&gt;</I> is a NULL terminates list of attribute-value pairs (in the Get function it is attribute-value pointer pairs).</P>
<P>HASH_ToArray() converts a hash table to an array of pointers.  The argument <I>array</I> must either be a pointer to an array of sufficient size to hold the number of items in the table or NULL in which case an array of sufficient size is allocated.  The argument <I>nel</I> (if non-NULL) is the location where the function will return the number of items placed in the array.</P>
<P>HASH_FromArray() converts an array to a hash table.  The argument <I>array</I> must be a pointer to the first item of an array of pointers to structures and <I>nel</I> is the number of elements in the array.  The argument <I>h</I> is the hash table to use for all the items in the array.  If <I>h</I> is non-NULL the <I>offset</I> and <I>embedded</I> arguments are ignored (they do not need to be placed in the function call) and all data currently in the hash table will be removed (without calling the destructor function) and the array will be converted in.  If <I>h</I> is NULL a default hash table with <I>nel</I> indices will be created and the arguments <I>offset</I> and <I>embedded</I> will be used to define the structure's hashing properties.</P>
<P>HASH_ToLinkedList() converts a hash table to a linked list.  If the argument<I> ll</I> is NULL a default linked list will be created.  Additions to the linked list are made by calling the function LL_Add() for each item of data.</P>
<P>HASH_FromLinkedList() converts a linked list to a hash table.  If the argument <I>h</I> is NULL the arguments <I>offset</I> and <I>embedded</I> are used to create a default hash table whose size is the same as the linked list count.</P>
<P>If h is non-NULL the offset and embedded arguments are ignored and all the data in the hash table is removed (without calling the destructor function).</P>
<P>HASH_GetCount() and HASH_GetSize() return the number of elements and the number of indices (respectively) in the hash table<I> h</I>.</P></DIR>

<B><P>Override Functions and Procedures</P><DIR>

</B><FONT FACE="Courier New" SIZE=1><P>void&#9;HASH_ClearFn(HASH_TABLE *h, HASH_DestroyProc destroy);</P>
<P>void&#9;HASH_DestroyFn(HASH_TABLE *h, HASH_DestroyProc destroy);</P>
<P>void &#9;HASH_RemoveFn(HASH_TABLE *h, DATA_PTR data, HASH_DestroyProc destroy);</P>
<P>void&#9;HASH_RemoveByKeyFn(HASH_TABLE *h, DATA_PTR key, HASH_DestroyProc destroy);</P></DIR>

</FONT><B><P>Override Function Description</P><DIR>

</B><P>The override functions perform the same operation as their generic counterparts except that the argument <I>destroy</I> is used to destroy the data rather than the destructor function attribute installed on the table.</P>
<B><P>&nbsp;</P></DIR>

<P>Debugging Functions</P><DIR>

</B><FONT FACE="Courier New" SIZE=1><P>int&#9;HASH_Verify(HASH_TABLE *h);</P>
<P>void&#9;HASH_Print(HASH_TABLE *h, HASH_PrintProc print);</P>
<P>HASH_CONTAINER*&#9;HASH_GetContainer(HASH_TABLE *h, DATA_PTR data);</P>
<P>HASH_CONTAINER*&#9;HASH_GetContainerByKey(HASH_TABLE *h, DATA_PTR key);</P></DIR>

</FONT><B><P>Debugging Function Description</P><DIR>

</B><P>HASH_Verify() verifies that all data in the hash table is correct.  It checks that each item of data is hashed at the correct index and that the count matches the expected count.</P>
<P>HASH_Print() first verifies the table, and then prints all the data out via calls to the function <I>print</I> for each item of data on the hash table.  If <I>print</I> is NULL the default printing function will be used which prints out the index, data's address, the key's address, and the character string key.  Note: Do not use NULL if data is not hashed by a character string.</P>
<P>HASH_GetContainer() returns the container of the item <I>data</I>.  HASH_GetContainerByKey() returns the container of the item found by a lookup on <I>key</I>.</P></DIR>

<B><P>Debugging </P><DIR>

</B><P>Hash table operations can be debugged by defining either HASH_DEBUG or STRUCT_DEBUG in any ".c" file prior to the inclusion of the &lt;hash.h&gt; header file and by using the hash_debug.a library in place of the hash.a library at compile time.  Defining HASH_DEBUG causes each operation to force a function call rather than the (occasional) faster macro expansion.  The debug library makes additional checks to verify the validity of the arguments passed to each function and the correctness of the internal variables (including the index returned by the hash function).  In addition, the attributes HASH_ReportChange and HASH_ReportAccess may be set resulting in each function call on a particular list reports the operation performed to stdout.</P></DIR>

<B><P>Notes</P><DIR>

</B><P>This library relies on the New.a library to perform the allocation and deallocation of memory for the tables, their hash-index arrays, and the containers on container style lists.  It also relies on the linked_list.a library for the conversion functions.  In total, using this library requires that the linked_list.a, array.a, stack.a, and New.a libraries be linked in at compile time.</P>
<P>The call New(HASH_TABLE) should not be used to create a hash table as the internal data may not be initialized correctly, nor will the allocation of the array take place.  Therefore always use the HASH_Create() function to create a hash table.</P>
<P>It is extremely important within iterations and processing calls that the current item of data does not have its key or pointers changed in any way (including an attempt to remove the item of data).  Doing so may cause unpredictable results.  This also applies to the functions installed on the hash table (with the obvious exception of the destructor function).</P></DIR>

<B><P>Errors</P><DIR>

</B><P>Any of the functions or procedures in this library may fail as a result of the errors described below.  At the occurrence of such a failure, the hash table error handler is called to report the error to the user.  The global variable char <FONT FACE="Courier New" SIZE=1>*HASH_errlist[]</FONT> provides a short description of the error which occurred (see examples for information on how to use the <FONT FACE="Courier New" SIZE=1>*HASH_errlist[]</FONT> variable).</P>
<FONT FACE="Courier New" SIZE=1><P>HASH_UnknownErr</FONT>&#9;-&#9;<FONT SIZE=2>Undocumented or unknown error.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>HASH_MemoryErr</FONT>&#9;-&#9;<FONT SIZE=2>Unable to allocate the necessary space to complete the operation.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>HASH_TableCorrupted</FONT>&#9;-&#9;<FONT SIZE=2>The hash table is corrupted in some way.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>HASH_BadIndex</FONT>&#9;-&#9;<FONT SIZE=2>Index returned by the hash function is too large.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>HASH_BadArgument</FONT>&#9;-&#9;<FONT SIZE=2>One or more of the arguments to the function are invalid.</P>
</FONT><FONT FACE="Courier New" SIZE=1><P>HASH_NoMember</FONT>&#9;-&#9;<FONT SIZE=2>No member matching key (...ByKey() functions).</P></DIR>

</FONT><B><P>Examples</P>
</B><U><FONT FACE="Courier" SIZE=2><P>Example Makefile</P>
</U></FONT><FONT FACE="Courier New" SIZE=2><P>&nbsp;</P><DIR>

</FONT><FONT FACE="Courier New" SIZE=1><P>INCDIR=-I$(HOME)/struct/include</P>
<P>LIBDIR=-L$(HOME)/struct/lib</P>
<P>LIBS=-lhash -llinked_list -larray -lstack -lNew</P>
<P>&nbsp;</P>
<P>## LIBS=-lstruct ## optional library which includes all of the libraries</P>
<P>&nbsp;</P>
<P>all: my_file</P>
<P>&nbsp;</P>
<P>my_file: my_file.o</P>
<P>&#9;$(CC) -o my_file myfile.o $(LIBDIR) $(LIBS)</P>
<P>&nbsp;</P>
<P>my_file.o: my_file.c</P>
<P>&#9;$(CC) -O $(INCDIR) -c my_file.c</P>
</FONT><U><P>&nbsp;</P>
<FONT SIZE=2><P>Example Use #1:  Container Style Table</P>
</U></FONT><FONT FACE="Courier New" SIZE=1><P>#include &lt;hash.h&gt;</P>
<P>#include &lt;New.h&gt;      /* used for New()      */</P>
<P>#include &lt;stdio.h&gt;    /* used for printing   */</P>
<P>#include &lt;string.h&gt;   /* used for comparison */</P>
<P>&nbsp;</P>
<P>typedef struct blee {</P>
<P>&#9;char *name;</P>
<P>&#9;int   val;</P>
<P>} BLEE;</P>
<P>&nbsp;</P>
<P>#define SIZE 10</P>
<P>const struct blee array[SIZE] = { </P>
<P>&#9;{"Joe",    0}, {"Frank",  1}, {"Buddy",  2}, {"Jim",    3}, {"George", 4},</P>
<P>&#9;{"Jane",   5}, {"Jay",    6}, {"Laura",  7}, {"Craig",  8}, {"Bill",   9},</P>
<P>};</P>
<P>&nbsp;</P>
<P>unsigned my_hash_fn   (int *val, unsigned size) { return((*val)%size); }</P>
<P>unsigned my_lookup_fn (int *key1, int *key2)    { return((!((*key1) - (*key2)))); }</P>
<P>void     my_destructor(BLEE *b)                 { Delete(b-&gt;name); Delete(b);     }</P>
<P>unsigned my_print_fn  (unsigned index, BLEE *b, int *key) { </P>
<P>   printf("%u (%d): %s, %d\n", index, *key, b-&gt;name, b-&gt;val);</P>
<P>}</P>
<P>void     my_handler   (HASH_TABLE *h, enum HASH_ERROR error_num, char *fn) {</P>
<P>   printf("Hash Table 0x%.8x had error %d = %s in %s.\n", h, error_num,</P>
<P>           HASH_errlist[error_num], fn);</P>
<P>}</P>
<P>&nbsp;</P>
<P>main () {</P><DIR>

<P>HASH_TABLE *h1, *h2;</P>
<P>BLEE *b, tmp;</P>
<P>int i;</P>
<P>&nbsp;</P>
<P>h1 = HASH_Create(7, HASH_KeyOffset, HASH_Offset(&amp;tmp, &amp;tmp.name), </P>
<P>                    HASH_DestroyFunction, my_destructor, NULL);</P>
<P>h2 = HASH_Create(7, HASH_EmbeddedKey, True, HASH_KeyOffset, HASH_Offset(&amp;tmp, &amp;tmp.val),</P>
<P>                    HASH_HashFunction, my_hash_fn, HASH_LookupFunction, my_lookup_fn</P>
<P>                    NULL);</P>
<P>&nbsp;</P>
<P>for (i = 0; i &lt; SIZE; i++) {</P>
<P>   b = New(BLEE); b-&gt;name = strdup(array[i].name); b-&gt;val = array[i].val;</P>
<P>   HASH_Insert(h1, b);</P>
<P>   HASH_Insert(h2, b);</P>
<P>}</P>
<P>&nbsp;</P>
<P>HASH_Print(h1, NULL);</P>
<P>HASH_Print(h2, my_print_fn);</P>
<P>&nbsp;</P>
<P>b = HASH_Lookup(h1, "Laura");</P>
<P>printf("%s = %d\n", b-&gt;name, b-&gt;val);</P>
<P>&nbsp;</P>
<P>i = 3;   b = HASH_Lookup(h2, &amp;i); /* Key must be a pointer */</P>
<P>printf("%d = %s\n", b-&gt;val, b-&gt;name);</P>
<P>&nbsp;</P>
<P>HASH_Remove(h2, b);</P>
<P>HASH_Remove(h1, b);  /* This one calls the destructor */</P>
<P>&nbsp;</P>
<P>b = HASH_Lookup(h1, "Frank");</P>
<P>HASH_Remove(h2, b);</P>
<P>HASH_RemoveByKey(h1, "Frank");  /* Destructor called  */</P>
<P>&nbsp;</P>
<P>HASH_Print(h1, NULL);</P>
<P>HASH_Print(h2, my_print_fn);</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>HASH_SetHandler(my_handler);</P>
<P>HASH_RemoveByKey(h1, "Frank");  /* Should fail */</P>
<P>&nbsp;</P>
<P>HASH_Destroy(h2);</P>
<P>HASH_Destroy(h1);</P></DIR>

<P>}</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
</FONT><U><FONT SIZE=2><P>Example Use #2:  Intrusive Style Table</P>
</U></FONT><FONT FACE="Courier New" SIZE=1><P>&nbsp;</P>
<P>#include &lt;hash.h&gt;</P>
<P>#include &lt;New.h&gt;      /* used for New()      */</P>
<P>#include &lt;stdio.h&gt;    /* used for printing   */</P>
<P>#include &lt;string.h&gt;   /* used for comparison */</P>
<P>&nbsp;</P>
<P>typedef struct blee {</P>
<P>&#9;char *name; int val;</P>
<P>} SIMPLE_BLEE;</P>
<P>&nbsp;</P>
<P>typedef struct blee_intr {</P>
<P>&#9;char *name; int val;</P>
<P>&#9;struct blee_intr ptr;</P>
<P>} BLEE;</P>
<P>&nbsp;</P>
<P>#define SIZE 10</P>
<P>const struct blee array[SIZE] = { </P>
<P>&#9;{"Joe",    0}, {"Frank",  1}, {"Buddy",  2}, {"Jim",    3}, {"George", 4},</P>
<P>&#9;{"Jane",   5}, {"Jay",    6}, {"Laura",  7}, {"Craig",  8}, {"Bill",   9},</P>
<P>};</P>
<P>&nbsp;</P>
<P>/* See example #1, all functions are identical with the exception of the creation</P>
<P>   functions which also include the following:</P>
<P>   HASH_Intrusive, True, HASH_NextOffset, HASH_Offset(&amp;tmp, &amp;tmp.ptr), </P>
<P>*/</P>
<P>&nbsp;</P></DIR>

</FONT><H4>Author</H4><DIR>

<P>Jonathan L. DeKock  </P></DIR>

<H2><A NAME="_Toc412283852"><A NAME="_Toc412283890">12. Packet Formats</A></A> </H2>
<P><A NAME="interface"><A NAME="select">Following are the binary packet formats used by most MRT tools.</P>
<PRE></PRE>
<P>1)  MRT header (12 bytes)</P>
<PRE>
     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                              Time                             |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |             Type              |            Subtype            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                             Length                            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

All MRT messages have this common header, which includes   Timestamp, message type and subtype and the length of the message.  The length does not include the MRT header itself.

MRT_MSG_TYPES 
0  MSG_NULL,
1  MSG_START,                   /* sender is starting up */
2  MSG_DIE,                     /* receiver should shut down */
3  MSG_I_AM_DEAD,               /* sender is shutting down */
4  MSG_PEER_DOWN,               /* sender's peer is down */
5  MSG_PROTOCOL_BGP,            /* msg is a BGP packet */
6  MSG_PROTOCOL_RIP,            /* msg is a RIP packet */
7  MSG_PROTOCOL_IDRP,           /* msg is an IDRP packet */
8  MSG_PROTOCOL_RIPNG,          /* msg is a RIPNG packet */
9  MSG_PROTOCOL_BGP4PLUS,       /* msg is a BGP4+ packet */
10 MSG_PROTOCOL_BGP4PLUS_01,    /* msg is a BGP4+ (draft 01) packet */
</PRE>
<P>2)  BGP <FONT FACE="Courier" SIZE=2>(MSG_PROTOCOL_BGP, MSG_PROTOCOL_BGP4PLUS, MSG_PROTOCOL_BGP4PLUS_01)</P>
</FONT><PRE>MRT_MSG_BGP_TYPES 
0  MSG_BGP_NULL,
1  MSG_BGP_UPDATE,      /* raw update packet (contains both with and ann) */
2  MSG_BGP_PREF_UPDATE, /* tlv preferences followed by raw update */
3  MSG_BGP_STATE_CHANGE /* state change */
4  MSG_BGP_SYNC



If the message type is MSG_PROTOCOL_BGP and the message subtype is MSG_BGP_UPDATE, the following applies:


     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |        Source AS number       |       Source IP address       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |   Source IP address (Cont'd)  |     Destination AS number     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                     Destination IP address                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                       BGP Update Packet                       |
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

If the message type is MSG_PROTOCOL_BGP4PLUS and the message subtype is MSG_BGP_UPDATE, the following applies:

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |        Source AS number       |       Source IP address       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Source IP address (Cont'd)                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Source IP address (Cont'd)                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Source IP address (Cont'd)                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |   Source IP address (Cont'd)  |     Destination AS number     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                     Destination IP address                    |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                 Destination IP address (Cont'd)               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                 Destination IP address (Cont'd)               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                 Destination IP address (Cont'd)               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                       BGP4 Update Packet                      |
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

</PRE>
<P>&nbsp;</P>
<P>If the message subtype is <FONT FACE="Courier" SIZE=2>MSG_BGP_STATE_CHANGE,</FONT> the following format should be used for state change messages:</P>
<PRE>
     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |        Source AS number       |       Source IP address       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Source IP address (Cont'd)                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Source IP address (Cont'd)                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Source IP address (Cont'd)                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |   Source IP address (Cont'd)  |     Old State                 |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |   New State                   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
<FONT FACE="Courier"></A></A></A></A></A></PRE>
</FONT><P>If the message subtype is <FONT FACE="Courier" SIZE=2>MSG_BGP_SYNC,</FONT> the following format applies:</P>
<PRE>
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |          View #              |       File Name [variable]     |</PRE>
<P>        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</P>
<P>The filename ends with \0 (null.)</P>
<P>3) The format for our routing table dump is:</P>
<P>&nbsp;</P>
<FONT FACE="Courier New" SIZE=2><P>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</P>
<P>    |          View #              |       Prefix                   |</P>
<P>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</P>
<P>    |       Prefix (continue)      |       Mask      |   Status     |</P>
<P>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</P>
<P>    |        Time last change                                       |</P>
<P>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</P>
<P>    |        Attr Len                                               |</P>
<P>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</P>
<P>    |      BGP Attribute (Variable length)....                      |</P>
<P>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+</P>
</FONT><P>&nbsp;</P></BODY>
</HTML>