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

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