async library for manda (adaptive backend manager protocol)
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.
 
 
 
 

115 lines
3.2 KiB

  1. #include "idlist.h"
  2. #define UL_BITS (sizeof(gulong) * 8)
  3. /* There are often no explicit bit shifts used in this code. This is on purpose, the
  4. * code looks much cleaner without them, the correct constant for *, / and % is easier to calculate
  5. * as constant (UL_BITS) and the compiler should know how to optimize the operations; as UL_BITS is hopefully
  6. * of the form 2^n this should result in bit shifts in the executable code.
  7. */
  8. manda_IDList* manda_idlist_new(gint max_ids) {
  9. manda_IDList *l = g_slice_new0(manda_IDList);
  10. g_assert(max_ids > 0);
  11. l->bitvector = g_array_new(FALSE, TRUE, sizeof(gulong));
  12. l->max_ids = max_ids;
  13. l->next_free_id = -1;
  14. l->used_ids = 0;
  15. return l;
  16. }
  17. void manda_idlist_free(manda_IDList *l) {
  18. if (!l) return;
  19. g_array_free(l->bitvector, TRUE);
  20. g_slice_free(manda_IDList, l);
  21. }
  22. static void mark_bit(GArray *a, gint id) {
  23. guint ndx = id / UL_BITS, bndx = id % UL_BITS;
  24. gulong bmask = 1 << bndx;
  25. g_assert(id >= 0 && ndx < a->len);
  26. g_assert(0 == (g_array_index(a, gulong, ndx) & (bmask))); /* bit musn't be set */
  27. g_array_index(a, gulong, ndx) |= (bmask);
  28. }
  29. static void clear_bit(GArray *a, gint id) {
  30. guint ndx = id / UL_BITS, bndx = id % UL_BITS;
  31. gulong bmask = 1 << bndx;
  32. g_assert(id >= 0 && ndx < a->len);
  33. g_assert(0 != (g_array_index(a, gulong, ndx) & (bmask))); /* bit must be set */
  34. g_array_index(a, gulong, ndx) &= ~(bmask);
  35. }
  36. static void idlist_reserve(GArray *a, guint id) {
  37. guint ndx = id / UL_BITS;
  38. if (ndx >= a->len) g_array_set_size(a, ndx+1);
  39. }
  40. gint manda_idlist_get(manda_IDList *l) {
  41. guint fndx, ndx;
  42. gint newid, bndx;
  43. gulong u = -1;
  44. GArray *a = l->bitvector;
  45. if (l->used_ids >= l->max_ids) return -1;
  46. if (l->next_free_id < 0) { /* all ids in use */
  47. newid = l->used_ids++;
  48. idlist_reserve(a, newid);
  49. mark_bit(a, newid);
  50. return newid;
  51. }
  52. /* search for an array entry which doesn't have all bits set (i.e. != (gulong) -1)
  53. * start with the entry of next_free_id, all below are in use anyway
  54. */
  55. fndx = l->next_free_id / UL_BITS;
  56. for (ndx = fndx; ndx < a->len && ((gulong) -1 == (u = g_array_index(a, gulong, ndx))); ndx++) ;
  57. if (ndx == a->len) { /* again: all ids are in use */
  58. l->next_free_id = -1;
  59. newid = l->used_ids++;
  60. idlist_reserve(a, newid);
  61. mark_bit(a, newid);
  62. return newid;
  63. }
  64. /* array entry != -1, search for free bit */
  65. if (fndx == ndx) bndx = (l->next_free_id / UL_BITS) - 1;
  66. else bndx = -1;
  67. bndx = g_bit_nth_lsf(~u, bndx);
  68. /* no free bit found; should never happen as u != -1 and next_free_id should be correct, i.e. all bits <= the bit start index should be set */
  69. g_assert(bndx != -1);
  70. newid = ndx * UL_BITS + bndx;
  71. if (newid == (gint) l->used_ids) {
  72. l->next_free_id = -1;
  73. } else {
  74. l->next_free_id = newid+1;
  75. }
  76. l->used_ids++;
  77. mark_bit(a, newid);
  78. return newid;
  79. }
  80. gboolean manda_idlist_is_used(manda_IDList *l, gint id) {
  81. GArray *a = l->bitvector;
  82. guint ndx = id / UL_BITS, bndx = id % UL_BITS;
  83. gulong bmask = 1 << bndx;
  84. if (id < 0 || ndx >= a->len) return FALSE;
  85. return (0 != (g_array_index(a, gulong, ndx) & (bmask)));
  86. }
  87. void manda_idlist_put(manda_IDList *l, gint id) {
  88. clear_bit(l->bitvector, id);
  89. l->used_ids--;
  90. if ((l->next_free_id < 0 && (guint) id < l->used_ids) || id < l->next_free_id) l->next_free_id = id;
  91. }