1
2 /* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */
3
4 /* FLASK */
5
6 /*
7 * An extensible bitmap is a bitmap that supports an
8 * arbitrary number of bits. Extensible bitmaps are
9 * used to represent sets of values, such as types,
10 * roles, categories, and classes.
11 *
12 * Each extensible bitmap is implemented as a linked
13 * list of bitmap nodes, where each bitmap node has
14 * an explicitly specified starting bit position within
15 * the total bitmap.
16 */
17
18 #ifndef _SEPOL_POLICYDB_EBITMAP_H_
19 #define _SEPOL_POLICYDB_EBITMAP_H_
20
21 #include <stdint.h>
22 #include <string.h>
23
24 #define MAPTYPE uint64_t /* portion of bitmap in each node */
25 #define MAPSIZE (sizeof(MAPTYPE) * 8) /* number of bits in node bitmap */
26 #define MAPBIT 1ULL /* a bit in the node bitmap */
27
28 typedef struct ebitmap_node {
29 uint32_t startbit; /* starting position in the total bitmap */
30 MAPTYPE map; /* this node's portion of the bitmap */
31 struct ebitmap_node *next;
32 } ebitmap_node_t;
33
34 typedef struct ebitmap {
35 ebitmap_node_t *node; /* first node in the bitmap */
36 uint32_t highbit; /* highest position in the total bitmap */
37 } ebitmap_t;
38
39 #define ebitmap_length(e) ((e)->highbit)
40 #define ebitmap_startbit(e) ((e)->node ? (e)->node->startbit : 0)
41 #define ebitmap_startnode(e) ((e)->node)
42
ebitmap_start(const ebitmap_t * e,ebitmap_node_t ** n)43 static inline unsigned int ebitmap_start(const ebitmap_t * e,
44 ebitmap_node_t ** n)
45 {
46
47 *n = e->node;
48 return ebitmap_startbit(e);
49 }
50
ebitmap_init(ebitmap_t * e)51 static inline void ebitmap_init(ebitmap_t * e)
52 {
53 memset(e, 0, sizeof(*e));
54 }
55
ebitmap_next(ebitmap_node_t ** n,unsigned int bit)56 static inline unsigned int ebitmap_next(ebitmap_node_t ** n, unsigned int bit)
57 {
58 if ((bit == ((*n)->startbit + MAPSIZE - 1)) && (*n)->next) {
59 *n = (*n)->next;
60 return (*n)->startbit;
61 }
62
63 return (bit + 1);
64 }
65
ebitmap_node_get_bit(ebitmap_node_t * n,unsigned int bit)66 static inline int ebitmap_node_get_bit(ebitmap_node_t * n, unsigned int bit)
67 {
68 if (n->map & (MAPBIT << (bit - n->startbit)))
69 return 1;
70 return 0;
71 }
72
73 #define ebitmap_for_each_bit(e, n, bit) \
74 for (bit = ebitmap_start(e, &n); bit < ebitmap_length(e); bit = ebitmap_next(&n, bit)) \
75
76 extern int ebitmap_cmp(const ebitmap_t * e1, const ebitmap_t * e2);
77 extern int ebitmap_or(ebitmap_t * dst, const ebitmap_t * e1, const ebitmap_t * e2);
78 extern int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1);
79 extern int ebitmap_and(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2);
80 extern int ebitmap_xor(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2);
81 extern int ebitmap_not(ebitmap_t *dst, ebitmap_t *e1, unsigned int maxbit);
82 extern int ebitmap_andnot(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2, unsigned int maxbit);
83 extern unsigned int ebitmap_cardinality(ebitmap_t *e1);
84 extern int ebitmap_hamming_distance(ebitmap_t * e1, ebitmap_t * e2);
85 extern int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src);
86 extern int ebitmap_contains(const ebitmap_t * e1, const ebitmap_t * e2);
87 extern int ebitmap_get_bit(const ebitmap_t * e, unsigned int bit);
88 extern int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value);
89 extern void ebitmap_destroy(ebitmap_t * e);
90 extern int ebitmap_read(ebitmap_t * e, void *fp);
91
92 #endif /* _EBITMAP_H_ */
93
94 /* FLASK */
95