path: root/lib/includes/hicn/util/set.h

/*
 * Copyright (c) 2021 Cisco and/or its affiliates.
 * 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.
 */

#ifndef UTIL_SET_H
#define UTIL_SET_H

#include <hicn/util/log.h>
#include <search.h>
#include <string.h>
//#if !defined(__ANDROID__) && !defined(__APPLE__)
//#include <threads.h>
//#else
#define thread_local _Thread_local
//#endif /* ! __ANDROID__ */

#define ERR_SET_EXISTS	  -2
#define ERR_SET_NOT_FOUND -3

/* FIXME: buffer overflow when this is too small... investigate */
#define BUFSIZE 1024

static inline int
int_cmp (const int x, const int y)
{
  return x - y;
}

static inline int
int_snprintf (char *buf, size_t size, int value)
{
  return snprintf (buf, size, "%d", value);
}

static inline int
string_snprintf (char *buf, size_t size, const char *s)
{
  return snprintf (buf, size, "%s", s);
}

static inline int
generic_snprintf (char *buf, size_t size, const void *value)
{
  return snprintf (buf, BUFSIZE, "%p", value);
}

typedef int (*cmp_t) (const void *x, const void *y);

#define TYPEDEF_SET_H(NAME, T)                                                \
                                                                              \
  typedef struct                                                              \
  {                                                                           \
    size_t size;                                                              \
    void *root;                                                               \
  } NAME##_t;                                                                 \
                                                                              \
  int NAME##_initialize (NAME##_t *set);                                      \
                                                                              \
  int NAME##_finalize (NAME##_t *set);                                        \
                                                                              \
  NAME##_t *NAME##_create ();                                                 \
                                                                              \
  void NAME##_free (NAME##_t *set);                                           \
                                                                              \
  int NAME##_add (NAME##_t *set, const T element);                            \
                                                                              \
  int NAME##_remove (NAME##_t *set, const T search, T *element);              \
                                                                              \
  int NAME##_clear (NAME##_t *set);                                           \
                                                                              \
  int NAME##_get (const NAME##_t *set, const T search, T *element);           \
                                                                              \
  int NAME##_get_array (const NAME##_t *set, T **element);                    \
                                                                              \
  void NAME##_dump (NAME##_t *set);

#define TYPEDEF_SET(NAME, T, CMP, SNPRINTF)                                   \
  int NAME##_initialize (NAME##_t *set)                                       \
  {                                                                           \
    set->root = NULL;                                                         \
    set->size = 0;                                                            \
    return 0;                                                                 \
  }                                                                           \
                                                                              \
  int NAME##_finalize (NAME##_t *set) { return NAME##_clear (set); }          \
                                                                              \
  NAME##_t *NAME##_create ()                                                  \
  {                                                                           \
    NAME##_t *set = malloc (sizeof (NAME##_t));                               \
    if (!set)                                                                 \
      goto ERR_MALLOC;                                                        \
                                                                              \
    if (NAME##_initialize (set) < 0)                                          \
      goto ERR_INITIALIZE;                                                    \
                                                                              \
    return set;                                                               \
                                                                              \
  ERR_INITIALIZE:                                                             \
    free (set);                                                               \
  ERR_MALLOC:                                                                 \
    return NULL;                                                              \
  }                                                                           \
                                                                              \
  void NAME##_free (NAME##_t *set)                                            \
  {                                                                           \
    NAME##_finalize (set);                                                    \
    free (set);                                                               \
  }                                                                           \
                                                                              \
  int NAME##_add (NAME##_t *set, const T element)                             \
  {                                                                           \
    T *found = tfind (element, &set->root, (cmp_t) CMP);                      \
    void *ptr = tsearch (element, &set->root, (cmp_t) CMP);                   \
    if (!ptr)                                                                 \
      return -1;                                                              \
    if (!found)                                                               \
      set->size++;                                                            \
    return 0;                                                                 \
  }                                                                           \
                                                                              \
  int NAME##_remove (NAME##_t *set, const T search, T *element)               \
  {                                                                           \
    T *found = tfind (search, &set->root, (cmp_t) CMP);                       \
    if (!found)                                                               \
      return ERR_SET_NOT_FOUND;                                               \
    if (element)                                                              \
      *element = *found;                                                      \
    tdelete (search, &set->root, (cmp_t) CMP);                                \
    set->size--;                                                              \
    return 0;                                                                 \
  }                                                                           \
                                                                              \
  int NAME##_clear (NAME##_t *set)                                            \
  {                                                                           \
    T *array;                                                                 \
    int n = NAME##_get_array (set, &array);                                   \
    if (n < 0)                                                                \
      return -1;                                                              \
    for (unsigned i = 0; i < n; i++)                                          \
      {                                                                       \
	T element = array[i];                                                 \
	NAME##_remove (set, element, NULL);                                   \
      }                                                                       \
    free (array);                                                             \
    return 0;                                                                 \
  }                                                                           \
                                                                              \
  int NAME##_get (const NAME##_t *set, const T search, T *element)            \
  {                                                                           \
    T *found = tfind (search, &set->root, (cmp_t) CMP);                       \
    if (element)                                                              \
      *element = found ? *found : NULL;                                       \
    return 0;                                                                 \
  }                                                                           \
                                                                              \
  static void NAME##_dump_node (const void *nodep, const VISIT which,         \
				const int depth)                              \
  {                                                                           \
    char buf[BUFSIZE];                                                        \
    switch (which)                                                            \
      {                                                                       \
      case preorder:                                                          \
      case endorder:                                                          \
	break;                                                                \
      case postorder:                                                         \
      case leaf:                                                              \
	SNPRINTF (buf, BUFSIZE, *(T *) nodep);                                \
	INFO ("%s", buf);                                                     \
	break;                                                                \
      }                                                                       \
  }                                                                           \
                                                                              \
  void NAME##_dump (NAME##_t *set) { twalk (set->root, NAME##_dump_node); }   \
                                                                              \
  thread_local T *NAME##_array_pos = NULL;                                    \
                                                                              \
  static void NAME##_add_node_to_array (const void *nodep, const VISIT which, \
					const int depth)                      \
  {                                                                           \
    if (!NAME##_array_pos)                                                    \
      return;                                                                 \
    switch (which)                                                            \
      {                                                                       \
      case preorder:                                                          \
      case endorder:                                                          \
	break;                                                                \
      case postorder:                                                         \
      case leaf:                                                              \
	*NAME##_array_pos = *(T *) nodep;                                     \
	NAME##_array_pos++;                                                   \
	break;                                                                \
      }                                                                       \
  }                                                                           \
                                                                              \
  int NAME##_get_array (const NAME##_t *set, T **element)                     \
  {                                                                           \
    if (!element)                                                             \
      goto END;                                                               \
    *element = calloc (set->size, sizeof (T));                                \
    if (!*element)                                                            \
      return -1;                                                              \
    NAME##_array_pos = *element;                                              \
    twalk (set->root, NAME##_add_node_to_array);                              \
    NAME##_array_pos = NULL;                                                  \
  END:                                                                        \
    return (int) (set->size);                                                 \
  }

#endif /* UTIL_SET_H */