text: /* Portions of this file are subject to the following copyright(s).  See
   * the Net-SNMP's COPYING file for more details and other copyrights
   * that may apply:
   */
  /*
   * Portions of this file are copyrighted by:
   * Copyright (C) 2007 Apple, Inc. All rights reserved.
   * Use is subject to license terms specified in the COPYING file
   * distributed with the Net-SNMP package.
   *
   * Portions of this file are copyrighted by:
   * Copyright (c) 2016 VMware, Inc. All rights reserved.
   * Use is subject to license terms specified in the COPYING file
   * distributed with the Net-SNMP package.
   */
  #include <net-snmp/net-snmp-config.h>
  #include <net-snmp/net-snmp-features.h>
  #include <net-snmp/net-snmp-includes.h>
  #include <net-snmp/library/container.h>
  #include <net-snmp/library/container_binary_array.h>
  #include <net-snmp/library/container_list_ssll.h>
  #include <net-snmp/library/container_null.h>
  #include "factory.h"
  
  #include <stdint.h>
  
  netsnmp_feature_child_of(container_all, libnetsnmp);
  
  netsnmp_feature_child_of(container_factories, container_all);
  netsnmp_feature_child_of(container_types, container_all);
  netsnmp_feature_child_of(container_compare, container_all);
  netsnmp_feature_child_of(container_dup, container_all);
  netsnmp_feature_child_of(container_free_all, container_all);
  netsnmp_feature_child_of(subcontainer_find, container_all);
  
  netsnmp_feature_child_of(container_ncompare_cstring, container_compare);
  netsnmp_feature_child_of(container_compare_mem, container_compare);
  netsnmp_feature_child_of(container_compare_long, container_compare);
  netsnmp_feature_child_of(container_compare_ulong, container_compare);
  netsnmp_feature_child_of(container_compare_int32, container_compare);
  netsnmp_feature_child_of(container_compare_uint32, container_compare);
  
  netsnmp_feature_child_of(container_find_factory, container_factories);
  
  /** @defgroup container container
   */
  
  /*------------------------------------------------------------------
   */
  static netsnmp_container *containers = NULL;
  
  typedef struct container_type_s {
     const char                 *name;
     netsnmp_factory            *factory;
     netsnmp_container_compare  *compare;
  } container_type;
  
  netsnmp_factory *
  netsnmp_container_get_factory(const char *type);
  
  /*------------------------------------------------------------------
   */
  static void 
  _factory_free(void *dat, void *context)
  {
      container_type *data = (container_type *)dat;
      if (data == NULL)
  	return;
      
      if (data->name != NULL) {
          DEBUGMSGTL(("container", "  _factory_free_list() called for %s\n",
                      data->name));
  	free(NETSNMP_REMOVE_CONST(void *, data->name)); /* SNMP_FREE wasted on object about to be freed */
      }
      free(data); /* SNMP_FREE wasted on param */
  }
  
  /*------------------------------------------------------------------
   */
  void
  netsnmp_container_init_list(void)
  {
      if (NULL != containers)
          return;
  
      /*
       * create a binary arry container to hold container
       * factories
       */
      containers = netsnmp_container_get_binary_array();
      containers->compare = netsnmp_compare_cstring;
      containers->container_name = strdup("container list");
  
      /*
       * register containers
       */
      netsnmp_container_binary_array_init();
  #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_LINKED_LIST
      netsnmp_container_ssll_init();
  #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_LINKED_LIST */
  #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_NULL
      netsnmp_container_null_init();
  #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_NULL */
  
      /*
       * default aliases for some containers
       */
      netsnmp_container_register("table_container",
                                 netsnmp_container_get_factory("binary_array"));
  
  #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_LINKED_LIST
      netsnmp_container_register("linked_list",
                                 netsnmp_container_get_factory("sorted_singly_linked_list"));
      netsnmp_container_register("ssll_container",
                                 netsnmp_container_get_factory("sorted_singly_linked_list"));
  #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_LINKED_LIST */
  
      netsnmp_container_register_with_compare
          ("cstring", netsnmp_container_get_factory("binary_array"),
           netsnmp_compare_direct_cstring);
  
      netsnmp_container_register_with_compare
          ("string", netsnmp_container_get_factory("binary_array"),
           netsnmp_compare_cstring);
      netsnmp_container_register_with_compare
          ("string_binary_array", netsnmp_container_get_factory("binary_array"),
           netsnmp_compare_cstring);
  
  }
  
  void
  netsnmp_container_free_list(void)
  {
      DEBUGMSGTL(("container", "netsnmp_container_free_list() called\n"));
      if (containers == NULL)
  	return;
  
      /*
       * free memory used by each factory entry
       */
      CONTAINER_FOR_EACH(containers, ((netsnmp_container_obj_func *)_factory_free), NULL);
  
      /*
       * free factory container
       */
      CONTAINER_FREE(containers);
      containers = NULL;
  }
  
  int
  netsnmp_container_register_with_compare(const char* name, netsnmp_factory *f,
                                          netsnmp_container_compare  *c)
  {
      container_type *ct, tmp;
  
      if (NULL==containers)
          return -1;
  
      tmp.name = NETSNMP_REMOVE_CONST(char *, name);
      ct = (container_type *)CONTAINER_FIND(containers, &tmp);
      if (NULL!=ct) {
          DEBUGMSGT(("container_registry",
                     "replacing previous container factory\n"));
          ct->factory = f;
      }
      else {
          ct = SNMP_MALLOC_TYPEDEF(container_type);
          if (NULL == ct)
              return -1;
          ct->name = strdup(name);
          ct->factory = f;
          ct->compare = c;
          CONTAINER_INSERT(containers, ct);
      }
      DEBUGMSGT(("container_registry", "registered container factory %s (%s)\n",
                 ct->name, f->product));
  
      return 0;
  }
  
  int
  netsnmp_container_register(const char* name, netsnmp_factory *f)
  {
      return netsnmp_container_register_with_compare(name, f, NULL);
  }
  
  /*------------------------------------------------------------------
   */
  netsnmp_factory *
  netsnmp_container_get_factory(const char *type)
  {
      container_type ct, *found;
      
      if (NULL==containers)
          return NULL;
  
      ct.name = type;
      found = (container_type *)CONTAINER_FIND(containers, &ct);
  
      return found ? found->factory : NULL;
  }
  
  #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_FIND_FACTORY
  netsnmp_factory *
  netsnmp_container_find_factory(const char *type_list)
  {
      netsnmp_factory   *f = NULL;
      char              *list, *entry;
      char              *st = NULL;
  
      if (NULL==type_list)
          return NULL;
  
      list = strdup(type_list);
      if (!list)
          return NULL;
      entry = strtok_r(list, ":", &st);
      while (entry) {
          f = netsnmp_container_get_factory(entry);
          if (NULL != f)
              break;
          entry = strtok_r(NULL, ":", &st);
      }
  
      free(list);
      return f;
  }
  #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_FIND_FACTORY */
  
  /*------------------------------------------------------------------
   */
  static container_type *
  netsnmp_container_get_ct(const char *type)
  {
      container_type ct;
  
      if (NULL == containers)
          return NULL;
      
      ct.name = type;
      return (container_type *)CONTAINER_FIND(containers, &ct);
  }
  
  static container_type *
  netsnmp_container_find_ct(const char *type_list)
  {
      container_type    *ct = NULL;
      char              *list, *entry;
      char              *st = NULL;
  
      if (NULL==type_list)
          return NULL;
  
      list = strdup(type_list);
      if (!list)
          return NULL;
      entry = strtok_r(list, ":", &st);
      while (entry) {
          ct = netsnmp_container_get_ct(entry);
          if (NULL != ct)
              break;
          entry = strtok_r(NULL, ":", &st);
      }
  
      free(list);
      return ct;
  }
  
  
  
  /*------------------------------------------------------------------
   */
  netsnmp_container *
  netsnmp_container_get(const char *type)
  {
      netsnmp_container *c;
      container_type *ct = netsnmp_container_get_ct(type);
      if (ct) {
          c = (netsnmp_container *)(ct->factory->produce());
          if (c && ct->compare)
              c->compare = ct->compare;
          return c;
      }
  
      return NULL;
  }
  
  /**
   * Allocate a new container of a given type.
   *
   * @param type A colon-separated string with the container name, followed by
   * a colon-separated list of container types.
   *
   * Creates a new container. The type of the container is the first type
   * mentioned in @type for which a factory has been registered with
   * netsnmp_container_register_with_compare() or netsnmp_container_register().
   */
  netsnmp_container *
  netsnmp_container_find(const char *type)
  {
      container_type *ct = netsnmp_container_find_ct(type);
      netsnmp_container *c = ct ? (netsnmp_container *)(ct->factory->produce()) : NULL;
  
      /*
       * provide default compare
       */
      if (c) {
          if (ct->compare)
              c->compare = ct->compare;
          else if (NULL == c->compare)
              c->compare = netsnmp_compare_netsnmp_index;
      }
  
      return c;
  }
  
  /*------------------------------------------------------------------
   */
  void
  netsnmp_container_add_index(netsnmp_container *primary,
                              netsnmp_container *new_index)
  {
      netsnmp_container *curr = primary;
  
      if((NULL == new_index) || (NULL == primary)) {
          snmp_log(LOG_ERR, "add index called with null pointer\n");
          return;
      }
  
      while(curr->next)
          curr = curr->next;
  
      curr->next = new_index;
      new_index->prev = curr;
  }
  
  int CONTAINER_INSERT_HELPER(netsnmp_container* x, const void* k)
  {
      while(x && x->insert_filter && x->insert_filter(x,k) == 1)
          x = x->next;
      if(x) {
          int rc = x->insert(x,k);
          if(rc)
              snmp_log(LOG_DEBUG,"error on subcontainer '%s' insert (%d)\n",
                       x->container_name ? x->container_name : "", rc);
          else {
              rc = CONTAINER_INSERT_HELPER(x->next, k);
              if(rc)
                  x->remove(x,k);
          }
          return rc;
      }
      return 0;
  }
  
  int CONTAINER_INSERT(netsnmp_container* x, const void* k)
  {
      /** start at first container */
      while(x->prev)
          x = x->prev;
      return CONTAINER_INSERT_HELPER(x, k);
  }
  
  int CONTAINER_INSERT_BEFORE(netsnmp_container *x, size_t pos, void *k)
  {
      int rc = 0;
  
      if (NULL == x || NULL == x->insert_before) {
          snmp_log(LOG_ERR, "container '%s' does not support insert_before\n",
                   x && x->container_name ? x->container_name : "");
          return -1;
      }
  
      rc = x->insert_before(x, pos, k);
      if (rc < 0)
          snmp_log(LOG_ERR, "error on container '%s' insert_before %" NETSNMP_PRIz "d (%d)\n",
                   x->container_name ? x->container_name : "", pos, rc);
  
      return rc;
  }
  
  int CONTAINER_REMOVE(netsnmp_container *x, const void *k)
  {
      int rc2, rc = 0;
      
      /** start at last container */
      while(x->next)
          x = x->next;
      while(x) {
          rc2 = x->remove(x,k);
          /** ignore remove errors if there is a filter in place */
          if ((rc2) && (NULL == x->insert_filter)) {
              snmp_log(LOG_ERR,"error on subcontainer '%s' remove (%d)\n",
                       x->container_name ? x->container_name : "", rc2);
              rc = rc2;
          }
          x = x->prev;
          
      }
      return rc;
  }
  
  int CONTAINER_REMOVE_AT(netsnmp_container *x, size_t pos, void **k)
  {
      int rc = 0;
      netsnmp_container *orig = x;
  
      if (NULL == x || NULL == x->remove_at) {
          snmp_log(LOG_ERR, "container '%s' does not support REMOVE_AT\n",
                   x && x->container_name ? x->container_name : "");
          return -1;
      }
  
      /** start at given container */
      rc = x->remove_at(x, pos, k);
      if (rc < 0) {
          snmp_log(LOG_ERR, "error on container '%s' remove_at %" NETSNMP_PRIz "d (%d)\n",
                   x->container_name ? x->container_name : "", pos, rc);
          return rc;
      } else if (NULL == k || NULL == *k)
          return rc;
  
      /** remove k from any other containers */
      while(x->prev)
          x = x->prev;
      for(; x; x = x->next) {
          if (x == orig)
              continue;
          x->remove(x,*k); /** ignore remove errors in other containers */
      }
      return rc;
  }
  
  int CONTAINER_GET_AT(netsnmp_container *x, size_t pos, void **k)
  {
      int rc = 0;
  
      if (NULL == x || NULL == x->get_at) {
          snmp_log(LOG_ERR, "container '%s' does not support GET_AT\n",
                   x && x->container_name ? x->container_name : "");
          return -1;
      }
  
      /** start at given container */
      rc = x->get_at(x, pos, k);
      if (rc < 0)
          snmp_log(LOG_ERR, "error on container '%s' get_at %" NETSNMP_PRIz "d (%d)\n",
                   x->container_name ? x->container_name : "", pos, rc);
  
      return rc;
  }
  
  #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_DUP
  netsnmp_container *CONTAINER_DUP(netsnmp_container *x, void *ctx, u_int flags)
  {
      if (NULL == x->duplicate) {
          snmp_log(LOG_ERR, "container '%s' does not support duplicate\n",
                   x->container_name ? x->container_name : "");
          return NULL;
      }
      return x->duplicate(x, ctx, flags);
  }
  #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_DUP */
  
  int CONTAINER_FREE(netsnmp_container *x)
  {
      int  rc2, rc = 0;
  
      if (!x)
          return rc;
  
      /** start at last container */
      while(x->next)
          x = x->next;
      while(x) {
          netsnmp_container *tmp;
          char *name;
          tmp = x->prev;
          name = x->container_name;
          x->container_name = NULL;
          rc2 = x->cfree(x);
          if (rc2) {
              snmp_log(LOG_ERR,"error on subcontainer '%s' cfree (%d)\n",
                       name ? name : "", rc2);
              rc = rc2;
          }
          SNMP_FREE(name);
          x = tmp;
      }
      return rc;
  }
  
  /*
   * clear all containers. When clearing the *first* container, and
   * *only* the first container, call the function f for each item.
   * After calling this function, all containers should be empty.
   */
  void CONTAINER_CLEAR(netsnmp_container *x, netsnmp_container_obj_func *f,
                      void *c)
  {
      /** start at last container */
      while(x->next)
          x = x->next;
      while(x->prev) {
          x->clear(x, NULL, c);
          x = x->prev;
      }
      x->clear(x, f, c);
  }
  
  #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_FREE_ALL
  /*
   * clear all containers. When clearing the *first* container, and
   * *only* the first container, call the free_item function for each item.
   * After calling this function, all containers should be empty.
   */
  void CONTAINER_FREE_ALL(netsnmp_container *x, void *c)
  {
      CONTAINER_CLEAR(x, x->free_item, c);
  }
  #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_FREE_ALL */
  
  #ifndef NETSNMP_FEATURE_REMOVE_SUBCONTAINER_FIND
  /*
   * Find a sub-container with the given name
   */
  netsnmp_container *SUBCONTAINER_FIND(netsnmp_container *x,
                                       const char* name)
  {
      if ((NULL == x) || (NULL == name))
          return NULL;
      
      /** start at first container */
      while(x->prev)
          x = x->prev;
      while(x) {
          if ((NULL != x->container_name) && (0 == strcmp(name,x->container_name)))
              break;
          x = x->next;
      }
      return x;
  }
  #endif /* NETSNMP_FEATURE_REMOVE_SUBCONTAINER_FIND */
  
  
  /*------------------------------------------------------------------
   */
  void
  netsnmp_init_container(netsnmp_container         *c,
                         netsnmp_container_rc      *init,
                         netsnmp_container_rc      *cfree,
                         netsnmp_container_size    *size,
                         netsnmp_container_compare *cmp,
                         netsnmp_container_op      *ins,
                         netsnmp_container_op      *rem,
                         netsnmp_container_rtn     *fnd)
  {
      if (c == NULL)
          return;
  
      c->init = init;
      c->cfree = cfree;
      c->get_size = size;
      c->compare = cmp;
      c->insert = ins;
      c->remove = rem;
      c->find = fnd;
      c->free_item = netsnmp_container_simple_free;
  }
  
  int
  netsnmp_container_data_dup(netsnmp_container *dup, netsnmp_container *c)
  {
      if (!dup || !c)
          return -1;
  
      if (c->container_name)
          dup->container_name = strdup(c->container_name);
      dup->compare = c->compare;
      dup->ncompare = c->ncompare;
      dup->release = c->release;
      dup->insert_filter = c->insert_filter;
      dup->free_item = c->free_item;
      dup->sync = c->sync;
      dup->flags = c->flags;
  
      return 0;
  }
  
  /*------------------------------------------------------------------
   *
   * simple comparison routines
   *
   */
  int
  netsnmp_compare_netsnmp_index(const void *lhs_arg, const void *rhs_arg)
  {
      const netsnmp_index *lhs = lhs_arg;
      const netsnmp_index *rhs = rhs_arg;
      int rc;
  
      netsnmp_assert(lhs && rhs);
      DEBUGIF("compare:index") {
          DEBUGMSGT(("compare:index", "compare "));
          DEBUGMSGSUBOID(("compare:index", lhs->oids, lhs->len));
          DEBUGMSG(("compare:index", " to "));
          DEBUGMSGSUBOID(("compare:index", rhs->oids, rhs->len));
          DEBUGMSG(("compare:index", "\n"));
      }
      rc = snmp_oid_compare(lhs->oids, lhs->len, rhs->oids, rhs->len);
      DEBUGMSGT(("compare:index", "result was %d\n", rc));
      return rc;
  }
  
  int
  netsnmp_ncompare_netsnmp_index(const void *lhs_arg, const void *rhs_arg)
  {
      const netsnmp_index *lhs = lhs_arg;
      const netsnmp_index *rhs = rhs_arg;
      int rc;
  
      netsnmp_assert(lhs && rhs);
      DEBUGIF("compare:index") {
          DEBUGMSGT(("compare:index", "compare "));
          DEBUGMSGSUBOID(("compare:index", lhs->oids, lhs->len));
          DEBUGMSG(("compare:index", " to "));
          DEBUGMSGSUBOID(("compare:index", rhs->oids, rhs->len));
          DEBUGMSG(("compare:index", "\n"));
      }
      rc = snmp_oid_ncompare(lhs->oids, lhs->len, rhs->oids, rhs->len, rhs->len);
      DEBUGMSGT(("compare:index", "result was %d\n", rc));
      return rc;
  }
  
  int
  netsnmp_compare_cstring(const void *lhs_arg, const void *rhs_arg)
  {
      const container_type *lhs = lhs_arg;
      const container_type *rhs = rhs_arg;
  
      return strcmp(lhs->name, rhs->name);
  }
  
  #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_NCOMPARE_CSTRING
  int
  netsnmp_ncompare_cstring(const void *lhs_arg, const void *rhs_arg)
  {
      const container_type *lhs = lhs_arg;
      const container_type *rhs = rhs_arg;
  
      return strncmp(lhs->name, rhs->name, strlen(rhs->name));
  }
  #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_NCOMPARE_CSTRING */
  
  int
  netsnmp_compare_direct_cstring(const void * lhs, const void * rhs)
  {
      return strcmp(lhs, rhs);
  }
  
  /*
   * compare two memory buffers
   *
   * since snmp strings aren't NULL terminated, we can't use strcmp. So
   * compare up to the length of the smaller, and then use length to
   * break any ties.
   */
  #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_COMPARE_MEM
  int
  netsnmp_compare_mem(const char * lhs, size_t lhs_len,
                      const char * rhs, size_t rhs_len)
  {
      int rc, min = SNMP_MIN(lhs_len, rhs_len);
  
      rc = memcmp(lhs, rhs, min);
      return rc ? rc : lhs_len - rhs_len;
  }
  #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_COMPARE_MEM */
  
  #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_COMPARE_LONG
  int
  netsnmp_compare_long(const void * lhs, const void * rhs)
  {
      typedef struct { long index; } dummy;
  
      const dummy *lhd = (const dummy*)lhs;
      const dummy *rhd = (const dummy*)rhs;
  
      if (lhd->index < rhd->index)
          return -1;
      else if (lhd->index > rhd->index)
          return 1;
  
      return 0;
  }
  #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_COMPARE_LONG */
  
  #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_COMPARE_ULONG
  int
  netsnmp_compare_ulong(const void * lhs, const void * rhs)
  {
      typedef struct { u_long index; } dummy;
  
      const dummy *lhd = (const dummy*)lhs;
      const dummy *rhd = (const dummy*)rhs;
  
      if (lhd->index < rhd->index)
          return -1;
      else if (lhd->index > rhd->index)
          return 1;
  
      return 0;
  }
  #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_COMPARE_ULONG */
  
  #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_COMPARE_INT32
  int
  netsnmp_compare_int32(const void * lhs, const void * rhs)
  {
      typedef struct { int32_t index; } dummy;
  
      const dummy *lhd = (const dummy*)lhs;
      const dummy *rhd = (const dummy*)rhs;
  
      if (lhd->index < rhd->index)
          return -1;
      else if (lhd->index > rhd->index)
          return 1;
  
      return 0;
  }
  #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_COMPARE_INT32 */
  
  #ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_COMPARE_UINT32
  int
  netsnmp_compare_uint32(const void * lhs, const void * rhs)
  {
      typedef struct { uint32_t index; } dummy;
  
      const dummy *lhd = (const dummy*)lhs;
      const dummy *rhd = (const dummy*)rhs;
  
      if (lhd->index < rhd->index)
          return -1;
      else if (lhd->index > rhd->index)
          return 1;
  
      return 0;
  }
  #endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_COMPARE_UINT32 */
  
  /*------------------------------------------------------------------
   * netsnmp_container_simple_free
   *
   * useful function to pass to CONTAINER_FOR_EACH, when a simple
   * free is needed for every item.
   */
  void 
  netsnmp_container_simple_free(void *data, void *context)
  {
      if (data == NULL)
  	return;
      
      DEBUGMSGTL(("verbose:container",
                  "netsnmp_container_simple_free) called for %p/%p\n",
                  data, context));
      free((void*)data); /* SNMP_FREE wasted on param */
  }
  