Complex Data and Control Structures
***********************************

This chapter describes features distributed with Emacs that build upon the basic Emacs Lisp data types and control structures described in previous chapters.  With these abstractions, you can idiomatically organize and present data in sophisticated ways.

The abstraction are typically provided as features to be loaded via the require mechanism (see How Programs Do Loading).

Managing a Fixed-Size Ring of Objects
=====================================

This section describes the functions provided by feature ring. A ring is a fixed-size data structure that supports insertion, deletion, rotation and modulo-indexed reference and traversal.

 -- Function: make-ring size
     Return a new ring capable of holding SIZE objects. SIZE should be an integer.

 -- Function: ring-p object
     Return t iff OBJECT is a ring.

 -- Function: ring-size ring
     Return the maximum capacity of the RING.

 -- Function: ring-length ring
     Return the number of objects that RING contains. The value will never exceed that returned by ring-size.

 -- Function: ring-elements ring
     Return a list of the objects in RING. The list is not guaranteed to be in any particular order.

 -- Function: ring-copy ring
     Return a copy of RING. The new ring contains the same objects as RING.

When a ring is full, insertion removes the oldest element to make room for the newest element, which always has index 0 (zero). Higher indexes correspond to older elements.  Index -1 corresponds to the oldest element, -2 to the next-oldest, and so forth.

 -- Function: ring-ref ring index
     Return the object in RING found at INDEX, an integer. INDEX may be negative or greater than the ring length. If RING is empty, signal error: Accessing an empty ring.

 -- Function: ring-insert ring object
     Insert into RING the OBJECT as the newest element. Return OBJECT.

 -- Function: ring-remove ring &optional index
     Remove an object from RING.  Return the removed object. If optional INDEX is nil, remove the oldest item. If numeric, remove the object indexed. If RING is empty, signal error: Ring empty.

 -- Function: ring-insert-at-beginning ring object
     Insert into RING the OBJECT as the oldest element. If RING is full, remove the newest element.

Note that when the ring length does not exceed the ring size, ring-insert and ring-remove on the ring effect a first-in-first-out queue, as in this example:

     (let ((fifo (make-ring 5)))
       (mapc (lambda (obj) (ring-insert fifo obj))
             '(0 one "two"))
       (list (ring-remove fifo) t
             (ring-remove fifo) t
             (ring-remove fifo)))
          => (0 t one t "two")

Converting Byte Arrays To and From Alists
=========================================

This section describes the functions provided by feature bindat.  Essentially, these convert byte arrays to and from alists.  The byte array may be in the form of either a unibyte string or a vector of integers, while the alist associates symbols with either fixed-size objects or recursive sub-alists.

Conversion from byte arrays to nested alists is also known as deserializing or unpacking, while going in the opposite direction is also known as serializing or packing.

Describing Data Layout
----------------------

To control unpacking and packing, you write a data layout specification, a specially constructed [formatted? arranged? styled?] nested list of named and typed fields.  Both bindat-unpack and bindat-pack use this specification to determine the length of each field to be processed, and their relative placement in the alist (when unpacking) and byte array (when packing).  See Bindat Functions.

A field's type describes the size (in bytes) of the object that the field represents and, in the case of integers greater than 255, how those bytes are internally ordered.  The two orderings are ``big endian'' (also known as ``network byte ordering'') and ``little endian''.  For instance, the number #x23cd (decimal 9165) in big endian would be the two bytes #x23 #xcd; and in little endian, #xcd #x23.  The specification for a field's type can be one of the following:

u8
byte
     Unsigned byte, with length 1.

u16
word
short
     Unsigned integer in network byte order, with length 2.

u24
     Unsigned integer in network byte order, with length 3.

u32
dword
long
     Unsigned integer in network byte order, with length 4. Note: These values may be limited by Emacs' integer implementation limits.

u16r
u24r
u32r
     Unsigned integer in little endian order, with length 2, 3 and 4, respectively.

str LEN
     String of length LEN.

strz LEN
     Zero-terminated string of length LEN.

vec LEN
     Vector of LEN bytes.

ip
     Four-byte vector.  For example: [127 0 0 1] for localhost.

bits LEN
     List of set bits in LEN bytes.  The bytes are taken in big endian order and the bits are numbered starting with 8LEN-1 and ending with zero.  For example: bits 2 unpacks #x28 #x1c to (2 3 4 11 13) and #x1c #x28 to (3 5 10 11 12).

(eval FORM)
     FORM is a Lisp expression evaluated at the moment the field is unpacked or packed.  The result of the evaluation should be one of the above-listed type specifications.

A field specification generally has the form ([NAME] HANDLER). The square braces indicate that NAME is optional.  When choosing a name, you should take care to avoid type specification (above) or handler specification (below) keywords; bindat.el may become confused otherwise.  NAME may be a symbol or the expression (eval FORM), in which case FORM should evaluate to a symbol. HANDLER describes how to unpack or pack the field and can be one of the following:

TYPE
     Unpack/pack this field according to the type specification TYPE.

eval FORM
     Evaluate FORM, a Lisp expression, for side-effect only.  If the field name is specified, the value is bound to that field.  FORM may access and update these dynamically bound variables:

     raw-data
          Byte array.

     pos
          Current position of the unpacking or packing operation.

     struct
          Alist.

     last
          Value of the last field processed.

fill LEN
     Skip LEN bytes.

align LEN
     Skip to the next multiple of LEN bytes.

struct SPEC-NAME
     SPEC-NAME names a variable whose value is a valid data layout specification.  Process the child specification here.

union FORM (TAG SPEC)...
     Evaluate FORM, a Lisp expression, find the first TAG that matches it, and process its associated data layout specification SPEC.  Matching can occur in one of three ways:

       * If a TAG has the form (eval EXPR), evaluate EXPR with the variable tag dynamically bound to the value of FORM.  A non-nil result indicates a match.

       * TAG matches if it is equal to the value of FORM.

       * TAG matches unconditionally if is t.

repeat COUNT FIELD-SPEC...
     COUNT may be an integer, or a list of one element naming a previous field.  [Each FIELD-SPEC should include a name, otherwise bindat.el gets confused. --ttn]

Functions to Unpack and Pack Bytes
----------------------------------

In the following documentation, SPEC refers to the data layout specification, raw-data the byte array, and STRUCT the alist.

 -- Function: bindat-unpack spec raw-data &optional pos
     Unpack according to SPEC the byte array raw-data. Normally, start unpacking at the beginning.  Optional third arg pos specifies a zero-based starting position to use instead.

 -- Function: bindat-get-field struct &rest name
     From alist STRUCT, return value of field NAME. Multiple field names specify a nested lookup of sub-structures. An integer name specifies an array index.

     For example, NAME with value (a b 2 c), corresponds to the C-language syntax struct.a.b[2].c.

 -- Function: bindat-length spec struct
     Return length in bytes of STRUCT according to SPEC.

 -- Function: bindat-pack spec struct &optional raw-data pos
     Return byte array packed according to SPEC for alist STRUCT. Normally a new byte array is created and packing starts at its beginning. Optional third arg RAW-DATA is a pre-allocated string or vector to pack into, and optional fourth arg POS is the starting offset into raw-data.

     Note: The result is a multibyte string; use string-make-unibyte on it to make it unibyte if necessary.

 -- Function: bindat-ip-to-string ip
     Return vector IP formatted as an ip address in dotted notation.

          (bindat-ip-to-string [127 0 0 1])
               => "127.0.0.1"

Examples of Byte Unpacking and Packing
--------------------------------------

Here is a complete example of byte unpacking and packing:

     (defvar fcookie-index-spec
       '((:version  u32)
         (:count    u32)
         (:longest  u32)
         (:shortest u32)
         (:flags    u32)
         (:delim    u8)
         (:ignored  fill 3)
         (:offset   repeat (:count)
                    (:foo u32)))
       "Description of a fortune cookie index file's contents.")

     (defun fcookie (cookies &optional index)
       "Display a random fortune cookie from file COOKIES.
     Optional second arg INDEX specifies the associated index
     filename, which is by default constructed by appending
     \".dat\" to COOKIES.  Display cookie text in possibly
     new buffer \"*Fortune Cookie: BASENAME*\" where BASENAME
     is COOKIES without the directory part."
       (interactive "fCookies file: ")
       (let* ((info (with-temp-buffer
                      (insert-file-contents-literally
                       (or index (concat cookies ".dat")))
                      (bindat-unpack fcookie-index-spec
                                     (buffer-string))))
              (sel (random (bindat-get-field info :count)))
              (beg (cdar (bindat-get-field info :offset sel)))
              (end (or (cdar (bindat-get-field info :offset (1+ sel)))
                       (nth 7 (file-attributes cookies)))))
         (switch-to-buffer (get-buffer-create
                            (format "*Fortune Cookie: %s*"
                                    (file-name-nondirectory cookies))))
         (erase-buffer)
         (insert-file-contents-literally cookies nil beg (- end 3))))

     (defun fcookie-create-index (cookies &optional index delim)
       "Scan file COOKIES, and write out its index file.
     Optional second arg INDEX specifies the index filename,
     which is by default constructed by appending \".dat\" to
     COOKIES.  Optional third arg DELIM specifies the unibyte
     character which, when found on a line of its own in
     COOKIES, indicates the border between entries."
       (interactive "fCookies file: ")
       (setq delim (or delim ?%))
       (let ((delim-line (format "\n%c\n" delim))
             (count 0)
             (max 0)
             min p q len offsets)
         (unless (= 3 (string-bytes delim-line))
           (error "Delimiter cannot be represented in one byte"))
         (with-temp-buffer
           (insert-file-contents-literally cookies)
           (while (and (setq p (point))
                       (search-forward delim-line (point-max) t)
                       (setq len (- (point) 3 p)))
             (setq count (1+ count)
                   max (max max len)
                   min (min (or min max) len)
                   offsets (cons (1- p) offsets))))
         (with-temp-buffer
           (set-buffer-multibyte nil)
           (insert (string-make-unibyte
                    (bindat-pack
                     fcookie-index-spec
                     `((:version . 2)
                       (:count . ,count)
                       (:longest . ,max)
                       (:shortest . ,min)
                       (:flags . 0)
                       (:delim . ,delim)
                       (:offset . ,(mapcar (lambda (o)
                                             (list (cons :foo o)))
                                           (nreverse offsets)))))))
           (let ((coding-system-for-write 'raw-text-unix))
             (write-file (or index (concat cookies ".dat")))))))

Following is an example of defining and unpacking a complex structure. Consider the following C structures:

     struct header {
         unsigned long    dest_ip;
         unsigned long    src_ip;
         unsigned short   dest_port;
         unsigned short   src_port;
     };

     struct data {
         unsigned char    type;
         unsigned char    opcode;
         unsigned long    length;  /* In little endian order */
         unsigned char    id[8];   /* nul-terminated string  */
         unsigned char    data[/* (length + 3) & ~3 */];
     };

     struct packet {
         struct header    header;
         unsigned char    items;
         unsigned char    filler[3];
         struct data      item[/* items */];

     };

The corresponding data layout specification:

     (setq header-spec
           '((dest-ip   ip)
             (src-ip    ip)
             (dest-port u16)
             (src-port  u16)))

     (setq data-spec
           '((type      u8)
             (opcode    u8)
             (length    u16r) ;; little endian order
             (id        strz 8)
             (data      vec (length))
             (align     4)))

     (setq packet-spec
           '((header    struct header-spec)
             (items     u8)
             (fill      3)
             (item      repeat (items)
                        (struct data-spec))))

A binary data representation:

     (setq binary-data
           [ 192 168 1 100 192 168 1 101 01 28 21 32 2 0 0 0
             2 3 5 0 ?A ?B ?C ?D ?E ?F 0 0 1 2 3 4 5 0 0 0
             1 4 7 0 ?B ?C ?D ?E ?F ?G 0 0 6 7 8 9 10 11 12 0 ])

The corresponding decoded structure:

     (setq decoded-structure (bindat-unpack packet-spec binary-data))
          =>
     ((header
       (dest-ip   . [192 168 1 100])
       (src-ip    . [192 168 1 101])
       (dest-port . 284)
       (src-port  . 5408))
      (items . 2)
      (item ((data . [1 2 3 4 5])
             (id . "ABCDEF")
             (length . 5)
             (opcode . 3)
             (type . 2))
            ((data . [6 7 8 9 10 11 12])
             (id . "BCDEFG")
             (length . 7)
             (opcode . 4)
             (type . 1))))

Fetching data from this structure:

     (bindat-get-field decoded-structure 'item 1 'id)
          => "BCDEFG"

Maintain a View of a List of Objects in a Buffer
================================================