Mirror of strace – the linux syscall tracer
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

number_set.c 3.5KB

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