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}
159