1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146


#[derive(Debug)]
pub enum AllocPolicy {
    /// Will not recycle released handles, regardless of whether they are tracked.
    NeverRecycle,
    /// Will always attempt to re-use the lowest ID out of all returned IDs.
    RecycleLowest,
}

#[derive(Debug)]
pub enum ReleasePolicy {
    /// Free handles are never tracked, and thus never re-used.
    DontTrack,
    /// Tracks a free list of handles.
    Tracked,
}

pub struct HandleManager {
    alloc_policy: AllocPolicy,
    release_policy: ReleasePolicy,
    highest: usize,
    highest_ever: Option<usize>,
    freed: Vec<usize>,
}

impl Default for HandleManager {
    fn default() -> Self {
        HandleManager{
            alloc_policy: AllocPolicy::RecycleLowest,
            release_policy: ReleasePolicy::DontTrack,
            highest: 0,
            highest_ever: None,
            freed: Vec::with_capacity(0),
        }
    }
}

impl HandleManager {
    /// Creates a new handle manager with some default settings. You very likely want to change
    /// these to suit your use case.
    pub fn new() -> Self {
        Default::default()
    }

    /// Changes the allocation policy of handles. Panics if handles have already been issued.
    pub fn with_alloc_policy(mut self, policy: AllocPolicy) -> Self {
        if self.highest_ever.is_some() {
            panic!("Cannot change allocation policy once handles have been dispensed.")
        }

        self.alloc_policy = policy;
        self
    }

    /// Changes the release policy of this handle manager. Panics if handles have already been issued.
    pub fn with_release_policy(mut self, policy: ReleasePolicy) -> Self {
        if self.highest_ever.is_some() {
            panic!("Cannot change release policy once handles have been dispensed.")
        }

        self.release_policy = policy;
        self
    }

    fn simple_allocate(&mut self) -> Option<usize> {
        let result = self.highest;
        // XXX what's the generic-safe way of doing this?
        if result == std::usize::MAX {
            None // We're out of IDs!
        } else {
            self.highest += 1;
            self.highest_ever = Some(result);
            Some(result)
        }
    }

    /// Retrieve a handle from the manager. Either generates a new ID if one cannot be recycled,
    /// or recycles one which was previously valid.
    pub fn next(&mut self) -> Option<usize> {
        match &self.release_policy {
            ReleasePolicy::DontTrack => self.simple_allocate(),
            ReleasePolicy::Tracked => {
                match self.alloc_policy {
                    AllocPolicy::NeverRecycle => self.simple_allocate(),
                    AllocPolicy::RecycleLowest => {
                        if self.freed.len() > 0 {
                            Some(self.freed.remove(0))
                        } else {
                            self.simple_allocate()
                        }
                    }
                }
            }
        }
    }

    /// Checks if a given ID is currently known to the handle manager. Note that if you are using
    /// a policy which does not track freed values, this can only check if a handle has never been
    /// valid to this point.
    pub fn is_used(&self, id: usize) -> bool {
        match self.highest_ever {
            None => false,
            Some(x) => {
                match &self.release_policy {
                    // when we don't track frees, we have to assume almost everything is still valid
                    ReleasePolicy::DontTrack => {id <= x},
                    // a little more cimplex
                    ReleasePolicy::Tracked => {
                        // if above highest ID ever assigned, can't be valid
                        if id > x {
                            return false
                        }
                        match self.freed.iter().find(|x| **x == id) {
                            Some(_) => false,
                            None => true,
                        }
                    },
                }
            },
        }
    }

    /// Returns a handle to the handle manager. This can fail if the handle was not valid or
    /// is currently in a free list.
    pub fn release(&mut self, handle: usize) -> Result<(),()> {
        // TODO think about how double-frees should be handled
        match &self.release_policy {
            ReleasePolicy::DontTrack => /* nothing to do */ Ok(()),
            ReleasePolicy::Tracked => {
                if self.is_used(handle) {
                    // XXX either an insertion sort or a heap would probably be better to be honest
                    self.freed.push(handle);
                    let mut jambojuice = &mut self.freed[..];
                    jambojuice.sort_unstable();
                    Ok(())
                } else {
                    // Uh oh. Either double free or invalid free attempt.
                    Err(())
                }
            },
        }
    }
}

#[cfg(test)]
mod test;