[PATCH] selinux: Reduce memory use by avtab
[linux-3.10.git] / security / selinux / ss / ebitmap.h
1 /*
2  * An extensible bitmap is a bitmap that supports an
3  * arbitrary number of bits.  Extensible bitmaps are
4  * used to represent sets of values, such as types,
5  * roles, categories, and classes.
6  *
7  * Each extensible bitmap is implemented as a linked
8  * list of bitmap nodes, where each bitmap node has
9  * an explicitly specified starting bit position within
10  * the total bitmap.
11  *
12  * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
13  */
14 #ifndef _SS_EBITMAP_H_
15 #define _SS_EBITMAP_H_
16
17 #define MAPTYPE u64                     /* portion of bitmap in each node */
18 #define MAPSIZE (sizeof(MAPTYPE) * 8)   /* number of bits in node bitmap */
19 #define MAPBIT  1ULL                    /* a bit in the node bitmap */
20
21 struct ebitmap_node {
22         u32 startbit;           /* starting position in the total bitmap */
23         MAPTYPE map;            /* this node's portion of the bitmap */
24         struct ebitmap_node *next;
25 };
26
27 struct ebitmap {
28         struct ebitmap_node *node;      /* first node in the bitmap */
29         u32 highbit;    /* highest position in the total bitmap */
30 };
31
32 #define ebitmap_length(e) ((e)->highbit)
33 #define ebitmap_startbit(e) ((e)->node ? (e)->node->startbit : 0)
34
35 static inline unsigned int ebitmap_start(struct ebitmap *e,
36                                          struct ebitmap_node **n)
37 {
38         *n = e->node;
39         return ebitmap_startbit(e);
40 }
41
42 static inline void ebitmap_init(struct ebitmap *e)
43 {
44         memset(e, 0, sizeof(*e));
45 }
46
47 static inline unsigned int ebitmap_next(struct ebitmap_node **n,
48                                         unsigned int bit)
49 {
50         if ((bit == ((*n)->startbit + MAPSIZE - 1)) &&
51             (*n)->next) {
52                 *n = (*n)->next;
53                 return (*n)->startbit;
54         }
55
56         return (bit+1);
57 }
58
59 static inline int ebitmap_node_get_bit(struct ebitmap_node * n,
60                                        unsigned int bit)
61 {
62         if (n->map & (MAPBIT << (bit - n->startbit)))
63                 return 1;
64         return 0;
65 }
66
67 #define ebitmap_for_each_bit(e, n, bit) \
68         for (bit = ebitmap_start(e, &n); bit < ebitmap_length(e); bit = ebitmap_next(&n, bit)) \
69
70 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2);
71 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src);
72 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2);
73 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit);
74 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value);
75 void ebitmap_destroy(struct ebitmap *e);
76 int ebitmap_read(struct ebitmap *e, void *fp);
77
78 #endif  /* _SS_EBITMAP_H_ */