]> git.proxmox.com Git - ovs.git/commit - lib/automake.mk
lib: Add new 'counting cmap' type.
authorJarno Rajahalme <jarno@ovn.org>
Sat, 23 Apr 2016 02:40:09 +0000 (19:40 -0700)
committerJarno Rajahalme <jarno@ovn.org>
Tue, 17 May 2016 00:46:55 +0000 (17:46 -0700)
commit1c4dd4246c2776a58b5c5a78db0d5581edf4205b
tree3f38ad3a9ace65bfe649184267cd5f8bc6a74449
parent9baaabfff3c7df014e9acbd4c68189b568552ca9
lib: Add new 'counting cmap' type.

cmap implements duplicates as linked lists, which causes removal of
rules to become (O^2) with large number of duplicates.  This patch
fixes the problem by introducing a new 'counting' variant of the cmap
(ccmap), which can be efficiently used to keep counts of inserted hash
values provided by the caller.  This does not require a node in the
user data structure, so this makes the user implementation a bit more
memory efficient, too.

Signed-off-by: Jarno Rajahalme <jarno@ovn.org>
Acked-by: Ben Pfaff <blp@ovn.org>
lib/automake.mk
lib/ccmap.c [new file with mode: 0644]
lib/ccmap.h [new file with mode: 0644]
tests/automake.mk
tests/library.at
tests/test-ccmap.c [new file with mode: 0644]