+// Maintain a list of free space within a section, segment, or file.
+// Used for incremental update links.
+
+class Free_list
+{
+ public:
+ struct Free_list_node
+ {
+ Free_list_node(off_t start, off_t end)
+ : start_(start), end_(end)
+ { }
+ off_t start_;
+ off_t end_;
+ };
+ typedef std::list<Free_list_node>::const_iterator Const_iterator;
+
+ Free_list()
+ : list_(), last_remove_(list_.begin()), extend_(false), length_(0),
+ min_hole_(0)
+ { }
+
+ // Initialize the free list for a section of length LEN.
+ // If EXTEND is true, free space may be allocated past the end.
+ void
+ init(off_t len, bool extend);
+
+ // Set the minimum hole size that is allowed when allocating
+ // from the free list.
+ void
+ set_min_hole_size(off_t min_hole)
+ { this->min_hole_ = min_hole; }
+
+ // Remove a chunk from the free list.
+ void
+ remove(off_t start, off_t end);
+
+ // Allocate a chunk of space from the free list of length LEN,
+ // with alignment ALIGN, and minimum offset MINOFF.
+ off_t
+ allocate(off_t len, uint64_t align, off_t minoff);
+
+ // Return an iterator for the beginning of the free list.
+ Const_iterator
+ begin() const
+ { return this->list_.begin(); }
+
+ // Return an iterator for the end of the free list.
+ Const_iterator
+ end() const
+ { return this->list_.end(); }
+
+ // Dump the free list (for debugging).
+ void
+ dump();
+
+ // Print usage statistics.
+ static void
+ print_stats();
+
+ private:
+ typedef std::list<Free_list_node>::iterator Iterator;
+
+ // The free list.
+ std::list<Free_list_node> list_;
+
+ // The last node visited during a remove operation.
+ Iterator last_remove_;
+
+ // Whether we can extend past the original length.
+ bool extend_;
+
+ // The total length of the section, segment, or file.
+ off_t length_;
+
+ // The minimum hole size allowed. When allocating from the free list,
+ // we must not leave a hole smaller than this.
+ off_t min_hole_;
+
+ // Statistics:
+ // The total number of free lists used.
+ static unsigned int num_lists;
+ // The total number of free list nodes used.
+ static unsigned int num_nodes;
+ // The total number of calls to Free_list::remove.
+ static unsigned int num_removes;
+ // The total number of nodes visited during calls to Free_list::remove.
+ static unsigned int num_remove_visits;
+ // The total number of calls to Free_list::allocate.
+ static unsigned int num_allocates;
+ // The total number of nodes visited during calls to Free_list::allocate.
+ static unsigned int num_allocate_visits;
+};
+