Fl_Group: convert array of children to std::vector

Note: this is only a hidden implementation detail: all concerned
variables are private, and the code is simplified (less error prone).

Size of Fl_Group on 64-bit Linux: 168 -> 176 Bytes (+8 Bytes).

test/group.cxx: test for Fl_Group::{add, insert, remove} etc.

4 files changed, 251 insertions, 117 deletions

diff --git a/FL/Fl_Group.H b/FL/Fl_Group.H
index 27c68ef8a..f09f98d18 100644
--- a/FL/Fl_Group.H
+++ b/FL/Fl_Group.H
@@ -23,27 +23,30 @@
 
 #include "Fl_Widget.H"
 
+#include <vector>
+
 // Don't #include Fl_Rect.H because this would introduce lots
 // of unnecessary dependencies on Fl_Rect.H
 class Fl_Rect;
 
 
 /**
-  The Fl_Group class is the main FLTK container widget. It maintains
-  an array of child widgets. These children can themselves be any widget
-  including Fl_Group. The most important subclass of Fl_Group
-  is Fl_Window, however groups can also be used to control radio buttons
-  or to enforce resize behavior.
+  The Fl_Group class is the main FLTK container widget. It maintains an
+  ordered list of child widgets. These children can themselves be any
+  widget including Fl_Group. The most important subclass of Fl_Group
+  is Fl_Window, however groups can also be used to control radio buttons,
+  to enforce resize behavior, or to manage layout of widgets, see
+  Fl_Pack, Fl_Flex, Fl_Grid.
 
   The tab and arrow keys are used to move the focus between widgets of
   this group, and to other groups. The only modifier grabbed is shift
-  (for shift-tab), so that ctrl-tab, alt-up, and such are free
-  for the app to use as shortcuts.
+  (for shift-tab), so that ctrl-tab, alt-up, and such are free for
+  the app to use as shortcuts.
 
   To remove a widget from the group and destroy it, in 1.3.x (and up)
   you can simply use:
   \code
-  delete some_widget;
+    delete some_widget;
   \endcode
   ..and this will trigger proper scheduling of the widget's removal
   from its parent group.
@@ -55,13 +58,9 @@ class Fl_Rect;
 */
 class FL_EXPORT Fl_Group : public Fl_Widget {
 
-  union {
-    Fl_Widget** array_; // used if group has two or more children or NULL
-    Fl_Widget* child1_; // used if group has one child or NULL
-  };
+  std::vector<Fl_Widget *>child_; // vector of children
   Fl_Widget* savedfocus_;
   Fl_Widget* resizable_;
-  int children_;
   Fl_Rect *bounds_; // remembered initial sizes of children
   int *sizes_; // remembered initial sizes of children (FLTK 1.3 compat.)
 
@@ -95,28 +94,29 @@ public:
   /**
     Returns how many child widgets the group has.
   */
-  int children() const { return children_; }
+  int children() const { return (int)child_.size(); }
 
   /**
     Returns the n'th child.
 
-    Returns \c NULL if \c n is out of range (since FLTK 1.4.0).
+    Returns \c nullptr if \c n is out of range (since FLTK 1.4.0).
 
     <i>No range checking was done in FLTK 1.3 and older versions!</i>
 
     \param[in]  n   index of child (0 .. children() - 1)
-    \return     pointer to the n'th child or NULL if out of range
+    \return     pointer to the n'th child or nullptr if out of range
   */
   Fl_Widget *child(int n) const {
-    if (n < 0 || n > children() - 1) return NULL;
-    return array()[n];
+    if (n < 0 || n > children() - 1) return nullptr;
+    return child_[n];
   }
 
   int find(const Fl_Widget*) const;
   /**
     See int Fl_Group::find(const Fl_Widget *w) const
   */
-  int find(const Fl_Widget& o) const {return find(&o);}
+  int find(const Fl_Widget& o) const { return find(&o); }
+
   Fl_Widget* const* array() const;
 
   void resize(int,int,int,int) FL_OVERRIDE;
diff --git a/src/Fl_Group.cxx b/src/Fl_Group.cxx
index 07079cf8c..e256e81ec 100644
--- a/src/Fl_Group.cxx
+++ b/src/Fl_Group.cxx
@@ -29,27 +29,30 @@
 
 Fl_Group* Fl_Group::current_;
 
-// Hack: A single child is stored in the pointer to the array, while
-// multiple children are stored in an allocated array:
-
 /**
-  Returns a pointer to the array of children.
+  Returns a pointer to the internal array of children.
 
   \note This pointer is only valid until the next time a child
         is added or removed.
+
+  \internal This "array" of children is the storage area of an
+        internal std::vector.
 */
 Fl_Widget*const* Fl_Group::array() const {
-  return children_ <= 1 ? &child1_ : array_;
+  return child_.data();
 }
 
 /**
-  Searches the child array for the widget and returns the index.
+  Searches the children for the widget and returns the index.
 
   Returns children() if the widget is NULL or not found.
 */
 int Fl_Group::find(const Fl_Widget* o) const {
   Fl_Widget*const* a = array();
-  int i; for (i=0; i < children_; i++) if (*a++ == o) break;
+  int i;
+  for (i = 0; i < children(); i++) {
+    if (*a++ == o) break;
+  }
   return i;
 }
 
@@ -307,17 +310,17 @@ int Fl_Group::navigation(int key) {
   if (children() <= 1) return 0;
   int i;
   for (i = 0; ; i++) {
-    if (i >= children_) return 0;
-    if (array_[i]->contains(Fl::focus())) break;
+    if (i >= children()) return 0;
+    if (child_[i]->contains(Fl::focus())) break;
   }
-  Fl_Widget *previous = array_[i];
+  Fl_Widget *previous = child_[i];
 
   for (;;) {
     switch (key) {
     case FL_Right:
     case FL_Down:
       i++;
-      if (i >= children_) {
+      if (i >= children()) {
         if (parent()) return 0;
         i = 0;
       }
@@ -327,13 +330,13 @@ int Fl_Group::navigation(int key) {
       if (i) i--;
       else {
         if (parent()) return 0;
-        i = children_-1;
+        i = children() - 1;
       }
       break;
     default:
       return 0;
     }
-    Fl_Widget* o = array_[i];
+    Fl_Widget* o = child_[i];
     if (o == previous) return 0;
     switch (key) {
     case FL_Down:
@@ -348,15 +351,13 @@ int Fl_Group::navigation(int key) {
 
 ////////////////////////////////////////////////////////////////
 
-Fl_Group::Fl_Group(int X,int Y,int W,int H,const char *l)
-: Fl_Widget(X,Y,W,H,l) {
+Fl_Group::Fl_Group(int X, int Y, int W, int H, const char *L)
+  : Fl_Widget(X, Y, W, H, L) {
   align(FL_ALIGN_TOP);
-  children_ = 0;
-  array_ = 0;
   savedfocus_ = 0;
   resizable_ = this;
   bounds_ = 0; // this is allocated when first resize() is done
-  sizes_ = 0; // see bounds_ (FLTK 1.3 compatibility)
+  sizes_ = 0;  // see bounds_ (FLTK 1.3 compatibility)
 
   // Subclasses may want to construct child objects as part of their
   // constructor, so make sure they are add()'d to this object.
@@ -408,25 +409,14 @@ void Fl_Group::clear() {
   // child which is much faster than the other way around and
   // should be the "natural order" (last in, first out).
 
-  while (children_) {                   // delete all children
-    int idx = children_-1;              // last child's index
-    Fl_Widget* w = child(idx);          // last child widget
-    if (w->parent()==this) {            // should always be true
-      if (children_>2) {                // optimized removal
-        w->parent_ = 0;                 // reset child's parent
-        on_remove(idx);
-        children_--;                    // update counter
-      } else {                          // slow removal
-        remove(idx);
-      }
-      delete w;                         // delete the child
-    } else {                            // should never happen
-      remove(idx);                      // remove it anyway
-    }
+  for (int i = children() - 1; i >= 0; i--) {
+    // some children may have been deleted, so check always
+    if (i >= children()) continue;
+    delete_child(i);
   }
 
-  if (pushed != this) Fl::pushed(pushed); // reset pushed() widget
-
+  if (pushed != this)
+    Fl::pushed(pushed);       // reset pushed() widget
 }
 
 /**
@@ -457,17 +447,17 @@ Fl_Group::~Fl_Group() {
  structures just before the child is added.
 
  This method usually returns the same index that was given in the parameters.
- By setting a new index, the position of other widgets in the child pointer
- array can be preserved (e.g. Fl_Scroll keeps its scroll bars as the last
+ By setting a new index, the position of other widgets in the list of children
+ can be preserved (e.g. Fl_Scroll keeps its scroll bars as the last
  two children).
 
- By returning -1, Fl_Group::insert will not add the child to
- array_. This is not recommended, but Fl_Table does something similar to
+ By returning -1, Fl_Group::insert will not add the child to the group.
+ This is not recommended, but Fl_Table does something similar to
  forward children to a hidden group.
 
- \param candidate the candidate will be added to the child array_ after this
+ \param candidate the candidate will be added to the child vector after this
             method returns.
- \param index add the child at this position in the array_
+ \param index add the child at this position in the list of children
  \return index to position the child as planned
  \return a new index to force the child to a different position
  \return -1 to keep the group from adding the candidate
@@ -485,8 +475,8 @@ int Fl_Group::on_insert(Fl_Widget *candidate, int index) {
  structures just before the child itself is moved.
 
  This method usually returns the new index that was given in the
- parameters. By setting a different destination index, the position of other
- widgets in the child pointer array can be preserved.
+ parameters. By setting a different destination index, the position of
+ other widgets in the list of children can be preserved.
 
  By returning -1, Fl_Group::insert will not move the child.
 
@@ -516,15 +506,21 @@ void Fl_Group::insert(Fl_Widget &o, int index) {
       // avoid expensive remove() and add() if we just move a widget within the group
       index = on_move(n, index);
       if (index < 0) return;      // don't move: requested by subclass
-      if (index > children_)
-        index = children_;
+      if (index > children())
+        index = children();
       if (index > n) index--;     // compensate for removal and re-insertion
-      if (index == n) return;     // same position; this includes (children_ == 1)
-      if (index > n)
-        memmove(array_+n, array_+(n+1), (index-n) * sizeof(Fl_Widget*));
-      else
-        memmove(array_+(index+1), array_+index, (n-index) * sizeof(Fl_Widget*));
-      array_[index] = &o;
+      if (index == n) return;     // same position; this includes (children() == 1)
+
+      // now it's OK to move the child inside this group
+
+      if (index > n) { // target > current position: move "up" and all other children "down"
+        for (int j = n; j < index; j++)
+          child_[j] = child_[j + 1];
+      } else { // n > index: move "down" and all other children "up"
+        for (int j = n; j > index; j--)
+          child_[j] = child_[j - 1];
+      }
+      child_[index] = &o;
       init_sizes();
       return;
     }
@@ -533,23 +529,12 @@ void Fl_Group::insert(Fl_Widget &o, int index) {
 
   index = on_insert(&o, index);
   if (index == -1) return;
-
-  o.parent_ = this;
-  if (children_ == 0) { // use array pointer to point at single child
-    child1_ = &o;
-  } else if (children_ == 1) { // go from 1 to 2 children
-    Fl_Widget* t = child1_;
-    array_ = (Fl_Widget**)malloc(2*sizeof(Fl_Widget*));
-    if (index) {array_[0] = t; array_[1] = &o;}
-    else {array_[0] = &o; array_[1] = t;}
-  } else {
-    if (!(children_ & (children_-1))) // double number of children
-      array_ = (Fl_Widget**)realloc((void*)array_,
-                                    2*children_*sizeof(Fl_Widget*));
-    int j; for (j = children_; j > index; j--) array_[j] = array_[j-1];
-    array_[j] = &o;
+  if (index >= children()) {              // append
+    child_.push_back(&o);
+  } else {                                // insert
+    child_.insert(child_.begin() + index, &o);
   }
-  children_++;
+  o.parent_ = this;
   init_sizes();
 }
 
@@ -557,7 +542,9 @@ void Fl_Group::insert(Fl_Widget &o, int index) {
   The widget is removed from its current group (if any) and then added
   to the end of this group.
 */
-void Fl_Group::add(Fl_Widget &o) {insert(o, children_);}
+void Fl_Group::add(Fl_Widget &o) {
+  insert(o, children());
+}
 
 /**
  Allow derived groups to act when a child widget is removed from the group.
@@ -566,7 +553,7 @@ void Fl_Group::add(Fl_Widget &o) {insert(o, children_);}
  Overriding this method will allow derived classes to remove these data
  structures just before the child is removed.
 
- \param index remove the child at this position in the array_
+ \param index remove the child at this position
  */
 void Fl_Group::on_remove(int index) {
   (void)index;
@@ -583,8 +570,11 @@ void Fl_Group::on_remove(int index) {
   \since FLTK 1.3.0
 */
 void Fl_Group::remove(int index) {
-  if (index < 0 || index >= children_) return;
-  on_remove(index);
+  if (index < 0 || index >= children())
+    return;
+  on_remove(index);         // notify subclass
+  if (index >= children())  // do nothing if the subclass removed it (?)
+    return;
 
   Fl_Widget &o = *child(index);
   if (&o == savedfocus_) savedfocus_ = 0;
@@ -593,15 +583,10 @@ void Fl_Group::remove(int index) {
     o.parent_ = 0;
   }
 
-  // remove the widget from the group
-
-  children_--;
-  if (children_ == 1) { // go from 2 to 1 child
-    Fl_Widget *t = array_[!index];
-    free((void*)array_);
-    child1_ = t;
-  } else if (children_ > 1) { // delete from array
-    for (; index < children_; index++) array_[index] = array_[index+1];
+  if (index == children() - 1) {
+    child_.pop_back();
+  } else {
+    child_.erase(child_.begin() + index); // remove the widget from the group
   }
   init_sizes();
 }
@@ -614,15 +599,15 @@ void Fl_Group::remove(int index) {
   This method differs from the clear() method in that it only affects
   a single widget and does not delete it from memory.
 
-  \note If you have the child's index anyway, use remove(int index)
-  instead, because this doesn't need a child lookup in the group's
-  table of children. This can be much faster, if there are lots of
-  children.
+  \note If you have the child's index anyway, use remove(int index) instead,
+  because this doesn't need a child lookup in the group's table of children.
+  This can be much faster, if there are lots of children.
 */
 void Fl_Group::remove(Fl_Widget &o) {
-  if (!children_) return;
+  if (!children()) return;
   int i = find(o);
-  if (i < children_) remove(i);
+  if (i < children())
+    remove(i);
 }
 
 /**
@@ -663,7 +648,7 @@ void Fl_Group::remove(Fl_Widget &o) {
   \since FLTK 1.4.0
 */
 int Fl_Group::delete_child(int index) {
-  if (index < 0 || index >= children_)
+  if (index < 0 || index >= children())
     return 1;
   Fl_Widget *w = child(index);
   remove(index);
@@ -740,7 +725,7 @@ void Fl_Group::init_sizes() {
 */
 Fl_Rect* Fl_Group::bounds() {
   if (!bounds_) {
-    Fl_Rect* p = bounds_ = new Fl_Rect[children_+2];
+    Fl_Rect* p = bounds_ = new Fl_Rect[children()+2];
     // first thing in bounds array is the group's size:
     if (as_window())
       p[0] = Fl_Rect(w(),h()); // x = y = 0
@@ -763,7 +748,7 @@ Fl_Rect* Fl_Group::bounds() {
     // next is all the children's sizes:
     p += 2;
     Fl_Widget*const* a = array();
-    for (int i=children_; i--;) {
+    for (int i = children(); i--;) {
       *p++ = Fl_Rect(*a++);
     }
   }
@@ -796,13 +781,12 @@ Fl_Rect* Fl_Group::bounds() {
 
   \see bounds()
 */
-int* Fl_Group::sizes()
-{
+int* Fl_Group::sizes() {
   if (sizes_) return sizes_;
   // allocate new sizes_ array and copy bounds_ over to sizes_
-  int* pi = sizes_ = new int[4*(children_+2)];
+  int* pi = sizes_ = new int[4*(children() + 2)];
   Fl_Rect *rb = bounds();
-  for (int i = 0; i < children_+2; i++, rb++) {
+  for (int i = 0; i < children() + 2; i++, rb++) {
     *pi++ = rb->x();
     *pi++ = rb->r();
     *pi++ = rb->y();
@@ -849,7 +833,7 @@ void Fl_Group::resize(int X, int Y, int W, int H) {
 
     if (Fl_Window::is_a_rescale() || dx || dy) {
       Fl_Widget*const* a = array();
-      for (int i = children_; i--;) {
+      for (int i = children(); i--;) {
         Fl_Widget* o = *a++;
         o->resize(o->x() + dx, o->y() + dy, o->w(), o->h());
       }
@@ -858,7 +842,7 @@ void Fl_Group::resize(int X, int Y, int W, int H) {
 
   // Part 2: here we definitely have a resizable() widget, resize children
 
-  else if (children_) {
+  else if (children()) {
 
     // get changes in size/position from the initial size:
     dx = X - p->x();
@@ -886,7 +870,7 @@ void Fl_Group::resize(int X, int Y, int W, int H) {
     // resize children
     Fl_Widget*const* a = array();
 
-    for (int i = children_; i--; p++) {
+    for (int i = children(); i--; p++) {
 
       Fl_Widget* o = *a++;
       int L = p->x();
@@ -928,13 +912,14 @@ void Fl_Group::draw_children() {
   }
 
   if (damage() & ~FL_DAMAGE_CHILD) { // redraw the entire thing:
-    for (int i=children_; i--;) {
+    for (int i = children(); i--;) {
       Fl_Widget& o = **a++;
       draw_child(o);
       draw_outside_label(o);
     }
   } else {      // only redraw the children that need it:
-    for (int i=children_; i--;) update_child(**a++);
+    for (int i = children(); i--;)
+      update_child(**a++);
   }
 
   if (clip_children()) fl_pop_clip();
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index eff372154..d2e1c9c5f 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -116,6 +116,7 @@ fl_create_example(grid_alignment grid_alignment.cxx fltk::fltk)
 fl_create_example(grid_buttons grid_buttons.cxx fltk::fltk)
 fl_create_example(grid_dialog grid_dialog.cxx fltk::fltk)
 fl_create_example(grid_login grid_login.cxx fltk::fltk)
+fl_create_example(group group.cxx fltk::fltk)
 fl_create_example(handle_events handle_events.cxx "${GLDEMO_LIBS}")
 fl_create_example(handle_keys handle_keys.cxx fltk::fltk)
 fl_create_example(hello hello.cxx fltk::fltk)
diff --git a/test/group.cxx b/test/group.cxx
new file mode 100644
index 000000000..2e661f560
--- /dev/null
+++ b/test/group.cxx
@@ -0,0 +1,148 @@
+//
+// Fl_Group manipulation test program for the Fast Light Tool Kit (FLTK).
+//
+// Copyright 2024 by Bill Spitzak and others.
+//
+// This library is free software. Distribution and use rights are outlined in
+// the file "COPYING" which should have been included with this file.  If this
+// file is missing or damaged, see the license at:
+//
+//     https://www.fltk.org/COPYING.php
+//
+// Please see the following page on how to report bugs and issues:
+//
+//     https://www.fltk.org/bugs.php
+//
+
+// This test program creates two groups and moves widgets around
+// between groups to test insert, append, remove, etc..
+
+#include <FL/Fl_Double_Window.H>
+#include <FL/Fl_Box.H>
+#include <FL/Fl_Button.H>
+#include <FL/Fl_Flex.H>
+#include <FL/Fl_Terminal.H>
+
+// #include <vector>
+
+// Globals for easier testing
+
+const int ww = 520; // window width
+const int wh = 200; // window height (w/o button and terminal)
+const int th = 200; // initial terminal (tty) height
+
+Fl_Double_Window *window;
+Fl_Flex *g1, *g2;
+Fl_Box *b1, *b2, *b3, *b4;
+Fl_Terminal *tty;
+
+void debug_group(Fl_Group *g) {
+  const int nc = g->children();
+  tty->printf("%s has %2d child%s\n", g->label(), nc, nc == 1 ? "" : "ren");
+  for (int i = 0; i < g->children(); i++) {
+    Fl_Widget *w = g->child(i);
+    const char *lbl = w ? w->label() : "";
+#if (0) // full info with child address
+    tty->printf("    Child[%2d] (%p) = %s\n", i, (void *)w, lbl);
+#else // short info
+    tty->printf("    Child[%2d] = %s\n", i, lbl);
+#endif
+  }
+}
+
+// This button callback exercises multiple Fl_Group operations in a circle.
+// Note to devs: make sure that the last action restores the original layout.
+
+void button_cb(Fl_Widget *, void *) {
+  static int move = 0;
+  move++;
+  tty->printf("\nMove %2d:\n", move);
+  switch(move) {
+    case  1: g1->insert(*b3, 0);    break;
+    case  2: g1->insert(*b3, 2);    break;
+    case  3: g1->insert(*b2, 1);    break;
+    case  4: g1->insert(*b1, 5);    break;
+    case  5: g1->insert(*b1, 1);    break;
+    case  6: g1->insert(*b4, 3);    break;
+    case  7: g1->insert(*b3, 2);    break; // no-op (same position)
+    case  8: g2->add(b3);           break;
+    case  9: g2->add(b3);           break; // no-op (same position)
+    case 10: g2->add(b4);           break;
+    case 11: g1->remove(b2);        break;
+    case 12: g1->add(b2); move = 0; break; // last move: reset counter
+    default:              move = 0; break; // safety: reset counter
+  }
+  debug_group(g1);
+  debug_group(g2);
+  g1->layout();
+  g2->layout();
+  window->redraw();
+}
+
+int main(int argc, char **argv) {
+  window = new Fl_Double_Window(ww, wh + th + 100, "Fl_Group Test");
+
+  g1 = new Fl_Flex(50, 20, ww - 80, wh / 2 - 20, "g1: ");
+  g1->type(Fl_Flex::HORIZONTAL);
+  g1->box(FL_FLAT_BOX);
+  g1->color(FL_WHITE);
+  g1->align(FL_ALIGN_LEFT);
+
+  b1 = new Fl_Box(0, 0, 0, 0, "b1");
+  b1->box(FL_FLAT_BOX);
+  b1->color(FL_RED);
+
+  b2 = new Fl_Box(0, 0, 0, 0, "b2");
+  b2->box(FL_FLAT_BOX);
+  b2->color(FL_GREEN);
+
+  g1->end();
+
+  g2 = new Fl_Flex(50, wh / 2 + 20, ww - 80, wh / 2 - 20, "g2: ");
+  g2->type(Fl_Flex::HORIZONTAL);
+  g2->box(FL_FLAT_BOX);
+  g2->color(FL_WHITE);
+  g2->align(FL_ALIGN_LEFT);
+
+  b3 = new Fl_Box(0, 0, 0, 0, "b3");
+  b3->box(FL_FLAT_BOX);
+  b3->color(FL_BLUE);
+  b3->labelcolor(FL_WHITE);
+
+  b4 = new Fl_Box(0, 0, 0, 0, "b4");
+  b4->box(FL_FLAT_BOX);
+  b4->color(FL_YELLOW);
+
+  g2->end();
+
+  auto bt = new Fl_Button(10, wh + 20, ww - 20, 40, "Move children ...");
+  bt->callback(button_cb);
+
+  tty = new Fl_Terminal(10, wh + 80, ww - 20, th);
+
+  window->end();
+  window->resizable(tty);
+  window->size_range(window->w(), window->h());
+  window->show(argc, argv);
+
+  tty->printf("sizeof(Fl_Widget)    = %3d\n", (int)sizeof(Fl_Widget));
+  tty->printf("sizeof(Fl_Box)       = %3d\n", (int)sizeof(Fl_Box));
+  tty->printf("sizeof(Fl_Button)    = %3d\n", (int)sizeof(Fl_Button));
+  tty->printf("sizeof(Fl_Group)     = %3d\n", (int)sizeof(Fl_Group));
+  tty->printf("sizeof(Fl_Window)    = %3d\n", (int)sizeof(Fl_Window));
+
+  int idx = g2->children() + 3;
+  tty->printf("child(n) out of range: g2->child(%d) = %p, children = %d\n",
+              idx, (void *)g2->child(idx), g2->children());
+
+  int ret = Fl::run();
+
+  // reset pointers to give memory checkers a chance to test for leaks
+  g1 = g2 = nullptr;
+  tty = nullptr;
+  b1 = b2 = b3 = b4 = nullptr;
+  bt = nullptr;
+  delete window;
+
+  return ret;
+}