x11rb_protocol/
id_allocator.rs

1//! A mechanism for allocating XIDs.
2
3use crate::errors::ConnectError;
4use crate::protocol::xc_misc::GetXIDRangeReply;
5
6#[cfg(feature = "std")]
7use std::error::Error;
8
9use core::fmt;
10
11/// An allocator for X11 IDs.
12///
13/// This struct handles the client-side generation of X11 IDs. The ID allocation is based on a
14/// range of IDs that the server assigned us. This range is described by a base and a mask. From
15/// the X11 protocol reference manual:
16///
17/// > The resource-id-mask contains a single contiguous set of bits (at least 18). The client
18/// > allocates resource IDs [..] by choosing a value with only some subset of these bits set and
19/// > ORing it with resource-id-base.
20#[derive(Debug, Clone, Copy)]
21pub struct IdAllocator {
22    next_id: u32,
23    max_id: u32,
24    increment: u32,
25}
26
27impl IdAllocator {
28    /// Create a new instance of an ID allocator.
29    ///
30    /// The arguments should be the `resource_id_base` and `resource_id_mask` values that the X11
31    /// server sent in a `Setup` response.
32    pub fn new(id_base: u32, id_mask: u32) -> Result<Self, ConnectError> {
33        if id_mask == 0 {
34            return Err(ConnectError::ZeroIdMask);
35        }
36        // Find the right-most set bit in id_mask, e.g. for 0b110, this results in 0b010.
37        let increment = id_mask & (1 + !id_mask);
38        Ok(Self {
39            next_id: id_base,
40            max_id: id_base | id_mask,
41            increment,
42        })
43    }
44
45    /// Update the available range of IDs based on a GetXIDRangeReply
46    pub fn update_xid_range(&mut self, xidrange: &GetXIDRangeReply) -> Result<(), IdsExhausted> {
47        let (start, count) = (xidrange.start_id, xidrange.count);
48        // Apparently (0, 1) is how the server signals "I am out of IDs".
49        // The second case avoids an underflow below and should never happen.
50        if (start, count) == (0, 1) || count == 0 {
51            return Err(IdsExhausted);
52        }
53        self.next_id = start;
54        self.max_id = start + (count - 1) * self.increment;
55        Ok(())
56    }
57
58    /// Generate the next ID.
59    pub fn generate_id(&mut self) -> Option<u32> {
60        if self.next_id > self.max_id {
61            None
62        } else {
63            let id = self.next_id;
64            self.next_id += self.increment;
65            Some(id)
66        }
67    }
68}
69
70/// The XID range has been exhausted.
71#[derive(Debug, Copy, Clone)]
72pub struct IdsExhausted;
73
74impl fmt::Display for IdsExhausted {
75    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
76        write!(f, "XID range has been exhausted")
77    }
78}
79
80#[cfg(feature = "std")]
81impl Error for IdsExhausted {}
82
83#[cfg(test)]
84mod test {
85    use super::{GetXIDRangeReply, IdAllocator, IdsExhausted};
86
87    #[test]
88    fn exhaustive() {
89        let mut allocator = IdAllocator::new(0x2800, 0x1ff).unwrap();
90        for expected in 0x2800..=0x29ff {
91            assert_eq!(Some(expected), allocator.generate_id());
92        }
93        assert_eq!(None, allocator.generate_id());
94    }
95
96    #[test]
97    fn increment() {
98        let mut allocator = IdAllocator::new(0, 0b1100).unwrap();
99        assert_eq!(Some(0b0000), allocator.generate_id());
100        assert_eq!(Some(0b0100), allocator.generate_id());
101        assert_eq!(Some(0b1000), allocator.generate_id());
102        assert_eq!(Some(0b1100), allocator.generate_id());
103        assert_eq!(None, allocator.generate_id());
104    }
105
106    #[test]
107    fn new_range() {
108        let mut allocator = IdAllocator::new(0x420, 2).unwrap();
109        assert_eq!(Some(0x420), allocator.generate_id());
110        assert_eq!(Some(0x422), allocator.generate_id());
111        // At this point the range is exhausted and a GetXIDRange request needs to be sent
112        assert_eq!(None, allocator.generate_id());
113        allocator
114            .update_xid_range(&generate_get_xid_range_reply(0x13370, 3))
115            .unwrap();
116        assert_eq!(Some(0x13370), allocator.generate_id());
117        assert_eq!(Some(0x13372), allocator.generate_id());
118        assert_eq!(Some(0x13374), allocator.generate_id());
119        // At this point the range is exhausted and a GetXIDRange request needs to be sent
120        assert_eq!(None, allocator.generate_id());
121        allocator
122            .update_xid_range(&generate_get_xid_range_reply(0x13370, 3))
123            .unwrap();
124        assert_eq!(Some(0x13370), allocator.generate_id());
125    }
126
127    #[test]
128    fn invalid_new_arg() {
129        let err = IdAllocator::new(1234, 0).unwrap_err();
130        if let super::ConnectError::ZeroIdMask = err {
131        } else {
132            panic!("Wrong error: {:?}", err);
133        }
134    }
135
136    #[test]
137    fn invalid_update_arg() {
138        fn check_ids_exhausted(arg: &Result<(), IdsExhausted>) {
139            if let Err(IdsExhausted) = arg {
140            } else {
141                panic!("Expected IdsExhausted, got {:?}", arg);
142            }
143        }
144
145        let mut allocator = IdAllocator::new(0x420, 2).unwrap();
146        check_ids_exhausted(&allocator.update_xid_range(&generate_get_xid_range_reply(0, 1)));
147        check_ids_exhausted(&allocator.update_xid_range(&generate_get_xid_range_reply(1, 0)));
148    }
149
150    fn generate_get_xid_range_reply(start_id: u32, count: u32) -> GetXIDRangeReply {
151        GetXIDRangeReply {
152            sequence: 0,
153            length: 0,
154            start_id,
155            count,
156        }
157    }
158}
x11rb_protocol/id_allocator.rs

x11rb_protocol/
id_allocator.rs
