Thu, 23 Feb 2023 22:27:41 +0100
add CX_LINKED_LIST_SORT_SBO_SIZE macro
universe@483 | 1 | /* |
universe@483 | 2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
universe@483 | 3 | * |
universe@483 | 4 | * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. |
universe@483 | 5 | * |
universe@483 | 6 | * Redistribution and use in source and binary forms, with or without |
universe@483 | 7 | * modification, are permitted provided that the following conditions are met: |
universe@483 | 8 | * |
universe@483 | 9 | * 1. Redistributions of source code must retain the above copyright |
universe@483 | 10 | * notice, this list of conditions and the following disclaimer. |
universe@483 | 11 | * |
universe@483 | 12 | * 2. Redistributions in binary form must reproduce the above copyright |
universe@483 | 13 | * notice, this list of conditions and the following disclaimer in the |
universe@483 | 14 | * documentation and/or other materials provided with the distribution. |
universe@483 | 15 | * |
universe@483 | 16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
universe@483 | 17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
universe@483 | 18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
universe@483 | 19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
universe@483 | 20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
universe@483 | 21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
universe@483 | 22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
universe@483 | 23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
universe@483 | 24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
universe@483 | 25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
universe@483 | 26 | * POSSIBILITY OF SUCH DAMAGE. |
universe@483 | 27 | */ |
universe@483 | 28 | |
universe@483 | 29 | /** |
universe@483 | 30 | * \file buffer.h |
universe@483 | 31 | * |
universe@483 | 32 | * \brief Advanced buffer implementation. |
universe@483 | 33 | * |
universe@483 | 34 | * Instances of CxBuffer can be used to read from or to write to like one |
universe@483 | 35 | * would do with a stream. |
universe@483 | 36 | * |
universe@483 | 37 | * Some features for convenient use of the buffer |
universe@483 | 38 | * can be enabled. See the documentation of the macro constants for more |
universe@483 | 39 | * information. |
universe@483 | 40 | * |
universe@483 | 41 | * \author Mike Becker |
universe@483 | 42 | * \author Olaf Wintermann |
universe@483 | 43 | * \version 3.0 |
universe@483 | 44 | * \copyright 2-Clause BSD License |
universe@483 | 45 | */ |
universe@483 | 46 | |
universe@483 | 47 | #ifndef UCX_BUFFER_H |
universe@484 | 48 | #define UCX_BUFFER_H |
universe@483 | 49 | |
universe@484 | 50 | #include "common.h" |
universe@501 | 51 | #include "allocator.h" |
universe@483 | 52 | |
universe@483 | 53 | #ifdef __cplusplus |
universe@483 | 54 | extern "C" { |
universe@483 | 55 | #endif |
universe@483 | 56 | |
universe@483 | 57 | /** |
universe@483 | 58 | * No buffer features enabled (all flags cleared). |
universe@483 | 59 | */ |
universe@483 | 60 | #define CX_BUFFER_DEFAULT 0x00 |
universe@483 | 61 | |
universe@483 | 62 | /** |
universe@483 | 63 | * If this flag is enabled, the buffer will automatically free its contents when destroyed. |
universe@483 | 64 | */ |
universe@483 | 65 | #define CX_BUFFER_FREE_CONTENTS 0x01 |
universe@483 | 66 | |
universe@483 | 67 | /** |
universe@483 | 68 | * If this flag is enabled, the buffer will automatically extends its capacity. |
universe@483 | 69 | */ |
universe@483 | 70 | #define CX_BUFFER_AUTO_EXTEND 0x02 |
universe@483 | 71 | |
universe@483 | 72 | /** Structure for the UCX buffer data. */ |
universe@483 | 73 | typedef struct { |
universe@483 | 74 | /** A pointer to the buffer contents. */ |
universe@483 | 75 | union { |
universe@483 | 76 | /** |
universe@483 | 77 | * Data is interpreted as text. |
universe@483 | 78 | */ |
universe@483 | 79 | char *space; |
universe@483 | 80 | /** |
universe@483 | 81 | * Data is interpreted as binary. |
universe@483 | 82 | */ |
universe@483 | 83 | unsigned char *bytes; |
universe@483 | 84 | }; |
universe@501 | 85 | /** The allocator to use for automatic memory management. */ |
universe@529 | 86 | CxAllocator const *allocator; |
universe@483 | 87 | /** Current position of the buffer. */ |
universe@483 | 88 | size_t pos; |
universe@483 | 89 | /** Current capacity (i.e. maximum size) of the buffer. */ |
universe@483 | 90 | size_t capacity; |
universe@483 | 91 | /** Current size of the buffer content. */ |
universe@483 | 92 | size_t size; |
universe@483 | 93 | /** |
universe@539 | 94 | * The buffer may not extend beyond this threshold before starting to flush. |
universe@539 | 95 | * Default is \c SIZE_MAX (flushing disabled when auto extension is enabled). |
universe@539 | 96 | */ |
universe@539 | 97 | size_t flush_threshold; |
universe@539 | 98 | /** |
universe@539 | 99 | * The block size for the elements to flush. |
universe@539 | 100 | * Default is 4096 bytes. |
universe@539 | 101 | */ |
universe@539 | 102 | size_t flush_blksize; |
universe@539 | 103 | /** |
universe@539 | 104 | * The maximum number of blocks to flush in one cycle. |
universe@539 | 105 | * Zero disables flushing entirely (this is the default). |
universe@539 | 106 | * Set this to \c SIZE_MAX to flush the entire buffer. |
universe@539 | 107 | * |
universe@539 | 108 | * @attention if the maximum number of blocks multiplied with the block size |
universe@539 | 109 | * is smaller than the expected contents written to this buffer within one write |
universe@539 | 110 | * operation, multiple flush cycles are performed after that write. |
universe@539 | 111 | * That means the total number of blocks flushed after one write to this buffer may |
universe@539 | 112 | * be larger than \c flush_blkmax. |
universe@539 | 113 | */ |
universe@539 | 114 | size_t flush_blkmax; |
universe@539 | 115 | |
universe@539 | 116 | /** |
universe@539 | 117 | * The write function used for flushing. |
universe@539 | 118 | * If NULL, the flushed content gets discarded. |
universe@539 | 119 | */ |
universe@545 | 120 | cx_write_func flush_func; |
universe@539 | 121 | |
universe@539 | 122 | /** |
universe@541 | 123 | * The target for \c flush_func. |
universe@541 | 124 | */ |
universe@541 | 125 | void *flush_target; |
universe@541 | 126 | |
universe@541 | 127 | /** |
universe@483 | 128 | * Flag register for buffer features. |
universe@485 | 129 | * @see #CX_BUFFER_DEFAULT |
universe@485 | 130 | * @see #CX_BUFFER_FREE_CONTENTS |
universe@485 | 131 | * @see #CX_BUFFER_AUTO_EXTEND |
universe@483 | 132 | */ |
universe@483 | 133 | int flags; |
universe@483 | 134 | } cx_buffer_s; |
universe@483 | 135 | |
universe@483 | 136 | /** |
universe@483 | 137 | * UCX buffer. |
universe@483 | 138 | */ |
universe@500 | 139 | typedef cx_buffer_s CxBuffer; |
universe@483 | 140 | |
universe@483 | 141 | /** |
universe@501 | 142 | * Initializes a fresh buffer. |
universe@483 | 143 | * |
universe@483 | 144 | * \note You may provide \c NULL as argument for \p space. |
universe@483 | 145 | * Then this function will allocate the space and enforce |
universe@483 | 146 | * the #CX_BUFFER_FREE_CONTENTS flag. |
universe@483 | 147 | * |
universe@501 | 148 | * @param buffer the buffer to initialize |
universe@501 | 149 | * @param space pointer to the memory area, or \c NULL to allocate |
universe@483 | 150 | * new memory |
universe@485 | 151 | * @param capacity the capacity of the buffer |
universe@501 | 152 | * @param allocator the allocator this buffer shall use for automatic memory management |
universe@485 | 153 | * @param flags buffer features (see cx_buffer_s.flags) |
universe@501 | 154 | * @return zero on success, non-zero if a required allocation failed |
universe@483 | 155 | */ |
universe@529 | 156 | __attribute__((__nonnull__(1, 4))) |
universe@501 | 157 | int cxBufferInit( |
universe@501 | 158 | CxBuffer *buffer, |
universe@483 | 159 | void *space, |
universe@483 | 160 | size_t capacity, |
universe@529 | 161 | CxAllocator const *allocator, |
universe@483 | 162 | int flags |
universe@483 | 163 | ); |
universe@483 | 164 | |
universe@483 | 165 | /** |
universe@501 | 166 | * Destroys the buffer contents. |
universe@483 | 167 | * |
universe@501 | 168 | * Has no effect if the #CX_BUFFER_FREE_CONTENTS feature is not enabled. |
universe@483 | 169 | * |
universe@501 | 170 | * @param buffer the buffer which contents shall be destroyed |
universe@483 | 171 | */ |
universe@529 | 172 | __attribute__((__nonnull__)) |
universe@500 | 173 | void cxBufferDestroy(CxBuffer *buffer); |
universe@483 | 174 | |
universe@483 | 175 | /** |
universe@483 | 176 | * Shifts the contents of the buffer by the given offset. |
universe@483 | 177 | * |
universe@483 | 178 | * If the offset is positive, the contents are shifted to the right. |
universe@483 | 179 | * If auto extension is enabled, the buffer grows, if necessary. |
universe@483 | 180 | * In case the auto extension fails, this function returns a non-zero value and |
universe@483 | 181 | * no contents are changed. |
universe@483 | 182 | * If auto extension is disabled, the contents that do not fit into the buffer |
universe@483 | 183 | * are discarded. |
universe@483 | 184 | * |
universe@483 | 185 | * If the offset is negative, the contents are shifted to the left where the |
universe@483 | 186 | * first \p shift bytes are discarded. |
universe@483 | 187 | * The new size of the buffer is the old size minus the absolute shift value. |
universe@483 | 188 | * If this value is larger than the buffer size, the buffer is emptied (but |
universe@483 | 189 | * not cleared, see the security note below). |
universe@483 | 190 | * |
universe@483 | 191 | * The buffer position gets shifted alongside with the content but is kept |
universe@483 | 192 | * within the boundaries of the buffer. |
universe@483 | 193 | * |
universe@483 | 194 | * \note For situations where \c off_t is not large enough, there are specialized cxBufferShiftLeft() and |
universe@483 | 195 | * cxBufferShiftRight() functions using a \c size_t as parameter type. |
universe@483 | 196 | * |
universe@485 | 197 | * \attention |
universe@485 | 198 | * Security Note: The shifting operation does \em not erase the previously occupied memory cells. |
universe@485 | 199 | * But you can easily do that manually, e.g. by calling |
universe@483 | 200 | * <code>memset(buffer->bytes, 0, shift)</code> for a right shift or |
universe@531 | 201 | * <code>memset(buffer->bytes + buffer->size, 0, buffer->capacity - buffer->size)</code> |
universe@483 | 202 | * for a left shift. |
universe@483 | 203 | * |
universe@485 | 204 | * @param buffer the buffer |
universe@485 | 205 | * @param shift the shift offset (negative means left shift) |
universe@485 | 206 | * @return 0 on success, non-zero if a required auto-extension fails |
universe@483 | 207 | */ |
universe@529 | 208 | __attribute__((__nonnull__)) |
universe@483 | 209 | int cxBufferShift( |
universe@500 | 210 | CxBuffer *buffer, |
universe@483 | 211 | off_t shift |
universe@483 | 212 | ); |
universe@483 | 213 | |
universe@483 | 214 | /** |
universe@483 | 215 | * Shifts the buffer to the right. |
universe@483 | 216 | * See cxBufferShift() for details. |
universe@483 | 217 | * |
universe@485 | 218 | * @param buffer the buffer |
universe@485 | 219 | * @param shift the shift offset |
universe@485 | 220 | * @return 0 on success, non-zero if a required auto-extension fails |
universe@485 | 221 | * @see cxBufferShift() |
universe@483 | 222 | */ |
universe@529 | 223 | __attribute__((__nonnull__)) |
universe@483 | 224 | int cxBufferShiftRight( |
universe@500 | 225 | CxBuffer *buffer, |
universe@483 | 226 | size_t shift |
universe@483 | 227 | ); |
universe@483 | 228 | |
universe@483 | 229 | /** |
universe@483 | 230 | * Shifts the buffer to the left. |
universe@483 | 231 | * See cxBufferShift() for details. |
universe@483 | 232 | * |
universe@483 | 233 | * \note Since a left shift cannot fail due to memory allocation problems, this |
universe@483 | 234 | * function always returns zero. |
universe@483 | 235 | * |
universe@485 | 236 | * @param buffer the buffer |
universe@485 | 237 | * @param shift the positive shift offset |
universe@485 | 238 | * @return always zero |
universe@485 | 239 | * @see cxBufferShift() |
universe@483 | 240 | */ |
universe@529 | 241 | __attribute__((__nonnull__)) |
universe@483 | 242 | int cxBufferShiftLeft( |
universe@500 | 243 | CxBuffer *buffer, |
universe@483 | 244 | size_t shift |
universe@483 | 245 | ); |
universe@483 | 246 | |
universe@483 | 247 | |
universe@483 | 248 | /** |
universe@483 | 249 | * Moves the position of the buffer. |
universe@483 | 250 | * |
universe@483 | 251 | * The new position is relative to the \p whence argument. |
universe@483 | 252 | * |
universe@483 | 253 | * \li \c SEEK_SET marks the start of the buffer. |
universe@483 | 254 | * \li \c SEEK_CUR marks the current position. |
universe@483 | 255 | * \li \c SEEK_END marks the end of the buffer. |
universe@483 | 256 | * |
universe@483 | 257 | * With an offset of zero, this function sets the buffer position to zero |
universe@483 | 258 | * (\c SEEK_SET), the buffer size (\c SEEK_END) or leaves the buffer position |
universe@483 | 259 | * unchanged (\c SEEK_CUR). |
universe@483 | 260 | * |
universe@485 | 261 | * @param buffer the buffer |
universe@485 | 262 | * @param offset position offset relative to \p whence |
universe@485 | 263 | * @param whence one of \c SEEK_SET, \c SEEK_CUR or \c SEEK_END |
universe@485 | 264 | * @return 0 on success, non-zero if the position is invalid |
universe@483 | 265 | * |
universe@483 | 266 | */ |
universe@529 | 267 | __attribute__((__nonnull__)) |
universe@483 | 268 | int cxBufferSeek( |
universe@500 | 269 | CxBuffer *buffer, |
universe@483 | 270 | off_t offset, |
universe@483 | 271 | int whence |
universe@483 | 272 | ); |
universe@483 | 273 | |
universe@483 | 274 | /** |
universe@483 | 275 | * Clears the buffer by resetting the position and deleting the data. |
universe@483 | 276 | * |
universe@483 | 277 | * The data is deleted by zeroing it with a call to memset(). |
universe@483 | 278 | * |
universe@485 | 279 | * @param buffer the buffer to be cleared |
universe@483 | 280 | */ |
universe@529 | 281 | __attribute__((__nonnull__)) |
universe@529 | 282 | void cxBufferClear(CxBuffer *buffer); |
universe@483 | 283 | |
universe@483 | 284 | /** |
universe@483 | 285 | * Tests, if the buffer position has exceeded the buffer capacity. |
universe@483 | 286 | * |
universe@485 | 287 | * @param buffer the buffer to test |
universe@485 | 288 | * @return non-zero, if the current buffer position has exceeded the last |
universe@483 | 289 | * available byte of the buffer. |
universe@483 | 290 | */ |
universe@529 | 291 | __attribute__((__nonnull__)) |
universe@529 | 292 | int cxBufferEof(CxBuffer const *buffer); |
universe@483 | 293 | |
universe@483 | 294 | |
universe@483 | 295 | /** |
universe@483 | 296 | * Ensures that the buffer has a minimum capacity. |
universe@483 | 297 | * |
universe@483 | 298 | * If the current capacity is not sufficient, the buffer will be extended. |
universe@483 | 299 | * |
universe@485 | 300 | * @param buffer the buffer |
universe@485 | 301 | * @param capacity the minimum required capacity for this buffer |
universe@485 | 302 | * @return 0 on success or a non-zero value on failure |
universe@483 | 303 | */ |
universe@529 | 304 | __attribute__((__nonnull__)) |
universe@483 | 305 | int cxBufferMinimumCapacity( |
universe@500 | 306 | CxBuffer *buffer, |
universe@483 | 307 | size_t capacity |
universe@483 | 308 | ); |
universe@483 | 309 | |
universe@483 | 310 | /** |
universe@483 | 311 | * Writes data to a CxBuffer. |
universe@483 | 312 | * |
universe@567 | 313 | * If flushing is enabled and the buffer needs to flush, the data is flushed to |
universe@567 | 314 | * the target until the target signals that it cannot take more data by |
universe@567 | 315 | * returning zero via the respective write function. In that case, the remaining |
universe@567 | 316 | * data in this buffer is shifted to the beginning of this buffer so that the |
universe@567 | 317 | * newly available space can be used to append as much data as possible. This |
universe@567 | 318 | * function only stops writing more elements, when the flush target and this |
universe@567 | 319 | * buffer are both incapable of taking more data or all data has been written. |
universe@567 | 320 | * The number returned by this function is the total number of elements that |
universe@567 | 321 | * could be written during the process. It does not necessarily mean that those |
universe@567 | 322 | * elements are still in this buffer, because some of them could have also be |
universe@567 | 323 | * flushed already. |
universe@567 | 324 | * |
universe@567 | 325 | * If automatic flushing is not enabled, the position of the buffer is increased |
universe@567 | 326 | * by the number of bytes written. |
universe@483 | 327 | * |
universe@483 | 328 | * \note The signature is compatible with the fwrite() family of functions. |
universe@483 | 329 | * |
universe@485 | 330 | * @param ptr a pointer to the memory area containing the bytes to be written |
universe@485 | 331 | * @param size the length of one element |
universe@485 | 332 | * @param nitems the element count |
universe@485 | 333 | * @param buffer the CxBuffer to write to |
universe@537 | 334 | * @return the total count of elements written |
universe@483 | 335 | */ |
universe@529 | 336 | __attribute__((__nonnull__)) |
universe@483 | 337 | size_t cxBufferWrite( |
universe@489 | 338 | void const *ptr, |
universe@483 | 339 | size_t size, |
universe@483 | 340 | size_t nitems, |
universe@500 | 341 | CxBuffer *buffer |
universe@483 | 342 | ); |
universe@483 | 343 | |
universe@483 | 344 | /** |
universe@483 | 345 | * Reads data from a CxBuffer. |
universe@483 | 346 | * |
universe@483 | 347 | * The position of the buffer is increased by the number of bytes read. |
universe@483 | 348 | * |
universe@483 | 349 | * \note The signature is compatible with the fread() family of functions. |
universe@483 | 350 | * |
universe@485 | 351 | * @param ptr a pointer to the memory area where to store the read data |
universe@485 | 352 | * @param size the length of one element |
universe@485 | 353 | * @param nitems the element count |
universe@485 | 354 | * @param buffer the CxBuffer to read from |
universe@485 | 355 | * @return the total number of elements read |
universe@483 | 356 | */ |
universe@529 | 357 | __attribute__((__nonnull__)) |
universe@483 | 358 | size_t cxBufferRead( |
universe@483 | 359 | void *ptr, |
universe@483 | 360 | size_t size, |
universe@483 | 361 | size_t nitems, |
universe@500 | 362 | CxBuffer *buffer |
universe@483 | 363 | ); |
universe@483 | 364 | |
universe@483 | 365 | /** |
universe@483 | 366 | * Writes a character to a buffer. |
universe@483 | 367 | * |
universe@483 | 368 | * The least significant byte of the argument is written to the buffer. If the |
universe@483 | 369 | * end of the buffer is reached and #CX_BUFFER_AUTO_EXTEND feature is enabled, |
universe@483 | 370 | * the buffer capacity is extended by cxBufferMinimumCapacity(). If the feature is |
universe@483 | 371 | * disabled or buffer extension fails, \c EOF is returned. |
universe@483 | 372 | * |
universe@483 | 373 | * On successful write, the position of the buffer is increased. |
universe@483 | 374 | * |
universe@485 | 375 | * @param buffer the buffer to write to |
universe@485 | 376 | * @param c the character to write |
universe@485 | 377 | * @return the byte that has bean written or \c EOF when the end of the stream is |
universe@483 | 378 | * reached and automatic extension is not enabled or not possible |
universe@483 | 379 | */ |
universe@529 | 380 | __attribute__((__nonnull__)) |
universe@483 | 381 | int cxBufferPut( |
universe@500 | 382 | CxBuffer *buffer, |
universe@483 | 383 | int c |
universe@483 | 384 | ); |
universe@483 | 385 | |
universe@483 | 386 | /** |
universe@529 | 387 | * Writes a string to a buffer. |
universe@529 | 388 | * |
universe@529 | 389 | * @param buffer the buffer |
universe@529 | 390 | * @param str the zero-terminated string |
universe@529 | 391 | * @return the number of bytes written |
universe@529 | 392 | */ |
universe@529 | 393 | __attribute__((__nonnull__)) |
universe@529 | 394 | size_t cxBufferPutString( |
universe@529 | 395 | CxBuffer *buffer, |
universe@529 | 396 | const char *str |
universe@529 | 397 | ); |
universe@529 | 398 | |
universe@529 | 399 | /** |
universe@483 | 400 | * Gets a character from a buffer. |
universe@483 | 401 | * |
universe@483 | 402 | * The current position of the buffer is increased after a successful read. |
universe@483 | 403 | * |
universe@485 | 404 | * @param buffer the buffer to read from |
universe@485 | 405 | * @return the character or \c EOF, if the end of the buffer is reached |
universe@483 | 406 | */ |
universe@529 | 407 | __attribute__((__nonnull__)) |
universe@500 | 408 | int cxBufferGet(CxBuffer *buffer); |
universe@483 | 409 | |
universe@483 | 410 | #ifdef __cplusplus |
universe@483 | 411 | } |
universe@483 | 412 | #endif |
universe@483 | 413 | |
universe@628 | 414 | #endif // UCX_BUFFER_H |