[patch 0/4] varobj_list replacement [Re: [patch 4/8] Types GC [varobj_list to all_root_varobjs]]

[Jan Kratochvil <jan.kratochvil@redhat.com>]

On Thu, 02 Jul 2009 12:09:39 +0200, Vladimir Prus wrote:
> Can we just make varobj.c expose vector of varobjs?

In general iterators are preferred over direct variable access in modern
programming.  It makes the implementation free to change the underlying data
structures to always use algorithms with optimal complexity.

Specifically the VEC structure (contiguous array) is not well suited as:
* It cannot effectively insert/remove elements while keeping the original order.
* Iterating such VEC while it is being changed is difficult.
* Current varobj_delete + install_variable API does not report the number of
  successfully deleted/inserted root items to make such iteration safe.

There are at least ways of implementing there the VEC:

VEC_safe_push + VEC_unordered_remove:
+ It is algorithmically optimal complexity.
- It no longer keeps the root variables order - this breaks the testsuite.
  Verified all the FAILs are just an order change having no real regressions.
  I will fix the testsuite if it gets approved this way.
  I believe frontends do not depend on the ordering, I would test
  Eclipse+Nemiver or some others upon recommendation.
- Difficult to keep iterating the VEC being changed
  by varobj_delete + install_variable in the meantime.
  varobj_delete + install_variable API change may be more appropriate.

VEC_safe_insert + VEC_ordered_remove:
+ It keeps the root variables in the current order.
+ It has no testsuite changes / regressions.
- It is ineffective (two memmove calls per varobj_invalidate per rootvar).
- Difficult to keep iterating the VEC being changed
  by varobj_delete + install_variable in the meantime.
  * Guess the index / placement will match one remove + insert
  or
  * Extend the varobj_delete + install_variable API to return the exact number
    of removed and inserted rootvars.

Still I would prefer:

Iterator - so-called "safe" (keeping the next pointer) double link list:
+ It is algorithmically optimal complexity.
+ It keeps the root variables in the current order.
+ It has no testsuite changes / regressions.
+ More simple usage at the caller (no varobj_root_get_var).
+ Separates the interface and implementation parts.
+ Easy iterating the list being changed by varobj_delete + install_variable
  in the meantime.  One just keeps the "next" pointer before calling them.

Regression tested all the 4 patches on {x86_64,i686}-fedora-linux-gnu.


Thanks,
Jan