17、作为对《C++17 STL cookbook》英文版的中文翻译。
https://github.com/xiaoweiChen/CPP-17-STL-cookbook
30 Seconds of C++ (STL in C++). Read More about 30C++ here ?https://bhupeshv.me/30-Seconds-of-C++/
https://github.com/Bhupesh-V/30-seconds-of-cpp
16、通用ringbuf
A simple ring buffer (circular buffer) designed for embedded systems.
https://github.com/AndersKaloer/Ring-Buffer
https://github.com/mayanguyen/threadSafe_ringBuffer_exercise
Generic ring buffer manager library
https://github.com/MaJerle/ringbuff
https://github.com/MaJerle/ringbuff_res
15、视频 ringfifo
ringfifo.c
/*ringbuf .c*/
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include "ringfifo.h"
void ring_init(rbuf_t* rbuf)
{
int i;
for(i =0; i<NMAX; i++)
{
memset(rbuf->ringfifo[i].buffer, 0, RING_BUFFER_SIZE);
rbuf->ringfifo[i].size = 0;
}
rbuf->iput = 0;
rbuf->iget = 0;
rbuf->n = 0;
}
void ringreset(rbuf_t* rbuf)
{
rbuf->iput = 0;
rbuf->iget = 0;
rbuf->n = 0;
}
int addring(int i)
{
return (i+1) == NMAX ? 0 : i+1;
}
ringbuf_t ringget(rbuf_t* rbuf)
{
ringbuf_t getinfo;
int Pos;
if(rbuf->n > 0)
{
Pos = rbuf->iget;
rbuf->iget = addring(rbuf->iget);
(rbuf->n)--;
memcpy(getinfo.buffer,rbuf->ringfifo[Pos].buffer,rbuf->ringfifo[Pos].size);
getinfo.size = rbuf->ringfifo[Pos].size;
//printf("ringget %d %d\n", getinfo.size, task->rbuf.n);
}
else
{
getinfo.size = 0;
//memset(&getinfo,0,sizeof(ringbuf_t));
}
return getinfo;
}
#if 0
void ringput(rbuf_t* rbuf, ringbuf_t ringbuf)
{
if((rbuf->n < NMAX))
{
memcpy(rbuf->ringfifo[rbuf->iput].buffer,ringbuf.buffer,ringbuf.size);
rbuf->ringfifo[rbuf->iput].size= ringbuf.size;
rbuf->iput = addring(rbuf->iput);
rbuf->n++;
//printf("ringput %d %d\n", size, rbuf.n);
}
else
{
}
}
#else
void ringput(rbuf_t* rbuf, char* buffer, int size)
{
if((rbuf->n < NMAX))
{
memcpy(rbuf->ringfifo[rbuf->iput].buffer,buffer,size);
rbuf->ringfifo[rbuf->iput].size= size;
rbuf->iput = addring(rbuf->iput);
rbuf->n++;
//printf("ringput %d %d\n", size, rbuf.n);
}
else
{
}
}
#endif
ringfifo.h
#define NMAX 32
#define RING_BUFFER_SIZE 1024
#if (RING_BUFFER_SIZE & (RING_BUFFER_SIZE - 1)) != 0
#error "RING_BUFFER_SIZE must be a power of two"
#endif
typedef struct ringbuf {
char buffer[RING_BUFFER_SIZE];
int size;
}ringbuf_t;
typedef struct rbuf
{
ringbuf_t ringfifo[NMAX];
int iput;
int iget;
int n;
}rbuf_t;
void ring_init(rbuf_t* rbuf);
void ringreset(rbuf_t* rbuf);
int addring (int i);
ringbuf_t ringget(rbuf_t* rbuf);
#if 0
void ringput(rbuf_t* rbuf, ringbuf_t ringbuf);
#else
void ringput(rbuf_t* rbuf, char* buffer, int size);
#endif
test.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "ringfifo.h"
int main(int argc, char **argv)
{
rbuf_t* rbuf = (rbuf_t*)malloc(sizeof(rbuf_t));
ring_init(rbuf);
ringbuf_t ringbuf1;
strcpy(ringbuf1.buffer,"hello");
//memcpy(ringbuf1.buffer,"hello", sizeof("hello"));
ringbuf1.size = sizeof("hello");
//ringput(rbuf, ringbuf1);
ringput(rbuf, "hello",5);
ringbuf_t ringbuf2 = ringget(rbuf);
printf("%s %d \n",ringbuf2.buffer, ringbuf2.size);
free(rbuf);
return 0;
}
gcc -g -o test test.c ringfifo.c
14、redis内置的链表，非常好
adlist.c
/* adlist.c - A generic doubly linked list implementation
*
* Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of Redis nor the names of its contributors may be used
* to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
#include <stdlib.h>
#include "adlist.h"
/* Create a new list. The created list can be freed with
* AlFreeList(), but private value of every node need to be freed
* by the user before to call AlFreeList().
*
* On error, NULL is returned. Otherwise the pointer to the new list. */
list *listCreate(void)
{
struct list *list;
if ((list = malloc(sizeof(*list))) == NULL)
return NULL;
list->head = list->tail = NULL;
list->len = 0;
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;
}
/* Remove all the elements from the list without destroying the list itself. */
void listEmpty(list *list)
{
unsigned long len;
listNode *current, *next;
current = list->head;
len = list->len;
while(len--) {
next = current->next;
if (list->free) list->free(current->value);
free(current);
current = next;
}
list->head = list->tail = NULL;
list->len = 0;
}
/* Free the whole list.
*
* This function can't fail. */
void listRelease(list *list)
{
listEmpty(list);
free(list);
}
/* Add a new node to the list, to head, containing the specified 'value'
* pointer as value.
*
* On error, NULL is returned and no operation is performed (i.e. the
* list remains unaltered).
* On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeHead(list *list, void *value)
{
listNode *node;
if ((node = malloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (list->len == 0) {
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
list->len++;
return list;
}
/* Add a new node to the list, to tail, containing the specified 'value'
* pointer as value.
*
* On error, NULL is returned and no operation is performed (i.e. the
* list remains unaltered).
* On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeTail(list *list, void *value)
{
listNode *node;
if ((node = malloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (list->len == 0) {
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
node->prev = list->tail;
node->next = NULL;
list->tail->next = node;
list->tail = node;
}
list->len++;
return list;
}
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
listNode *node;
if ((node = malloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (after) {
node->prev = old_node;
node->next = old_node->next;
if (list->tail == old_node) {
list->tail = node;
}
} else {
node->next = old_node;
node->prev = old_node->prev;
if (list->head == old_node) {
list->head = node;
}
}
if (node->prev != NULL) {
node->prev->next = node;
}
if (node->next != NULL) {
node->next->prev = node;
}
list->len++;
return list;
}
/* Remove the specified node from the specified list.
* It's up to the caller to free the private value of the node.
*
* This function can't fail. */
void listDelNode(list *list, listNode *node)
{
if (node->prev)
node->prev->next = node->next;
else
list->head = node->next;
if (node->next)
node->next->prev = node->prev;
else
list->tail = node->prev;
if (list->free) list->free(node->value);
free(node);
list->len--;
}
/* Returns a list iterator 'iter'. After the initialization every
* call to listNext() will return the next element of the list.
*
* This function can't fail. */
listIter *listGetIterator(list *list, int direction)
{
listIter *iter;
if ((iter = malloc(sizeof(*iter))) == NULL) return NULL;
if (direction == AL_START_HEAD)
iter->next = list->head;
else
iter->next = list->tail;
iter->direction = direction;
return iter;
}
/* Release the iterator memory */
void listReleaseIterator(listIter *iter) {
free(iter);
}
/* Create an iterator in the list private iterator structure */
void listRewind(list *list, listIter *li) {
li->next = list->head;
li->direction = AL_START_HEAD;
}
void listRewindTail(list *list, listIter *li) {
li->next = list->tail;
li->direction = AL_START_TAIL;
}
/* Return the next element of an iterator.
* It's valid to remove the currently returned element using
* listDelNode(), but not to remove other elements.
*
* The function returns a pointer to the next element of the list,
* or NULL if there are no more elements, so the classical usage patter
* is:
*
* iter = listGetIterator(list,<direction>);
* while ((node = listNext(iter)) != NULL) {
* doSomethingWith(listNodeValue(node));
* }
*
* */
listNode *listNext(listIter *iter)
{
listNode *current = iter->next;
if (current != NULL) {
if (iter->direction == AL_START_HEAD)
iter->next = current->next;
else
iter->next = current->prev;
}
return current;
}
/* Duplicate the whole list. On out of memory NULL is returned.
* On success a copy of the original list is returned.
*
* The 'Dup' method set with listSetDupMethod() function is used
* to copy the node value. Otherwise the same pointer value of
* the original node is used as value of the copied node.
*
* The original list both on success or error is never modified. */
list *listDup(list *orig)
{
list *copy;
listIter iter;
listNode *node;
if ((copy = listCreate()) == NULL)
return NULL;
copy->dup = orig->dup;
copy->free = orig->free;
copy->match = orig->match;
listRewind(orig, &iter);
while((node = listNext(&iter)) != NULL) {
void *value;
if (copy->dup) {
value = copy->dup(node->value);
if (value == NULL) {
listRelease(copy);
return NULL;
}
} else
value = node->value;
if (listAddNodeTail(copy, value) == NULL) {
listRelease(copy);
return NULL;
}
}
return copy;
}
/* Search the list for a node matching a given key.
* The match is performed using the 'match' method
* set with listSetMatchMethod(). If no 'match' method
* is set, the 'value' pointer of every node is directly
* compared with the 'key' pointer.
*
* On success the first matching node pointer is returned
* (search starts from head). If no matching node exists
* NULL is returned. */
listNode *listSearchKey(list *list, void *key)
{
listIter iter;
listNode *node;
listRewind(list, &iter);
while((node = listNext(&iter)) != NULL) {
if (list->match) {
if (list->match(node->value, key)) {
return node;
}
} else {
if (key == node->value) {
return node;
}
}
}
return NULL;
}
/* Return the element at the specified zero-based index
* where 0 is the head, 1 is the element next to head
* and so on. Negative integers are used in order to count
* from the tail, -1 is the last element, -2 the penultimate
* and so on. If the index is out of range NULL is returned. */
listNode *listIndex(list *list, long index) {
listNode *n;
if (index < 0) {
index = (-index)-1;
n = list->tail;
while(index-- && n) n = n->prev;
} else {
n = list->head;
while(index-- && n) n = n->next;
}
return n;
}
/* Rotate the list removing the tail node and inserting it to the head. */
void listRotate(list *list) {
listNode *tail = list->tail;
if (listLength(list) <= 1) return;
/* Detach current tail */
list->tail = tail->prev;
list->tail->next = NULL;
/* Move it as head */
list->head->prev = tail;
tail->prev = NULL;
tail->next = list->head;
list->head = tail;
}
/* Add all the elements of the list 'o' at the end of the
* list 'l'. The list 'other' remains empty but otherwise valid. */
void listJoin(list *l, list *o) {
if (o->head)
o->head->prev = l->tail;
if (l->tail)
l->tail->next = o->head;
else
l->head = o->head;
if (o->tail) l->tail = o->tail;
l->len += o->len;
/* Setup other as an empty list. */
o->head = o->tail = NULL;
o->len = 0;
}
adlist.h
/* adlist.h - A generic doubly linked list implementation
*
* Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of Redis nor the names of its contributors may be used
* to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef __ADLIST_H__
#define __ADLIST_H__
/* Node, List, and Iterator are the only data structures used currently. */
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
typedef struct listIter {
listNode *next;
int direction;
} listIter;
typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned long len;
} list;
/* Functions implemented as macros */
#define listLength(l) ((l)->len)
#define listFirst(l) ((l)->head)
#define listLast(l) ((l)->tail)
#define listPrevNode(n) ((n)->prev)
#define listNextNode(n) ((n)->next)
#define listNodeValue(n) ((n)->value)
#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))
#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)
/* Prototypes */
list *listCreate(void);
void listRelease(list *list);
void listEmpty(list *list);
list *listAddNodeHead(list *list, void *value);
list *listAddNodeTail(list *list, void *value);
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotate(list *list);
void listJoin(list *l, list *o);
/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1
#endif /* __ADLIST_H__ */
13、嵌入式非常不错的环形缓冲
a ring buffer like kfifo, work in linux kernel and user space, test on kernel 3.16 on both x86 and ARM platform
https://github.com/dennis-musk/ringbuffer
12、A ring buffer implemented in C
https://github.com/dhess/c-ringbuf
https://github.com/XinLiGH/RingBuffer
11、Just a dead simple set of c macros for working with ring buffers in a generic manner.
https://github.com/pthrasher/c-generic-ring-buffer
10、fifo
https://github.com/resset/fifo
9、A thread safe type-agnostic header-only macro-based struct queue implementation in C.
这是个结构体队列
https://github.com/nullseed/queue
queue.h
#ifndef QUEUE_H
#define QUEUE_H
#include <stdbool.h>
#include <stdlib.h>
#include <pthread.h>
typedef struct {
pthread_mutex_t mutex;
pthread_cond_t cond;
void* front;
void* back;
void* backqh;
unsigned int size;
} queue_core;
typedef struct queue_handle {
queue_core* qc;
void* next;
} queue_handle;
#define QUEUE_INIT(qt, q) \
do { \
queue_core* qc; \
(q) = malloc(sizeof (qt)); \
if (q) { \
(q)->qh.qc = malloc(sizeof (queue_core)); \
if ((q)->qh.qc) { \
qc = (q)->qh.qc; \
pthread_mutex_init(&qc->mutex, NULL); \
pthread_cond_init(&qc->cond, NULL); \
qc->front = qc->back = NULL; \
qc->backqh = NULL; \
qc->size = 0; \
(q)->qh.next = NULL; \
} else { \
free(q); \
(q) = NULL; \
} \
} \
} while (false)
#define QUEUE_PUSH(q, e) \
do { \
queue_core* qc; \
queue_handle* backqh; \
qc = (q)->qh.qc; \
pthread_mutex_lock(&qc->mutex); \
(e)->qh.qc = qc; \
(e)->qh.next = NULL; \
backqh = qc->backqh; \
if (!qc->front) { \
qc->front = qc->back = (e); \
} else { \
backqh->next = (e); \
qc->back = (e); \
} \
backqh = &((e)->qh); \
qc->backqh = backqh; \
qc->size++; \
pthread_mutex_unlock(&qc->mutex); \
pthread_cond_signal(&qc->cond); \
} while (false)
#define QUEUE_POP(q, e) \
do { \
queue_core* qc; \
(e) = NULL; \
qc = (q)->qh.qc; \
pthread_mutex_lock(&qc->mutex); \
while (QUEUE_SIZE(q) == 0) { \
pthread_cond_wait(&qc->cond, &qc->mutex); \
} \
if ((q)->qh.qc->front != NULL) { \
(e) = (q)->qh.qc->front; \
(q)->qh.qc->front = (e)->qh.next; \
(q)->qh.qc->size--; \
} \
pthread_mutex_unlock(&qc->mutex); \
} while (false)
#define QUEUE_LOCK(q) \
pthread_mutex_lock(&q->qh.qc->mutex);
#define QUEUE_SIZE(q) \
((q)->qh.qc->size)
#define QUEUE_UNLOCK(q) \
pthread_mutex_unlock(&q->qh.qc->mutex);
#define QUEUE_FREE(q) \
do { \
queue_core* qc; \
if ((q) && (q)->qh.qc) { \
qc = (q)->qh.qc; \
pthread_cond_destroy(&qc->cond); \
pthread_mutex_destroy(&qc->mutex); \
free(qc); \
free(q); \
} \
} while (false)
#endif /* QUEUE_H */
simple.c
#include <stdlib.h>
#include <stdio.h>
#include "queue.h"
struct msg {
char *content;
queue_handle qh;
};
int main(void) {
struct msg *msgs; // message queue
struct msg m1, *m2;
QUEUE_INIT(struct msg, msgs);
m1.content = "abc";
QUEUE_PUSH(msgs, &m1);
printf("msgs size: %d\n", QUEUE_SIZE(msgs)); // msgs size: 1
QUEUE_POP(msgs, m2);
printf("m2 content: %s\n", m2->content); // m2 content: abc
QUEUE_FREE(msgs);
return EXIT_SUCCESS;
}
8、ring_queue
https://github.com/dodng/fast_ring_queue
7、fifo
https://github.com/geekfactory/FIFO
6、list
5、栈
https://blog.csdn.net/TECH_PRO/article/details/72930404
4 从nodejs底层框架libuv源码中发现一个高效的C语言队列
https://www.oschina.net/code/snippet_2373320_52425
3、Linux内核链表-通用链表的实现
https://www.cnblogs.com/kanite/p/5833492.html
https://www.cnblogs.com/westfly/archive/2011/04/07/2007549.html
实例1：
选自https://blog.csdn.net/codeTZ/article/details/53229439
实例2：
选自http://blog.sina.com.cn/s/blog_70a1af020100rnbh.html
2、Nordic库中的 E:\nRF52_SDK_0.9.2_dbc28c9\components\libraries\fifo
app_fifo.c
#include <stdbool.h>
#include "app_fifo.h"
bool is_power_of_two(uint32_t n)
{
if(n<=0)
return false;
return (n&(n-1))==0;
}
static uint32_t fifo_length(app_fifo_t * p_fifo)
{
uint32_t tmp = p_fifo->read_pos;
return p_fifo->write_pos - tmp;
}
#define FIFO_LENGTH fifo_length(p_fifo) /**< Macro for calculating the FIFO length. */
uint32_t app_fifo_init(app_fifo_t * p_fifo, uint8_t * p_buf, uint16_t buf_size)
{
// Check buffer for null pointer.
if (p_buf == NULL)
{
return ERROR_NULL;
}
// Check that the buffer size is a power of two.
if (!is_power_of_two(buf_size))
{
return ERROR_INVALID_LENGTH;
}
p_fifo->p_buf = p_buf;
p_fifo->buf_size_mask = buf_size - 1;
p_fifo->read_pos = 0;
p_fifo->write_pos = 0;
return SUCCESS;
}
uint32_t app_fifo_put(app_fifo_t * p_fifo, uint8_t byte)
{
if (FIFO_LENGTH <= p_fifo->buf_size_mask)
{
p_fifo->p_buf[p_fifo->write_pos & p_fifo->buf_size_mask] = byte;
p_fifo->write_pos++;
return SUCCESS;
}
return ERROR_NO_MEM;
}
uint32_t app_fifo_get(app_fifo_t * p_fifo, uint8_t * p_byte)
{
if (FIFO_LENGTH != 0)
{
*p_byte = p_fifo->p_buf[p_fifo->read_pos & p_fifo->buf_size_mask];
p_fifo->read_pos++;
return SUCCESS;
}
return ERROR_NOT_FOUND;
}
uint32_t app_fifo_flush(app_fifo_t * p_fifo)
{
p_fifo->read_pos = p_fifo->write_pos;
return SUCCESS;
}
app_fifo.h
/**@file
*
* @defgroup app_fifo FIFO implementation
* @{
* @ingroup app_common
*
* @brief FIFO implementation.
*/
#ifndef APP_FIFO_H__
#define APP_FIFO_H__
#include <stdint.h>
#include <stdlib.h>
enum {
SUCCESS,
ERROR_NULL,
ERROR_INVALID_LENGTH,
ERROR_NO_MEM,
ERROR_NOT_FOUND
};
/**@brief A FIFO instance structure. Keeps track of which bytes to read and write next.
* Also it keeps the information about which memory is allocated for the buffer
* and its size. This needs to be initialized by app_fifo_init() before use.
*/
typedef struct
{
uint8_t * p_buf; /**< Pointer to FIFO buffer memory. */
uint16_t buf_size_mask; /**< Read/write index mask. Also used for size checking. */
volatile uint32_t read_pos; /**< Next read position in the FIFO buffer. */
volatile uint32_t write_pos; /**< Next write position in the FIFO buffer. */
} app_fifo_t;
/**@brief Function for initializing the FIFO.
*
* @param[out] p_fifo FIFO object.
* @param[in] p_buf FIFO buffer for storing data. The buffer size has to be a power of two.
* @param[in] buf_size Size of the FIFO buffer provided, has to be a power of 2.
*
* @retval SUCCESS If initialization was successful.
* @retval ERROR_NULL If a NULL pointer is provided as buffer.
* @retval ERROR_INVALID_LENGTH If size of buffer provided is not a power of two.
*/
uint32_t app_fifo_init(app_fifo_t * p_fifo, uint8_t * p_buf, uint16_t buf_size);
/**@brief Function for adding an element to the FIFO.
*
* @param[in] p_fifo Pointer to the FIFO.
* @param[in] byte Data byte to add to the FIFO.
*
* @retval SUCCESS If an element has been successfully added to the FIFO.
* @retval ERROR_NO_MEM If the FIFO is full.
*/
uint32_t app_fifo_put(app_fifo_t * p_fifo, uint8_t byte);
/**@brief Function for getting the next element from the FIFO.
*
* @param[in] p_fifo Pointer to the FIFO.
* @param[out] p_byte Byte fetched from the FIFO.
*
* @retval SUCCESS If an element was returned.
* @retval ERROR_NOT_FOUND If there is no more elements in the queue.
*/
uint32_t app_fifo_get(app_fifo_t * p_fifo, uint8_t * p_byte);
/**@brief Function for flushing the FIFO.
*
* @param[in] p_fifo Pointer to the FIFO.
*
* @retval SUCCESS If the FIFO flushed successfully.
*/
uint32_t app_fifo_flush(app_fifo_t * p_fifo);
#endif // APP_FIFO_H__
/** @} */
main.c
#include <stdio.h>
#include <stdlib.h>
#include "app_fifo.h"
#define WS_BUF_LEN 1024
uint8_t ws_buf[WS_BUF_LEN];
app_fifo_t ws_fifo;
int main()
{
uint32_t ws_fifo_status=app_fifo_init(&ws_fifo, ws_buf, 64);
printf("ws_fifo_status: %d! \n" , ws_fifo_status);
ws_fifo_status=app_fifo_put(&ws_fifo, 0x55);
uint8_t p_ws_byte ;
ws_fifo_status=app_fifo_get(&ws_fifo, &p_ws_byte);
printf("data = 0x%x \n",p_ws_byte);
printf("data = 0x%x \n",ws_buf[0]);
return 0;
}
改造一下,支持多字节操作
app_fifo.c
#include <stdbool.h>
#include "app_fifo.h"
bool is_power_of_two(uint32_t n)
{
if(n<=0)
return false;
return (n&(n-1))==0;
}
uint32_t fifo_length(app_fifo_t * p_fifo)
{
uint32_t tmp = p_fifo->read_pos;
return p_fifo->write_pos - tmp;
}
#define FIFO_LENGTH fifo_length(p_fifo) /**< Macro for calculating the FIFO length. */
uint32_t app_fifo_init(app_fifo_t * p_fifo, uint16_t buf_size)
{
//p_fifo->p_buf = p_buf;
p_fifo->buf_size_mask = buf_size - 1;
p_fifo->read_pos = 0;
p_fifo->write_pos = 0;
return SUCCESS;
}
uint32_t app_fifo_put(app_fifo_t * p_fifo, uint8_t byte)
{
if (FIFO_LENGTH <= p_fifo->buf_size_mask)
{
p_fifo->p_buf[p_fifo->write_pos & p_fifo->buf_size_mask] = byte;
p_fifo->write_pos++;
return SUCCESS;
}
return ERROR_NO_MEM;
}
uint32_t app_fifo_get(app_fifo_t * p_fifo, uint8_t * p_byte)
{
if (FIFO_LENGTH != 0)
{
*p_byte = p_fifo->p_buf[p_fifo->read_pos & p_fifo->buf_size_mask];
p_fifo->read_pos++;
return SUCCESS;
}
return ERROR_NOT_FOUND;
}
uint32_t app_fifo_put_multiple(app_fifo_t * p_fifo, uint8_t* data, uint8_t len)
{
if (FIFO_LENGTH <= p_fifo->buf_size_mask)
{ /*
memcpy(&(p_fifo->p_buf[p_fifo->write_pos & p_fifo->buf_size_mask]),data,len);
//p_fifo->p_buf[p_fifo->write_pos & p_fifo->buf_size_mask] = byte;
p_fifo->write_pos+len;
*/
int i;
for(i=0;i<len;i++)
app_fifo_put(p_fifo, data[i]);
return SUCCESS;
}
return ERROR_NO_MEM;
}
uint32_t app_fifo_get_multiple(app_fifo_t * p_fifo, uint8_t * data, uint8_t len)
{
if (FIFO_LENGTH >= len)
{ /*
memcpy(data,&(p_fifo->p_buf[p_fifo->write_pos & p_fifo->buf_size_mask]),len);
//*p_byte = p_fifo->p_buf[p_fifo->read_pos & p_fifo->buf_size_mask];
p_fifo->read_pos+len;
*/
int i;
for(i=0;i<len;i++)
app_fifo_get(p_fifo, &data[i]);
return SUCCESS;
}
return ERROR_NOT_FOUND;
}
uint32_t app_fifo_flush(app_fifo_t * p_fifo)
{
p_fifo->read_pos = p_fifo->write_pos;
return SUCCESS;
}
app_fifo.h
/**@file
*
* @defgroup app_fifo FIFO implementation
* @{
* @ingroup app_common
*
* @brief FIFO implementation.
*/
#ifndef APP_FIFO_H__
#define APP_FIFO_H__
#include <stdint.h>
#include <stdlib.h>
#define FIFO_BUF_LEN 1024
enum {
SUCCESS,
ERROR_NULL,
ERROR_INVALID_LENGTH,
ERROR_NO_MEM,
ERROR_NOT_FOUND
};
/**@brief A FIFO instance structure. Keeps track of which bytes to read and write next.
* Also it keeps the information about which memory is allocated for the buffer
* and its size. This needs to be initialized by app_fifo_init() before use.
*/
typedef struct
{
uint8_t p_buf[FIFO_BUF_LEN]; /**< Pointer to FIFO buffer memory. */
uint16_t buf_size_mask; /**< Read/write index mask. Also used for size checking. */
volatile uint32_t read_pos; /**< Next read position in the FIFO buffer. */
volatile uint32_t write_pos; /**< Next write position in the FIFO buffer. */
} app_fifo_t;
uint32_t fifo_length(app_fifo_t * p_fifo);
/**@brief Function for initializing the FIFO.
*
* @param[out] p_fifo FIFO object.
* @param[in] p_buf FIFO buffer for storing data. The buffer size has to be a power of two.
* @param[in] buf_size Size of the FIFO buffer provided, has to be a power of 2.
*
* @retval SUCCESS If initialization was successful.
* @retval ERROR_NULL If a NULL pointer is provided as buffer.
* @retval ERROR_INVALID_LENGTH If size of buffer provided is not a power of two.
*/
//uint32_t app_fifo_init(app_fifo_t * p_fifo, uint8_t * p_buf, uint16_t buf_size);
uint32_t app_fifo_init(app_fifo_t * p_fifo, uint16_t buf_size);
/**@brief Function for adding an element to the FIFO.
*
* @param[in] p_fifo Pointer to the FIFO.
* @param[in] byte Data byte to add to the FIFO.
*
* @retval SUCCESS If an element has been successfully added to the FIFO.
* @retval ERROR_NO_MEM If the FIFO is full.
*/
uint32_t app_fifo_put(app_fifo_t * p_fifo, uint8_t byte);
/**@brief Function for getting the next element from the FIFO.
*
* @param[in] p_fifo Pointer to the FIFO.
* @param[out] p_byte Byte fetched from the FIFO.
*
* @retval SUCCESS If an element was returned.
* @retval ERROR_NOT_FOUND If there is no more elements in the queue.
*/
uint32_t app_fifo_get(app_fifo_t * p_fifo, uint8_t * p_byte);
/**@brief Function for adding multiple element to the FIFO.
*
* @param[in] p_fifo Pointer to the FIFO.
* @param[in] data Data byte to add to the FIFO.
* @param[in] len data len.
* @retval SUCCESS If an element has been successfully added to the FIFO.
* @retval ERROR_NO_MEM If the FIFO is full.
*/
uint32_t app_fifo_put_multiple(app_fifo_t * p_fifo, uint8_t* data, uint8_t len);
/**@brief Function for getting the multiple element from the FIFO.
*
* @param[in] p_fifo Pointer to the FIFO.
* @param[out] data data fetched from the FIFO.
* @param[in] len data len.
* @retval SUCCESS If an element was returned.
* @retval ERROR_NOT_FOUND If there is no more elements in the queue.
*/
uint32_t app_fifo_get_multiple(app_fifo_t * p_fifo, uint8_t * data, uint8_t len);
/**@brief Function for flushing the FIFO.
*
* @param[in] p_fifo Pointer to the FIFO.
*
* @retval SUCCESS If the FIFO flushed successfully.
*/
uint32_t app_fifo_flush(app_fifo_t * p_fifo);
#endif // APP_FIFO_H__
/** @} */
//example.c
app_fifo_t * app_fifo;
app_fifo = (app_fifo_t *)malloc(sizeof(app_fifo_t));
app_fifo_init(app_fifo, FIFO_BUF_LEN);
app_fifo_put_multiple(app_fifo, (uint8_t*)pcm_data_buf, ret);
int ret = app_fifo_get_multiple(app_fifo, (uint8_t*)buf, 320);
1、芯艺设计室
queue.c
/********************************
队列管理模块
文件名:queue.c
编译：WinAVR-20070122
芯艺设计室 2004-2007 版权所有
转载请保留本注释在内的全部内容
WEB: http://www.chipart.cn
Email: changfutong@sina.com
*******************************/
#include <stdint.h>
#include "queue.h"
//向队列插入一字节
void QueueInput(PHQUEUE Q,uint8_t dat)
{
if(Q->data_count < Q->buf_size)
{
Q->pBuffer[Q->in_index]=dat; //写入数据
Q->in_index=(Q->in_index+1) % (Q->buf_size);//调整入口地址
Q->data_count++; //调整数据个数(此操作不可被中断)
}
else
{
if(Q->error<255)
Q->error++;
}
}
//从队列读出一字节
uint8_t QueueOutput(PHQUEUE Q)
{
uint8_t Ret=0;
if(Q->data_count > 0)
{
Ret=Q->pBuffer[Q->out_index]; //读数据
Q->out_index=(Q->out_index+1) % (Q->buf_size); //调整出口地址
Q->data_count--;
}
return Ret;
}
//获得队列中数据个数
uint8_t QueueGetDataCount(PHQUEUE Q)
{
return Q->data_count;
}
//清空队列,执行时不可被中断
void QueueClear(PHQUEUE Q)
{
Q->in_index=0;
Q->out_index=0;
Q->data_count=0;
Q->error=0;
}
//初始化一队列
void QueueCreate(PHQUEUE Q,uint8_t *buffer,uint8_t buf_size)
{
Q->pBuffer=buffer;
Q->buf_size=buf_size;
QueueClear(Q);
}
queue.h
//queue.h
#ifndef QUEUE_H_
#define QUEUE_H_
//队列数据结构
typedef struct QUEUE_S
{
uint8_t in_index;//入队地址
uint8_t out_index;//出队地址
uint8_t buf_size; //缓冲区长度
uint8_t *pBuffer;//缓冲
volatile uint8_t data_count; //队列内数据个数
uint8_t error;
}HQUEUE,*PHQUEUE;
void QueueInput(PHQUEUE Q,uint8_t dat);
uint8_t QueueOutput(PHQUEUE Q);
uint8_t QueueGetDataCount(PHQUEUE Q);
void QueueClear(PHQUEUE Q);
void QueueCreate(PHQUEUE Q,uint8_t *buffer,uint8_t buf_size);
#endif
uart.h
//uart.h
#ifndef UART_H
#define UART_H
void UartInit(void);
uint8_t UartRecv(uint8_t *buf,uint8_t size);
void UartSend(uint8_t *buf,uint8_t size);
#endif
uart.c
/********************************
基于队列的Mega8 UART通信驱动程序
文件名:uart.c
编译：WinAVR-20070122
硬件：CA-M8X
时钟：外部4MHz
芯艺设计室 2004-2007 版权所有
转载请保留本注释在内的全部内容
WEB: http://www.chipart.cn
Email: changfutong@sina.com
*******************************/
#include <avr/io.h>
#include <avr/interrupt.h>
#include "queue.h"
#define UART_BUF_SIZE 16 //发送和接收缓冲长度
HQUEUE g_SendQueue; //发送队列句柄
HQUEUE g_RecvQueue;//接收队列句柄
uint8_t g_SendBuffer[UART_BUF_SIZE];//发送缓冲
uint8_t g_RecvBuffer[UART_BUF_SIZE];//接收缓冲
//接收中断SIG_UART_RECV
ISR(USART_RXC_vect )
{
uint8_t c=UDR;
QueueInput(&g_RecvQueue,c);
}
//发送寄存器空中断
ISR (USART_UDRE_vect)
{
if(QueueGetDataCount(&g_SendQueue)>0)//如果发送缓冲队列不空
{
UDR=QueueOutput(&g_SendQueue); //发送一字节
}
else //否则关闭发送中断
{
UCSRB&=~_BV(UDRIE);//关闭数据空中断
}
}
////////////以下为本模块三个接口函数///////////////////////////
//初始化
void UartInit(void)
{
//UART硬件初始化
UCSRB=0;
UBRRH=0;
UBRRL=25; //9600 4MHz
UCSRB=(1<<RXCIE)|(1<<RXEN)|(1<<TXEN);
//创建发送／接收队列
QueueCreate(&g_SendQueue,g_SendBuffer,UART_BUF_SIZE);
QueueCreate(&g_RecvQueue,g_RecvBuffer,UART_BUF_SIZE);
}
//读接收缓冲内的数据，buf为读取缓冲，size为buf能接收的最大长度，返回实际接收的长度
uint8_t UartRecv(uint8_t *buf,uint8_t size)
{
uint8_t i;
for(i=0;i<size;i++)
{
if(QueueGetDataCount(&g_RecvQueue)>0)
{
cli();//以下的队列操作不可被中断
buf[i]=QueueOutput(&g_RecvQueue);
sei();//中断重新允许
}
else
{
break;
}//if else
}//for
return i;//返回读到的数据字节数
}
//发送数据 ，buf为发送数据缓冲器，size为要发送的长度
void UartSend(uint8_t *buf,uint8_t size)
{
uint8_t i;
cli(); //以下的队列操作不可被中断
for(i=0;i<size;i++)
QueueInput(&g_SendQueue,buf[i]);
sei(); //中断重新允许
UCSRB|=_BV(UDRIE);//数据空中断允许
}
//////////////////////////////////////////////////////////
18. list
list.h
#ifndef lcthw_List_h
#define lcthw_List_h
#include <stdlib.h>
struct ListNode;
typedef struct ListNode {
struct ListNode *next;
struct ListNode *prev;
void *value;
} ListNode;
typedef struct List {
int count;
ListNode *first;
ListNode *last;
} List;
List *List_create();
void List_destroy(List * list);
void List_clear(List * list);
void List_clear_destroy(List * list);
#define List_count(A) ((A)->count)
#define List_first(A) ((A)->first != NULL ? (A)->first->value : NULL)
#define List_last(A) ((A)->last != NULL ? (A)->last->value : NULL)
void List_push(List * list, void *value);
void *List_pop(List * list);
void List_unshift(List * list, void *value);
void *List_shift(List * list);
void *List_remove(List * list, ListNode * node);
#define LIST_FOREACH(L, S, M, V) ListNode *_node = NULL;\
ListNode *V = NULL;\
for(V = _node = L->S; _node != NULL; V = _node = _node->M)
#endif
list.c
#include <lcthw/list.h>
#include <lcthw/dbg.h>
List *List_create()
{
return calloc(1, sizeof(List));
}
void List_destroy(List * list)
{
LIST_FOREACH(list, first, next, cur) {
if (cur->prev) {
free(cur->prev);
}
}
free(list->last);
free(list);
}
void List_clear(List * list)
{
LIST_FOREACH(list, first, next, cur) {
free(cur->value);
}
}
void List_clear_destroy(List * list)
{
List_clear(list);
List_destroy(list);
}
void List_push(List * list, void *value)
{
ListNode *node = calloc(1, sizeof(ListNode));
check_mem(node);
node->value = value;
if (list->last == NULL) {
list->first = node;
list->last = node;
} else {
list->last->next = node;
node->prev = list->last;
list->last = node;
}
list->count++;
error:
return;
}
void *List_pop(List * list)
{
ListNode *node = list->last;
return node != NULL ? List_remove(list, node) : NULL;
}
void List_unshift(List * list, void *value)
{
ListNode *node = calloc(1, sizeof(ListNode));
check_mem(node);
node->value = value;
if (list->first == NULL) {
list->first = node;
list->last = node;
} else {
node->next = list->first;
list->first->prev = node;
list->first = node;
}
list->count++;
error:
return;
}
void *List_shift(List * list)
{
ListNode *node = list->first;
return node != NULL ? List_remove(list, node) : NULL;
}
void *List_remove(List * list, ListNode * node)
{
void *result = NULL;
check(list->first && list->last, "List is empty.");
check(node, "node can't be NULL");
if (node == list->first && node == list->last) {
list->first = NULL;
list->last = NULL;
} else if (node == list->first) {
list->first = node->next;
check(list->first != NULL,
"Invalid list, somehow got a first that is NULL.");
list->first->prev = NULL;
} else if (node == list->last) {
list->last = node->prev;
check(list->last != NULL,
"Invalid list, somehow got a next that is NULL.");
list->last->next = NULL;
} else {
ListNode *after = node->next;
ListNode *before = node->prev;
after->prev = before;
before->next = after;
}
list->count--;
result = node->value;
free(node);
error:
return result;
}
https://github.com/zedshaw/liblcthw/blob/master/src/lcthw/list.c
17. ringbuf
https://github.com/mayanguyen/threadSafe_ringBuffer_exercise
16. A thread safe type-agnostic header-only macro-based struct queue implementation in C.
queue.h
#ifndef QUEUE_H
#define QUEUE_H
#include <stdbool.h>
#include <stdlib.h>
#include <pthread.h>
typedef struct {
pthread_mutex_t mutex;
pthread_cond_t cond;
void* front;
void* back;
void* backqh;
unsigned int size;
} queue_core;
typedef struct queue_handle {
queue_core* qc;
void* next;
} queue_handle;
#define QUEUE_INIT(qt, q) \
do { \
queue_core* qc; \
(q) = malloc(sizeof (qt)); \
if (q) { \
(q)->qh.qc = malloc(sizeof (queue_core)); \
if ((q)->qh.qc) { \
qc = (q)->qh.qc; \
pthread_mutex_init(&qc->mutex, NULL); \
pthread_cond_init(&qc->cond, NULL); \
qc->front = qc->back = NULL; \
qc->backqh = NULL; \
qc->size = 0; \
(q)->qh.next = NULL; \
} else { \
free(q); \
(q) = NULL; \
} \
} \
} while (false)
#define QUEUE_PUSH(q, e) \
do { \
queue_core* qc; \
queue_handle* backqh; \
qc = (q)->qh.qc; \
pthread_mutex_lock(&qc->mutex); \
(e)->qh.qc = qc; \
(e)->qh.next = NULL; \
backqh = qc->backqh; \
if (!qc->front) { \
qc->front = qc->back = (e); \
} else { \
backqh->next = (e); \
qc->back = (e); \
} \
backqh = &((e)->qh); \
qc->backqh = backqh; \
qc->size++; \
pthread_mutex_unlock(&qc->mutex); \
pthread_cond_signal(&qc->cond); \
} while (false)
#define QUEUE_POP(q, e) \
do { \
queue_core* qc; \
(e) = NULL; \
qc = (q)->qh.qc; \
pthread_mutex_lock(&qc->mutex); \
while (QUEUE_SIZE(q) == 0) { \
pthread_cond_wait(&qc->cond, &qc->mutex); \
} \
if ((q)->qh.qc->front != NULL) { \
(e) = (q)->qh.qc->front; \
(q)->qh.qc->front = (e)->qh.next; \
(q)->qh.qc->size--; \
} \
pthread_mutex_unlock(&qc->mutex); \
} while (false)
#define QUEUE_LOCK(q) \
pthread_mutex_lock(&q->qh.qc->mutex);
#define QUEUE_SIZE(q) \
((q)->qh.qc->size)
#define QUEUE_UNLOCK(q) \
pthread_mutex_unlock(&q->qh.qc->mutex);
#define QUEUE_FREE(q) \
do { \
queue_core* qc; \
if ((q) && (q)->qh.qc) { \
qc = (q)->qh.qc; \
pthread_cond_destroy(&qc->cond); \
pthread_mutex_destroy(&qc->mutex); \
free(qc); \
free(q); \
} \
} while (false)
#endif /* QUEUE_H */
simple.c
#include <stdlib.h>
#include <stdio.h>
#include "queue.h"
struct msg {
char *content;
queue_handle qh;
};
int main(void) {
struct msg *msgs; // message queue
struct msg m1, *m2;
QUEUE_INIT(struct msg, msgs);
m1.content = "abc";
QUEUE_PUSH(msgs, &m1);
printf("msgs size: %d\n", QUEUE_SIZE(msgs)); // msgs size: 1
QUEUE_POP(msgs, m2);
printf("m2 content: %s\n", m2->content); // m2 content: abc
QUEUE_FREE(msgs);
return EXIT_SUCCESS;
}
https://github.com/nullseed/queue
https://github.com/alexandru-calinoiu/queue/blob/master/queue.c
https://github.com/lattera/queue/blob/master/src/queue.c
https://github.com/tobithiel/Queue/blob/master/example.c
A simple C thread pool implementation
https://github.com/mbrossard/threadpool
A simple C++11 Thread Pool implementation
https://github.com/progschj/ThreadPool
原文链接: https://www.cnblogs.com/dong1/p/5982208.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/242460
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
