diff options
Diffstat (limited to 'include/haproxy/ncbuf-t.h')
-rw-r--r-- | include/haproxy/ncbuf-t.h | 104 |
1 files changed, 104 insertions, 0 deletions
diff --git a/include/haproxy/ncbuf-t.h b/include/haproxy/ncbuf-t.h new file mode 100644 index 0000000..0dd958f --- /dev/null +++ b/include/haproxy/ncbuf-t.h @@ -0,0 +1,104 @@ +#ifndef _HAPROXY_NCBUF_T_H +#define _HAPROXY_NCBUF_T_H + +/* **** public documentation **** + * + * <ncbuf> stands for non-contiguous circular buffer. This type can be used to + * store data in a non-linear way with gaps between them. The buffer is + * circular and so data may wrapped. + * + * The API of <ncbuf> is split in two parts. Please refer to the public API + * declared in this header file which should cover all the needs. + * + * To minimize the memory footprint, size of data and gaps are inserted in the + * gaps themselves. This way <ncbuf> does not need to maintain a separate list + * of data offsets in a dedicated structure. However, this put some limitations + * on the buffer usage that the user need to know. + * + * First, a space will always be reserved in the allocated buffer area to store + * the size of the first data block. Use ncb_size(buf) to retrieve the usable + * size of the allocated buffer excluding the reserved space. + * + * Second, add and deletion operations are constraint and may be impossible if + * a minimal gap size between data is not respected. A caller must always + * inspect the return values of these functions. To limit these errors and + * improve the buffer performance, <ncbuf> should be reserved for use-cases + * where the number of formed gaps is kept minimal and evenly spread. + */ + +/* **** internal documentation **** + * + * This section is useful to users who need to understand how ncbuf are + * implemented. + * + * Public and internal functions all shared a common abstraction of the buffer. + * The buffer content is represented as a list of blocks, alternating between + * DATA and GAP blocks. This simplifies the buffer examination loop and + * insertion/deletion. Note that this list of blocks is not stored in the + * buffer structure. + * + * The buffer is considered to always start with a DATA block. The size of this + * block is stored just before <head> which is the pointer for offset 0. This + * space will always be reserved for this usage. It can be accessed through + * ncb_int_head(buf). If the buffer has no data at head, the reserved space + * will simply contains the value 0, and will be follow by a gap. + * + * A gap always contains the size of the gap itself and the size of the next + * data block. Here is a small representation of a gap stored at offset <x> + * before a data block at offset <y>. + * + * x y + * ------------------------------------------------------------ + * xxxxxx| GAP-SZ | DATA-SZ | | xxxxxxxxxxxxx... + * ------------------------------------------------------------ + * | -------- GAP-SZ -------------- > | --- DATA-SZ ---> + * + * This means that a gap must be at least big enough to store two sizes. + * However, there is an optimization when the last block of the buffer is a + * gap. In this case, there is no minimal size for this block. If the gap is + * too small, the two sizes won't be stored in it. This block is considered + * to be a reduced gap. The block API will detect such a gap if stored at an + * offset near the end of the buffer. + * + */ + +#include <inttypes.h> + +/* ncb_sz_t is the basic type used in ncbuf to represent data and gap sizes. + * Use a bigger type to extend the maximum data size supported in the buffer. + * On the other hand, this also increases the minimal gap size which can + * cause more rejection for add/delete operations. + */ +typedef uint32_t ncb_sz_t; + +/* reserved size before head used to store first data block size */ +#define NCB_RESERVED_SZ (sizeof(ncb_sz_t)) + +/* A gap contains its size and the size of the data following it. */ +#define NCB_GAP_MIN_SZ (sizeof(ncb_sz_t) * 2) +#define NCB_GAP_SZ_OFF 0 +#define NCB_GAP_SZ_DATA_OFF (sizeof(ncb_sz_t)) + +#define NCBUF_NULL ((struct ncbuf){ }) + +struct ncbuf { + char *area; + ncb_sz_t size; + ncb_sz_t head; +}; + +enum ncb_ret { + NCB_RET_OK = 0, /* no error */ + + NCB_RET_GAP_SIZE, /* operation would create a too small gap */ + NCB_RET_DATA_REJ, /* operation would overwrite data with different one */ +}; + +/* Define how insert is conducted in regards with already stored data. */ +enum ncb_add_mode { + NCB_ADD_PRESERVE, /* keep the already stored data and only insert in gaps */ + NCB_ADD_OVERWRT, /* overwrite old data with new ones */ + NCB_ADD_COMPARE, /* compare before insert : if new data are different do not proceed */ +}; + +#endif /* _HAPROXY_NCBUF_T_H */ |