LCOV - code coverage report
Current view: top level - lib/generic - array.h Hit Total Coverage
Test: Knot Resolver 3.2.1-POSIX coverage report Lines: 15 17 88.2 %
Date: 2019-03-12 03:31:59
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*  Copyright (C) 2015-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
       2             : 
       3             :     This program is free software: you can redistribute it and/or modify
       4             :     it under the terms of the GNU General Public License as published by
       5             :     the Free Software Foundation, either version 3 of the License, or
       6             :     (at your option) any later version.
       7             : 
       8             :     This program is distributed in the hope that it will be useful,
       9             :     but WITHOUT ANY WARRANTY; without even the implied warranty of
      10             :     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      11             :     GNU General Public License for more details.
      12             : 
      13             :     You should have received a copy of the GNU General Public License
      14             :     along with this program.  If not, see <https://www.gnu.org/licenses/>.
      15             :  */
      16             : 
      17             : /**
      18             :  *
      19             :  * @file array.h
      20             :  * @brief A set of simple macros to make working with dynamic arrays easier.
      21             :  *
      22             :  * @note The C has no generics, so it is implemented mostly using macros.
      23             :  * Be aware of that, as direct usage of the macros in the evaluating macros
      24             :  * may lead to different expectations:
      25             :  *
      26             :  * @code{.c}
      27             :  *     MIN(array_push(arr, val), other)
      28             :  * @endcode
      29             :  *
      30             :  * May evaluate the code twice, leading to unexpected behaviour.
      31             :  * This is a price to pay for the absence of proper generics.
      32             :  *
      33             :  * # Example usage:
      34             :  *
      35             :  * @code{.c}
      36             :  *      array_t(const char*) arr;
      37             :  *      array_init(arr);
      38             :  *
      39             :  *      // Reserve memory in advance
      40             :  *      if (array_reserve(arr, 2) < 0) {
      41             :  *          return ENOMEM;
      42             :  *      }
      43             :  *
      44             :  *      // Already reserved, cannot fail
      45             :  *      array_push(arr, "princess");
      46             :  *      array_push(arr, "leia");
      47             :  *
      48             :  *      // Not reserved, may fail
      49             :  *      if (array_push(arr, "han") < 0) {
      50             :  *          return ENOMEM;
      51             :  *      }
      52             :  *
      53             :  *      // It does not hide what it really is
      54             :  *      for (size_t i = 0; i < arr.len; ++i) {
      55             :  *          printf("%s\n", arr.at[i]);
      56             :  *      }
      57             :  *
      58             :  *      // Random delete
      59             :  *      array_del(arr, 0);
      60             :  * @endcode
      61             :  * \addtogroup generics
      62             :  * @{
      63             :  */
      64             : 
      65             : #pragma once
      66             : #include <stdlib.h>
      67             : 
      68             : /** Simplified Qt containers growth strategy. */
      69      114454 : static inline size_t array_next_count(size_t want)
      70             : {
      71      122944 :         if (want < 2048) {
      72      122940 :                 return (want < 20) ? want + 4 : want * 2;
      73             :         } else {
      74           4 :                 return want + 2048;
      75             :         }
      76             : }
      77             : 
      78             : /** @internal Incremental memory reservation */
      79         109 : static inline int array_std_reserve(void *baton, char **mem, size_t elm_size, size_t want, size_t *have)
      80             : {
      81         109 :         if (*have >= want) {
      82           0 :                 return 0;
      83             :         }
      84             :         /* Simplified Qt containers growth strategy */
      85          28 :         size_t next_size = array_next_count(want);
      86         124 :         void *mem_new = realloc(*mem, next_size * elm_size);
      87         124 :         if (mem_new != NULL) {
      88         124 :                 *mem = mem_new;
      89         124 :                 *have = next_size;
      90          28 :                 return 0;
      91             :         }
      92           0 :         return -1;
      93             : }
      94             : 
      95             : /** @internal Wrapper for stdlib free. */
      96          32 : static inline void array_std_free(void *baton, void *p)
      97             : {
      98          50 :         free(p);
      99          32 : }
     100             : 
     101             : /** Declare an array structure. */
     102             : #define array_t(type) struct {type * at; size_t len; size_t cap; }
     103             : 
     104             : /** Zero-initialize the array. */
     105             : #define array_init(array) ((array).at = NULL, (array).len = (array).cap = 0)
     106             : 
     107             : /** Free and zero-initialize the array (plain malloc/free). */
     108             : #define array_clear(array) \
     109             :         array_clear_mm(array, array_std_free, NULL)
     110             : 
     111             : /** Make the array empty and free pointed-to memory.
     112             :  * Mempool usage: pass mm_free and a knot_mm_t* . */
     113             : #define array_clear_mm(array, free, baton) \
     114             :         (free)((baton), (array).at), array_init(array)
     115             : 
     116             : /** Reserve capacity for at least n elements.
     117             :  * @return 0 if success, <0 on failure */
     118             : #define array_reserve(array, n) \
     119             :         array_reserve_mm(array, n, array_std_reserve, NULL)
     120             : 
     121             : /** Reserve capacity for at least n elements.
     122             :  * Mempool usage: pass kr_memreserve and a knot_mm_t* .
     123             :  * @return 0 if success, <0 on failure */
     124             : #define array_reserve_mm(array, n, reserve, baton) \
     125             :         (reserve)((baton), (char **) &(array).at, sizeof((array).at[0]), (n), &(array).cap)
     126             : 
     127             : /**
     128             :  * Push value at the end of the array, resize it if necessary.
     129             :  * Mempool usage: pass kr_memreserve and a knot_mm_t* .
     130             :  * @note May fail if the capacity is not reserved.
     131             :  * @return element index on success, <0 on failure
     132             :  */
     133             : #define array_push_mm(array, val, reserve, baton) \
     134             :         (int)((array).len < (array).cap ? ((array).at[(array).len] = val, (array).len++) \
     135             :                 : (array_reserve_mm(array, ((array).cap + 1), reserve, baton) < 0 ? -1 \
     136             :                         : ((array).at[(array).len] = val, (array).len++)))
     137             : 
     138             : /**
     139             :  * Push value at the end of the array, resize it if necessary (plain malloc/free).
     140             :  * @note May fail if the capacity is not reserved.
     141             :  * @return element index on success, <0 on failure
     142             :  */
     143             : #define array_push(array, val) \
     144             :         array_push_mm(array, val, array_std_reserve, NULL)
     145             : 
     146             : /**
     147             :  * Pop value from the end of the array.
     148             :  */
     149             : #define array_pop(array) \
     150             :         (array).len -= 1
     151             : 
     152             : /**
     153             :  * Remove value at given index.
     154             :  * @return 0 on success, <0 on failure
     155             :  */
     156             : #define array_del(array, i) \
     157             :         (int)((i) < (array).len ? ((array).len -= 1,(array).at[i] = (array).at[(array).len], 0) : -1)
     158             : 
     159             : /**
     160             :  * Return last element of the array.
     161             :  * @warning Undefined if the array is empty.
     162             :  */
     163             : #define array_tail(array) \
     164             :     (array).at[(array).len - 1]
     165             : 
     166             : /** @} */

Generated by: LCOV version 1.13