Awesome

Longest Prefix Match (LPM) library

Longest Prefix Match (LPM) library supporting IPv4 and IPv6. The implementation is written in C99 and is distributed under the 2-clause BSD license.

Additionally, bindings are available for Lua and Java. Specifications to build RPM and DEB packages are also provided.

API

• lpm_t *lpm_create(void)

  • Construct a new LPM object.

• void lpm_destroy(lpm_t *lpm)

  • Destroy the LPM object and any entries in it.

• void lpm_clear(lpm_t *lpm, lpm_dtor_t *dtor, void *arg)

  • Remove all entries in the LPM object. It calls the passed destructor function, if it is not NULL, as it traverses the entries. The destructor function prototype:
  • typedef void (*lpm_dtor_t)(void *arg, const void *key, size_t len, void *val);

• int lpm_insert(lpm_t *lpm, const void *addr, size_t len, unsigned preflen, void *val)

  • Insert the network address of a given length and prefix length into the LPM object and associate the entry with specified pointer value. The address must be in the network byte order. Returns 0 on success or -1 on failure.

• int lpm_remove(lpm_t *lpm, const void *addr, size_t len, unsigned preflen)

  • Remove the network address of a given length and prefix length from the LPM object. Returns 0 on success or -1 on failure.

• void *lpm_lookup_prefix(lpm_t *lpm, const void *addr, size_t len, unsigned preflen)

  • Retrieve the pointer associated with a specific prefix. Returns the said pointer, or NULL on failure.

• void *lpm_lookup(lpm_t *lpm, const void *addr, size_t len)

  • Lookup the given address performing the longest prefix match. Returns the associated pointer value on success or NULL on failure.

• int lpm_strtobin(const char *cidr, void *addr, size_t *len, unsigned *preflen)

  • Convert a string in CIDR notation to a binary address, to be stored in the addr buffer and its length in len, as well as the prefix length (if not specified, then the maximum length of the address family will be set). The address will be stored in the network byte order. Its buffer must provide at least 4 or 16 bytes (depending on the address family). Returns zero on success and -1 on failure.

Examples

Lua

local lpm = require("lpm")

local acl = lpm.new()
local some_info = { val = "test" }

local addr, preflen = lpm.tobin("10.0.0.0/24")
if not acl:insert(addr, preflen, some_info) then
  print("acl:insert() failed")
  return -1
end

local ret = acl:lookup(lpm.tobin("10.0.0.100"))
print(ret.val)

Java

See README how to build the JAR and the test case as example how to use the Java API

Packages

Just build the package, install it and link the library using the -llpm flag.

• RPM (tested on RHEL/CentOS 7): cd pkg && make rpm
• DEB (tested on Debian 9): cd pkg && make deb