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

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141
  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. void
  78. add_number_to_set(const unsigned int number, struct number_set *const set)
  79. {
  80. reallocate_number_set(set, number / BITS_PER_SLOT + 1);
  81. number_setbit(number, set->vec);
  82. }
  83. void
  84. add_number_to_set_array(const unsigned int number, struct number_set *const set,
  85. const unsigned int idx)
  86. {
  87. add_number_to_set(number, &set[idx]);
  88. }
  89. void
  90. clear_number_set_array(struct number_set *const set, const unsigned int nmemb)
  91. {
  92. unsigned int i;
  93. for (i = 0; i < nmemb; ++i) {
  94. if (set[i].nslots)
  95. memset(set[i].vec, 0,
  96. sizeof(*set[i].vec) * set[i].nslots);
  97. set[i].not = false;
  98. }
  99. }
  100. void
  101. invert_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. set[i].not = !set[i].not;
  106. }
  107. struct number_set *
  108. alloc_number_set_array(const unsigned int nmemb)
  109. {
  110. return xcalloc(nmemb, sizeof(struct number_set));
  111. }
  112. void
  113. free_number_set_array(struct number_set *const set, unsigned int nmemb)
  114. {
  115. while (nmemb) {
  116. --nmemb;
  117. free(set[nmemb].vec);
  118. set[nmemb].vec = NULL;
  119. }
  120. free(set);
  121. }