1 /*
2 +----------------------------------------------------------------------+
3 | Zend OPcache JIT |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2014 The PHP Group |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
15 | Authors: Dmitry Stogov <dmitry@zend.com> |
16 +----------------------------------------------------------------------+
17 */
18
19 /* $Id:$ */
20
21 #ifndef _ZEND_BITSET_H_
22 #define _ZEND_BITSET_H_
23
24 typedef zend_ulong *zend_bitset;
25
26 #define ZEND_BITSET_ELM_SIZE sizeof(zend_ulong)
27
28 #if SIZEOF_ZEND_LONG == 4
29 # define ZEND_BITSET_ELM_NUM(n) ((n) >> 5)
30 # define ZEND_BITSET_BIT_NUM(n) ((zend_ulong)(n) & Z_UL(0x1f))
31 #elif SIZEOF_ZEND_LONG == 8
32 # define ZEND_BITSET_ELM_NUM(n) ((n) >> 6)
33 # define ZEND_BITSET_BIT_NUM(n) ((zend_ulong)(n) & Z_UL(0x3f))
34 #else
35 # define ZEND_BITSET_ELM_NUM(n) ((n) / (sizeof(zend_long) * 8))
36 # define ZEND_BITSET_BIT_NUM(n) ((n) % (sizeof(zend_long) * 8))
37 #endif
38
39 /* Returns the number of zend_ulong words needed to store a bitset that is N
40 bits long. */
zend_bitset_len(uint32_t n)41 static inline uint32_t zend_bitset_len(uint32_t n)
42 {
43 return (n + ((sizeof(zend_long) * 8) - 1)) / (sizeof(zend_long) * 8);
44 }
45
46 #define ZEND_BITSET_ALLOCA(n, use_heap) \
47 (zend_bitset)do_alloca((n) * ZEND_BITSET_ELM_SIZE, use_heap)
48
zend_bitset_in(zend_bitset set,uint32_t n)49 static inline zend_bool zend_bitset_in(zend_bitset set, uint32_t n)
50 {
51 return (set[ZEND_BITSET_ELM_NUM(n)] & (Z_UL(1) << ZEND_BITSET_BIT_NUM(n))) != Z_UL(0);
52 }
53
zend_bitset_incl(zend_bitset set,uint32_t n)54 static inline void zend_bitset_incl(zend_bitset set, uint32_t n)
55 {
56 set[ZEND_BITSET_ELM_NUM(n)] |= Z_UL(1) << ZEND_BITSET_BIT_NUM(n);
57 }
58
zend_bitset_excl(zend_bitset set,uint32_t n)59 static inline void zend_bitset_excl(zend_bitset set, uint32_t n)
60 {
61 set[ZEND_BITSET_ELM_NUM(n)] &= ~(Z_UL(1) << ZEND_BITSET_BIT_NUM(n));
62 }
63
zend_bitset_clear(zend_bitset set,uint32_t len)64 static inline void zend_bitset_clear(zend_bitset set, uint32_t len)
65 {
66 memset(set, 0, len * ZEND_BITSET_ELM_SIZE);
67 }
68
zend_bitset_empty(zend_bitset set,uint32_t len)69 static inline int zend_bitset_empty(zend_bitset set, uint32_t len)
70 {
71 uint32_t i;
72 for (i = 0; i < len; i++) {
73 if (set[i]) {
74 return 0;
75 }
76 }
77 return 1;
78 }
79
zend_bitset_fill(zend_bitset set,uint32_t len)80 static inline void zend_bitset_fill(zend_bitset set, uint32_t len)
81 {
82 memset(set, 0xff, len * ZEND_BITSET_ELM_SIZE);
83 }
84
zend_bitset_equal(zend_bitset set1,zend_bitset set2,uint32_t len)85 static inline zend_bool zend_bitset_equal(zend_bitset set1, zend_bitset set2, uint32_t len)
86 {
87 return memcmp(set1, set2, len * ZEND_BITSET_ELM_SIZE) == 0;
88 }
89
zend_bitset_copy(zend_bitset set1,zend_bitset set2,uint32_t len)90 static inline void zend_bitset_copy(zend_bitset set1, zend_bitset set2, uint32_t len)
91 {
92 memcpy(set1, set2, len * ZEND_BITSET_ELM_SIZE);
93 }
94
zend_bitset_intersection(zend_bitset set1,zend_bitset set2,uint32_t len)95 static inline void zend_bitset_intersection(zend_bitset set1, zend_bitset set2, uint32_t len)
96 {
97 uint32_t i;
98
99 for (i = 0; i < len; i++) {
100 set1[i] &= set2[i];
101 }
102 }
103
zend_bitset_union(zend_bitset set1,zend_bitset set2,uint32_t len)104 static inline void zend_bitset_union(zend_bitset set1, zend_bitset set2, uint32_t len)
105 {
106 uint32_t i;
107
108 for (i = 0; i < len; i++) {
109 set1[i] |= set2[i];
110 }
111 }
112
zend_bitset_difference(zend_bitset set1,zend_bitset set2,uint32_t len)113 static inline void zend_bitset_difference(zend_bitset set1, zend_bitset set2, uint32_t len)
114 {
115 uint32_t i;
116
117 for (i = 0; i < len; i++) {
118 set1[i] = set1[i] & ~set2[i];
119 }
120 }
121
zend_bitset_union_with_intersection(zend_bitset set1,zend_bitset set2,zend_bitset set3,zend_bitset set4,uint32_t len)122 static inline void zend_bitset_union_with_intersection(zend_bitset set1, zend_bitset set2, zend_bitset set3, zend_bitset set4, uint32_t len)
123 {
124 uint32_t i;
125
126 for (i = 0; i < len; i++) {
127 set1[i] = set2[i] | (set3[i] & set4[i]);
128 }
129 }
130
zend_bitset_union_with_difference(zend_bitset set1,zend_bitset set2,zend_bitset set3,zend_bitset set4,uint32_t len)131 static inline void zend_bitset_union_with_difference(zend_bitset set1, zend_bitset set2, zend_bitset set3, zend_bitset set4, uint32_t len)
132 {
133 uint32_t i;
134
135 for (i = 0; i < len; i++) {
136 set1[i] = set2[i] | (set3[i] & ~set4[i]);
137 }
138 }
139
zend_bitset_first(zend_bitset set,uint32_t len)140 static inline int zend_bitset_first(zend_bitset set, uint32_t len)
141 {
142 uint32_t i;
143
144 for (i = 0; i < len; i++) {
145 if (set[i]) {
146 int j = ZEND_BITSET_ELM_SIZE * 8 * i;
147 zend_ulong x = set[i];
148 while ((x & Z_UL(1)) == 0) {
149 x = x >> Z_UL(1);
150 j++;
151 }
152 return j;
153 }
154 }
155 return -1; /* empty set */
156 }
157
zend_bitset_last(zend_bitset set,uint32_t len)158 static inline int zend_bitset_last(zend_bitset set, uint32_t len)
159 {
160 uint32_t i = len;
161
162 while (i > 0) {
163 i--;
164 if (set[i]) {
165 int j = ZEND_BITSET_ELM_SIZE * 8 * i - 1;
166 zend_ulong x = set[i];
167 while (x != Z_UL(0)) {
168 x = x >> Z_UL(1);
169 j++;
170 }
171 return j;
172 }
173 }
174 return -1; /* empty set */
175 }
176
177 #endif /* _ZEND_BITSET_H_ */
178
179 /*
180 * Local variables:
181 * tab-width: 4
182 * c-basic-offset: 4
183 * indent-tabs-mode: t
184 * End:
185 */
186
