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 is_number_in_set(const unsigned int number, const struct number_set *const set)
  65 {
  66         return set && ((number / BITS_PER_SLOT < set->nslots)
  67                 && number_isset(number, set->vec)) ^ set->not;
  68 }
  69
  70 void
  71 add_number_to_set(const unsigned int number, struct number_set *const set)
  72 {
  73         reallocate_number_set(set, number / BITS_PER_SLOT + 1);
  74         number_setbit(number, set->vec);
  75 }