/* Abstract AVL Tree Generic Package Example 2.
** This code is in the public domain.
** Version: 1.5  Author: Walt Karas
**
** This example shows how to use the AVL generic package to create an
** IP address counting facility.  Imagine we are writing software for
** an embedded CPU (with limited memory) that processes IP packets.
** We want to keep count of the number of times that we see each
** distinct destination address.  We can assume that we will see at
** most 100 distinct destination addresses.
*/

#undef AVL_READ_ERRORS_HAPPEN

/* Handle is index into array of nodes. */
#define AVL_HANDLE unsigned char

/* Key is 32-bit IP address. */
#define AVL_KEY unsigned long

typedef struct
  {
    /* IP address. */
    unsigned long ip_addr;

    /* Number of times IP address seen. */
    unsigned short cnt;

    /* Child node handles.  The high bit of gt is robbed and used as
    ** the balance factor sign.  The high bit of lt is robbed and used
    ** as the magnitude of the balance factor. */
    unsigned char gt, lt;
  }
node_T;

/* The tree nodes are in an array which is inside the AVL tree structure
** (generated by cavl_if.h).  The handles are indexes into this array. */
#define AVL_INSIDE_STRUCT node_T node[100];

#define AVL_GET_LESS(H, ACCESS) (L__tree->node[H].lt & 127)
#define AVL_SET_LESS(H, LH) \
  { register node_T *n = L__tree->node + (H); \
    n->lt &= 128; n->lt |= (LH); }

#define AVL_GET_GREATER(H, ACCESS) (L__tree->node[H].gt & 127)
#define AVL_SET_GREATER(H, GH) \
  { register node_T *n = L__tree->node + (H); \
    n->gt &= 128; n->gt |= (GH); }

#define AVL_GET_BALANCE_FACTOR(H) \
  ((L__tree->node[H].gt & 128) ? -1 : ((L__tree->node[H].lt & 128) ? 1 : 0))
#define AVL_SET_BALANCE_FACTOR(H, BF) \
  {							\
    register node_T *n = L__tree->node + (H);	\
    n->lt &= 127; n->lt |= ((BF) != 0) << 7;		\
    n->gt &= 127; n->gt |= ((BF) < 0) << 7;		\
  }

#define COMPARE_KEY_KEY(K1, K2) ((K1) > (K2) ? 1 : ((K1) < (K2) ? -1 : 0))

#define AVL_COMPARE_KEY_NODE(K, H) \
  COMPARE_KEY_KEY((K), L__tree->node[H].ip_addr)

#define AVL_COMPARE_NODE_NODE(H1, H2) \
  COMPARE_KEY_KEY(L__tree->node[H1].ip_addr, L__tree->node[H2].ip_addr)

#define AVL_NULL 127

#define AVL_MAX_DEPTH 9 

#define AVL_PRIVATE

#include "cavl_if.h"

static unsigned char num_nodes_used = 0;

static avl tree;

void init_ipac(void) { init(&tree); }

/* The given IP address appeared as the destination address in a
** packet. */
void see_ipac(unsigned long ip_addr)
  {
    unsigned char n;
    node_T *p;

    if (num_nodes_used == 100)
      {
	n = search(&tree, ip_addr, AVL_EQUAL);
	if (n == 127)
	  /* More than 100 distinct addresses seen, so ignore. */
	  return;
	p = tree.node + n;
      }
    else
      {
	/* Make p point to next free node. */
	p = tree.node + num_nodes_used;

	p->ip_addr = ip_addr;
	p->cnt = 0;

	n = insert(&tree, num_nodes_used);
	if (n != num_nodes_used)
	  /* Didn't insert the new node, because there is already a node
	  ** in the tree with the seen address.  So, we just want to
	  ** increment the pointer in the node already in the tree. */
	  p = tree.node + n;
	else
	  /* IP address was not seen before, so the new node was
	  ** successfully inserted into the tree. */
	  num_nodes_used++;
      }

    /* Increment seen count, handling saturation properly. */
    if ((~(p->cnt)) != 0)
      p->cnt++;
  }

/* Dump contents of tree into array of addresses and corresponding
** array of counts.  (Dump will be in ascending order by IP address.)
*/
unsigned char dump_ipac(unsigned long *ip_addr_list, unsigned short *cnt_list)
  {
    iter it;
    unsigned char n;
    node_T *p;
    unsigned char num_addr = 0;

    start_iter_least(&tree, &it);

    for (n = get_iter(&it); n != 127; incr_iter(&it), n = get_iter(&it))
      {
	p = tree.node + n;
	*(ip_addr_list++) = p->ip_addr;
	*(cnt_list++) = p->cnt;
	num_addr++;
      }

    return(num_addr);
  }

#define AVL_IMPL_MASK \
(AVL_IMPL_INSERT | AVL_IMPL_SEARCH | AVL_IMPL_START_ITER_LEAST | \
 AVL_IMPL_GET_ITER | AVL_IMPL_INCR_ITER | AVL_IMPL_INIT)

#include "cavl_impl.h"

/* Demo main program. */

#define remove not_going_to_use
#include <stdio.h>
#undef remove

int main(void)
  {
    init_ipac();

    see_ipac(40);
    see_ipac(35);
    see_ipac(30);
    see_ipac(25);
    see_ipac(20);
    see_ipac(15);
    see_ipac(10);
    see_ipac(5);

    see_ipac(35);
    see_ipac(30);
    see_ipac(25);
    see_ipac(20);
    see_ipac(15);
    see_ipac(10);
    see_ipac(5);

    see_ipac(30);
    see_ipac(25);
    see_ipac(20);
    see_ipac(15);
    see_ipac(10);
    see_ipac(5);

    see_ipac(25);
    see_ipac(20);
    see_ipac(15);
    see_ipac(10);
    see_ipac(5);

    see_ipac(20);
    see_ipac(15);
    see_ipac(10);
    see_ipac(5);

    see_ipac(15);
    see_ipac(10);
    see_ipac(5);

    see_ipac(10);
    see_ipac(5);

    see_ipac(5);

    {
      unsigned long ip_addr[100];
      unsigned short count[100];
      unsigned char i, num_addr = dump_ipac(ip_addr, count);

      for (i = 0; i < num_addr; i++)
	printf("%12lu %12u\n", ip_addr[i], count[i]);
    }

    return(0);
  }