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  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. The name of the author may not be used to endorse or promote products
  14  *    derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #ifdef HAVE_CONFIG_H
  29 # include "config.h"
  30 #endif
  31
  32 #include <stdbool.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35 #include "number_set.h"
  36 #include "xmalloc.h"
  37
  38 typedef unsigned int number_slot_t;
  39 #define BITS_PER_SLOT (sizeof(number_slot_t) * 8)
  40
  41 struct number_set {
  42         number_slot_t *vec;
  43         unsigned int nslots;
  44         bool not;
  45 };
  46
  47 static void
  48 number_setbit(const unsigned int i, number_slot_t *const vec)
  49 {
  50         vec[i / BITS_PER_SLOT] |= (number_slot_t) 1 << (i % BITS_PER_SLOT);
  51 }
  52
  53 static bool
  54 number_isset(const unsigned int i, const number_slot_t *const vec)
  55 {
  56         return vec[i / BITS_PER_SLOT] & ((number_slot_t) 1 << (i % BITS_PER_SLOT));
  57 }
  58
  59 static void
  60 reallocate_number_set(struct number_set *const set, const unsigned int new_nslots)
  61 {
  62         if (new_nslots <= set->nslots)
  63                 return;
  64         set->vec = xreallocarray(set->vec, new_nslots, sizeof(*set->vec));
  65         memset(set->vec + set->nslots, 0,
  66                sizeof(*set->vec) * (new_nslots - set->nslots));
  67         set->nslots = new_nslots;
  68 }
  69
  70 bool
  71 number_set_array_is_empty(const struct number_set *const set,
  72                           const unsigned int idx)
  73 {
  74         return !(set && (set[idx].nslots || set[idx].not));
  75 }
  76
  77 bool
  78 is_number_in_set(const unsigned int number, const struct number_set *const set)
  79 {
  80         return set && ((number / BITS_PER_SLOT < set->nslots)
  81                 && number_isset(number, set->vec)) ^ set->not;
  82 }
  83
  84 bool
  85 is_number_in_set_array(const unsigned int number, const struct number_set *const set,
  86                        const unsigned int idx)
  87 {
  88         return set && ((number / BITS_PER_SLOT < set[idx].nslots)
  89                 && number_isset(number, set[idx].vec)) ^ set[idx].not;
  90 }
  91
  92 void
  93 add_number_to_set(const unsigned int number, struct number_set *const set)
  94 {
  95         reallocate_number_set(set, number / BITS_PER_SLOT + 1);
  96         number_setbit(number, set->vec);
  97 }
  98
  99 void
 100 add_number_to_set_array(const unsigned int number, struct number_set *const set,
 101                         const unsigned int idx)
 102 {
 103         add_number_to_set(number, &set[idx]);
 104 }
 105
 106 void
 107 clear_number_set_array(struct number_set *const set, const unsigned int nmemb)
 108 {
 109         unsigned int i;
 110
 111         for (i = 0; i < nmemb; ++i) {
 112                 if (set[i].nslots)
 113                         memset(set[i].vec, 0,
 114                                sizeof(*set[i].vec) * set[i].nslots);
 115                 set[i].not = false;
 116         }
 117 }
 118
 119 void
 120 invert_number_set_array(struct number_set *const set, const unsigned int nmemb)
 121 {
 122         unsigned int i;
 123
 124         for (i = 0; i < nmemb; ++i)
 125                 set[i].not = !set[i].not;
 126 }
 127
 128 struct number_set *
 129 alloc_number_set_array(const unsigned int nmemb)
 130 {
 131         return xcalloc(nmemb, sizeof(struct number_set));
 132 }
 133
 134 void
 135 free_number_set_array(struct number_set *const set, unsigned int nmemb)
 136 {
 137         while (nmemb) {
 138                 --nmemb;
 139                 free(set[nmemb].vec);
 140                 set[nmemb].vec = NULL;
 141         }
 142         free(set);
 143 }