Home | History | Annotate | Download | only in strace 
      1 /*
      2  * Copyright (c) 2016-2017 Dmitry V. Levin <ldv (at) 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 }
    144