Re: fast and simple array ? (NSAnimation)

[Xavier Glattard]

Richard Frith-Macdonald <richard <at> tiptree.demon.co.uk> writes:

> The base library contains an extension header (GSIArray,h) which  
> provides array management macros for fast C style arrays.  It's used  
> in various places within the coire libraries. 

Thanks :-)
That's what i'm looking for.

May i suggest some improvements ?

First i think the GSUNION mechanism shouldn't be mandatory.

In NSAnimation i would write :
  #define GSIArrayItem NSAnimationProgress
for a simple array of NSAnimatinProgress float values.
The code would then be more readable (no cast, no '.ext')

Suggested patch (not tested) :

<code>

@@ -105,6 +105,8 @@
 #define        GSI_ARRAY_TYPES GSUNION_ALL
 #endif
 
+#ifndef GSIArrayItem
+
 /*
  *     Set up the name of the union to store array elements.
  */
@@ -137,6 +139,8 @@
  */
 #include <GNUstepBase/GSUnion.h>
 
+#endif /* #ifndef GSIArrayItem */
+
 struct _GSIArray {
   GSIArrayItem *ptr;
   unsigned     count;

</code>

I would also add a new function.
In fact i would split GSIArrayInsertionPosition :
 1) the binary search
 2) the 'skipping'

The functions : (not tested)

<code>

static INLINE unsigned
GSIArraySearch(GSIArray array, GSIArrayItem item, 
        NSComparisonResult (*sorter)(GSIArrayItem, GSIArrayItem))
{
  unsigned int  upper = array->count;
  unsigned int  lower = 0;
  unsigned int  index;

  /*
   *    Binary search for an item equal to the one to be inserted.
   *    Only for sorted array !
   */
  for (index = upper/2; upper != lower; index = (upper+lower)/2)
    {
      NSComparisonResult comparison;

      comparison = (*sorter)(item, (array->ptr[index]));
      if (comparison == NSOrderedAscending)
        {
          upper = index;
        }
      else if (comparison == NSOrderedDescending)
        {
          lower = index + 1;
        }
      else
        {
          break;
        }
    }
  return index;
}

static INLINE unsigned
GSIArrayInsertionPosition(GSIArray array, GSIArrayItem item, 
        NSComparisonResult (*sorter)(GSIArrayItem, GSIArrayItem))
{
  unsigned int  index;

  index = GSIArraySearch(array,item,sorter);
  /*
   *    Now skip past any equal items so the insertion point is AFTER any
   *    items that are equal to the new one.
   */
  while (index < array->count
    && (*sorter)(item, (array->ptr[index])) != NSOrderedAscending)
    {
      index++;
    }
#ifdef  GSI_ARRAY_CHECKS
  NSCAssert(index <= array->count, NSInternalInconsistencyException);
#endif
  return index;
}

</code>

I think these changes wouldn't break anything...
But if one doesn't like them i might do without them ;-)

Thanks

Xavier