BSD radix porting note 1

前言

最近需要一个 IP 路由搜索的算法,看了一眼 Linux 的 HASH 和 LC-Trie 算法之后,完全搞不定,后来发现了 BSD 的 Radix, 相比而言,BSD 的算法更简单一些,于是开始分析 BSD 的 Radix,这里是我的部分总结。

看了 FreeBSD,NetBSD,OpenBSD 的 Radix 虽说本质上都是同一个Radix算法,代码也几乎一样,但是当我看到 Apple 的 Radix 时, 发现代码和注释原来可以写得这样优美,于是我决定在 Apple 的 Radix 文件上开始移植。

源文件:

  1. radix.c
  2. radix.h

古老的函数:

  1. bzero – memset

    POSIX 里用 memset 替代

  2. bcopy – memcpy, args reverse

    POSIX 里用 memcpy 替代,但是要注意参数是反着的

  3. bcmp – memcmp

    POSIX 里用 memcmp 替代

在 GCC 的 string.h 的头文件里上面这三个函数还是存在的

步骤

  1. panic() & log()

    这两个函数都被我使用空白宏替换了

  2. 去除无用的头文件

    换上常用的 stdio.h, stdlib.h, string.h, sys/parm.h, stdint.h

  3. 去除无用的mutex锁

    原来这个文件有几个 mutex 锁,用于初始化,我全部删掉了

  4. 修改初始化函数

    原来的初始化会涉及 BSD 的内核,所以稍加修改(rn_init())

我移植的代码: radix_for_linux

comments powered by Disqus