lib/src/clixon_xml_sort.c

/*
 *
  ***** BEGIN LICENSE BLOCK *****

  Copyright (C) 2009-2016 Olof Hagsand and Benny Holmgren
  Copyright (C) 2017-2019 Olof Hagsand
  Copyright (C) 2020 Olof Hagsand and Rubicon Communications, LLC(Netgate)

  This file is part of CLIXON.

  Licensed under the Apache License, Version 2.0 (the "License");
  you may not use this file except in compliance with the License.
  You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the specific language governing permissions and
  limitations under the License.

  Alternatively, the contents of this file may be used under the terms of
  the GNU General Public License Version 3 or later (the "GPL"),
  in which case the provisions of the GPL are applicable instead
  of those above. If you wish to allow use of your version of this file only
  under the terms of the GPL, and not to allow others to
  use your version of this file under the terms of Apache License version 2,
  indicate your decision by deleting the provisions above and replace them with
  the  notice and other provisions required by the GPL. If you do not delete
  the provisions above, a recipient may use your version of this file under
  the terms of any one of the Apache License version 2 or the GPL.

  ***** END LICENSE BLOCK *****

 * XML sort and search functions when used with YANG
 */

#ifdef HAVE_CONFIG_H
#include "clixon_config.h" /* generated by config & autoconf */
#endif

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <limits.h>
#include <stdint.h>
#include <assert.h>
#include <syslog.h>

/* cligen */
#include <cligen/cligen.h>

/* clixon */
#include "clixon_err.h"
#include "clixon_log.h"
#include "clixon_string.h"
#include "clixon_queue.h"
#include "clixon_hash.h"
#include "clixon_handle.h"
#include "clixon_yang.h"
#include "clixon_xml.h"
#include "clixon_xml_nsctx.h"
#include "clixon_xml_io.h"
#include "clixon_xpath_ctx.h"
#include "clixon_xpath.h"
#include "clixon_options.h"
#include "clixon_xml_map.h"
#include "clixon_yang_type.h"
#include "clixon_yang_module.h"
#include "clixon_xml_vec.h"
#include "clixon_xml_sort.h"

/*! Get xml body value as cligen variable
 * @param[in]  x   XML node (body and leaf/leaf-list)
 * @param[out] cvp Pointer to cligen variable containing value of x body
 * @retval     0   OK, cvp contains cv or NULL
 * @retval    -1   Error
 * @note only applicable if x is body and has yang-spec and is leaf or leaf-list
 * Move to clixon_xml.c?
 * As a side-effect sets the cache.
 * Clear cache with xml_cv_set(x, NULL)
 */
static int
xml_cv_cache(cxobj   *x,
	     cg_var **cvp)
{
    int          retval = -1;
    cg_var      *cv = NULL;
    yang_stmt   *y;
    yang_stmt   *yrestype;
    enum cv_type cvtype;
    int          ret;
    char        *reason=NULL;
    int          options = 0;
    uint8_t      fraction = 0;
    char        *body;

    if ((body = xml_body(x)) == NULL)
	body="";
    if ((cv = xml_cv(x)) != NULL)
	goto ok;
    if ((y = xml_spec(x)) == NULL){
	clicon_err(OE_XML, EFAULT, "Yang binding missing for xml symbol %s, body:%s", xml_name(x), body);
	goto done;
    }
    if (yang_type_get(y, NULL, &yrestype, &options, NULL, NULL, NULL, &fraction) < 0)
	goto done;
    yang2cv_type(yang_argument_get(yrestype), &cvtype);
    if (cvtype==CGV_ERR){
	clicon_err(OE_YANG, errno, "yang->cligen type %s mapping failed",
		   yang_argument_get(yrestype));
	goto done;
    }
    if ((cv = cv_new(cvtype)) == NULL){
	clicon_err(OE_YANG, errno, "cv_new");
	goto done;
    }
    if (cvtype == CGV_DEC64)
	cv_dec64_n_set(cv, fraction);

    if ((ret = cv_parse1(body, cv, &reason)) < 0){
	clicon_err(OE_YANG, errno, "cv_parse1");
	goto done;
    }
    if (ret == 0){
	clicon_err(OE_YANG, EINVAL, "cv parse error: %s\n", reason);
	goto done;
    }
    if (xml_cv_set(x, cv) < 0)
	goto done;
 ok:
    *cvp = cv;
    cv = NULL;
    retval = 0;
 done:
    if (reason)
	free(reason);
    if (cv)
	cv_free(cv);
    return retval;
}

static int
xml_cv_cache_clear(cxobj *xt)
{
    int    retval = -1;
    cxobj *x = NULL;

    while ((x = xml_child_each(xt, x, CX_ELMNT)) != NULL)
	if (xml_cv_set(x, NULL) < 0)
	    goto done;
    retval = 0;
 done:
    return retval;
}

/*! Help function to qsort for sorting entries in xml child vector same parent
 * @param[in]  x1    object 1
 * @param[in]  x2    object 2
 * @param[in]  same  If set, x1 and x2 are member of same parent & enumeration
 *                   is used (see explanation below)
 * @param[in]  skip1 Key matching skipped for keys not in x1 (see explanation)
 * @param[in]  explicit For list nodes, use explicit index variables, not keys
 * @retval     0     If equal
 * @retval    <0     If x1 is less than x2
 * @retval    >0     If x1 is greater than x2
 *
 * There are distinct calls for this function:
 * 1. For sorting in an existing list of XML children
 * 2. For searching of an existing element in a list
 * In the first case, there is a special case for "ordered-by-user", where
 * if they have the same yang-spec, the existing order is used as tie-breaker.
 * In other words, if order-by-system, or if the case (2) above, the existing
 * order is ignored and the actual xml element contents is examined.
 *
 * Also, if pattern is set, list matching is not made so that x1 and x2 must have same keys.
 * instead, x1 and x2 are considered equal if the keys that x1 have match. Keys that x2 but not
 * x1 has are ignored.
 * Example: x1: <x><k1>1</k1></x> and x2: <x><k1>1</k1><k2>2</k2></x> are considered equal.
 * This is useful in searching for indexes in trees, where x1 is a search index and not a
 * complete tree.
 *
 * @note empty value/NULL is smallest value
 * @note some error cases return as -1 (qsort cant handle errors)
 * @note some error cases return as -1 (qsort cant handle errors)
 *
 * @note "comparing" x1 and x2 here judges equality from a structural (model)
 * perspective, ie both have the same yang spec, if they are lists, they have the
 * the same keys. NOT that the values are equal!
 * In other words, if x is a leaf with the same yang spec, <x>1</x> and <x>2</x> are
 * "equal".
 * If x is a list element (with key "k"),
 * <x><k>42</42><y>foo</y></x> and <x><k>42</42><y>bar</y></x> are equal,
 * but is not equal to <x><k>71</42><y>bar</y></x>
 */
int
xml_cmp(cxobj  *x1,
	cxobj  *x2,
	int     same,
    	int     skip1,
	char   *indexvar)
{
    yang_stmt  *y1;
    yang_stmt  *y2;
    int         yi1 = 0;
    int         yi2 = 0;
    cvec       *cvk = NULL; /* vector of index keys */
    cg_var     *cvi;
    int         equal = 0;
    char       *b1;
    char       *b2;
    char       *keyname;
    cg_var     *cv1 = NULL;
    cg_var     *cv2 = NULL;
    int         nr1 = 0;
    int         nr2 = 0;
    cxobj      *x1b;
    cxobj      *x2b;
    enum cxobj_type xt1;
    enum cxobj_type xt2;

    if (x1==NULL || x2==NULL)
	goto done; /* shouldnt happen */
    /* Sort according to attributes first */
    if ((xt1 = xml_type(x1)) != (xt2 = xml_type(x2))){
	if (xt1 == CX_ATTR){
	    equal = -1;
	    goto done;
	}
	else if (xt2 == CX_ATTR){
	    equal = 1;
	    goto done;
	}
    }
    /* Here x1 and x2 are same type */
    y1 = xml_spec(x1);
    y2 = xml_spec(x2);
    if (same){
	nr1 = xml_enumerate_get(x1);
	nr2 = xml_enumerate_get(x2);
    }
    if (y1==NULL && y2==NULL){
	if (same)
	    equal = nr1-nr2;
	goto done;
    }
    if (y1==NULL){
        equal = -1;
        goto done;
    }
    if (y2==NULL){
        equal = 1;
        goto done;
    }
    if (y1 != y2){
	yi1 = yang_order(y1);
	yi2 = yang_order(y2);
	if ((equal = yi1-yi2) != 0)
	    goto done;
    }
    /* Now y1==y2, same Yang spec, can only be list or leaf-list,
     * But first check exceptions, eg config false or ordered-by user
     * otherwise sort according to key
     * If the two elements are in the same list, and they are ordered-by user
     * then do not look more into equivalence, use the enumeration in the
     * existing list.
     */
    if (same &&
	(
#ifndef STATE_ORDERED_BY_SYSTEM
	 yang_config(y1)==0 ||
#endif
	 yang_find(y1, Y_ORDERED_BY, "user") != NULL)){
	    equal = nr1-nr2;
	    goto done; /* Ordered by user or state data : maintain existing order */
	}
    switch (yang_keyword_get(y1)){
    case Y_LEAF_LIST: /* Match with name and value */
	b1 = xml_body(x1);
	b2 = xml_body(x2);
	if (b1 == NULL && b2 == NULL)
	    ;
	else if (b1 == NULL)
	    equal = -1;
	else if (b2 == NULL)
	    equal = 1;
	else{
	    if (xml_cv_cache(x1, &cv1) < 0) /* error case */
		goto done;
	    if (xml_cv_cache(x2, &cv2) < 0) /* error case */
		goto done;
	    if (cv1 != NULL && cv2 != NULL)
		equal = cv_cmp(cv1, cv2);
	    else if (cv1 == NULL && cv2 == NULL)
		equal = 0;
	    else if (cv1 == NULL)
		equal = -1;
	    else
		equal = 1;
	}
	break;
    case Y_LIST: /* Match with key values  */
	if (indexvar != NULL){
#ifdef XML_EXPLICIT_INDEX
	    x1b = xml_find(x1, indexvar);
	    x2b = xml_find(x2, indexvar);
	    if (x1b == NULL && x2b == NULL)
		;
	    else if (x1b == NULL)
		equal = -1;
	    else if (x2b == NULL)
		equal = 1;
	    else{
		b1 = xml_body(x1b);
		b2 = xml_body(x2b);
		if (b1 == NULL && b2 == NULL)
		    ;
		else if (b1 == NULL)
		    equal = -1;
		else if (b2 == NULL)
		    equal = 1;
		else{
		    if (xml_cv_cache(x1b, &cv1) < 0) /* error case */
			goto done;
		    if (xml_cv_cache(x2b, &cv2) < 0) /* error case */
			goto done;
		    assert(cv1 && cv2);
		    equal = cv_cmp(cv1, cv2);
		}
	    }
	    if (equal)
		break;
#endif /* XML_EXPLICIT_INDEX */
	}
	else {
	/* Use Y_LIST cache (see struct yang_stmt) */
	cvk = yang_cvec_get(y1); /* Use Y_LIST cache, see ys_populate_list() */
	cvi = NULL;
	while ((cvi = cvec_each(cvk, cvi)) != NULL) {
	    keyname = cv_string_get(cvi); /* operational data may have NULL keys*/
	    x1b = xml_find(x1, keyname);
	    /* match1: key matching skipped for keys not in x1 (see explanation) */
	    if (skip1 && x1b == NULL)
		continue;
	    x2b = xml_find(x2, keyname);
	    if (x1b == NULL && x2b == NULL)
		;
	    else if (x1b == NULL)
		equal = -1;
	    else if (x2b == NULL)
		equal = 1;
	    else{
		b1 = xml_body(x1b);
		b2 = xml_body(x2b);
		if (b1 == NULL && b2 == NULL)
		    ;
		else if (b1 == NULL)
		    equal = -1;
		else if (b2 == NULL)
		    equal = 1;
		else{
		    if (xml_cv_cache(x1b, &cv1) < 0) /* error case */
			goto done;
		    if (xml_cv_cache(x2b, &cv2) < 0) /* error case */
			goto done;
		    assert(cv1 && cv2);
		    equal = cv_cmp(cv1, cv2);
		}
	    }
	    if (equal)
		break;
	} /* while cvi */
	}
	break;
    default:
	/* This is a very special case such as for two choices - which is not validation correct, but we
	   should sort them according to nr1, nr2 since their yang is equal order */
	if (same)
	    equal = nr1-nr2;
	break;
    } /* switch */
 done:
    clicon_debug(3, "%s %s %s eq:%d nr: %d %d yi: %d %d", __FUNCTION__, xml_name(x1), xml_name(x2), equal, nr1, nr2, yi1, yi2);
    return equal;
}

/*!
 * @note args are pointer ot pointers, to fit into qsort cmp function
 */
static int
xml_cmp_qsort(const void* arg1,
	      const void* arg2)
{
    return xml_cmp(*(struct xml**)arg1, *(struct xml**)arg2, 1, 0, NULL);
}

/*! Sort children of an XML node
 * Assume populated by yang spec.
 * @param[in] x0   XML node
 * @retval    -1    Error, aborted at first error encounter
 * @retval     0    OK, all nodes traversed (subparts may have been skipped)
 * @retval     1    OK, aborted on first fn returned 1
 * @see xml_apply  - typically called by recursive apply function
 * @see xml_sort_verify
 */
int
xml_sort(cxobj *x)
{
#ifndef STATE_ORDERED_BY_SYSTEM
    yang_stmt *ys;

    /* Abort sort if non-config (=state) data */
    if ((ys = xml_spec(x)) != 0	&& yang_config(ys)==0)
	return 1;
#endif
    xml_enumerate_children(x);
    qsort(xml_childvec_get(x), xml_child_nr(x), sizeof(cxobj *), xml_cmp_qsort);
    return 0;
}

/*! Recursively sort a tree
 * Alt to use xml_apply
 */
int
xml_sort_recurse(cxobj *xn)
{
    int    retval = -1;
    cxobj *x;
    int    ret;

    ret = xml_sort_verify(xn, NULL);
    if (ret == 1) /* This node is not sortable */
	goto ok;
    if (ret == -1){ /* not sorted */
	if ((ret = xml_sort(xn)) < 0)
	    goto done;
	if (ret == 1) /* This node is not sortable */
	    goto ok;
    }
    if (xml_cv_cache_clear(xn) < 0)
	goto done;
    x = NULL;
    while ((x = xml_child_each(xn, x, CX_ELMNT)) != NULL) {
	if (xml_sort_recurse(x) < 0)
	    goto done;
    }
 ok:
    retval = 0;
 done:
    return retval;
}

/*! Special case search for ordered-by user or state data where linear sort is used
 *
 * @param[in]  xp    Parent XML node (go through its childre)
 * @param[in]  x1    XML node to match
 * @param[in]  yangi Yang order number (according to spec)
 * @param[in]  mid   Where to start from (may be in middle of interval)
 * @param[out] xvec      Vector of matching XML return objects (can be empty)
 * @retval     0         OK, see xvec (may be empty)
 * @retval    -1         Error
 * XXX: only first match
 */
static int
xml_find_keys_notsorted(cxobj   *xp,
			cxobj   *x1,
			int      yangi,
			int      mid,
			int      skip1,
			clixon_xvec *xvec)
{
    int        retval = -1;
    int        i;
    cxobj     *xc;
    yang_stmt *yc;

    for (i=mid+1; i<xml_child_nr(xp); i++){ /* First increment */
	xc = xml_child_i(xp, i);
	yc = xml_spec(xc);
	if (yangi != yang_order(yc)) /* wrong yang */
	    break;
	if (xml_cmp(xc, x1, 0, skip1, NULL) == 0){
	    if (clixon_xvec_append(xvec, xc) < 0)
		goto done;
	    goto ok; /* found */
	}
    }
    for (i=mid-1; i>=0; i--){ /* Then decrement */
	xc = xml_child_i(xp, i);
	yc = xml_spec(xc);
	if (yangi != yang_order(yc)) /* wrong yang */
	    break;
	if (xml_cmp(xc, x1, 0, skip1, NULL) == 0){
	    if (clixon_xvec_append(xvec, xc) < 0)
		goto done;
	    goto ok; /* found */
	}
    }
 ok:
    retval = 0;
 done:
    return retval;
}

/*! Find more equal objects in a vector up and down in the array of the present
 * @param[in]  childvec  Vector of children of parent
 * @param[in]  childlen  Length of child vector
 * @param[in]  x1        XML node to match
 * @param[in]  yangi     Yang order number (according to spec)
 * @param[in]  mid       Where to start from (may be in middle of interval)
 * @param[out] xvec      Vector of matching XML return objects (can be empty)
 * @retval     0         OK, see xvec (may be empty)
 * @retval    -1         Error
 */
static int
search_multi_equals(cxobj  **childvec,
		    size_t   childlen,
		    cxobj   *x1,
		    int      yangi,
		    int      mid,
		    int      skip1,
		    clixon_xvec *xvec)
{
    int        retval = -1;
    int        i;
    cxobj     *xc;
    yang_stmt *yc;

    for (i=mid-1; i>=0; i--){ /* First decrement */
	xc = childvec[i];
	yc = xml_spec(xc);
	if (yangi != yang_order(yc)) /* wrong yang */
	    break;
	if (xml_cmp(x1, xc, 0, skip1, NULL) != 0)
	    break;
	if (clixon_xvec_prepend(xvec, xc) < 0)
	    goto done;
    }
    for (i=mid+1; i<childlen; i++){ /* Then increment */
	xc = childvec[i];
	yc = xml_spec(xc);
	if (yangi != yang_order(yc)) /* wrong yang */
	    break;
	if (xml_cmp(x1, xc, 0, skip1, NULL) != 0)
	    break;
	if (clixon_xvec_append(xvec, xc) < 0)
	    goto done;
    }

    retval = 0;
 done:
    return retval;
}

#ifdef XML_EXPLICIT_INDEX
/* XXX unify with search_multi_equals */
static int
search_multi_equals_xvec(clixon_xvec  *childvec,
			 cxobj        *x1,
			 int           yangi,
			 int           mid,
			 int           skip1,
			 clixon_xvec  *xvec)
{
    int        retval = -1;
    int        i;
    cxobj     *xc;
    yang_stmt *yc;

    for (i=mid-1; i>=0; i--){ /* First decrement */
	xc = clixon_xvec_i(childvec, i);
	yc = xml_spec(xc);
	if (yangi != yang_order(yc)) /* wrong yang */
	    break;
	if (xml_cmp(x1, xc, 0, skip1, NULL) != 0)
	    break;
	if (clixon_xvec_prepend(xvec, xc) < 0)
	    goto done;
    }
    for (i=mid+1; i<clixon_xvec_len(childvec); i++){ /* Then increment */
	xc = clixon_xvec_i(childvec, i);
	yc = xml_spec(xc);
	if (yangi != yang_order(yc)) /* wrong yang */
	    break;
	if (xml_cmp(x1, xc, 0, skip1, NULL) != 0)
	    break;
	if (clixon_xvec_append(xvec, xc) < 0)
	    goto done;
    }
    retval = 0;
 done:
    return retval;
}

/*! Insert xi in vector sorted according to index variable xi
 * @param[in]  x1    XML parent object (the list element)
 * @param[in]  ivec  Sorted index vector
 * @param[in]  low   Lower range limit
 * @param[in]  upper Upper range limit
 * @param[in]  max   Upper range limit
 * @param[out] eq    If 0, not equal object found; if 1 pos is one equivalent object
 * @retval     0     Position, where to insert xn
 * @retval    -1     Error
 * @see xml_search_indexvar_binary which returns the found objects, this one just returns
 * position of where to insert xn.
 */
int
xml_search_indexvar_binary_pos(cxobj       *x1,
			       char        *indexvar,
			       clixon_xvec *ivec,
			       int          low,
			       int          upper,
			       int          max,
			       int         *eq)
{
    int        retval = -1;
    int        mid;
    int        cmp;
    cxobj     *xc;

    if (upper < low){  /* beyond range */
	clicon_err(OE_XML, 0, "low>upper %d %d", low, upper);
	goto done;
    }
    if (low == upper){
	retval = low;
	goto done;
    }
    mid = (low + upper) / 2;
    if (mid >= max){  /* beyond range */
	clicon_err(OE_XML, 0, "Beyond range %d %d %d", low, mid, upper);
	goto done;
    }
    xc = clixon_xvec_i(ivec, mid);
    /* >0 means search upper interval, <0 lower interval, = 0 is equal */
    cmp = xml_cmp(x1, xc, 0, 0, indexvar);
    if (low +1 == upper){ /* termination criterium */
    }
    if (cmp == 0){
	retval = mid; /* equal */
	if (eq)
	    *eq = 1;
	goto done;
    }
    else {
	if (low +1 == upper){ /* termination criterium */
	    if (eq)           /* No exact match */
		*eq = 0;
	    if (cmp < 0)      /* return either 0 if cmp<0 or +1 if cmp>0 */
		retval = mid;
	    else
		retval = mid+1;
	    goto done;
	}
	if (cmp < 0)
	    return xml_search_indexvar_binary_pos(x1, indexvar, ivec, low, mid, max, eq);
	else
	    return xml_search_indexvar_binary_pos(x1, indexvar, ivec, mid+1, upper, max, eq);
    }
 done:
    return retval;
}

static int
xml_search_indexvar(cxobj   *xp,
		    cxobj   *x1,
		    int      yangi,
		    int      low,
		    int      upper,
		    char    *indexvar,
		    clixon_xvec *xvec)
{
    int          retval = -1;
    clixon_xvec *ivec = NULL;
    int          ilen;
    int          pos;
    int          eq = 0;
    cxobj       *xc;

    /* Check if (exactly one) explicit indexes in cvk */
    if (xml_search_vector_get(xp, indexvar, &ivec) < 0)
	goto done;
    if (ivec){
	ilen = clixon_xvec_len(ivec);
	if ((pos = xml_search_indexvar_binary_pos(x1, indexvar,
						  ivec, 0,
						  ilen, ilen, &eq)) < 0)
	    goto done;
	if (eq){ /* Found */
	    xc = clixon_xvec_i(ivec, pos);
	    if (clixon_xvec_append(xvec, xc) < 0)
		goto done;
	    /* there may be more? */
	    if (search_multi_equals_xvec(ivec, x1, yangi, pos,
					 0, xvec) < 0)
		goto done;
	}
    }
    retval = 0;
 done:
    return retval;
}
#endif /* XML_EXPLICIT_INDEX */

/*! Find XML child under xp matching x1 using binary search
 * @param[in]  xp        Parent xml node.
 * @param[in]  x1        Find this object among xp:s children
 * @param[in]  sorted    If x1 is ordered by user or statedata, the list is not sorted
 * @param[in]  yangi     Yang order
 * @param[in]  low       Lower bound of childvec search interval
 * @param[in]  upper     Lower bound of childvec search interval
 * @param[in]  skip1     Key matching skipped for keys not in x1
 * @param[in]  indexvar  Override list key value search with explicit search index of x1
 * @param[out] xvec      Vector of matching XML return objects (can be empty)
 * @retval     0         OK, see xvec (may be empty)
 * @retval    -1         Error
 */
static int
xml_search_binary(cxobj   *xp,
		  cxobj   *x1,
		  int      sorted,
		  int      yangi,
		  int      low,
		  int      upper,
		  int      skip1,
		  char    *indexvar,
		  clixon_xvec *xvec)
{
    int        retval = -1;
    int        mid;
    int        cmp;
    cxobj     *xc;
    yang_stmt *y;

    if (upper < low)
    	goto ok;
    mid = (low + upper) / 2;
    if (mid >= xml_child_nr(xp))  /* beyond range */
    	goto ok;
    xc = xml_child_i(xp, mid);
    if ((y = xml_spec(xc)) == NULL)
	goto ok;
    cmp = yangi-yang_order(y);
    /* Here is right yang order == same yang? */
    if (cmp == 0){
#ifdef XML_EXPLICIT_INDEX
	if (indexvar){
	    if (xml_search_indexvar(xp, x1, yangi, low, upper, indexvar, xvec) < 0)
		goto done;
	    goto ok;
	}
#endif
	/* >0 means search upper interval, <0 lower interval, = 0 is equal */
	cmp = xml_cmp(x1, xc, 0, skip1, NULL);
	if (cmp && !sorted){ /* Ordered by user (if not equal) */
	    retval = xml_find_keys_notsorted(xp, x1, yangi, mid, skip1, xvec);
	    goto done;
	}
    }
    if (cmp == 0){
	if (clixon_xvec_append(xvec, xc) < 0)
	    goto done;
	/* there may be more? */
	if (search_multi_equals(xml_childvec_get(xp), xml_child_nr(xp),
				x1, yangi, mid,	skip1, xvec) < 0)
	    goto done;
    }
    else if (cmp < 0)
	xml_search_binary(xp, x1, sorted, yangi, low, mid-1, skip1, indexvar, xvec);
    else
	xml_search_binary(xp, x1, sorted, yangi, mid+1, upper, skip1, indexvar, xvec);
 ok:
    retval = 0;
 done:
    return retval;
}

/*! Search XML child under xp matching x1 using yang-based binary search for list/leaf-list keys
 *
 * Match is tried xp with x1 with either name only (container/leaf) or using keys (list/leaf-lists)
 * Any non-key leafs or other structure of x1 is not matched (unless indexvar is set).
 * If x1 is list or leaf-list, the function assumes key values / indexvar exists in x1.
 *
 * @param[in]  xp    Parent xml node.
 * @param[in]  x1    Find this object among xp:s children
 * @param[in]  yc    Yang spec of x1
 * @param[in]  skip1 Key matching skipped for keys not in x1
 * @param[in]  indexvar Override list key value search with explicit search index var of x1
 * @param[out] xvec  Vector of matching XML return objects (can be empty)
 * @retval     0     OK, see xvec (may be empty)
 * @retval    -1     Error
 * @see xml_find_index  for a generic search function
 */
static int
xml_search_yang(cxobj       *xp,
		cxobj       *x1,
		yang_stmt   *yc,
		int          skip1,
	        char        *indexvar,
		clixon_xvec *xvec)
{
    int    retval = -1;
    cxobj *xa;
    int    low = 0;
    int    upper = xml_child_nr(xp);
    int    sorted = 1;
    int    yangi;

    if (xp == NULL){
	clicon_err(OE_XML, EINVAL, "xp is NULL");
	goto done;
    }
    upper = xml_child_nr(xp);
    /* Assume if there are any attributes, they are first in the list, mask
       them by raising low to skip them */
    for (low=0; low<upper; low++)
	if ((xa = xml_child_i(xp, low)) == NULL || xml_type(xa) != CX_ATTR)
	    break;
#ifndef STATE_ORDERED_BY_SYSTEM
    /* Find if non-config and if ordered-by-user */
    if (yang_config_ancestor(yc)==0)
	sorted = 0;
    else
#endif
	if (yang_keyword_get(yc) == Y_LIST || yang_keyword_get(yc) == Y_LEAF_LIST)
	    sorted = (yang_find(yc, Y_ORDERED_BY, "user") == NULL);
    yangi = yang_order(yc);

    if (xml_search_binary(xp, x1, sorted, yangi, low, upper, skip1, indexvar, xvec) < 0)
	goto done;
    retval = 0;
 done:
    return retval;
}

/*! Insert xn in xp:s sorted child list (special case of ordered-by user)
 * @param[in] xp      Parent xml node. If NULL just remove from old parent.
 * @param[in] xn      Child xml node to insert under xp
 * @param[in] yn      Yang stmt of xml child node
 * @param[in] ins     Insert operation (if ordered-by user)
 * @param[in] key_val Key if LIST and ins is before/after, val if LEAF_LIST
 * @param[in] nsc_key Network namespace for key
 * @retval    i       Order where xn should be inserted into xp:s children
 * @retval   -1       Error
 * LIST: RFC 7950 7.8.6:
 * The value of the "key" attribute is the key predicates of the
 *  full instance identifier (see Section 9.13) for the list entry.
 * This means the value can be [x='a'] but the full instance-id should be prepended,
 * such as /ex:system/ex:services[x='a']
 *
 * LEAF-LIST: RFC7950 7.7.9
 *                       yang:insert="after"
 *                       yang:value="3des-cbc">blowfish-cbc</cipher>)
 */
static int
xml_insert_userorder(cxobj           *xp,
		     cxobj           *xn,
		     yang_stmt       *yn,
		     int              mid,
		     enum insert_type ins,
		     char            *key_val,
		     cvec            *nsc_key)
{
    int        retval = -1;
    int        i;
    cxobj     *xc;
    yang_stmt *yc;

    switch (ins){
    case INS_FIRST:
	for (i=mid-1; i>=0; i--){ /* decrement */
	    xc = xml_child_i(xp, i);
	    yc = xml_spec(xc);
	    if (yc != yn){
		retval = i+1;
		goto done;
	    }
	}
	retval = i+1;
	break;
    case INS_LAST:
	for (i=mid+1; i<xml_child_nr(xp); i++){ /* First increment */
	    xc = xml_child_i(xp, i);
	    yc = xml_spec(xc);
	    if (yc != yn){
		retval = i;
		goto done;
	    }
	}
	retval = i;
	break;
    case INS_BEFORE:
    case INS_AFTER: /* see retval handling different between before and after */
	if (key_val == NULL)
	    /* shouldnt happen */
	    clicon_err(OE_YANG, 0, "Missing key/value attribute when insert is before");
	else{
	    switch (yang_keyword_get(yn)){
	    case Y_LEAF_LIST:
		if ((xc = xpath_first(xp, nsc_key, "%s[.='%s']", xml_name(xn), key_val)) == NULL)
		    clicon_err(OE_YANG, 0, "bad-attribute: value, missing-instance: %s", key_val);
		else {
		    if ((i = xml_child_order(xp, xc)) < 0)
			clicon_err(OE_YANG, 0, "internal error xpath found but not in child list");
		    else
			retval = (ins==INS_BEFORE)?i:i+1;
		}
		break;
	    case Y_LIST:
		if ((xc = xpath_first(xp, nsc_key, "%s%s", xml_name(xn), key_val)) == NULL)
		    clicon_err(OE_YANG, 0, "bad-attribute: key, missing-instance: %s", key_val);
		else {
		    if ((i = xml_child_order(xp, xc)) < 0)
			clicon_err(OE_YANG, 0, "internal error xpath found but not in child list");
		    else
			retval = (ins==INS_BEFORE)?i:i+1;
		}
		break;
	    default:
		clicon_err(OE_YANG, 0, "insert only for leaf or leaf-list");
		break;
	    } /* switch */
	}
    }
 done:
    return retval;
}

/*! Insert xn in xp:s sorted child list
 * Find a point in xp childvec with two adjacent nodes xi,xi+1 such that
 * xi<=xn<=xi+1 or xn<=x0 or xmax<=xn
 * @param[in] xp      Parent xml node. If NULL just remove from old parent.
 * @param[in] xn      Child xml node to insert under xp
 * @param[in] yn      Yang stmt of xml child node
 * @param[in] yni     yang order
 * @param[in] userorder Set if ordered-by user, otherwise 0
 * @param[in] ins     Insert operation (if ordered-by user)
 * @param[in] key_val Key if LIST and ins is before/after, val if LEAF_LIST
 * @param[in] nsc_key Network namespace for key
 * @param[in] low     Lower range limit
 * @param[in] upper   Upper range limit
 * @retval    i       Order where xn should be inserted into xp:s children
 * @retval   -1       Error
 */
static int
xml_insert2(cxobj           *xp,
	    cxobj           *xn,
	    yang_stmt       *yn,
	    int              yni,
	    int              userorder,
	    enum insert_type ins,
	    char            *key_val,
	    cvec            *nsc_key,
	    int              low,
	    int              upper)
{
    int        retval = -1;
    int        mid;
    int        cmp;
    cxobj     *xc;
    yang_stmt *yc;

    if (low > upper){  /* beyond range */
	clicon_err(OE_XML, 0, "low>upper %d %d", low, upper);
	goto done;
    }
    if (low == upper){
	retval = low;
	goto done;
    }
    mid = (low + upper) / 2;
    if (mid >= xml_child_nr(xp)){  /* beyond range */
	clicon_err(OE_XML, 0, "Beyond range %d %d %d", low, mid, upper);
	goto done;
    }
    xc = xml_child_i(xp, mid);
    if ((yc = xml_spec(xc)) == NULL){
	if (xml_type(xc) != CX_ELMNT)
	    clicon_err(OE_XML, 0, "No spec found %s (wrong xml type:%s)",
		       xml_name(xc), xml_type2str(xml_type(xc)));
	else
	    clicon_err(OE_XML, 0, "No spec found %s", xml_name(xc));
	goto done;
    }
    if (yc == yn){ /* Same yang */
	if (userorder){ /* append: increment linearly until no longer equal */
	    retval = xml_insert_userorder(xp, xn, yn, mid, ins, key_val, nsc_key);
	    goto done;
	}
	else /* Ordered by system */
	    cmp = xml_cmp(xn, xc, 0, 0, NULL);
    }
    else{ /* Not equal yang - compute diff */
	cmp = yni - yang_order(yc);
	/* One case is a choice where
	 * xc = <tcp/>, xn = <udp/>
	 * same order but different yang spec
	 */
    }
    if (low +1 == upper){ /* termination criterium */
	if (cmp<0) {
	    retval = mid;
	    goto done;
	}
	retval = mid+1;
	goto done;
    }
    if (cmp == 0){
	retval = mid;
	goto done;
    }
    else if (cmp < 0)
	return xml_insert2(xp, xn, yn, yni, userorder, ins, key_val, nsc_key, low, mid);
    else
	return xml_insert2(xp, xn, yn, yni, userorder, ins, key_val, nsc_key, mid+1, upper);
 done:
    return retval;
}

/*! Insert xc as child to xp in sorted place. Remove xc from previous parent.
 * @param[in] xp      Parent xml node. If NULL just remove from old parent.
 * @param[in] x       Child xml node to insert under xp
 * @param[in] ins     Insert operation (if ordered-by user)
 * @param[in] key_val Key if x is LIST and ins is before/after, val if LEAF_LIST
 * @param[in] nsc_key Network namespace for key
 * @retval    0       OK
 * @retval   -1       Error
 * @see xml_addsub where xc is appended. xml_insert is xml_addsub();xml_sort()
 * @note It is assumed that all siblings of xi are YANG bound
 */
int
xml_insert(cxobj           *xp,
	   cxobj           *xi,
	   enum insert_type ins,
	   char            *key_val,
	   cvec            *nsc_key)
{
    int        retval = -1;
    cxobj     *xa;
    int        low = 0;
    int        upper;
    yang_stmt *y;
    int        userorder= 0;
    int        yi; /* Global yang-stmt order */
    int        i;

    /* Ensure the intermediate state that xp is parent of x but has not yet been
     * added as a child
     */
    if (xml_parent(xi) != NULL){
	clicon_err(OE_XML, 0, "XML node %s should not have parent", xml_name(xi));
	goto done;
    }
    if ((y = xml_spec(xi)) == NULL){
	clicon_err(OE_XML, 0, "No spec found %s", xml_name(xi));
	goto done;
    }
    upper = xml_child_nr(xp);
    /* Assume if there are any attributes, they are first in the list, mask
       them by raising low to skip them */
    for (low=0; low<upper; low++)
	if ((xa = xml_child_i(xp, low)) == NULL || xml_type(xa)!=CX_ATTR)
	    break;
    /* Find if non-config and if ordered-by-user */
#ifndef STATE_ORDERED_BY_SYSTEM
    if (yang_config_ancestor(y)==0)
	userorder = 1;
    else
#endif
	if (yang_keyword_get(y) == Y_LIST || yang_keyword_get(y) == Y_LEAF_LIST)
	    userorder = (yang_find(y, Y_ORDERED_BY, "user") != NULL);
    yi = yang_order(y);
    if ((i = xml_insert2(xp, xi, y, yi,
			 userorder, ins, key_val, nsc_key,
			 low, upper)) < 0)
	goto done;
    if (xml_child_insert_pos(xp, xi, i) < 0)
	goto done;
    xml_parent_set(xi, xp);
    /* clear namespace context cache of child */
    nscache_clear(xi);

    retval = 0;
 done:
    return retval;
}

/*! Verify all children of XML node are sorted according to xml_sort()
 * @param[in]   x    XML node. Check its children
 * @param[in]   arg  Dummy. Ensures xml_apply can be used with this fn
 * @retval      1    Not sortable
 * @retval      0    Sorted
 * @retval     -1    Not sorted
 * @see xml_apply
 */
int
xml_sort_verify(cxobj *x0,
		void  *arg)
{
    int    retval = -1;
    cxobj *x = NULL;
    cxobj *xprev = NULL;
#ifndef STATE_ORDERED_BY_SYSTEM
    yang_stmt *ys;

    /* Abort sort if non-config (=state) data */
    if ((ys = xml_spec(x0)) != 0 && yang_config_ancestor(ys)==0){
	retval = 1;
	goto done;
    }
#endif
    if (xml_type(x0) == CX_ELMNT){
	xml_enumerate_children(x0);
	while ((x = xml_child_each(x0, x, -1)) != NULL) {
	    if (xprev != NULL){ /* Check xprev <= x */
		if (xml_cmp(xprev, x, 1, 0, NULL) > 0)
		    goto done;
	    }
	    xprev = x;
	}
    }
    retval = 0;
 done:
    return retval;
}

/*! Given child tree x1c, find (first) matching child in base tree x0 and return as x0cp
 * @param[in]  x0      Base tree node
 * @param[in]  x1c     Modification tree child
 * @param[in]  yc      Yang spec of tree child. If null revert to linear search.
 * @param[out] x0cp    Matching base tree child (if any)
 * @retval     0       OK
 * @retval    -1       Error
 * @note only handles first match
 */
int
match_base_child(cxobj      *x0,
		 cxobj      *x1c,
		 yang_stmt  *yc,
		 cxobj     **x0cp)
{
    int          retval = -1;
    cvec        *cvk = NULL; /* vector of index keys */
    cg_var      *cvi;
    cxobj       *xb;
    char        *keyname;
    cxobj       *x0c = NULL;
    yang_stmt   *y0c;
    yang_stmt   *y0p;
    yang_stmt   *yp; /* yang parent */
    clixon_xvec *xvec = NULL;

    *x0cp = NULL; /* init return value */
    /* Revert to simple xml lookup if no yang */
    if (yc == NULL){
	*x0cp = xml_find(x0, xml_name(x1c));
	goto ok;
    }
    /* Special case is if yc parent (yp) is choice/case
     * then find x0 child with same yc even though it does not match lexically
     * However this will give another y0c != yc
     */
    if ((yp = yang_choice(yc)) != NULL){
	x0c = NULL;
	while ((x0c = xml_child_each(x0, x0c, CX_ELMNT)) != NULL) {
	    if ((y0c = xml_spec(x0c)) != NULL &&
		(y0p = yang_choice(y0c)) != NULL &&
		y0p == yp)
		break;	/* x0c will have a value */
	}
	*x0cp = x0c;
	goto ok; /* What to do if not found? */
    }
    switch (yang_keyword_get(yc)){
    case Y_CONTAINER: 	/* Equal regardless */
    case Y_LEAF: 	/* Equal regardless */
	break;
    case Y_LEAF_LIST: /* Match with name and value */
	if (xml_body(x1c) == NULL) /* Treat as empty string */
	    goto ok;
	break;
    case Y_LIST: /* Match with key values */
	cvk = yang_cvec_get(yc); /* Use Y_LIST cache, see ys_populate_list() */
	cvi = NULL;
	while ((cvi = cvec_each(cvk, cvi)) != NULL) {
	    keyname = cv_string_get(cvi);
	    if ((xb = xml_find(x1c, keyname)) == NULL)
		goto ok;
	}
    default:
	break;
    }
    if ((xvec = clixon_xvec_new()) == NULL)
	goto done;
    /* Get match. */
    if (xml_search_yang(x0, x1c, yc, 0, 0, xvec) < 0)
	goto done;
    if (clixon_xvec_len(xvec))
	*x0cp = clixon_xvec_i(xvec, 0);
 ok:
    retval = 0;
 done:
    if (xvec)
	clixon_xvec_free(xvec);
    return retval;
}

/*! API for search in XML child list with non-indexed variables
 */
static int
xml_find_noyang_cvk(char        *ns0,
		    cxobj       *xc,
		    cvec        *cvk,
		    clixon_xvec *xvec)
{
    int     retval = -1;
    cg_var *cvi;
    char   *ns;
    cxobj  *xcc;
    char   *keyname;
    char   *keyval;
    char   *body;

    cvi = NULL;
    /* Loop through index variables. xc should match all, on exit if cvi=NULL it macthes */
    while ((cvi = cvec_each(cvk, cvi)) != NULL) {
	keyname = cv_name_get(cvi);
	keyval = cv_string_get(cvi);
	if (keyname==NULL || strcmp(keyname, ".")==0){ 	    /* Index variable on form .=<val> (self) */
	    body = xml_body(xc);
	    if ((body==NULL && (keyval==NULL || strlen(keyval) == 0)) || /* both null, break */
		(body != NULL && strcmp(body, keyval) == 0)) /* Name match, break */
		continue; /* match */
	    break; /* nomatch */
	}
	else{
	    /* Index variable on form <id>=<val>
	     * Loop through children of the matched x (to match keyname and value) */
	    xcc = NULL;
	    while ((xcc = xml_child_each(xc, xcc, CX_ELMNT)) != NULL) {
		if (xml2ns(xcc, xml_prefix(xcc), &ns) < 0)
		    goto done;
		if (strcmp(ns0, ns) != 0) /* Namespace does not match, skip */
		    continue;
		if (strcmp(keyname, xml_name(xcc)) != 0) /* Name does not match, skip */
		    continue;
		body = xml_body(xcc);
		if (body==NULL && (keyval==NULL || strlen(keyval) == 0)) /* both null, break */
		    break;
		if (body != NULL &&	strcmp(body, keyval) == 0) /* Name match, break */
		    break;
	    }
	    if (xcc == NULL)
		break; /* No match found */
	}
    }
    if (cvi == NULL) /* means we iterated through all indexes without breaks */
	if (clixon_xvec_append(xvec, xc) < 0)
	    goto done;
    retval = 0;
 done:
    return retval;
}

/*! API for search in XML child list with no yang available
 * Fallback if no yang available. Only linear search for matching name, and eventual index match
 */
static int
xml_find_noyang_name(cxobj       *xp,
		     char        *ns0,
		     char        *name,
		     cvec        *cvk,
		     clixon_xvec *xvec)

{
    int     retval = -1;
    cxobj  *xc;
    char   *ns;

    if (name == NULL || ns0 == NULL){
	clicon_err(OE_XML, EINVAL, "name and namespace required");
	goto done;
    }
    /* Go through children linearly */
    xc = NULL;
    while ((xc = xml_child_each(xp, xc, CX_ELMNT)) != NULL) {
	ns = NULL;
	if (xml2ns(xc, xml_prefix(xc), &ns) < 0)
	    goto done;
	if (ns == NULL)
	    continue;
	if (strcmp(ns0, ns) != 0) /* Namespace does not match, skip */
	    continue;
	if (strcmp(name, xml_name(xc)) != 0) /* Namespace does not match, skip */
	    continue;
	if (cvk){ 	/* Check indexes */
	    if (xml_find_noyang_cvk(ns0, xc, cvk, xvec) < 0)
		goto done;
	}
	else /* No index variables: just add node to found list */
	    if (clixon_xvec_append(xvec, xc) < 0)
		goto done;
    }
    retval = 0;
 done:
    return retval;
}

/*! Try to find an XML child from parent with yang available using list keys and leaf-lists
 *
 * Must be populated with Yang specs, parent must be list or leaf-list, and (for list) search
 * index MUST be keys in the order they are declared.
 * First identify that this search qualifies for yang-based list/leaf-list optimized search,
 * - if no, revert (return 0) so that the overlying algorithm can try next or fallback to
 *   linear seacrh
 * - if yes, then construct a dummy search object and find it in the list of xp:s children
 *   using binary search
 * @param[in]  xp    Parent xml node.
 * @param[in]  yc    Yang spec of list child (preferred) See rule (2) above
 * @param[in]  cvk   List of keys and values as CLIgen vector on the form k1=foo, k2=bar
 * @param[out] xvec  Array of found nodes
 * @retval     1     OK
 * @retval     0     Revert, try again with no-yang search
 * @retval    -1     Error
 */
static int
xml_find_index_yang(cxobj       *xp,
		    yang_stmt   *yc,
		    cvec        *cvk,
		    clixon_xvec *xvec)
{
    int        retval = -1;
    cxobj     *xc = NULL;
    cxobj     *xk;
    cg_var    *cvi = NULL;
    cbuf      *cb = NULL;
    yang_stmt *yk;
    char      *kname;
    cvec      *ycvk;
    cg_var    *ycv = NULL;
    int        i;
    char      *name;
    int        revert = 0;
    char      *indexvar = NULL;

    if (xp == NULL){
	clicon_err(OE_XML, EINVAL, "xp is NULL");
	goto done;
    }
    name = yang_argument_get(yc);
    if ((cb = cbuf_new()) == NULL){
	clicon_err(OE_UNIX, errno, "cbuf_new");
	goto done;
    }
    switch (yang_keyword_get(yc)){
    case Y_LIST:
	cprintf(cb, "<%s>", name);
	ycvk = yang_cvec_get(yc); /* Check that those are proper index keys */
	cvi = NULL;
	if (cvk == NULL){ /* If list and no keys, all should match */
	    revert++;
	    break;
	}
	i = 0;
	while ((cvi = cvec_each(cvk, cvi)) != NULL) {
	    if ((kname = cv_name_get(cvi)) == NULL){
		clicon_err(OE_YANG, ENOENT, "missing yang key name in cvk");
		goto done;
	    }
	    /* Parameter in cvk is not key or not in right key order, then we cannot call
	     * xml_find_keys and we need to revert to noyang
	     */
	    if ((ycv = cvec_i(ycvk, i)) == NULL || strcmp(kname, cv_string_get(ycv))){
		revert++;
		break;
	    }
	    cprintf(cb, "<%s>%s</%s>", kname, cv_string_get(cvi), kname);
	    i++;
	}
	if (revert)
	    break;
	cprintf(cb, "</%s>", name);
	break;
    case Y_LEAF_LIST:
	if (cvec_len(cvk) != 1){
	    clicon_err(OE_YANG, ENOENT, "expected exactly one leaf-list key");
	    goto done;
	}
	cvi = cvec_i(cvk, 0);
	cprintf(cb, "<%s>%s</%s>", name, cv_string_get(cvi), name);
	break;
    default:
	cprintf(cb, "<%s/>", name);
	break;
    }
#ifdef XML_EXPLICIT_INDEX
    if (revert){
	char      *iname;
	yang_stmt *yi;
	if (cvec_len(cvk) != 1 ||
	    (cvi = cvec_i(cvk, 0)) == NULL ||
	    (iname = cv_name_get(cvi)) == NULL ||
	    (yi = yang_find_datanode(yc, iname)) == NULL ||
	    yang_flag_get(yi, YANG_FLAG_INDEX) == 0)
	    goto revert;
	cbuf_reset(cb);
	cprintf(cb, "<%s><%s>%s</%s></%s>", name, iname, cv_string_get(cvi), iname, name);
	indexvar = iname;
    }
#else
    if (revert)
	goto revert;
#endif
    if (clixon_xml_parse_string(cbuf_get(cb), YB_NONE, NULL, &xc, NULL) < 0)
	goto done;
    if (xml_rootchild(xc, 0, &xc) < 0)
	goto done;
    /* Populate created XML tree with yang specs */
    if (xml_spec_set(xc, yc) < 0)
	goto done;
    xk = NULL;
    while ((xk = xml_child_each(xc, xk, CX_ELMNT)) != NULL) {
	if ((yk = yang_find(yc, Y_LEAF, xml_name(xk))) == NULL){
	    clicon_err(OE_YANG, ENOENT, "yang spec of key %s not found", xml_name(xk));
	    goto done;
	}
	if (xml_spec_set(xk, yk) < 0)
	    goto done;
    }
    if (xml_search_yang(xp, xc, yc, 1, indexvar, xvec) < 0)
	goto done;
    retval = 1; /* OK */
 done:
    if (cb)
	cbuf_free(cb);
    if (xc)
	xml_free(xc);
    return retval;
 revert: /* means give up yang/key search, try next (eg explicit/noyang) */
    retval = 0;
    goto done;
}

/*! API for search in XML child list using indexes and binary search if applicable
 *
 * Generic search function as alternative to xml_find() and others that finds YANG associated
 * children of an XML tree node using indexes and optimized lookup. Optimized lookup is used only
 * if an associated YANG exists. The optimized lookup is based on binary trees but is used
 * The function takes as input:
 * 1) An XML tree (parent) node (cxobj). See note(1) below
 * 2) A set of parameters to define wanted children by name or yang-spec using yc, name, ns, yp:
 *   a. yp and ns:name given: YANG spec of parent + ns:name derives yc. Not found: only ns:name
 *   b. name given: yp is derived from xp spec, then goto 2b above.
 * 3) A vector of index expressions on the form <id>=<val> refining the child set:
 *   a. cvk is NULL, return all children matching according to (B)
 *   b. cvk contains <id>=<val> entries, return children with <id> leafs matching <val>.
 *       See "Optimized" section below.
 * 4) A return vector of XML nodes matching name and index variables
 *
 * # Optimized
 * The function makes the index matching <id>=<val> above optimized using binary search if:
 * - yc is defined AND one of the following
 * - if xp is leaf-list and "id" is "."
 * - if xp is a yang list and "id" is a registered index key
 * - if xp is a yang list and first "id" is first leaf key, second "id" is second leaf key, etc.
 * - Otherwise search is made using linear search
 *
 * @param[in]  xp     Parent xml node.
 * @param[in]  yp     Yang spec of parent node or yang-spec/yang (Alternative if yc not given).
 * @param[in]  ns     Namespace (needed only if name is derived from top-symbol)
 * @param[in]  name   Name of child
 * @param[in]  cvk    List of keys and values as CLIgen vector on the form k1=foo, k2=bar
 * @param[out] xvec   Array of result nodes. Must be initialized on entry
 * @retval     0      OK, see xret
 * @retval    -1      Error
 * @code
 *    clixon_xvec *xv = NULL;
 *    cvec        *cvk = NULL; vector of index keys
 *    cxobj       *x;
 *    ... Populate cvk with key/values eg a:5 b:6
 *    if ((xv = clixon_xvec_new()) == NULL)
 *       err;
 *    if (clixon_xml_find_index(xp, yp, NULL, "a", ns, cvk, xv) < 0)
 *       err;
 *    for (i=0; i<clixon_xvec_len(xv); i++){
 *       x = clixon_xpath_i(xv, i);
 *       ...
 *    }
 *    clixon_xvec_free(xvec);
 * @endcode
 * Discussion:
 * (1) Rule 2 on how to get the child name election seems unecessary complex. First, it would be
 * nice to just state name and parent 2c. But xp as top-objects may sometimes be dummies, for
 * parsing, copy-buffers, or simply for XML nodes that do not have YANG.
 */
int
clixon_xml_find_index(cxobj        *xp,
		      yang_stmt    *yp,
		      char         *ns,
		      char         *name,
		      cvec         *cvk,
		      clixon_xvec  *xvec)
{
    int        retval = -1;
    int        ret;
    yang_stmt *yc = NULL;

    if (xvec == NULL){
	clicon_err(OE_YANG, EINVAL, "xvec");
	goto done;
    }
    if (name == NULL){
	clicon_err(OE_YANG, EINVAL, "name");
	goto done;
    }
    if (yp == NULL)
	yp = xml_spec(xp);
    if (yp){/* 2. YANG spec of parent + name derives yc. If not found use just name. */
	if (yang_keyword_get(yp) == Y_SPEC)
	    yp = yang_find_module_by_namespace(yp, ns);
	if (yp)
	    yc = yang_find_datanode(yp, name);
    }
    if (yc){
	if ((ret = xml_find_index_yang(xp, yc, cvk, xvec)) < 0)
	    goto done;
	if (ret == 0){ /* This means yang method did not work for some reason
			* such as not being list key indexes in cvk, for example
			*/
	    if (xml_find_noyang_name(xp, ns, name, cvk, xvec) < 0)
		goto done;
	}
    }
    else
	if (xml_find_noyang_name(xp, ns, name, cvk, xvec) < 0)
	    goto done;
    retval = 0;
 done:
    return retval;
}

/*! Find positional parameter in xml child list, eg x/y[42]. Note, not optimized
 *
 * Create a temporary search object: a list (xc) with a key (xk) and call the binary search.
 * @param[in]  xp     Parent xml node.
 * @param[in]  yc     Yang spec of list child
 * @param[in]  pos    Position
 * @param[out] xvec   Array of found nodes
 * @retval     0      OK, see xret
 * @retval    -1      Error
 */
int
clixon_xml_find_pos(cxobj        *xp,
		    yang_stmt    *yc,
		    uint32_t      pos,
		    clixon_xvec  *xvec)
{
    int        retval = -1;
    cxobj     *xc = NULL;
    char      *name;
    uint32_t   u;

    if (yc == NULL){
	clicon_err(OE_YANG, ENOENT, "yang spec not found");
	goto done;
    }
    name = yang_argument_get(yc);
    u = 0;
    xc = NULL;
    while ((xc = xml_child_each(xp, xc, CX_ELMNT)) != NULL) {
	if (strcmp(name, xml_name(xc)))
	    continue;
	if (pos == u++){ /* Found */
	    if (clixon_xvec_append(xvec, xc) < 0)
		goto done;
	    break;
	}
    }
    retval = 0;
 done:
    return retval;
}