granicus.if.org Git - strace/blob - number_set.c

   1 /*
   2  * Copyright (c) 2016-2018 Dmitry V. Levin <ldv@altlinux.org>
   3  * Copyright (c) 2017-2019 The strace developers.
   4  * All rights reserved.
   5  *
   6  * SPDX-License-Identifier: LGPL-2.1-or-later
   7  */
   8
   9 #ifdef HAVE_CONFIG_H
  10 # include "config.h"
  11 #endif
  12
  13 #include <stdbool.h>
  14 #include <stdlib.h>
  15 #include <string.h>
  16 #include "defs.h"
  17 #include "number_set.h"
  18 #include "static_assert.h"
  19 #include "xmalloc.h"
  20
  21 typedef unsigned int number_slot_t;
  22 #define BITS_PER_SLOT (sizeof(number_slot_t) * 8)
  23
  24 struct number_set {
  25         number_slot_t *vec;
  26         unsigned int nslots;
  27         bool not;
  28 };
  29
  30 static void
  31 number_setbit(const unsigned int i, number_slot_t *const vec)
  32 {
  33         vec[i / BITS_PER_SLOT] |= (number_slot_t) 1 << (i % BITS_PER_SLOT);
  34 }
  35
  36 static bool
  37 number_isset(const unsigned int i, const number_slot_t *const vec)
  38 {
  39         return vec[i / BITS_PER_SLOT] & ((number_slot_t) 1 << (i % BITS_PER_SLOT));
  40 }
  41
  42 static void
  43 reallocate_number_set(struct number_set *const set, const unsigned int new_nslots)
  44 {
  45         if (new_nslots <= set->nslots)
  46                 return;
  47         set->vec = xreallocarray(set->vec, new_nslots, sizeof(*set->vec));
  48         memset(set->vec + set->nslots, 0,
  49                sizeof(*set->vec) * (new_nslots - set->nslots));
  50         set->nslots = new_nslots;
  51 }
  52
  53 static unsigned int
  54 get_number_setbit(const struct number_set *const set)
  55 {
  56         static_assert(sizeof(number_slot_t) == sizeof(uint32_t),
  57                       "number_slot_t is not 32-bit long");
  58         return popcount32(set->vec, set->nslots);
  59 }
  60
  61 bool
  62 number_set_array_is_empty(const struct number_set *const set,
  63                           const unsigned int idx)
  64 {
  65         return !(set && (set[idx].nslots || set[idx].not));
  66 }
  67
  68 bool
  69 is_number_in_set(const unsigned int number, const struct number_set *const set)
  70 {
  71         return set && ((number / BITS_PER_SLOT < set->nslots)
  72                 && number_isset(number, set->vec)) ^ set->not;
  73 }
  74
  75 bool
  76 is_number_in_set_array(const unsigned int number, const struct number_set *const set,
  77                        const unsigned int idx)
  78 {
  79         return set && ((number / BITS_PER_SLOT < set[idx].nslots)
  80                 && number_isset(number, set[idx].vec)) ^ set[idx].not;
  81 }
  82
  83 bool
  84 is_complete_set(const struct number_set *const set, const unsigned int max_numbers)
  85 {
  86         return set && ((set->not && !set->nslots) ||
  87                        (get_number_setbit(set) == max_numbers));
  88 }
  89
  90 bool
  91 is_complete_set_array(const struct number_set *const set,
  92                       const unsigned int *const max_numbers,
  93                       const unsigned int nmemb)
  94 {
  95         for (unsigned int i = 0; i < nmemb; ++i) {
  96                 if (!is_complete_set(&set[i], max_numbers[i]))
  97                         return false;
  98         }
  99         return true;
 100 }
 101
 102 void
 103 add_number_to_set(const unsigned int number, struct number_set *const set)
 104 {
 105         reallocate_number_set(set, number / BITS_PER_SLOT + 1);
 106         number_setbit(number, set->vec);
 107 }
 108
 109 void
 110 add_number_to_set_array(const unsigned int number, struct number_set *const set,
 111                         const unsigned int idx)
 112 {
 113         add_number_to_set(number, &set[idx]);
 114 }
 115
 116 void
 117 clear_number_set_array(struct number_set *const set, const unsigned int nmemb)
 118 {
 119         unsigned int i;
 120
 121         for (i = 0; i < nmemb; ++i) {
 122                 if (set[i].nslots)
 123                         memset(set[i].vec, 0,
 124                                sizeof(*set[i].vec) * set[i].nslots);
 125                 set[i].not = false;
 126         }
 127 }
 128
 129 void
 130 invert_number_set_array(struct number_set *const set, const unsigned int nmemb)
 131 {
 132         unsigned int i;
 133
 134         for (i = 0; i < nmemb; ++i)
 135                 set[i].not = !set[i].not;
 136 }
 137
 138 struct number_set *
 139 alloc_number_set_array(const unsigned int nmemb)
 140 {
 141         return xcalloc(nmemb, sizeof(struct number_set));
 142 }
 143
 144 void
 145 free_number_set_array(struct number_set *const set, unsigned int nmemb)
 146 {
 147         while (nmemb) {
 148                 --nmemb;
 149                 free(set[nmemb].vec);
 150                 set[nmemb].vec = NULL;
 151         }
 152         free(set);
 153 }