+// Class Free_list.
+
+// The total number of free lists used.
+unsigned int Free_list::num_lists = 0;
+// The total number of free list nodes used.
+unsigned int Free_list::num_nodes = 0;
+// The total number of calls to Free_list::remove.
+unsigned int Free_list::num_removes = 0;
+// The total number of nodes visited during calls to Free_list::remove.
+unsigned int Free_list::num_remove_visits = 0;
+// The total number of calls to Free_list::allocate.
+unsigned int Free_list::num_allocates = 0;
+// The total number of nodes visited during calls to Free_list::allocate.
+unsigned int Free_list::num_allocate_visits = 0;
+
+// Initialize the free list. Creates a single free list node that
+// describes the entire region of length LEN. If EXTEND is true,
+// allocate() is allowed to extend the region beyond its initial
+// length.
+
+void
+Free_list::init(off_t len, bool extend)
+{
+ this->list_.push_front(Free_list_node(0, len));
+ this->last_remove_ = this->list_.begin();
+ this->extend_ = extend;
+ this->length_ = len;
+ ++Free_list::num_lists;
+ ++Free_list::num_nodes;
+}
+
+// Remove a chunk from the free list. Because we start with a single
+// node that covers the entire section, and remove chunks from it one
+// at a time, we do not need to coalesce chunks or handle cases that
+// span more than one free node. We expect to remove chunks from the
+// free list in order, and we expect to have only a few chunks of free
+// space left (corresponding to files that have changed since the last
+// incremental link), so a simple linear list should provide sufficient
+// performance.
+
+void
+Free_list::remove(off_t start, off_t end)
+{
+ if (start == end)
+ return;
+ gold_assert(start < end);
+
+ ++Free_list::num_removes;
+
+ Iterator p = this->last_remove_;
+ if (p->start_ > start)
+ p = this->list_.begin();
+
+ for (; p != this->list_.end(); ++p)
+ {
+ ++Free_list::num_remove_visits;
+ // Find a node that wholly contains the indicated region.
+ if (p->start_ <= start && p->end_ >= end)
+ {
+ // Case 1: the indicated region spans the whole node.
+ // Add some fuzz to avoid creating tiny free chunks.
+ if (p->start_ + 3 >= start && p->end_ <= end + 3)
+ p = this->list_.erase(p);
+ // Case 2: remove a chunk from the start of the node.
+ else if (p->start_ + 3 >= start)
+ p->start_ = end;
+ // Case 3: remove a chunk from the end of the node.
+ else if (p->end_ <= end + 3)
+ p->end_ = start;
+ // Case 4: remove a chunk from the middle, and split
+ // the node into two.
+ else
+ {
+ Free_list_node newnode(p->start_, start);
+ p->start_ = end;
+ this->list_.insert(p, newnode);
+ ++Free_list::num_nodes;
+ }
+ this->last_remove_ = p;
+ return;
+ }
+ }
+
+ // Did not find a node containing the given chunk. This could happen
+ // because a small chunk was already removed due to the fuzz.
+ gold_debug(DEBUG_INCREMENTAL,
+ "Free_list::remove(%d,%d) not found",
+ static_cast<int>(start), static_cast<int>(end));
+}
+
+// Allocate a chunk of size LEN from the free list. Returns -1ULL
+// if a sufficiently large chunk of free space is not found.
+// We use a simple first-fit algorithm.
+
+off_t
+Free_list::allocate(off_t len, uint64_t align, off_t minoff)
+{
+ gold_debug(DEBUG_INCREMENTAL,
+ "Free_list::allocate(%08lx, %d, %08lx)",
+ static_cast<long>(len), static_cast<int>(align),
+ static_cast<long>(minoff));
+ if (len == 0)
+ return align_address(minoff, align);
+
+ ++Free_list::num_allocates;
+
+ // We usually want to drop free chunks smaller than 4 bytes.
+ // If we need to guarantee a minimum hole size, though, we need
+ // to keep track of all free chunks.
+ const int fuzz = this->min_hole_ > 0 ? 0 : 3;
+
+ for (Iterator p = this->list_.begin(); p != this->list_.end(); ++p)
+ {
+ ++Free_list::num_allocate_visits;
+ off_t start = p->start_ > minoff ? p->start_ : minoff;
+ start = align_address(start, align);
+ off_t end = start + len;
+ if (end > p->end_ && p->end_ == this->length_ && this->extend_)
+ {
+ this->length_ = end;
+ p->end_ = end;
+ }
+ if (end == p->end_ || (end <= p->end_ - this->min_hole_))
+ {
+ if (p->start_ + fuzz >= start && p->end_ <= end + fuzz)
+ this->list_.erase(p);
+ else if (p->start_ + fuzz >= start)
+ p->start_ = end;
+ else if (p->end_ <= end + fuzz)
+ p->end_ = start;
+ else
+ {
+ Free_list_node newnode(p->start_, start);
+ p->start_ = end;
+ this->list_.insert(p, newnode);
+ ++Free_list::num_nodes;
+ }
+ return start;
+ }
+ }
+ if (this->extend_)
+ {
+ off_t start = align_address(this->length_, align);
+ this->length_ = start + len;
+ return start;
+ }
+ return -1;
+}
+
+// Dump the free list (for debugging).
+void
+Free_list::dump()
+{
+ gold_info("Free list:\n start end length\n");
+ for (Iterator p = this->list_.begin(); p != this->list_.end(); ++p)
+ gold_info(" %08lx %08lx %08lx", static_cast<long>(p->start_),
+ static_cast<long>(p->end_),
+ static_cast<long>(p->end_ - p->start_));
+}
+
+// Print the statistics for the free lists.
+void
+Free_list::print_stats()
+{
+ fprintf(stderr, _("%s: total free lists: %u\n"),
+ program_name, Free_list::num_lists);
+ fprintf(stderr, _("%s: total free list nodes: %u\n"),
+ program_name, Free_list::num_nodes);
+ fprintf(stderr, _("%s: calls to Free_list::remove: %u\n"),
+ program_name, Free_list::num_removes);
+ fprintf(stderr, _("%s: nodes visited: %u\n"),
+ program_name, Free_list::num_remove_visits);
+ fprintf(stderr, _("%s: calls to Free_list::allocate: %u\n"),
+ program_name, Free_list::num_allocates);
+ fprintf(stderr, _("%s: nodes visited: %u\n"),
+ program_name, Free_list::num_allocate_visits);
+}
+