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 #define BITS_PER_SLOT (sizeof(number_slot_t) * 8)
  39
  40 static void
  41 number_setbit(const unsigned int i, number_slot_t *const vec)
  42 {
  43         vec[i / BITS_PER_SLOT] |= (number_slot_t) 1 << (i % BITS_PER_SLOT);
  44 }
  45
  46 static bool
  47 number_isset(const unsigned int i, const number_slot_t *const vec)
  48 {
  49         return vec[i / BITS_PER_SLOT] & ((number_slot_t) 1 << (i % BITS_PER_SLOT));
  50 }
  51
  52 static void
  53 reallocate_number_set(struct number_set *const set, const unsigned int new_nslots)
  54 {
  55         if (new_nslots <= set->nslots)
  56                 return;
  57         set->vec = xreallocarray(set->vec, new_nslots, sizeof(*set->vec));
  58         memset(set->vec + set->nslots, 0,
  59                sizeof(*set->vec) * (new_nslots - set->nslots));
  60         set->nslots = new_nslots;
  61 }
  62
  63 bool
  64 number_set_array_is_empty(const struct number_set *const set,
  65                           const unsigned int idx)
  66 {
  67         return !(set && (set[idx].nslots || set[idx].not));
  68 }
  69
  70 bool
  71 is_number_in_set(const unsigned int number, const struct number_set *const set)
  72 {
  73         return set && ((number / BITS_PER_SLOT < set->nslots)
  74                 && number_isset(number, set->vec)) ^ set->not;
  75 }
  76
  77 bool
  78 is_number_in_set_array(const unsigned int number, const struct number_set *const set,
  79                        const unsigned int idx)
  80 {
  81         return set && ((number / BITS_PER_SLOT < set[idx].nslots)
  82                 && number_isset(number, set[idx].vec)) ^ set[idx].not;
  83 }
  84
  85 void
  86 add_number_to_set(const unsigned int number, struct number_set *const set)
  87 {
  88         reallocate_number_set(set, number / BITS_PER_SLOT + 1);
  89         number_setbit(number, set->vec);
  90 }
  91
  92 void
  93 add_number_to_set_array(const unsigned int number, struct number_set *const set,
  94                         const unsigned int idx)
  95 {
  96         add_number_to_set(number, &set[idx]);
  97 }
  98
  99 void
 100 clear_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                 if (set[i].nslots)
 106                         memset(set[i].vec, 0,
 107                                sizeof(*set[i].vec) * set[i].nslots);
 108                 set[i].not = false;
 109         }
 110 }
 111
 112 void
 113 invert_number_set_array(struct number_set *const set, const unsigned int nmemb)
 114 {
 115         unsigned int i;
 116
 117         for (i = 0; i < nmemb; ++i)
 118                 set[i].not = !set[i].not;
 119 }
 120
 121 struct number_set *
 122 alloc_number_set_array(const unsigned int nmemb)
 123 {
 124         return xcalloc(nmemb, sizeof(struct number_set));
 125 }
 126
 127 void
 128 free_number_set_array(struct number_set *const set, unsigned int nmemb)
 129 {
 130         while (nmemb) {
 131                 --nmemb;
 132                 free(set[nmemb].vec);
 133                 set[nmemb].vec = NULL;
 134         }
 135         free(set);
 136 }