Index: configure.in
===================================================================
RCS file: /cvs/gnome/pango/configure.in,v
retrieving revision 1.196
diff -u -p -r1.196 configure.in
--- configure.in	1 Mar 2005 20:01:35 -0000	1.196
+++ configure.in	15 Mar 2005 06:42:51 -0000
@@ -428,7 +428,7 @@ AM_CONDITIONAL(INCLUDE_TIBETAN_FC,echo $
 # We use flockfile to implement pango_getline() - should be moved to GLib
 # strtok_r isn't present on some systems
 #
-AC_CHECK_FUNCS(flockfile strtok_r)
+AC_CHECK_FUNCS(flockfile strtok_r bsearch)
 
 #
 # Check for the Uniscribe header usp10.h for Win32
Index: pango/opentype/ftxopen.c
===================================================================
RCS file: /cvs/gnome/pango/pango/opentype/ftxopen.c,v
retrieving revision 1.14
diff -u -p -r1.14 ftxopen.c
--- pango/opentype/ftxopen.c	3 Mar 2005 19:38:02 -0000	1.14
+++ pango/opentype/ftxopen.c	15 Mar 2005 06:42:52 -0000
@@ -20,6 +20,10 @@
 
 #include "fterrcompat.h"
 
+#ifdef HAVE_BSEARCH
+#include <stdlib.h>
+#endif /* HAVE_BSEARCH */
+
 #include FT_INTERNAL_STREAM_H
 #include FT_INTERNAL_MEMORY_H
 #include FT_INTERNAL_TRUETYPE_TYPES_H
@@ -929,103 +933,163 @@
   }
 
 
+#ifdef HAVE_BSEARCH
+  static int comp_glypharray( const void *key,
+			      const void *slot )
+  {
+    FT_UShort glyphID = *(FT_UShort *)key;
+    FT_UShort item = *(FT_UShort *)slot;
+
+    return glyphID == item ? 0 : glyphID < item ? -1 : 1;
+  }
+#endif /* HAVE_BSEARCH */
+
+
   static FT_Error  Coverage_Index1( TTO_CoverageFormat1*  cf1,
                                     FT_UShort             glyphID,
                                     FT_UShort*            index )
   {
-    FT_UShort min, max, new_min, new_max, middle;
-
     FT_UShort*  array = cf1->GlyphArray;
+    FT_UShort*  match = NULL;
 
+    if ( cf1->GlyphCount )
+    {
+      /* binary search */
+#ifdef HAVE_BSEARCH
 
-    /* binary search */
+      match = bsearch (&glyphID,
+		       array,
+		       cf1->GlyphCount,
+		       sizeof (FT_UShort),
+		       comp_glypharray);
 
-    if ( cf1->GlyphCount == 0 )
-      return TTO_Err_Not_Covered;
+#else /* !HAVE_BSEARCH */
 
-    new_min = 0;
-    new_max = cf1->GlyphCount - 1;
+      FT_UShort min, max, new_min, new_max, middle;
 
-    do
+      new_min = 0;
+      new_max = cf1->GlyphCount - 1;
+
+      do
+      {
+	min = new_min;
+	max = new_max;
+
+	/* we use (min + max) / 2 = max - (max - min) / 2  to avoid
+	   overflow and rounding errors                             */
+
+	middle = max - ( ( max - min ) >> 1 );
+
+	if ( glyphID == array[middle] )
+	{
+	  match = array + middle;
+	  break;
+	}
+	else if ( glyphID < array[middle] )
+	{
+	  if ( middle == min )
+	    break;
+	  new_max = middle - 1;
+	}
+	else
+	{
+	  if ( middle == max )
+	    break;
+	  new_min = middle + 1;
+	}
+      } while ( min < max );
+#endif /* !HAVE_BSEARCH */
+    }
+
+    if (match)
     {
-      min = new_min;
-      max = new_max;
+      *index = match - array;
+    }
 
-      /* we use (min + max) / 2 = max - (max - min) / 2  to avoid
-         overflow and rounding errors                             */
+    return match ? TT_Err_Ok : TTO_Err_Not_Covered;
+  }
 
-      middle = max - ( ( max - min ) >> 1 );
 
-      if ( glyphID == array[middle] )
-      {
-        *index = middle;
-        return TT_Err_Ok;
-      }
-      else if ( glyphID < array[middle] )
-      {
-        if ( middle == min )
-          break;
-        new_max = middle - 1;
-      }
-      else
-      {
-        if ( middle == max )
-          break;
-        new_min = middle + 1;
-      }
-    } while ( min < max );
+#ifdef HAVE_BSEARCH
+  static int comp_range_record( const void *key,
+				const void *slot )
+  {
+    FT_UShort glyphID = *(FT_UShort *)key;
+    const TTO_RangeRecord *rr = slot;
 
-    return TTO_Err_Not_Covered;
+    if ( glyphID >= rr->Start && glyphID <= rr->End )
+      return 0;
+    else if ( glyphID < rr->Start )
+      return -1;
+    else
+      return 1;
   }
+#endif /* HAVE_BSEARCH */
 
 
   static FT_Error  Coverage_Index2( TTO_CoverageFormat2*  cf2,
                                     FT_UShort             glyphID,
                                     FT_UShort*            index )
   {
-    FT_UShort         min, max, new_min, new_max, middle;
 
     TTO_RangeRecord*  rr = cf2->RangeRecord;
+    TTO_RangeRecord*  match = NULL;
 
+    if ( cf2->RangeCount )
+    {
+      /* binary search */
+#ifdef HAVE_BSEARCH
 
-    /* binary search */
+      match = bsearch (&glyphID,
+		       rr,
+		       cf2->RangeCount,
+		       sizeof (TTO_RangeRecord),
+		       comp_range_record);
 
-    if ( cf2->RangeCount == 0 )
-      return TTO_Err_Not_Covered;
+#else /* !HAVE_BSEARCH */
 
-    new_min = 0;
-    new_max = cf2->RangeCount - 1;
+      FT_UShort         min, max, new_min, new_max, middle;
 
-    do
-    {
-      min = new_min;
-      max = new_max;
+      new_min = 0;
+      new_max = cf2->RangeCount - 1;
 
-      /* we use (min + max) / 2 = max - (max - min) / 2  to avoid
-         overflow and rounding errors                             */
+      do
+      {
+	min = new_min;
+	max = new_max;
 
-      middle = max - ( ( max - min ) >> 1 );
+	/* we use (min + max) / 2 = max - (max - min) / 2  to avoid
+	   overflow and rounding errors                             */
 
-      if ( glyphID >= rr[middle].Start && glyphID <= rr[middle].End )
-      {
-        *index = rr[middle].StartCoverageIndex + glyphID - rr[middle].Start;
-        return TT_Err_Ok;
-      }
-      else if ( glyphID < rr[middle].Start )
-      {
-        if ( middle == min )
-          break;
-        new_max = middle - 1;
-      }
-      else
-      {
-        if ( middle == max )
-          break;
-        new_min = middle + 1;
-      }
-    } while ( min < max );
+	middle = max - ( ( max - min ) >> 1 );
+
+	if ( glyphID >= rr[middle].Start && glyphID <= rr[middle].End )
+	{
+	  match = rr + middle;
+	  break;
+	}
+	else if ( glyphID < rr[middle].Start )
+	{
+	  if ( middle == min )
+	    break;
+	  new_max = middle - 1;
+	}
+	else
+	{
+	  if ( middle == max )
+	    break;
+	  new_min = middle + 1;
+	}
+      } while ( min < max );
+#endif /* !HAVE_BSEARCH */
+    }
 
-    return TTO_Err_Not_Covered;
+    if (match)
+    {
+      *index = match->StartCoverageIndex + glyphID - match->Start;
+    }
+
+    return match ? TT_Err_Ok : TTO_Err_Not_Covered;
   }
 
 
@@ -1316,6 +1380,23 @@
   }
 
 
+#ifdef HAVE_BSEARCH
+  static int comp_class_range_record( const void *key,
+				      const void *slot )
+  {
+    FT_UShort glyphID = *(FT_UShort *)key;
+    const TTO_ClassRangeRecord *crr = slot;
+
+    if ( glyphID >= crr->Start && glyphID <= crr->End )
+      return 0;
+    else if ( glyphID < crr->Start )
+      return -1;
+    else
+      return 1;
+  }
+#endif /* HAVE_BSEARCH */
+
+
   /* we need the index value of the last searched class range record
      in case of failure for constructed GDEF tables                  */
 
@@ -1324,68 +1405,73 @@
                                FT_UShort*            class,
                                FT_UShort*            index )
   {
-    FT_Error               error = TT_Err_Ok;
-    FT_UShort              min, max, new_min, new_max, middle;
-
     TTO_ClassRangeRecord*  crr = cdf2->ClassRangeRecord;
+    TTO_ClassRangeRecord*  match = NULL;
 
 
-    /* binary search */
+    if ( cdf2->ClassRangeCount )
+    {
+      /* binary search */
+#ifdef HAVE_BSEARCH
 
-    if ( cdf2->ClassRangeCount == 0 )
-      {
-	*class = 0;
-	if ( index )
-	  *index = 0;
-	
-	return TTO_Err_Not_Covered;
-      }
+      match = bsearch (&glyphID,
+		       crr,
+		       cdf2->ClassRangeCount,
+		       sizeof (TTO_ClassRangeRecord),
+		       comp_class_range_record);
 
-    new_min = 0;
-    new_max = cdf2->ClassRangeCount - 1;
+#else /* !HAVE_BSEARCH */
 
-    do
-    {
-      min = new_min;
-      max = new_max;
+      FT_UShort              min, max, new_min, new_max, middle;
 
-      /* we use (min + max) / 2 = max - (max - min) / 2  to avoid
-         overflow and rounding errors                             */
+      new_min = 0;
+      new_max = cdf2->ClassRangeCount - 1;
 
-      middle = max - ( ( max - min ) >> 1 );
-
-      if ( glyphID >= crr[middle].Start && glyphID <= crr[middle].End )
-      {
-        *class = crr[middle].Class;
-        error  = TT_Err_Ok;
-        break;
-      }
-      else if ( glyphID < crr[middle].Start )
+      do
       {
-        if ( middle == min )
-        {
-          *class = 0;
-          error  = TTO_Err_Not_Covered;
-          break;
-        }
-        new_max = middle - 1;
-      }
-      else
-      {
-        if ( middle == max )
-        {
-          *class = 0;
-          error  = TTO_Err_Not_Covered;
-          break;
-        }
-        new_min = middle + 1;
-      }
-    } while ( min < max );
+	min = new_min;
+	max = new_max;
 
-    if ( index )
-      *index = middle;
+	/* we use (min + max) / 2 = max - (max - min) / 2  to avoid
+	   overflow and rounding errors                             */
 
-    return error;
+	middle = max - ( ( max - min ) >> 1 );
+
+	if ( glyphID >= crr[middle].Start && glyphID <= crr[middle].End )
+	{
+	  match = crr + middle;
+	  break;
+	}
+	else if ( glyphID < crr[middle].Start )
+	{
+	  if ( middle == min )
+	    break;
+	  new_max = middle - 1;
+	}
+	else
+	{
+	  if ( middle == max )
+	    break;
+	  new_min = middle + 1;
+	}
+      } while ( min < max );
+#endif /* !HAVE_BSEARCH */
+    }
+
+    if (match)
+    {
+      *class = match->Class;
+      if (index)
+	*index = match - crr;
+    }
+    else
+    {
+      *class = 0;
+      if (index)
+	*index = 0;
+    }
+
+    return match ? TT_Err_Ok : TTO_Err_Not_Covered;
   }
 
 
