1 /*
2  * Copyright (C) 1996-2021 The Squid Software Foundation and contributors
3  *
4  * Squid software is distributed under GPLv2+ license and includes
5  * contributions from numerous individuals and organizations.
6  * Please see the COPYING and CONTRIBUTORS files for details.
7  */
8 
9 #ifndef SQUID_DESCRIPTOR_SET_H
10 #define SQUID_DESCRIPTOR_SET_H
11 
12 #include <iosfwd>
13 
14 /** \ingroup Comm
15 
16     \todo: Should we use std::set<int> with its flexibility? Our implementation
17     has constant overhead, which is smaller than log(n) of std::set.
18 
19 an unordered collection of unique descriptors with O(1) add/del/has ops */
20 class DescriptorSet
21 {
22 public:
23     // for STL compatibility, should we decide to switch to std::set or similar
24     typedef const int *const_iterator;
25 
26     DescriptorSet();
27     ~DescriptorSet();
28 
29     /// checks whether fd is in the set
has(const int fd)30     bool has(const int fd) const {
31         return 0 <= fd && fd < capacity_ &&
32                index_[fd] >= 0;
33     }
34 
35     bool add(int fd); ///< adds if unique; returns true if added
36     bool del(int fd); ///< deletes if there; returns true if deleted
37     int pop(); ///< deletes and returns one descriptor, in unspecified order
38 
empty()39     bool empty() const { return !size_; } ///< number of descriptors in the set
40 
41     /// begin iterator a la STL; may become invalid if the object is modified
begin()42     const_iterator begin() const { return descriptors_; }
43     /// end iterator a la STL; may become invalid if the object is modified
end()44     const_iterator end() const { return begin() + size_; }
45 
46     /// outputs debugging info about the set
47     void print(std::ostream &os) const;
48 
49 private:
50     // these would be easy to support when needed; prohibit for now
51     DescriptorSet(const DescriptorSet &s); // declared but undefined
52     DescriptorSet &operator =(const DescriptorSet &s); // declared, undefined
53 
54     int *descriptors_; ///< descriptor values in random order
55     int *index_; ///< descriptor:position index into descriptors_
56     int capacity_; ///< total number of descriptor slots
57     int size_; ///< number of descriptors in the set
58 };
59 
60 /// convenience wrapper to be used in debugs() context
61 inline std::ostream &
62 operator <<(std::ostream &os, const DescriptorSet &ds)
63 {
64     ds.print(os);
65     return os;
66 }
67 
68 #endif /* SQUID_DESCRIPTOR_SET_H */
69 
70