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 void
  91 add_number_to_set(const unsigned int number, struct number_set *const set)
  92 {
  93         reallocate_number_set(set, number / BITS_PER_SLOT + 1);
  94         number_setbit(number, set->vec);
  95 }
  96
  97 void
  98 add_number_to_set_array(const unsigned int number, struct number_set *const set,
  99                         const unsigned int idx)
 100 {
 101         add_number_to_set(number, &set[idx]);
 102 }
 103
 104 void
 105 clear_number_set_array(struct number_set *const set, const unsigned int nmemb)
 106 {
 107         unsigned int i;
 108
 109         for (i = 0; i < nmemb; ++i) {
 110                 if (set[i].nslots)
 111                         memset(set[i].vec, 0,
 112                                sizeof(*set[i].vec) * set[i].nslots);
 113                 set[i].not = false;
 114         }
 115 }
 116
 117 void
 118 invert_number_set_array(struct number_set *const set, const unsigned int nmemb)
 119 {
 120         unsigned int i;
 121
 122         for (i = 0; i < nmemb; ++i)
 123                 set[i].not = !set[i].not;
 124 }
 125
 126 struct number_set *
 127 alloc_number_set_array(const unsigned int nmemb)
 128 {
 129         return xcalloc(nmemb, sizeof(struct number_set));
 130 }
 131
 132 void
 133 free_number_set_array(struct number_set *const set, unsigned int nmemb)
 134 {
 135         while (nmemb) {
 136                 --nmemb;
 137                 free(set[nmemb].vec);
 138                 set[nmemb].vec = NULL;
 139         }
 140         free(set);
 141 }