path: root/lib/qpath.c

/* Some primitive path handling
 * Copyright (C) 2010 Chris Hall (GMCH), Highwayman
 *
 * This file is part of GNU Zebra.
 *
 * GNU Zebra is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published
 * by the Free Software Foundation; either version 2, or (at your
 * option) any later version.
 *
 * GNU Zebra is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with GNU Zebra; see the file COPYING.  If not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#include "qpath.h"
#include "qstring.h"

#include "zassert.h"

/*==============================================================================
 * Some primitive path handling, based on qstrings.
 *
 *
 *==============================================================================
 * Path Reduction
 *
 * As per POSIX, multiple '/' count as single '/', except for the very special
 * case of exactly two '/' at the start of a path.  (That case is referred to
 * here as a "double root".)
 *
 * So this code reduces runs of '/' to single '/' -- except for the special
 * case.
 *
 * This code also replaces "/./" by "/".
 *
 *
 */

/*------------------------------------------------------------------------------
 * Initialise a brand new qpath -- allocate if required.
 *
 * If a path is given, set that path -- allocating body even if path is zero
 * length.
 *
 * If no path is given, leaves qpath with no body.
 *
 * If path is given, the qpath is set and reduced (see above).
 *
 * Returns: address of qpath
 *
 * NB: assumes initialising a new structure.  If not, then caller should
 *     use qpath_reset() or qs_clear().
 */
extern qpath
qpath_init_new(qpath qp, const char* path)
{
  if (qp == NULL)
    qp = XCALLOC(MTYPE_QPATH, sizeof(qpath_t)) ;
  else
    memset(qp, 0, sizeof(qpath_t)) ;

  /* Worry about fields other than the path             */

  qs_init_new(&qp->path, 0) ;

  if (path != NULL)
    qpath_set(qp, path) ;

  return qp ;
} ;

/*------------------------------------------------------------------------------
 * Reset contents of given qpath, freeing the structure if required.
 *
 * Discards all the contents of the qpath.
 */
extern qpath
qpath_reset(qpath qp, bool free_structure)
{
  if (qp == NULL)
    return NULL ;

  qs_reset_keep(&qp->path, keep_it) ;

  if (free_structure)
    XFREE(MTYPE_QPATH, qp) ;            /* sets qp = NULL       */
  else
    /* Worry about fields other than the path             */
    ;

  return qp ;
} ;

/*------------------------------------------------------------------------------
 * Set given qpath to copy of the given string -- allocate if required.
 *
 * If setting an existing qpath, discards any existing contents -- so the qpath
 * MUST have been initialised at some time (qpath_init_new).  Keeps any body
 * that has been allocated if possible.
 *
 * Reduces the path (see above).
 *
 * Sets the path len, but does not touch the path cp.
 */
extern qpath
qpath_set(qpath qp, const char* path)
{
  if (qp == NULL)
    qp = qpath_init_new(NULL, path) ;
  else
    {
      if (path != NULL)
        qs_set(&qp->path, path) ;
      else
        qs_clear(&qp->path) ;
      /* Worry about fields other than the path             */
    } ;

  qpath_reduce(qp) ;

  return qp ;
} ;

/*------------------------------------------------------------------------------
 * Reduce multiple '/' to single '/' (except for exactly "//" at start).
 *
 * Reduce "/./" to "/".
 */
static void
qpath_reduce(qpath qp, size_t off)
{
  qpath   part ;
  qstring qs ;
  char*   sp ;
  char*   p ;
  char*   q ;

  if (qp == NULL)
    {
      assert(off == 0) ;
      return ;                  /* NULL qpath is empty                  */
    } ;

  qs = &qp->path ;
  assert(off <= qs->len) ;      /* Make sure 'off' is kosher            */

  sp = qs_chars(qs) ;           /* NULL if qpath is completely empty    */

  if (sp == NULL)
    return ;                    /* NULL path part is completely empty   */

  p = sp + off ;

  /* Deal with special case of "//" at start.
   *
   * If find "//x", where x is anything other than '/', step past the first
   * '/'.  Could step past both "//", but that stops it seeing "//./zzz"
   */
  if ((*p == '/') && (*(p + 1) == '/') && (*(p + 2) != '/'))
    ++p ;

  /* Scan to see if there is anything that needs to be fixed.
   *
   * Looking for "//" and "/./".
   */
  while (1)
    {
      if (*p++ == '\0')
        return ;                /* nothing to do if hit end of string   */

      if ( (*p == '/') || ((*p == '.') && (*(p + 1) == '/')) )
        {
          if (*(p - 1) == '/')
            break ;             /* found "//" or "/./"                  */
        }
    } ;

  /* Rats... there is something to be fixed.
   *
   * *p is second '/' of "//" or '.' of "/./".
   */
  q = p ;

  while (*p != '\0')
    {
      /* Step past any number of '/' and any number of "./".            */
      while (1)
        {
          while (*p == '/')
            ++p ;

          if ((*p != '.') || (*p != '/'))
            break ;

          p += 2 ;
        } ;

      /* Scan, copying stuff, until get to '\0' or find "//" or "/./"   */
      while (*p != '\0')
        {
          *q++ = *p++ ;         /* copy non-'\0'                        */

          if ( (*p == '/') || ((*p == '.') && (*(p + 1) == '/')) )
            {
              if (*(p - 1) == '/')
                break ;         /* found "//" or "/./"                  */
            } ;
        } ;
    } ;

  /* Adjust the length and terminate                                    */

  qs->len = (q - sp) ;      /* set the new length (shorter !)   */
  *q = '\0' ;               /* and terminate                    */
} ;

/*------------------------------------------------------------------------------
 * Make a copy of the given qpath.
 *
 * Creates a brand new qpath object, which is a full copy of the given one.
 *
 * The result is an empty qpath if the given one is NULL.
 */
extern qpath
qpath_copy(qpath qp_x)
{
  return qpath_init_new(NULL, qpath_path(qp_x)) ;
} ;

/*------------------------------------------------------------------------------
 * Make a copy of a qpath to the given qpath.
 *
 * If required, creates new qpath object -- so qpath_copy_to(NULL, ...) is the
 * same as qpath_copy(...).
 *
 * The result is an empty qpath if the given one is NULL.
 */
extern qpath
qpath_copy_to(qpath qp, qpath qp_x)
{
  return qpath_set(qp, qpath_path(qp_x)) ;
} ;

/*==============================================================================
 * Pop the last part of the given path.
 *
 * The cases are (where 'a' is anything except '/' and 'z' is anything):
 *
 *   1. ""        -- empty path
 *
 *                    - path unchanged
 *                    - return empty part
 *
 *   2. "aaa"     -- the path is a single part
 *
 *                    - part removed from path, leaves ""
 *                    - return the part
 *
 * Note that in (1) and (2) there is no '/', in the following there is at least
 * one '/'.
 *
 *   3. "/"       -- root only, or
 *      "//"         double root only
 *
 *                    - path unchanged
 *                    - return empty part
 *
 *   4. "/aaa"    -- one remaining part before the root,
 *      "//aaa"      or one remaining part after double route
 *
 *                    - part removed from path, leaves "/" or "//"
 *                    - return the part
 *
 *   5. "zzz/"    -- empty last part
 *
 *                    - "/" removed from end of path
 *                    - return empty part
 *
 *   6. "zzz/aaa" -- non-empty last part
 *
 *                    - part and "/" removed from end of path
 *                    - return part
 *
 * Note that other forms of multiple '/' have been reduced, already.
 */
extern qpath
qpath_pop(qpath qp)
{
  qpath   part ;
  qstring qs ;
  char*   sp ;
  char*   p ;

  /* Get pointers to start and end of path                              */
  if (qp != NULL)
    {
      qs = &qp->path ;

      sp = qs_chars(qs) ;       /* NULL if qpath is completely empty    */
      p  = qs_ep_char(qs) ;     /* points at trailing '\0'              */
    }
  else
    qs = sp = p = NULL ;

  /* Deal with NULL-ness                                                */
  if (sp == NULL)
    {
      assert(p == sp) ;         /* ie qs->len == 0 if qs->body == NULL  */

      return qpath_init_new(NULL, NULL) ;
    } ;

  /* Track back to last '/'                     */
  while ( (p > sp) && (*(p - 1) != '/') )
    --p ;

  /* Construct result which is from p forwards
   *
   * p == NULL if the given path is completely empty.
   */
  part = qpath_init_new(NULL, p) ;

  /* If what remains is not empty, and not just "/" or "//", remove trailing '/'
   *
   * If p == sp,     there was no '/', so path ends up empty.
   * If p == sp + 1, there is one '/', and that is at the front of the path
   * If p == sp + 2, there is either "//" or "a/"
   * If p >  sp + 2, there is "aa/"
   */
  if (p >= (sp + 2))    /* if "//", "a/" or "aa/" etc.          */
    {
      /* Unless is special case of "//"...                      */
      if ( ! ((p == (sp + 2)) && (*sp == '/')) )
        --p ;           /* ... discard trailing '/'             */
    } ;

  qs->len = (p - sp) ;  /* set the new length (shorter !)       */
  *p = '\0' ;           /* and terminate                        */

  /* Return the part we hacked off                              */
  return part ;
} ;

/*==============================================================================
 * Shift off the first part of the given path.
 *
 * The cases are (where 'a' is anything except '/' and 'z' is anything):
 *
 *   1. ""        -- empty path
 *
 *                    - path unchanged
 *                    - return empty part
 *
 *   2. "aaa"     -- the path is a single part
 *
 *                    - part removed from path, leaves ""
 *                    - return the part
 *
 * Note that in (1) and (2) there is no '/', in the following there is at least
 * one '/'.
 *
 *   3. "/"       -- root only, or
 *      "//"         double root
 *
 *                    - remove the "/" or "//" -- result is empty
 *                    - return "/" or "//" part
 *
 *   4. "/azz"    -- root followed by stuff, or
 *      "//zzz"      double root followed by stuff.
 *
 *                    - remove the "/" or "//"
 *                    - return "/" or "//" part
 *
 *   5. "aaa/"    -- something followed by first '/' which is end of path
 *
 *                    - remove upto and including '/' -- result is empty
 *                    - return upto but excluding '/'
 *
 *   6. "aaa/azz" -- something followed by first '/' followed by something else
 *
 *                    - remove upto and including '/'
 *                    - return upto but excluding '/'
 *
 * Note that other forms of multiple '/' have been reduced, already.
 */
extern qpath
qpath_shift(qpath qp)
{
  qpath   part ;
  qstring qs ;
  char*   sp ;
  char*   p ;
  char*   q ;

  /* Get pointers to start and end of path                              */
  if (qp != NULL)
    {
      qs = &qp->path ;
      sp = qs_chars(qs) ;       /* NULL if qpath is completely empty    */
    }
  else
    qs = sp = NULL ;

  /* Deal with NULL-ness                                                */
  if (sp == NULL)
    return qpath_init_new(NULL, NULL) ;

  p = sp ;

  /* Set p such that sp..p-1 is to be shifted off.
   * And q such that  q..end-1 is to be kept.
   */
  if (*sp == '/')
    {
      ++p ;             /* single root          */
      if (*p == '/')
        ++p ;           /* double root          */
      q = p ;
    }
  else
    {
      while ((*p != '/') && (*p != '/0'))
        ++p ;           /* step to '/' or end   */

      if (*p == '/')
        q = p + 1 ;     /* don't keep '/'       */
      else
        q = p ;         /* keep '\0' !          */
    } ;

  /* Construct qpath for shifted off stuff              */
  part = qpath_init_new(NULL, NULL) ;

  /* Hack off the shifted off stuff & '/' if required   */


  /* Return the part we hacked off                      */
  return part ;
} ;

/*------------------------------------------------------------------------------
 * Push one path onto the end of the given path.
 *
 * If the given path is NULL, creates a new, empty qpath to push onto.
 *
 * The given path is assumed to be the path to a "directory".  An empty
 * given path is treated as "the current directory".
 *
 * If the path to be pushed starts '/' or '~', then it is trimmed, removing
 * leading characters upto and including '/' (stopping at '\0' if no '/' found).
 *
 * If path to be pushed onto is not empty, and does not end '/', then an '/'
 * is appended before the path is pushed.
 *
 * Note that this means:
 *
 *   -- pushing an empty path or one which is just "/", will leave the path
 *      ending "/" -- unless the given path is empty.
 *
 *   -- cannot create a rooted path by pushing a path onto an empty path.
 *
 *   -- pushing a "homed" path "~...." is assumed to be pushing onto the
 *      required "home".
 *
 * The resulting path is reduced (see above).
 */

extern qpath
qpath_push(qpath qp, qpath qp_a)
{
  return qpath_push_str(qp, qpath_path(qp_a)) ;
} ;

/*------------------------------------------------------------------------------
 * Push path string onto the end of the given path.
 *
 * See above for discussion of "push" operation.
 */
extern qpath
qpath_push_str(qpath qp, const char* path)
{
  qstring   qs ;
  char*     ep ;
  char*     sp ;
  size_t    len ;
  size_t    off ;

  if (qp == NULL)
    qp = qpath_init_new(NULL, NULL) ;

  qs = &qp->path ;

  /* Trim the path to be pushed:
   *
   *   1. discard from any leading '~' to the first '/' or to '\0'.
   *
   *   2. then discard any leading '/'
   *
   *   3. then establish length of result.
   */
  if (path != NULL)
    {
      if (*path == '~')
        do
          {
            ++path ;
          } while ((*path != '/') && (*path != '\0')) ;

      while (*path == '/')
        ++path ;                /* Step past leading '/'                */
      len = strlen(path) ;
    }
  else
    len = 0 ;

  /* Worry about whether need to add a '/' to the path before pushing   */
  sp  = qs_chars(qs) ;
  ep  = qs_ep_char(qs) ;        /* points at trailing '\0'              */

  if (sp == NULL)
    assert(ep == sp) ;          /* ie qs->len == 0 if qs->body == NULL  */

  off = qs->len ;               /* where new stuff starts               */

  if (ep != sp)
    {
      if (*(ep - 1) == '/')
        --off ;                 /* step back to the '/'                 */
      else
        {
          /* Destination is not empty and does not end '/', so append one.
           *
           * Note that we ensure there is space for the path which are
           * about to push, so at most one allocation required.
           */
          qs_need(qs, (ep - sp) + 1 + len) ;
          qs_append_n(qs, "/", 1) ;
        } ;
    } ;

  /* Now push path                                                      */
  qs_append_n(qs, path, len) ;

  /* Reduce the new part of the result, and return
   *
   * Note that the 'off' points at the '/' which precedes the new stuff.
   * So will spot "/./" where the new stuff starts "./".
   */
  qpath_reduce(qp, off) ;

  return qp ;
} ;

/*------------------------------------------------------------------------------
 * Join two paths to create a new path.
 *
 * Copies the destination path and then pushes the other path onto it.
 */
extern qpath
qpath_join(qpath qp, qpath qp_a)
{
  qpath qp_n ;

  qp_n = qpath_copy(qp) ;
  return qpath_push(qp_n, qp_a) ;
} ;

/*------------------------------------------------------------------------------
 * Join path string to the given path to create a new path.
 *
 * Copies the destination path and then pushes the path string onto it.
 */
extern qpath
qpath_join_str(qpath qp, const char* path)
{
  qpath qp_n ;

  qp_n = qpath_copy(qp) ;
  return qpath_push_str(qp_n, path) ;
} ;

/*------------------------------------------------------------------------------
 * Does the given path start and end '/' ?
 */
extern bool
qpath_sex(qpath qp)
{
  char*     sp ;

  if (qp == NULL)
    return qp_empty ;           /* NULL qpath is empty          */

  sp  = qs_chars(&qp->path) ;

  if ((sp == NULL) || (*sp == '\0'))
    return qp_empty ;           /* NULL body or just '\0'       */

  if (*sp == '~')
    return qp_homed ;

  if (*sp == '/')
    {
      ++sp ;
      if (*sp == '\0')
        return qp_root ;
      if (*sp != '/')
        return qp_absolute ;

      ++sp ;
      if (*sp == '\0')
        return qp_double_root ;
      else
        return qp_double_absolute ;
    } ;



  qp_empty,             /* nothing at all                       */
  qp_relative,          /* something, not starting '/'          */
  qp_root,              /* "/" all on its own                   */
  qp_absolute,          /* something, starting with single '/'  */
  qp_homed,             /* something, starting with '~'         */
  qp_double_root,       /* "//" all on its own                  */
  qp_double_absolute    /* something, starting with "//"        */



  return ((qp->path).len == 1) && (*sp == '/') ;
} ;

/*------------------------------------------------------------------------------
 * Is there anything there ?
 */
extern bool
qpath_is_empty(qpath qp)
{
  if (qp == NULL)
    return true ;               /* NULL qpath is empty          */

  return (qp->path).len == 0 ;
} ;

/*------------------------------------------------------------------------------
 * Is it: not empty, not starting '/' (or '//') and not starting '~'
 */
extern bool
qpath_is_relative(qpath qp)
{
  char*     sp ;

  if (qp == NULL)
    return false ;              /* NULL qpath is not relative   */

  sp = qs_chars(&qp->path) ;

  return (sp != NULL) && (*sp != '/') && (*sp != '.') ;
} ;

/*------------------------------------------------------------------------------
 * Does the given path start and end '/' ?
 */
extern bool
qpath_is_root(qpath qp)
{
  char*     sp ;

  if (qp == NULL)
    return false ;              /* NULL qpath cannot be root    */

  sp = qs_chars(&qp->path) ;

  return ((qp->path).len == 1) && (*sp == '/') ;
} ;

/*------------------------------------------------------------------------------
 * Does the given path start '/' (and not '//') ?
 *
 * Note that just "/" (ie root) will return true => it is also absolute.
 */
extern bool
qpath_is_absolute(qpath qp)
{
  char*     sp ;

  if (qp == NULL)
    return false ;              /* NULL qpath cannot be absolute        */

  sp = qs_chars(&qp->path) ;

  return (sp != NULL) && (*sp == '/') && (*(sp + 1) != '/') ;
} ;

/*------------------------------------------------------------------------------
 * Does the given path start '~'
 */
extern bool
qpath_is_homed(qpath qp)
{
  char*     sp ;

  if (qp == NULL)
    return false ;              /* NULL qpath cannot be homed   */

  sp = qs_chars( &qp->path) ;

  return (sp != NULL) && (*sp == '~') ;
} ;

/*------------------------------------------------------------------------------
 * Does the given path start and end '/' ?
 */
extern bool
qpath_is_double_root(qpath qp)
{
  char*     sp ;

  if (qp == NULL)
    return false ;              /* NULL qpath cannot be root    */

  sp = qs_chars(&qp->path) ;

  return ((qp->path).len == 2) && (*sp == '/') && (*(sp + 1) == '/') ;
} ;

/*------------------------------------------------------------------------------
 * Does the given path start '/' (and not '//') ?
 *
 * Note that just "/" (ie root) will return true => it is also absolute.
 */
extern bool
qpath_is_double_absolute(qpath qp)
{
  char*     sp ;

  if (qp == NULL)
    return false ;              /* NULL qpath cannot be absolute        */

  sp = qs_chars(&qp->path) ;

  return (sp != NULL) && (*sp == '/') && (*(sp + 1) == '/') ;
} ;

/*------------------------------------------------------------------------------
 * Does the given path *end* '/', or is it ~aaaa with no '/' at all.
 *
 * Note that root and double route return directory true.
 */
extern bool
qpath_is_directory(qpath qp)
{
  char*     sp ;

  if (qp == NULL)
    return false ;              /* NULL qpath cannot be directory       */

  sp = qs_chars(&qp->path) ;

  if ((sp == NULL) || (*sp = '\0'))
    return false ;              /* Empty qpath cannot be directory      */

  ep = qs_ep_char(qs) ;

  if (*(ep - 1) == '/')
    return true ;               /* Ends '/'                             */

  if (*sp == '~')
    {
      while (*(++sp) != '/')
        {
          if (*sp == '\0')      /* Starts '~' and no '/' found          */
            return true ;
        } ;
    } ;

  return false ;
} ;

/*------------------------------------------------------------------------------
 * Is the given path an atom
 *
 * Note that root and double route are .
 */
extern bool
qpath_is_atom(qpath qp)
{
  char*     sp ;

  if (qp == NULL)
    return false ;              /* NULL qpath cannot be directory       */

  sp = qs_chars(&qp->path) ;

  if ((sp == NULL) || (*sp = '\0'))
    return false ;              /* Empty qpath cannot be directory      */

  ep = qs_ep_char(qs) ;

  if (*(ep - 1) == '/')
    return true ;               /* Ends '/'                             */

  if (*sp == '~')
    {
      while (*(++sp) != '/')
        {
          if (*sp == '\0')      /* Starts '~' and no '/' found          */
            return true ;
        } ;
    } ;

  return false ;
} ;