1 /*
2 * Copyright (c) 2023 Institute of Parallel And Distributed Systems (IPADS), Shanghai Jiao Tong University (SJTU)
3 * Licensed under the Mulan PSL v2.
4 * You can use this software according to the terms and conditions of the Mulan PSL v2.
5 * You may obtain a copy of Mulan PSL v2 at:
6 * http://license.coscl.org.cn/MulanPSL2
7 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR
8 * IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR
9 * PURPOSE.
10 * See the Mulan PSL v2 for more details.
11 */
12
13 #pragma once
14
15 #include <chcore/type.h>
16 #include <errno.h>
17 #include <stdint.h>
18 #include <stdlib.h>
19 #include <assert.h>
20 #include <string.h>
21 #include <sys/types.h>
22
23 #ifdef __cplusplus
24 extern "C" {
25 #endif
26
27 #define DIV_ROUND_UP(n, d) (((n) + (d)-1) / (d))
28
29 /* Avaliable id range is [min_id, max_id) */
30 struct id_manager {
31 int min_id;
32 int max_id;
33 int curr_slot;
34 long *bitmap;
35 size_t nr_slots;
36 };
37
38 #define BITS_PER_LONG (sizeof(long) * 8)
39 #define DEFAULT_INIT_ID (0)
40
41 #define __assemble_idx_bit(idx, bit) ((idx)*BITS_PER_LONG + (bit))
42
43 #define __disassemble_idx_bit(id, idx, bit) \
44 do { \
45 idx = (id) / BITS_PER_LONG; \
46 bit = (id) % BITS_PER_LONG; \
47 } while (0)
48
49 #define __clear_bit(slot, bit) (slot) = (slot) & ~(1UL << (bit))
50
51 #define __set_bit(slot, bit) (slot) = (slot) | (1UL << (bit))
52
53 #define __query_bit(slot, bit) ((slot) & (1UL << (bit)))
54
__find_first_zero(long slot)55 static inline int __find_first_zero(long slot)
56 {
57 int i;
58 for (i = 0; i < BITS_PER_LONG; ++i) {
59 if (!__query_bit(slot, i))
60 return i;
61 }
62 return i;
63 }
64
alloc_id(struct id_manager * idman)65 static inline int alloc_id(struct id_manager *idman)
66 {
67 size_t nr_slots_tried = 0;
68 int bit;
69 int id;
70
71 while (nr_slots_tried <= idman->nr_slots) {
72 /* Loop back. */
73 if (idman->curr_slot >= idman->nr_slots)
74 idman->curr_slot = 0;
75
76 bit = __find_first_zero(idman->bitmap[idman->curr_slot]);
77 if (bit == BITS_PER_LONG) {
78 /* All bits are set. Try next slot. */
79 next:
80 idman->curr_slot += 1;
81 nr_slots_tried += 1;
82 continue;
83 }
84
85 id = __assemble_idx_bit(idman->curr_slot, bit);
86 if (id >= idman->max_id)
87 goto next;
88
89 __set_bit(idman->bitmap[idman->curr_slot], bit);
90
91 return id;
92 }
93
94 return -EINVAL;
95 }
96
init_id_manager(struct id_manager * idman,int max_id,int min_id)97 static inline int init_id_manager(struct id_manager *idman, int max_id,
98 int min_id)
99 {
100 int i;
101 size_t __size = DIV_ROUND_UP(max_id, BITS_PER_LONG);
102
103 /* min_id must >= 0 */
104 if (min_id < 0)
105 return -EINVAL;
106
107 idman->min_id = min_id;
108 idman->max_id = max_id;
109 idman->curr_slot = 0;
110 idman->bitmap = malloc(__size * sizeof(long));
111 if (!idman->bitmap)
112 return -EINVAL;
113
114 idman->nr_slots = __size;
115
116 /* NOTE(MK): (bitmap[0] & 0x1) is the first bit. */
117 memset(idman->bitmap, 0, __size * sizeof(long));
118
119 /* Set min_id by reserving all the id below min_id */
120 for (i = DEFAULT_INIT_ID; i < min_id; i++) {
121 alloc_id(idman);
122 }
123
124 return 0;
125 }
126
free_id(struct id_manager * idman,int id)127 static inline int free_id(struct id_manager *idman, int id)
128 {
129 off_t idx, bit;
130
131 assert(id >= idman->min_id && id < idman->max_id);
132
133 __disassemble_idx_bit(id, idx, bit);
134
135 if (!__query_bit(idman->bitmap[idx], bit))
136 return -ENOENT;
137
138 __clear_bit(idman->bitmap[idx], bit);
139
140 idman->curr_slot = idx;
141
142 return 0;
143 }
144
query_id(struct id_manager * idman,int id)145 static inline int query_id(struct id_manager *idman, int id)
146 {
147 off_t idx, bit;
148
149 assert(id >= idman->min_id && id < idman->max_id);
150
151 __disassemble_idx_bit(id, idx, bit);
152
153 if (!__query_bit(idman->bitmap[idx], bit))
154 return -ENOENT;
155
156 return 0;
157 }
158
159 #ifdef __cplusplus
160 }
161 #endif
162