DSAS開発者の部屋

コード

#include <stdio.h>
#include <stdlib.h>

#include <unistd.h>
#include <stdint.h>
#include <dirent.h>
#include <string.h>
#include <fcntl.h>
#include <ctype.h>

#include <libgen.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#ifndef DBDIR
#  define DBDIR "../data"
#endif

#ifndef CIDR_TABLE_BITS
#  define CIDR_TABLE_BITS 8   /* 8 or 16: 16 is bit faster but use mooooooore memory. */
#endif
#define CIDR_TABLE_SIZE (1 << CIDR_TABLE_BITS)

/* データ構造について
 *
 * 葉以外の節
 *  node->child[n] はすべてのnにおいて別の節へのポインタになっている
 * 葉
 *  node->child[n] はすべてのnにおいてnodeになっている.
 */

typedef struct CIDR_TRIE {
  const char *name;
  uint32_t addr;
  uint32_t bits;
  struct CIDR_TRIE *child[CIDR_TABLE_SIZE];
} CIDR_TRIE;

static CIDR_TRIE trie_root;

static int getnetmask(int n, uint32_t *netmask)
{
  uint32_t m;
  if (n < 0 || 32 < n) return 0;

  m = 1UL << (32 - n);
  --m;
  *netmask = ~m;
  return 1;
}

static int is_leaf(const CIDR_TRIE *pt) {
  return pt->child[0] == pt;
}

static CIDR_TRIE* new_trie_node() {
  int i;
  CIDR_TRIE *pt = malloc(sizeof(CIDR_TRIE));
  pt->name = 0;
  pt->addr = 0;
  pt->bits = 0;
  for (i = 0; i < CIDR_TABLE_SIZE; ++i)
    pt->child[i] = pt;
  return pt;
}

static void init_root()
{
  int i;
  CIDR_TRIE *nullnode;
  nullnode = new_trie_node();
  for (i = 0; i < CIDR_TABLE_SIZE; ++i)
    trie_root.child[i] = nullnode;
}

/** 子node 'child' から親ノードを作る(親ノードの子はすべてchildになる) */
static CIDR_TRIE* digg_trie(CIDR_TRIE *child) {
  int i;
  CIDR_TRIE *parent = new_trie_node();
  for (i = 0; i < CIDR_TABLE_SIZE; ++i)
    parent->child[i] = child;
  return parent;
}

/* Trieを巡回して、与えられたleafよりもbitsが短い葉を全部leafで置き換える */
static int update_leaf(CIDR_TRIE *pt, CIDR_TRIE *leaf)
{
  int used = 0;
  int i;
  for (i = 0; i < CIDR_TABLE_SIZE; ++i) {
    CIDR_TRIE *next = pt->child[i];
    if (is_leaf(next)) {
      if (next->bits < leaf->bits) {
        pt->child[i] = leaf;
        used = 1;
      }
    }
    else {
      used |= update_leaf(next, leaf);
    }
  }
  return used;
}

int initread(int fd, char *type)
{
  int  r;
  int  l;
  char buff[256];
  char *p = buff;
  uint32_t ad;
  uint32_t nm = 0xffffffff;
  char ip[64];

  while((r=read(fd,p,1)) != 0){
    if(r == -1)
      return(-1);
    if(*p == '#')
      *p = 0;
    if(*p == '/')
      *p = ' ';
    if(*p == '\r')
      *p = 0;
    if(*p == '\n'){
      *p = 0;
      l = 32;
      if(sscanf(buff,"%s%d", ip, &l) < 1){
        /***** not ip addr ******/
        if(buff[0]){
          fprintf(stderr,"read error: %s(%s/%d)\n",buff,ip,l);
        }
      }else{
        if(!inet_aton(ip, (struct in_addr *)&ad)){
          fprintf(stderr,"ip addr error: %s\n", buff);
        }
        if(!getnetmask(l,&nm)){
          fprintf(stderr,"netmask error: %s\n", buff);
        }
        //printf("adding: %s %x %d\n", type, ad, nm);

        ad = ntohl(ad);
        ad &= nm;

        {
          CIDR_TRIE *pt = &trie_root;
          CIDR_TRIE *p_leaf = new_trie_node();

          p_leaf->name = type;
          p_leaf->addr = ad;
          p_leaf->bits = l;

          while (l > CIDR_TABLE_BITS) {
            int b = ad >> (32 - CIDR_TABLE_BITS);
            CIDR_TRIE *next = pt->child[b];
            if (is_leaf(next)) {
              pt->child[b] = next = digg_trie(next);
            }
            pt = next;
            ad <<= CIDR_TABLE_BITS;
            l -= CIDR_TABLE_BITS;
          }
          {
            int i;
            const int bmin = ad >> (32 - CIDR_TABLE_BITS);
            const int bmax = bmin + (1 << (CIDR_TABLE_BITS - l));
            int used = 0; // delete p_leaf if it is not used.
            for (i = bmin; i < bmax; ++i) {
              CIDR_TRIE *target = pt->child[i];
              if (is_leaf(target)) {
                if (target->bits < p_leaf->bits) {
                  pt->child[i] = p_leaf;
                  used = 1;
                }
              }
              else {
                int j;
                for (j = 0; j < CIDR_TABLE_SIZE; ++j) {
                  used |= update_leaf(target, p_leaf);
                }
              }
            }
            if (!used) {
              free(p_leaf);
            }
          }
        }
      }
      p = buff;
      continue;
    }
    p++;
  }
  return(0);  
}

#if 0
/* for debug. */
static void dump_trie(const CIDR_TRIE *pt, int indent) {
  int i, j;
  if (is_leaf(pt)) {
    for (j = 0; j < indent; ++j) putchar(' '); 
    printf("%s (%d/%d)\n", pt->name, pt->addr, pt->bits);
    return;
  }
  for (i = 0; i < CIDR_TABLE_SIZE; ++i) {
    CIDR_TRIE *next = pt->child[i];
    for (j = 0; j < indent; ++j) putchar(' '); 
    printf("child[%d]: %p", i, next);
    if (is_leaf(next)) {
      printf(" %s (%d/%d)\n", next->name, next->addr, next->bits);
    } else {
      putchar('\n');
      dump_trie(next, indent+2);
    }
  }
}
#endif

char *alloctype(char *name)
{
  char *base;
  char path[PATH_MAX];
  strcpy(path, name);
  base=basename(path);
  return strdup(base);
}

/*----- 初期化 -----*/
void cidr_initialize()
{
  int  f;
  char path[PATH_MAX];
  struct stat   st;
  struct dirent **namelist;
  int n;

  init_root();

  n = scandir(DBDIR, &namelist, 0, alphasort);
  if (n < 0)
    perror("scandir");
  else {
    int i;
    for (i=0; i<n; i++) {
      sprintf(path,"%s/%s", DBDIR, namelist[i]->d_name);
      //----- レギュラーファイル以外は見ない -----
      if(stat(path, &st) != 0) {
        free(namelist[i]);
        continue;
      }
      if(!S_ISREG(st.st_mode)) {
        free(namelist[i]);
        continue;
      }
      f = open(path, O_RDONLY);
      if(f == -1){
        fprintf(stderr,"file open error %s\n", path);
      }else{
        //printf("reading: %s\n", path);
        initread(f,alloctype(path));
        close(f);
      }
      free(namelist[i]);
    }
    free(namelist);
  }
  //dump_trie(&trie_root, 0);
}

const char *cidr_lookup(const uint8_t *addr, int len)
{
  CIDR_TRIE *pt = &trie_root;

#if CIDR_TABLE_BITS == 8
  pt = pt->child[*addr++];
  pt = pt->child[*addr++];
  pt = pt->child[*addr++];
  pt = pt->child[*addr++];
#elif CIDR_TABLE_BITS == 16
  pt = pt->child[addr[0] * 256 + addr[1]];
  pt = pt->child[addr[2] * 256 + addr[3]];
#else
#error CIDR_TABLE_BITS must be 8 or 16.
#endif

  return pt->name;
}

/* vim: set shiftwidth=2: */