Replace 'KEITH PACKARD' with 'THE AUTHOR(S)' in license text in all files

[fontconfig.git] / src / fccharset.c

diff --git a/src/fccharset.c b/src/fccharset.c
index f4042db07dbc2c541213b5578f160456d3023d81..2ec74da2893c9fca98442aafb33c8accb5247bb4 100644 (file)
--- a/src/fccharset.c
+++ b/src/fccharset.c
@@ -1,5 +1,5 @@
 /*
- * $RCSId: xc/lib/fontconfig/src/fccharset.c,v 1.18 2002/08/22 07:36:44 keithp Exp $
+ * fontconfig/src/fccharset.c
  *
  * Copyright © 2001 Keith Packard
  *
@@ -13,9 +13,9 @@
  * representations about the suitability of this software for any purpose.  It
  * is provided "as is" without express or implied warranty.
  *
- * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
- * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
@@ -81,38 +81,50 @@ FcCharSetDestroy (FcCharSet *fcs)
 }
 
 /*
- * Locate the leaf containing the specified char, return
- * its index if it exists, otherwise return negative of
+ * Search for the leaf containing with the specified num.
+ * Return its index if it exists, otherwise return negative of
  * the (position + 1) where it should be inserted
  */
 
+
 static int
-FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
+FcCharSetFindLeafForward (const FcCharSet *fcs, int start, FcChar16 num)
 {
     FcChar16           *numbers = FcCharSetNumbers(fcs);
     FcChar16           page;
-    int                        low = 0;
+    int                        low = start;
     int                        high = fcs->num - 1;
 
     if (!numbers)
        return -1;
-    ucs4 >>= 8;
     while (low <= high)
     {
        int mid = (low + high) >> 1;
        page = numbers[mid];
-       if (page == ucs4)
+       if (page == num)
            return mid;
-       if (page < ucs4)
+       if (page < num)
            low = mid + 1;
        else
            high = mid - 1;
     }
-    if (high < 0 || (high < fcs->num && numbers[high] < ucs4))
+    if (high < 0 || (high < fcs->num && numbers[high] < num))
        high++;
     return -(high + 1);
 }
 
+/*
+ * Locate the leaf containing the specified char, return
+ * its index if it exists, otherwise return negative of
+ * the (position + 1) where it should be inserted
+ */
+
+static int
+FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
+{
+    return FcCharSetFindLeafForward (fcs, 0, ucs4 >> 8);
+}
+
 static FcCharLeaf *
 FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
 {
@@ -452,6 +464,54 @@ FcCharSetUnion (const FcCharSet *a, const FcCharSet *b)
     return FcCharSetOperate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
 }
 
+FcBool
+FcCharSetMerge (FcCharSet *a, const FcCharSet *b, FcBool *changed)
+{
+    int                ai = 0, bi = 0;
+    FcChar16   an, bn;
+
+    if (a->ref == FC_REF_CONSTANT)
+       return FcFalse;
+
+    if (changed) {
+       *changed = !FcCharSetIsSubset(b, a);
+       if (!*changed)
+           return FcTrue;
+    }
+
+    while (bi < b->num)
+    {
+       an = ai < a->num ? FcCharSetNumbers(a)[ai] : ~0;
+       bn = FcCharSetNumbers(b)[bi];
+
+       if (an < bn)
+       {
+           ai = FcCharSetFindLeafForward (a, ai + 1, bn);
+           if (ai < 0)
+               ai = -ai - 1;
+       }
+       else
+       {
+           FcCharLeaf *bl = FcCharSetLeaf(b, bi);
+           if (bn < an)
+           {
+               if (!FcCharSetAddLeaf (a, bn << 8, bl))
+                   return FcFalse;
+           }
+           else
+           {
+               FcCharLeaf *al = FcCharSetLeaf(a, ai);
+               FcCharSetUnionLeaf (al, al, bl);
+           }
+
+           ai++;
+           bi++;
+       }
+    }
+
+    return FcTrue;
+}
+
 static FcBool
 FcCharSetSubtractLeaf (FcCharLeaf *result,
                       const FcCharLeaf *al,
@@ -484,10 +544,14 @@ FcCharSetHasChar (const FcCharSet *fcs, FcChar32 ucs4)
 static FcChar32
 FcCharSetPopCount (FcChar32 c1)
 {
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+    return __builtin_popcount (c1);
+#else
     /* hackmem 169 */
     FcChar32   c2 = (c1 >> 1) & 033333333333;
     c2 = c1 - c2 - ((c2 >> 1) & 033333333333);
     return (((c2 + (c2 >> 3)) & 030707070707) % 077);
+#endif
 }
 
 FcChar32
@@ -620,29 +684,9 @@ FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b)
            return FcFalse;
        else
        {
-           int     low = bi + 1;
-           int     high = b->num - 1;
-
-           /*
-            * Search for page 'an' in 'b'
-            */
-           while (low <= high)
-           {
-               int mid = (low + high) >> 1;
-               bn = FcCharSetNumbers(b)[mid];
-               if (bn == an)
-               {
-                   high = mid;
-                   break;
-               }
-               if (bn < an)
-                   low = mid + 1;
-               else
-                   high = mid - 1;
-           }
-           bi = high;
-           while (bi < b->num && FcCharSetNumbers(b)[bi] < an)
-               bi++;
+           bi = FcCharSetFindLeafForward (b, bi + 1, an);
+           if (bi < 0)
+               bi = -bi - 1;
        }
     }
     /*