[PATCH 4/7] jit: make gdb_symtab::blocks a vector

[Simon Marchi <simon.marchi@polymtl.ca>]

This patch changes the gdb_symtab::blocks linked list to be an
std::vector, simplifying memory management.

Currently, the list is sorted as blocks are created.  It is easier (and
probably a bit more efficient) to sort them once at the end, so this is
what I did.

A note about the comment on the "next" field:

  /* gdb_blocks are linked into a tree structure.  Next points to the
     next node at the same depth as this block and parent to the
     parent gdb_block.  */

I don't think it's true that "next" points to the next node at the same
depth.  It might happen to be true for some nodes, but it can't be true
in general, as this is a simple linked list containing all the created
blocks.

gdb/ChangeLog:

	* jit.c (struct gdb_block) <next>: Remove field.
	(struct gdb_symtab) <~gdb_symtab>: Adjust to std::vector.
	<blocks>: Change type to std::vector<gdb_block *>.
	<nblocks>: Remove.
	(compare_block): Remove.
	(jit_block_open_impl): Adjust to std::vector.  Place the new
	block at the end, don't mind about sorting.
	(finalize_symtab): Adjust to std::vector, sort the blocks vector
	before using it.
---
 gdb/jit.c | 111 +++++++++++++++---------------------------------------
 1 file changed, 31 insertions(+), 80 deletions(-)

diff --git a/gdb/jit.c b/gdb/jit.c
index eace83e583d3..bb855e09f59b 100644
--- a/gdb/jit.c
+++ b/gdb/jit.c
@@ -428,10 +428,8 @@ jit_read_code_entry (struct gdbarch *gdbarch,
 
 struct gdb_block
 {
-  /* gdb_blocks are linked into a tree structure.  Next points to the
-     next node at the same depth as this block and parent to the
-     parent gdb_block.  */
-  struct gdb_block *next, *parent;
+  /* The parent of this block.  */
+  struct gdb_block *parent;
 
   /* Points to the "real" block that is being built out of this
      instance.  This block will be added to a blockvector, which will
@@ -456,14 +454,8 @@ struct gdb_symtab
 
   ~gdb_symtab ()
   {
-    gdb_block *gdb_block_iter, *gdb_block_iter_tmp;
-
-    for ((gdb_block_iter = this->blocks,
-	  gdb_block_iter_tmp = gdb_block_iter->next);
-         gdb_block_iter;
-         gdb_block_iter = gdb_block_iter_tmp)
+    for (gdb_block *gdb_block_iter : this->blocks)
       {
-        gdb_block_iter_tmp = gdb_block_iter->next;
         xfree ((void *) gdb_block_iter->name);
         xfree (gdb_block_iter);
       }
@@ -471,10 +463,7 @@ struct gdb_symtab
 
   /* The list of blocks in this symtab.  These will eventually be
      converted to real blocks.  */
-  struct gdb_block *blocks = nullptr;
-
-  /* The number of blocks inserted.  */
-  int nblocks = 0;
+  std::vector<gdb_block *> blocks;
 
   /* A mapping between line numbers to PC.  */
   gdb::unique_xmalloc_ptr<struct linetable> linetable;
@@ -537,28 +526,6 @@ jit_symtab_open_impl (struct gdb_symbol_callbacks *cb,
   return symtab;
 }
 
-/* Returns true if the block corresponding to old should be placed
-   before the block corresponding to new in the final blockvector.  */
-
-static int
-compare_block (const struct gdb_block *const old,
-               const struct gdb_block *const newobj)
-{
-  if (old == NULL)
-    return 1;
-  if (old->begin < newobj->begin)
-    return 1;
-  else if (old->begin == newobj->begin)
-    {
-      if (old->end > newobj->end)
-        return 1;
-      else
-        return 0;
-    }
-  else
-    return 0;
-}
-
 /* Called by readers to open a new gdb_block.  This function also
    inserts the new gdb_block in the correct place in the corresponding
    gdb_symtab.  */
@@ -570,37 +537,15 @@ jit_block_open_impl (struct gdb_symbol_callbacks *cb,
 {
   struct gdb_block *block = XCNEW (struct gdb_block);
 
-  block->next = symtab->blocks;
   block->begin = (CORE_ADDR) begin;
   block->end = (CORE_ADDR) end;
   block->name = name ? xstrdup (name) : NULL;
   block->parent = parent;
 
-  /* Ensure that the blocks are inserted in the correct (reverse of
-     the order expected by blockvector).  */
-  if (compare_block (symtab->blocks, block))
-    {
-      symtab->blocks = block;
-    }
-  else
-    {
-      struct gdb_block *i = symtab->blocks;
-
-      for (;; i = i->next)
-        {
-          /* Guaranteed to terminate, since compare_block (NULL, _)
-             returns 1.  */
-          if (compare_block (i->next, block))
-            {
-              block->next = i->next;
-              i->next = block;
-              break;
-            }
-        }
-    }
-  symtab->nblocks++;
-
-  return block;
+  /* Place the block at the end of the vector, it will be sorted when the
+     symtab is finalized.  */
+  symtab->blocks.push_back (block);
+  return symtab->blocks.back ();
 }
 
 /* Readers call this to add a line mapping (from PC to line number) to
@@ -646,14 +591,21 @@ static void
 finalize_symtab (struct gdb_symtab *stab, struct objfile *objfile)
 {
   struct compunit_symtab *cust;
-  struct gdb_block *gdb_block_iter;
-  struct block *block_iter;
-  int actual_nblocks, i;
   size_t blockvector_size;
   CORE_ADDR begin, end;
   struct blockvector *bv;
 
-  actual_nblocks = FIRST_LOCAL_BLOCK + stab->nblocks;
+  int actual_nblocks = FIRST_LOCAL_BLOCK + stab->blocks.size ();
+
+  /* Sort the blocks in the order they should appear in the blockvector. */
+  std::sort (stab->blocks.begin (), stab->blocks.end (),
+	     [] (const gdb_block *a, const gdb_block *b)
+	       {
+		 if (a->begin != b->begin)
+		   return a->begin < b->begin;
+
+		 return b->begin < a->begin;
+	       });
 
   cust = allocate_compunit_symtab (objfile, stab->file_name.c_str ());
   allocate_symtab (cust, stab->file_name.c_str ());
@@ -680,19 +632,18 @@ finalize_symtab (struct gdb_symtab *stab, struct objfile *objfile)
 					     blockvector_size);
   COMPUNIT_BLOCKVECTOR (cust) = bv;
 
-  /* (begin, end) will contain the PC range this entire blockvector
-     spans.  */
+  /* At the end of this function, (begin, end) will contain the PC range this
+     entire blockvector spans.  */
   BLOCKVECTOR_MAP (bv) = NULL;
-  begin = stab->blocks->begin;
-  end = stab->blocks->end;
+  begin = stab->blocks.front ()->begin;
+  end = stab->blocks.front ()->end;
   BLOCKVECTOR_NBLOCKS (bv) = actual_nblocks;
 
   /* First run over all the gdb_block objects, creating a real block
      object for each.  Simultaneously, keep setting the real_block
      fields.  */
-  for (i = (actual_nblocks - 1), gdb_block_iter = stab->blocks;
-       i >= FIRST_LOCAL_BLOCK;
-       i--, gdb_block_iter = gdb_block_iter->next)
+  int block_idx = FIRST_LOCAL_BLOCK;
+  for (gdb_block *gdb_block_iter : stab->blocks)
     {
       struct block *new_block = allocate_block (&objfile->objfile_obstack);
       struct symbol *block_name = allocate_symbol (objfile);
@@ -719,18 +670,20 @@ finalize_symtab (struct gdb_symtab *stab, struct objfile *objfile)
 
       BLOCK_FUNCTION (new_block) = block_name;
 
-      BLOCKVECTOR_BLOCK (bv, i) = new_block;
+      BLOCKVECTOR_BLOCK (bv, block_idx) = new_block;
       if (begin > BLOCK_START (new_block))
         begin = BLOCK_START (new_block);
       if (end < BLOCK_END (new_block))
         end = BLOCK_END (new_block);
 
       gdb_block_iter->real_block = new_block;
+
+      block_idx++;
     }
 
   /* Now add the special blocks.  */
-  block_iter = NULL;
-  for (i = 0; i < FIRST_LOCAL_BLOCK; i++)
+  struct block *block_iter = NULL;
+  for (enum block_enum i : { GLOBAL_BLOCK, STATIC_BLOCK })
     {
       struct block *new_block;
 
@@ -753,9 +706,7 @@ finalize_symtab (struct gdb_symtab *stab, struct objfile *objfile)
 
   /* Fill up the superblock fields for the real blocks, using the
      real_block fields populated earlier.  */
-  for (gdb_block_iter = stab->blocks;
-       gdb_block_iter;
-       gdb_block_iter = gdb_block_iter->next)
+  for (gdb_block *gdb_block_iter : stab->blocks)
     {
       if (gdb_block_iter->parent != NULL)
 	{
-- 
2.24.1