LCOV - code coverage report
Current view: top level - lib/generic - pack.h Hit Total Coverage
Test: Knot Resolver 3.2.1-POSIX coverage report Lines: 51 74 68.9 %
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             :  * @file pack.h
      19             :  * @brief A length-prefixed list of objects, also an array list.
      20             :  * 
      21             :  * Each object is prefixed by item length, unlike array this structure 
      22             :  * permits variable-length data. It is also equivallent to forward-only list
      23             :  * backed by an array.
      24             :  *
      25             :  * @note Maximum object size is 2^16 bytes, see  ::pack_objlen_t
      26             :  * @TODO If some mistake happens somewhere, the access may end up in an infinite loop.
      27             :  *       (equality comparison on pointers)
      28             :  *
      29             :  * # Example usage:
      30             :  *
      31             :  * @code{.c}
      32             :  *      pack_t pack;
      33             :  *      pack_init(pack);
      34             :  *
      35             :  *      // Reserve 2 objects, 6 bytes total
      36             :  *      pack_reserve(pack, 2, 4 + 2);
      37             :  * 
      38             :  *      // Push 2 objects
      39             :  *      pack_obj_push(pack, U8("jedi"), 4)
      40             :  *      pack_obj_push(pack, U8("\xbe\xef"), 2);
      41             :  *
      42             :  *      // Iterate length-value pairs
      43             :  *      uint8_t *it = pack_head(pack);
      44             :  *      while (it != pack_tail(pack)) {
      45             :  *          uint8_t *val = pack_obj_val(it);
      46             :  *          it = pack_obj_next(it);
      47             :  *      }
      48             :  *
      49             :  *      // Remove object
      50             :  *      pack_obj_del(pack, U8("jedi"), 4);
      51             :  *
      52             :  *      pack_clear(pack);
      53             :  * @endcode
      54             :  *
      55             :  * \addtogroup generics
      56             :  * @{
      57             :  */
      58             : 
      59             : #pragma once
      60             : 
      61             : #include <stdint.h>
      62             : #include <string.h>
      63             : #include "array.h"
      64             : 
      65             : #ifdef __cplusplus
      66             : extern "C" {
      67             : #endif
      68             : 
      69             : /** Packed object length type. */
      70             : typedef uint16_t pack_objlen_t;
      71             : 
      72             : /** Pack is defined as an array of bytes */
      73             : typedef array_t(uint8_t) pack_t;
      74             : 
      75             : /** Zero-initialize the pack. */
      76             : #define pack_init(pack) \
      77             :         array_init(pack)
      78             : 
      79             : /** Make the pack empty and free pointed-to memory (plain malloc/free). */
      80             : #define pack_clear(pack) \
      81             :         array_clear(pack)
      82             : 
      83             : /** Make the pack empty and free pointed-to memory.
      84             :  * Mempool usage: pass mm_free and a knot_mm_t* . */
      85             : #define pack_clear_mm(pack, free, baton) \
      86             :         array_clear_mm((pack), (free), (baton))
      87             : 
      88             : /** Reserve space for *additional* objects in the pack (plain malloc/free).
      89             :  * @return 0 if success, <0 on failure */
      90             : #define pack_reserve(pack, objs_count, objs_len) \
      91             :         pack_reserve_mm((pack), (objs_count), (objs_len), array_std_reserve, NULL)
      92             : 
      93             : /** Reserve space for *additional* objects in the pack.
      94             :  * Mempool usage: pass kr_memreserve and a knot_mm_t* .
      95             :  * @return 0 if success, <0 on failure */
      96             : #define pack_reserve_mm(pack, objs_count, objs_len, reserve, baton) \
      97             :         array_reserve_mm((pack), (pack).len + (sizeof(pack_objlen_t)*(objs_count) + (objs_len)), (reserve), (baton))
      98             : 
      99             : /** Return pointer to first packed object.
     100             :  *
     101             :  * Recommended way to iterate:
     102             :  *   for (uint8_t *it = pack_head(pack); it != pack_tail(pack); it = pack_obj_next(it))
     103             :  */
     104             : #define pack_head(pack) \
     105             :         ((pack).len > 0 ? &((pack).at[0]) : NULL)
     106             : 
     107             : /** Return pack end pointer. */
     108             : #define pack_tail(pack) \
     109             :         ((pack).len > 0 ? &((pack).at[(pack).len]) : NULL)
     110             : 
     111             : /** Return packed object length. */
     112      233780 : static inline pack_objlen_t pack_obj_len(uint8_t *it)
     113             : {
     114      233780 :         pack_objlen_t len = 0;
     115      233868 :         if (it != NULL)
     116      242796 :                 memcpy(&len, it, sizeof(len));
     117      233780 :         return len;
     118             : }
     119             : 
     120             : /** Return packed object value. */
     121      233780 : static inline uint8_t *pack_obj_val(uint8_t *it)
     122             : {
     123      238236 :         if (it == NULL) {
     124           0 :                 assert(it);
     125           0 :                 return NULL;
     126             :         }
     127      238548 :         return it + sizeof(pack_objlen_t);
     128             : }
     129             : 
     130             : /** Return pointer to next packed object. */
     131       91226 : static inline uint8_t *pack_obj_next(uint8_t *it)
     132             : {
     133       91226 :         if (it == NULL) {
     134           0 :                 assert(it);
     135           0 :                 return NULL;
     136             :         }
     137       95682 :         return pack_obj_val(it) + pack_obj_len(it);
     138             : }
     139             : 
     140             : /** Return pointer to the last packed object. */
     141           0 : static inline uint8_t *pack_last(pack_t pack)
     142             : {
     143           0 :         if (pack.len == 0) {
     144           0 :                 return NULL;
     145             :         }
     146           0 :         uint8_t *it = pack_head(pack);
     147           0 :         uint8_t *tail = pack_tail(pack);
     148           0 :         while (true) {
     149           0 :                 uint8_t *next = pack_obj_next(it);
     150           0 :                 if (next == tail) {
     151           0 :                         return it;
     152             :                 }
     153           0 :                 it = next;
     154             :         }
     155             : }
     156             : 
     157             : /** Push object to the end of the pack
     158             :   * @return 0 on success, negative number on failure
     159             :   */
     160       82689 : static inline int pack_obj_push(pack_t *pack, const uint8_t *obj, pack_objlen_t len)
     161             : {
     162       82689 :         if (pack == NULL || obj == NULL) {
     163           0 :                 assert(false);
     164             :                 return kr_error(EINVAL);
     165             :         }
     166       82689 :         size_t packed_len = len + sizeof(len);
     167       82689 :         if (pack->len + packed_len > pack->cap) {
     168           0 :                 return kr_error(ENOSPC);
     169             :         }
     170             : 
     171       82689 :         uint8_t *endp = pack->at + pack->len;
     172       82689 :         memcpy(endp, (char *)&len, sizeof(len));
     173       82689 :         memcpy(endp + sizeof(len), obj, len);
     174       82689 :         pack->len += packed_len;
     175       82689 :         return 0;
     176             : }
     177             : 
     178             : /** Returns a pointer to packed object.
     179             :   * @return pointer to packed object or NULL
     180             :   */
     181       17109 : static inline uint8_t *pack_obj_find(pack_t *pack, const uint8_t *obj, pack_objlen_t len)
     182             : {
     183       17109 :                 if (pack == NULL || obj == NULL) {
     184           0 :                         assert(obj != NULL);
     185           0 :                         return NULL;
     186             :                 }
     187       17109 :                 uint8_t *endp = pack_tail(*pack);
     188       17109 :                 uint8_t *it = pack_head(*pack);
     189       29091 :                 while (it != endp) {
     190       11882 :                         uint8_t *val = pack_obj_val(it);
     191       12090 :                         if (pack_obj_len(it) == len && memcmp(obj, val, len) == 0) {
     192         108 :                                 return it;
     193             :                         }
     194       11774 :                         it = pack_obj_next(it);
     195             :                 }
     196       16581 :                 return NULL;
     197             : }
     198             : 
     199             : /** Delete object from the pack
     200             :   * @return 0 on success, negative number on failure
     201             :   */
     202          97 : static inline int pack_obj_del(pack_t *pack, const uint8_t *obj, pack_objlen_t len)
     203             : {
     204          97 :         if (pack == NULL || obj == NULL) {
     205           0 :                 assert(obj != NULL);
     206           0 :                 return kr_error(EINVAL);
     207             :         }
     208          97 :         uint8_t *endp = pack_tail(*pack);
     209          97 :         uint8_t *it = pack_obj_find(pack, obj, len);
     210          97 :         if (it) {
     211          97 :                 size_t packed_len = len + sizeof(len);
     212          97 :                 memmove(it, it + packed_len, endp - it - packed_len);
     213          97 :                 pack->len -= packed_len;
     214          97 :                 return 0;
     215             :         }
     216           0 :         return -1;
     217             : }
     218             : 
     219             : /** Clone a pack, replacing destination pack; (*dst == NULL) is valid input.
     220             :  * @return kr_error(ENOMEM) on allocation failure. */
     221        8574 : static inline int pack_clone(pack_t **dst, const pack_t *src, knot_mm_t *pool)
     222             : {
     223        8574 :         if (!dst || !src) {
     224           0 :                 assert(false);
     225             :                 return kr_error(EINVAL);
     226             :         }
     227             :         /* Get a valid pack_t. */
     228        8574 :         if (!*dst) {
     229        8574 :                 *dst = mm_alloc(pool, sizeof(pack_t));
     230        8574 :                 if (!*dst) return kr_error(ENOMEM);
     231        8574 :                 pack_init(**dst);
     232             :                 /* Clone data only if needed */
     233        8574 :                 if (src->len == 0) return kr_ok();
     234             :         }
     235             :         /* Replace the contents of the pack_t. */
     236        8252 :         int ret = array_reserve_mm(**dst, src->len, kr_memreserve, pool);
     237        8252 :         if (ret < 0) {
     238           0 :                 return kr_error(ENOMEM);
     239             :         }
     240        8252 :         memcpy((*dst)->at, src->at, src->len);
     241        8252 :         (*dst)->len = src->len;
     242        8252 :         return kr_ok();
     243             : }
     244             : 
     245             : #ifdef __cplusplus
     246             : }
     247             : #endif
     248             : 
     249             : /** @} */

Generated by: LCOV version 1.13