C11 兼容的那些库

发表于 分类于 ， 阅读次数： Disqus： 本文字数： 3.6k 阅读时长 ≈ 3 分钟

  • 常用开源库收集, C11 linux x64 兼容

  • 资料来源:

    <>

  • 更新

    1
    2024.11.20 初始

导语

最近这一年尝试 N 多的开源库,评估使用, 单个库并不值得一篇水文, 但是合集就可以了, 长期更新中.

cJSON

cJSON 从写嵌入式就开始使用的老友.

一个 .c 一个 .h, 与 json 有关的一切.

utX

全部采用头文件, 使用极其方便.

uthash

非常方便的通用 hash 表, 几乎能够应对所有场景, 当然目前有更高效的实现, 但 uthash 依旧异常便捷.

https://troydhanson.github.io/uthash/

自定义 hash 函数 https://blog.icpz.dev/articles/programming/utstring-as-uthash-key/

utlist

https://troydhanson.github.io/uthash/utlist.html

单链表 双向链表 循环双向链表

utlist 是尾插法, 新的在尾部, 旧的 在头部.

Klib

提供了通用的 数据结构 与 算法实现,

效率和内存占用

  • khash.h: generic hash table based on double hashing.
  • kbtree.h: generic search tree based on B-tree.
  • kavl.h: generic intrusive AVL tree.
  • ksort.h: generic sort, including introsort, merge sort, heap sort, comb sort, Knuth shuffle and the k-small algorithm.
  • kseq.h: generic stream buffer and a FASTA/FASTQ format parser.
  • kvec.h: generic dynamic array.
  • kdq.h: generic double-ended queue (de-queue).
  • klist.h: generic single-linked list and memory pool.
  • kstring.{h,c}: basic string library.
  • ketopt.h: command-line argument parser, similar to getopt_long.
  • kmath.{h,c}: numerical routines including basic nonlinear programming and a few special math functions.
  • kson.{h,c}: simple JSON parser (no streaming)
  • kthread.{h,c}: simple multi-threading models.

抠出来一堆单独使用

Kvec

Kavl

liburcu

用户空间的 rcu 实现, 也提供了基于 urcu 的一些数据结构实现: hash 表 队列等等;

  • 基于 urcu 的数据结构使用不多, 当性能优化直接上 urcu 肯定没问题

What is RCU, Fundamentally?

liburcu: https://liburcu.org

  • mirror: https://github.com/urcu/userspace-rcu/
  • https://www.cnblogs.com/codestack/p/15265743.html

data

  • https://airekans.github.io/c/2016/05/10/dive-into-liburcu

rocky 8.9 的库: https://rockylinux.pkgs.org/8/rockylinux-baseos-x86_64/userspace-rcu-0.10.1-4.el8.x86_64.rpm.html

提供了 liburcu-cds 有 无锁 hash 表实现

  • https://github.com/urcu/userspace-rcu/tree/master/doc/examples/rculfhash
  • https://github.com/urcu/userspace-rcu/tree/master/doc/examples

两个 benchmark

  • https://github.com/nenuadrian/read-copy-update-mutex-benchmark/
  • https://github.com/airekans/urcu-benchmark

https://github.com/urcu/userspace-rcu/blob/master/doc/rcu-api.md

Liblfds

最爱的一个库, 大量无锁的高性能数据结构. 性能优化神

liblfds 提供无锁的高性能数据结构.

  • ARM32, x64 提供全面支持, 编译及测试
  • 最新版本 7.1.1; 7.1.1 Doc

ringbuffer

循环队列: 多读多写 无锁 容量固定; 用来做多线程的负载均衡屡试不爽.

最严重警告: struct lfds711_ringbuffer_state 要求 128 字节对齐, 动态申请时不能调用常规的 alloc 要用 posix_memalign 或 aligned_alloc 才行.

发现这个问题场景也贼无语: 代码开启 AddressSanitizer (aka ASan) 正常无报错, 关闭 ASan 报段错误… 几辈子没遇到过这么离谱的场景;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <stdlib.h>
#include "liblfds711.h"
int main() {
	enum lfds711_misc_flag overwrite_occurred_flag;
	int long long unsigned loop,overwrite_count = 0;
	struct lfds711_ringbuffer_element *re; // 访问
	struct lfds711_ringbuffer_state rs; // 真正 ring, 要么在栈上, 要么 128 对齐在堆上申请.
	void *key;
	
	// TRD : ten elements + 1 需要一个额外 empty 元素
	re = malloc( sizeof(struct lfds711_ringbuffer_element) * 11 );
	// 初始化
	lfds711_ringbuffer_init_valid_on_current_logical_core( &rs, re, 11, NULL );
	// TRD : the ringbuffer has ten elements, we write fifteen times; we will overwrite the first five elements
	for ( loop = 0 ; loop < 15 ; loop++ ) {
      	// 写入元素
		lfds711_ringbuffer_write( &rs, (void *) (lfds711_pal_uint_t) loop, NULL, &overwrite_occurred_flag, NULL, NULL );
    	// 溢出了的计数
		if( overwrite_occurred_flag == LFDS711_MISC_FLAG_RAISED)
		      overwrite_count++;
	}
	if( overwrite_count != 5 )
	    printf( "Oh bugger!\n" );
	for ( loop = 0 ; loop < 10 ; loop++ ) {
      	// 读取
		lfds711_ringbuffer_read( &rs, &key, NULL );
		// TRD : this will print 5 to 14
		printf( "key = %llu\n", (int long long unigned) key );
	}
	// 清理
	lfds711_ringbuffer_cleanup( &rs, NULL );
	free( re );
	return( EXIT_SUCCESS );
}

Fastrange

算完 hash 还有取模映射到 [0,p) 取模太贵了 -> fastrange

头文件 fastrange.h && API

  • 非常简单
1
2
3
4
5
6
7
#include "fastrange"

// given a value word, produces an integer in [0,p) without division
uint32_t fastrange32(uint32_t word, uint32_t p);
uint64_t fastrange64(uint64_t word, uint64_t p);
size_t fastrangesize(size_t word, size_t p);
int fastrangeint(int word, int p);