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.6KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162
  1. /*
  2. * Copyright (c) 2016-2018 Dmitry V. Levin <ldv@altlinux.org>
  3. * All rights reserved.
  4. *
  5. * SPDX-License-Identifier: LGPL-2.1-or-later
  6. */
  7. #ifdef HAVE_CONFIG_H
  8. # include "config.h"
  9. #endif
  10. #include <stdbool.h>
  11. #include <stdlib.h>
  12. #include <string.h>
  13. #include "macros.h"
  14. #include "number_set.h"
  15. #include "xmalloc.h"
  16. typedef unsigned int number_slot_t;
  17. #define BITS_PER_SLOT (sizeof(number_slot_t) * 8)
  18. struct number_set {
  19. number_slot_t *vec;
  20. unsigned int nslots;
  21. bool not;
  22. };
  23. static void
  24. number_setbit(const unsigned int i, number_slot_t *const vec)
  25. {
  26. vec[i / BITS_PER_SLOT] |= (number_slot_t) 1 << (i % BITS_PER_SLOT);
  27. }
  28. static bool
  29. number_isset(const unsigned int i, const number_slot_t *const vec)
  30. {
  31. return vec[i / BITS_PER_SLOT] & ((number_slot_t) 1 << (i % BITS_PER_SLOT));
  32. }
  33. static void
  34. reallocate_number_set(struct number_set *const set, const unsigned int new_nslots)
  35. {
  36. if (new_nslots <= set->nslots)
  37. return;
  38. set->vec = xreallocarray(set->vec, new_nslots, sizeof(*set->vec));
  39. memset(set->vec + set->nslots, 0,
  40. sizeof(*set->vec) * (new_nslots - set->nslots));
  41. set->nslots = new_nslots;
  42. }
  43. bool
  44. number_set_array_is_empty(const struct number_set *const set,
  45. const unsigned int idx)
  46. {
  47. return !(set && (set[idx].nslots || set[idx].not));
  48. }
  49. bool
  50. is_number_in_set(const unsigned int number, const struct number_set *const set)
  51. {
  52. return set && ((number / BITS_PER_SLOT < set->nslots)
  53. && number_isset(number, set->vec)) ^ set->not;
  54. }
  55. bool
  56. is_number_in_set_array(const unsigned int number, const struct number_set *const set,
  57. const unsigned int idx)
  58. {
  59. return set && ((number / BITS_PER_SLOT < set[idx].nslots)
  60. && number_isset(number, set[idx].vec)) ^ set[idx].not;
  61. }
  62. void
  63. add_number_to_set(const unsigned int number, struct number_set *const set)
  64. {
  65. reallocate_number_set(set, number / BITS_PER_SLOT + 1);
  66. number_setbit(number, set->vec);
  67. }
  68. void
  69. add_number_to_set_array(const unsigned int number, struct number_set *const set,
  70. const unsigned int idx)
  71. {
  72. add_number_to_set(number, &set[idx]);
  73. }
  74. void
  75. clear_number_set_array(struct number_set *const set, const unsigned int nmemb)
  76. {
  77. unsigned int i;
  78. for (i = 0; i < nmemb; ++i) {
  79. if (set[i].nslots)
  80. memset(set[i].vec, 0,
  81. sizeof(*set[i].vec) * set[i].nslots);
  82. set[i].not = false;
  83. }
  84. }
  85. void
  86. invert_number_set_array(struct number_set *const set, const unsigned int nmemb)
  87. {
  88. unsigned int i;
  89. for (i = 0; i < nmemb; ++i)
  90. set[i].not = !set[i].not;
  91. }
  92. /**
  93. * Returns index of the next non-zero bit (starting at bit number) in number set
  94. * or limit.
  95. */
  96. unsigned int
  97. next_set_bit_in_set_array(unsigned int number,
  98. const struct number_set *const set,
  99. const unsigned int idx, const unsigned limit)
  100. {
  101. unsigned pos;
  102. unsigned limit_slots = MIN(set[idx].nslots,
  103. (limit + BITS_PER_SLOT - 1) / BITS_PER_SLOT);
  104. number_slot_t bitmask;
  105. number_slot_t cur_slot;
  106. for (pos = number / BITS_PER_SLOT; pos < limit_slots; pos++) {
  107. cur_slot = set[idx].vec[pos] ^ (-1U * set[idx].not);
  108. if (cur_slot == 0) {
  109. number = (number + BITS_PER_SLOT) & (-BITS_PER_SLOT);
  110. continue;
  111. }
  112. bitmask = 1 << (number & (BITS_PER_SLOT - 1));
  113. for (;;) {
  114. if (cur_slot & bitmask)
  115. return MIN(number, limit);
  116. number++;
  117. bitmask <<= 1;
  118. /* This check *can't be* optimized out: */
  119. if (bitmask == 0)
  120. break;
  121. }
  122. }
  123. return limit;
  124. }
  125. struct number_set *
  126. alloc_number_set_array(const unsigned int nmemb)
  127. {
  128. return xcalloc(nmemb, sizeof(struct number_set));
  129. }
  130. void
  131. free_number_set_array(struct number_set *const set, unsigned int nmemb)
  132. {
  133. while (nmemb) {
  134. --nmemb;
  135. free(set[nmemb].vec);
  136. set[nmemb].vec = NULL;
  137. }
  138. free(set);
  139. }