1 /* 2 * Copyright (c) 2018, Sam Kumar <samkumar@cs.berkeley.edu> 3 * Copyright (c) 2018, University of California, Berkeley 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. Neither the name of the copyright holder nor the 14 * names of its contributors may be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27 * POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30 #ifndef CBUF_H_ 31 #define CBUF_H_ 32 33 /* CIRCULAR BUFFER */ 34 35 #include <stdbool.h> 36 #include <stdint.h> 37 #include <stdlib.h> 38 #include <sys/types.h> 39 40 struct otLinkedBuffer; 41 42 /* Represents a circular buffer. */ 43 struct cbufhead { 44 size_t r_index; 45 size_t used; 46 size_t size; 47 uint8_t* buf; 48 }; 49 50 /* Initializes a circular buffer (chdr is the header storing metadata). */ 51 void cbuf_init(struct cbufhead* chdr, uint8_t* buf, size_t len); 52 53 /* Function type for copying data into or out of a circular buffer. */ 54 typedef void(*cbuf_copier_t)(void*, size_t, const void*, size_t, size_t); 55 56 /* Instantiations of cbuf_copier_t, for copying data between circular buffers and regular buffers. */ 57 void cbuf_copy_into_buffer(void* buffer, size_t buffer_offset, const void* arr, size_t arr_offset, size_t num_bytes); 58 void cbuf_copy_from_buffer(void* arr, size_t arr_offset, const void* buffer, size_t buffer_offset, size_t num_bytes); 59 60 /* Instantiations of cbuf_copier_t, for copying data between circular buffers and otMessages. */ 61 void cbuf_copy_into_message(void* buffer, size_t buffer_offset, const void* arr, size_t arr_offset, size_t num_bytes); 62 void cbuf_copy_from_message(void* arr, size_t arr_offset, const void* buffer, size_t buffer_offset, size_t num_bytes); 63 64 /* Writes data to the back of the circular buffer using the specified copier. */ 65 size_t cbuf_write(struct cbufhead* chdr, const void* data, size_t data_offset, size_t data_len, cbuf_copier_t copy_from); 66 67 /* Reads data from the front of the circular buffer using the specified copier. */ 68 size_t cbuf_read(struct cbufhead* chdr, void* data, size_t data_offset, size_t numbytes, int pop, cbuf_copier_t copy_into); 69 70 /* Reads data at the specified offset, in bytes, from the front of the circular buffer using the specified copier. */ 71 size_t cbuf_read_offset(struct cbufhead* chdr, void* data, size_t data_offset, size_t numbytes, size_t offset, cbuf_copier_t copy_into); 72 73 /* Drops bytes from the front of the circular buffer. */ 74 size_t cbuf_pop(struct cbufhead* chdr, size_t numbytes); 75 76 /* Returns the number of bytes available for reading from the circular buffer. */ 77 size_t cbuf_used_space(struct cbufhead* chdr); 78 79 /* Returns the number of bytes that can be written to the circular buffer before it is full. */ 80 size_t cbuf_free_space(struct cbufhead* chdr); 81 82 /* Returns the total capacity of the circular buffer, in bytes. */ 83 size_t cbuf_size(struct cbufhead* chdr); 84 85 /* Returns true if the circular buffer is empty, and false if it is not empty. */ 86 bool cbuf_empty(struct cbufhead* chdr); 87 88 /* Rotates the circular buffer's data so that the "used" portion begins at the beginning of the buffer. */ 89 void cbuf_contiguify(struct cbufhead* chdr, uint8_t* bitmap); 90 91 /* Populates the provided otLinkedBuffers to reference the data currently in the circular buffer. */ 92 void cbuf_reference(const struct cbufhead* chdr, struct otLinkedBuffer* first, struct otLinkedBuffer* second); 93 94 /* Writes DATA at the end of the circular buffer without making it available for 95 reading. This data is said to be "out-of-sequence". OFFSET is position at 96 which to write these bytes, relative to the position where cbuf_write would 97 write them. Each bit in the BITMAP corresponds to a byte in the circular 98 buffer; the bits corresponding to the bytes containing the newly written 99 data are set. The index of the first byte written is stored into FIRSTINDEX, 100 if it is not NULL. */ 101 size_t cbuf_reass_write(struct cbufhead* chdr, size_t offset, const void* data, size_t data_offset, size_t numbytes, uint8_t* bitmap, size_t* firstindex, cbuf_copier_t copy_from); 102 103 /* Makes NUMBYTES out-of-seqence bytes available for reading in the circular 104 buffer. No data is copied; the out-of-sequence bytes made available are the 105 bytes currently at the position where cbuf_write would write them. The bytes 106 are taken from the unused space of the buffer, and can be set using 107 cbuf_reass_write. */ 108 size_t cbuf_reass_merge(struct cbufhead* chdr, size_t numbytes, uint8_t* bitmap); 109 110 /* Counts the number of contiguous out-of-sequence bytes at the specified 111 OFFSET, until the count reaches the specified LIMIT. Note that, for a given, 112 limit, this function might overcount the length of the continuous 113 out-of-sequence bytes and return a greater number; the caller is assumed to 114 handle this appropriately (i.e., treating the limit not as a hard upper 115 bound on the return value, but rather as, "I don't care if more bits than 116 this are set"). Just because the function returns something more than 117 LIMIT, it doesn't necessarily mean that more than LIMIT bits are actually 118 set. Note that LIMIT should never be set to a value greater than the number 119 of bytes in the circular buffer. */ 120 size_t cbuf_reass_count_set(struct cbufhead* chdr, size_t offset, uint8_t* bitmap, size_t limit); 121 122 /* Returns a true value iff INDEX is the index of a byte within OFFSET bytes 123 past the end of the buffer. */ 124 int cbuf_reass_within_offset(struct cbufhead* chdr, size_t offset, size_t index); 125 126 #endif 127
