#ifndef _RADIX_H_
#define _RADIX_H_

#include "ldp_mm_impl.h"
#include <unistd.h>

#define RADIX_INIT(head)						\
{									\
  (head)->RdX_root = NULL;						\
}

#define RADIX_ENTRY(type,bits)						\
struct {								\
  struct type *RdX_next[(0x01 << bits)];				\
}

#define RADIX_HEAD(name,type)						\
struct name {								\
  struct type *RdX_root;						\
};

#define RADIX_INSERT(head,type,field,bits,tdef,key,klen,result)		\
{									\
  struct type **RdX_node = &((head)->RdX_root);				\
  tdef RdX_mask = (0x01 << bits)-1;					\
  int RdX_index;							\
  int RdX_size = sizeof(tdef)*8;					\
  int RdX_count = 0;							\
									\
  if(klen == 0) {							\
    result = 0;								\
  } else {								\
    result = -10;							\
  }									\
									\
  if(!(klen % bits)) {							\
    result = -9;							\
    while((RdX_count*bits) < klen) {					\
      if(!(*RdX_node)) {						\
         (*RdX_node) = (struct type *)malloc(sizeof(struct type));	\
         if(!(*RdX_node)) {						\
           result = -2;							\
           break;							\
         }								\
         memset((*RdX_node),0,sizeof(struct type));			\
      }									\
      RdX_index = (key >> (RdX_size - bits - (RdX_count * bits))) & RdX_mask; \
      RdX_node = &((*RdX_node)->field.RdX_next[RdX_index]);		\
      RdX_count++;							\
    }									\
    if(result != -2 && (!(*RdX_node))) {				\
      (*RdX_node) = (struct type *)malloc(sizeof(struct type));		\
      if(!(*RdX_node)) {						\
        result = -2;							\
      } else {								\
        memset((*RdX_node),0,sizeof(struct type));			\
        result = 0;							\
      }									\
    } else {								\
      result = 0;							\
    }									\
  }									\
}

#define RADIX_DO(head,type,field,bits,tdef,key,klen,flm,elem,result,RxD_set) \
{									\
  struct type *RdX_node = (head)->RdX_root;				\
  struct type *RdX_last = (head)->RdX_root;				\
  tdef RdX_mask = (0x01 << bits)-1;					\
  int RdX_index;							\
  int RdX_size = sizeof(tdef)*8;					\
  int RdX_count = 0;							\
									\
  result = -10;								\
									\
  if(!(klen % bits)) {							\
    if(RxD_set == 2) {							\
      result = 0;							\
    }									\
    RdX_mask = (0x01 << bits)-1;					\
    while((RdX_count*bits) < klen) {					\
      if(!RdX_node) {							\
        result = -2;							\
        break;								\
      } else {								\
        if(RdX_node->flm) RdX_last = RdX_node;				\
        RdX_index = (key >> (RdX_size - bits - (RdX_count * bits))) & RdX_mask;\
        RdX_node = RdX_node->field.RdX_next[RdX_index];			\
      }									\
      RdX_count++;							\
    }									\
    if(RxD_set == 2) RdX_node = RdX_last;				\
    if(!RdX_node) {							\
      result = -3;							\
    } else {								\
      switch(RxD_set) {							\
        case 0:								\
          elem = RdX_node->flm;						\
          result = 0;							\
          break;							\
        case 1:								\
          RdX_node->flm = elem;						\
          result = 0;							\
          break;							\
        case 2:								\
          if((elem = RdX_node->flm)) {					\
            result = 0;							\
          } else {							\
            result = -4;						\
          }								\
          break;							\
      }									\
    }									\
  }									\
}

#define RADIX_SET(head,type,field,bits,tdef,key,klen,flm,elem,result)	\
        RADIX_DO(head,type,field,bits,tdef,key,klen,flm,elem,result,1)
#define RADIX_GET(head,type,field,bits,tdef,key,klen,flm,elem,result)	\
        RADIX_DO(head,type,field,bits,tdef,key,klen,flm,elem,result,0)
#define RADIX_GET_LONG(head,type,field,bits,tdef,key,flm,elem,result)\
        RADIX_DO(head,type,field,bits,tdef,key,sizeof(tdef)*8,flm,elem,result,2)

#define RADIX_VISIT_ALL(head,type,field,bits,depth,visit,extra)		\
{									\
  int RdX_node_count = (0x1 << bits);					\
  struct type *RdX_stack[(depth / bits) + 1];				\
  int RdX_stack_count[(depth / bits) + 1];				\
  int RdX_stack_depth = 0;						\
  struct type *RdX_node;						\
  int RdX_done = 0;							\
  int R = 0;								\
									\
  if((RdX_node = (head)->RdX_root)) {					\
    while(!RdX_done) {							\
      if(R < RdX_node_count && RdX_node->field.RdX_next[R]) {		\
        RdX_stack[RdX_stack_depth] = RdX_node;				\
        RdX_stack_count[RdX_stack_depth] = R + 1;			\
        RdX_stack_depth++;						\
        RdX_node = RdX_node->field.RdX_next[R];				\
        R = 0;								\
      } else {								\
        R++;								\
        if(R >= RdX_node_count) {					\
          if(visit(RdX_node,extra)) {					\
            RdX_done = 1;						\
            break;							\
          }								\
          RdX_stack_depth--;						\
          if(RdX_stack_depth >= 0) {					\
            RdX_node = RdX_stack[RdX_stack_depth];			\
            R = RdX_stack_count[RdX_stack_depth];			\
          } else {							\
            RdX_done = 1;						\
          }								\
        }								\
      }									\
    }									\
  }									\
}

#endif