| // Copyright 2018 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| use failure::bail; |
| |
| const ASSOCIATION_ID_MAX_VALUE: u16 = 2007; |
| |
| pub type AssociationId = u16; |
| |
| #[derive(Debug)] |
| pub struct Map { |
| // bitmap representing the "claimed" association IDs; examples: |
| // Claimed AIDs: [0] -- array 1st element is 1, remaining are zeroes |
| // Claimed AIDs: [0, 1] -- array 1st element is 3, remaining are zeroes |
| // Claimed AIDs: [64] -- array 2nd element is 1, remaining are zeroes |
| // |
| // Type u64 was chosen since it's the largest unsigned integer type that provides methods |
| // like `count_zeroes` and `trailing_zeros`. Array has 32 elements since 64 * 32 provides |
| // enough bits to cover the maximum number of clients (2008). |
| aids: [u64; 32], |
| } |
| |
| impl Map { |
| const ELEM_BITS: u16 = 64; |
| |
| pub fn assign_aid(&mut self) -> Result<AssociationId, failure::Error> { |
| for (i, bitmap) in self.aids.iter_mut().enumerate() { |
| if bitmap.count_zeros() > 0 { |
| let first_unset_bit_pos = (!*bitmap).trailing_zeros() as u16; |
| let aid = first_unset_bit_pos + Map::ELEM_BITS * (i as u16); |
| if aid <= ASSOCIATION_ID_MAX_VALUE { |
| *bitmap |= 1 << first_unset_bit_pos; |
| return Ok(aid); |
| } else { |
| bail!("no available association ID") |
| } |
| } |
| } |
| // control flow should never reach here since once we reach the max AID, we should already |
| // return in the above loop with an error (i.e., the last element in `aids` array is never |
| // all 1's) |
| panic!("unexpected error assigning association ID") |
| } |
| |
| pub fn release_aid(&mut self, aid: AssociationId) { |
| let index = (aid / Map::ELEM_BITS) as usize; |
| self.aids[index] &= !(1 << (aid % Map::ELEM_BITS)); |
| } |
| } |
| |
| impl Default for Map { |
| fn default() -> Self { |
| let mut map = Map { aids: [0u64; 32] }; |
| map.aids[0] = 1; |
| map |
| } |
| } |
| |
| #[cfg(test)] |
| mod tests { |
| use super::*; |
| |
| #[test] |
| fn test_map_never_assign_zero() { |
| let mut aid_map: Map = Default::default(); |
| for i in 1..=2007u16 { |
| assert_eq!(aid_map.assign_aid().unwrap(), i); |
| } |
| let result = aid_map.assign_aid(); |
| assert!(result.is_err()); |
| assert_eq!(format!("{}", result.unwrap_err()), "no available association ID"); |
| } |
| |
| #[test] |
| fn test_map_no_available_assoc_id() { |
| let mut aid_map: Map = Default::default(); |
| // Set all the bits in the first 31 elements to 1's (so 64 * 31 = 1984 aids claimed) |
| for i in 0..31 { |
| aid_map.aids[i] = u64::max_value(); |
| } |
| // Set the remaining 24 aids in the last array positions |
| for i in 0..24 { |
| aid_map.aids[31] += 1 << i; |
| } |
| let result = aid_map.assign_aid(); |
| assert!(result.is_err()); |
| assert_eq!(format!("{}", result.unwrap_err()), "no available association ID"); |
| } |
| |
| #[test] |
| fn test_map_mixed_case() { |
| let mut aid_map: Map = Default::default(); |
| for i in 1..=1000u16 { |
| assert_eq!(aid_map.assign_aid().unwrap(), i); |
| } |
| aid_map.release_aid(157); |
| aid_map.release_aid(792); |
| aid_map.release_aid(533); |
| assert_eq!(aid_map.assign_aid().unwrap(), 157); |
| assert_eq!(aid_map.assign_aid().unwrap(), 533); |
| assert_eq!(aid_map.assign_aid().unwrap(), 792); |
| |
| for i in 1001..=2007u16 { |
| assert_eq!(aid_map.assign_aid().unwrap(), i); |
| } |
| let result = aid_map.assign_aid(); |
| assert!(result.is_err()); |
| assert_eq!(format!("{}", result.unwrap_err()), "no available association ID"); |
| aid_map.release_aid(666); |
| aid_map.release_aid(222); |
| aid_map.release_aid(111); |
| assert_eq!(aid_map.assign_aid().unwrap(), 111); |
| assert_eq!(aid_map.assign_aid().unwrap(), 222); |
| assert_eq!(aid_map.assign_aid().unwrap(), 666); |
| } |
| } |