summaryrefslogtreecommitdiff
path: root/lib/librte_member/rte_member.c
AgeCommit message (Collapse)Author
2019-04-04replace snprintf with strlcpyBruce Richardson
Do a global replace of snprintf(..."%s",...) with strlcpy, adding in the rte_string_fns.h header if needed. The function changes in this patch were auto-generated via command: spatch --sp-file devtools/cocci/strlcpy.cocci --dir . --in-place and then the files edited using awk to add in the missing header: gawk -i inplace '/include <rte_/ && ! seen { \ print "#include <rte_string_fns.h>"; seen=1} {print}' Signed-off-by: Bruce Richardson <bruce.richardson@intel.com>
2018-07-12remove useless constructor headersThomas Monjalon
A constructor is usually declared with RTE_INIT* macros. As it is a static function, no need to declare before its definition. The macro is used directly in the function definition. Signed-off-by: Thomas Monjalon <thomas@monjalon.net>
2018-01-19member: fix memory leak on errorAnatoly Burakov
rte_member may have allocated a tailq entry or setum before failure, so free them. Fixes: 857ed6c68cf2 ("member: implement main API") Cc: stable@dpdk.org Signed-off-by: Anatoly Burakov <anatoly.burakov@intel.com> Acked-by: Yipeng Wang <yipeng1.wang@intel.com>
2018-01-17log: update legacy modules dynamic logs regexPavan Nikhilesh
Update legacy log types regex strings used for registering dynamic logs. Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com> Reviewed-by: Ferruh Yigit <ferruh.yigit@intel.com> Reviewed-by: Olivier Matz <olivier.matz@6wind.com>
2018-01-16lib: remove unnecessary pointer castZhiyong Yang
void * pointer can be assigned to any data type pointer. Unnecessary cast can be removed in order to keep code clearer. Signed-off-by: Zhiyong Yang <zhiyong.yang@intel.com> Reviewed-by: Ferruh Yigit <ferruh.yigit@intel.com>
2018-01-04lib: use SPDX tag for Intel copyright filesBruce Richardson
Replace the BSD license header with the SPDX tag for files with only an Intel copyright on them. Signed-off-by: Bruce Richardson <bruce.richardson@intel.com>
2017-11-06remove useless memzone includesThomas Monjalon
The memzone header is often included without good reason. Signed-off-by: Thomas Monjalon <thomas@monjalon.net> Acked-by: Bruce Richardson <bruce.richardson@intel.com>
2017-10-09member: implement vBF modeYipeng Wang
Bloom Filter (BF) [1] is a well-known space-efficient probabilistic data structure that answers set membership queries. Vector of Bloom Filters (vBF) is an extension to traditional BF that supports multi-set membership testing. Traditional BF will return found or not-found for each key. vBF will also return which set the key belongs to if it is found. Since each set requires a BF, vBF should be used when set count is small. vBF's false positive rate could be set appropriately so that its memory requirement and lookup speed is better in certain cases comparing to HT based set-summary. This patch adds the vBF implementation. [1]B H Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,” Communications of the ACM, 1970. Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com> Reviewed-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
2017-10-09member: implement HT modeYipeng Wang
One of the set-summary structures is hash-table based set-summary (HTSS). One example is cuckoo filter [1]. Comparing to a traditional hash table, HTSS has a much more compact structure. For each element, only one signature and its corresponding set ID is stored. No key comparison is required during lookup. For the table structure, there are multiple entries in each bucket, and the table is composed of many buckets. Two modes are supported for HTSS, "cache" and "none-cache" modes. The non-cache mode is similar to the cuckoo filter [1]. When a bucket is full, one entry will be evicted to its alternative bucket to make space for the new key. The table could be full and then no more keys could be inserted. This mode has false-positive rate but no false-negative. Multiple entries with same signature could stay in the same bucket. The "cache" mode does not evict key to its alternative bucket when a bucket is full, an existing key will be evicted out of the table like a cache. Thus, the table will never reject keys when it is full. Another property is in each bucket, there cannot be multiple entries with same signature. The mode could have both false-positive and false-negative probability. This patch adds the implementation of HTSS. [1] B Fan, D G Andersen and M Kaminsky, “Cuckoo Filter: Practically Better Than Bloom,” in Conference on emerging Networking Experiments and Technologies, 2014. Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com> Reviewed-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
2017-10-09member: implement main APIYipeng Wang
Membership library is an extension and generalization of a traditional filter (for example Bloom Filter and cuckoo filter) structure. In general, the Membership library is a data structure that provides a "set-summary" and responds to set-membership queries of whether a certain element belongs to a set(s). A membership test for an element will return the set this element belongs to or not-found if the element is never inserted into the set-summary. The results of the membership test are not 100% accurate. Certain false positive or false negative probability could exist. However, comparing to a "full-blown" complete list of elements, a "set-summary" is memory efficient and fast on lookup. This patch adds the main API definition. Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com> Reviewed-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>