text: /*
   * fontconfig/src/fclist.c
   *
   * Copyright © 2000 Keith Packard
   *
   * Permission to use, copy, modify, distribute, and sell this software and its
   * documentation for any purpose is hereby granted without fee, provided that
   * the above copyright notice appear in all copies and that both that
   * copyright notice and this permission notice appear in supporting
   * documentation, and that the name of the author(s) not be used in
   * advertising or publicity pertaining to distribution of the software without
   * specific, written prior permission.  The authors make no
   * representations about the suitability of this software for any purpose.  It
   * is provided "as is" without express or implied warranty.
   *
   * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
   * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
   * 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
   * PERFORMANCE OF THIS SOFTWARE.
   */
  
  #include "fcint.h"
  #include <stdlib.h>
  
  FcObjectSet *
  FcObjectSetCreate (void)
  {
      FcObjectSet    *os;
  
      os = (FcObjectSet *) malloc (sizeof (FcObjectSet));
      if (!os)
  	return 0;
      os->nobject = 0;
      os->sobject = 0;
      os->objects = 0;
      return os;
  }
  
  FcBool
  FcObjectSetAdd (FcObjectSet *os, const char *object)
  {
      int		s;
      const char	**objects;
      int		high, low, mid, c;
  
      if (os->nobject == os->sobject)
      {
  	s = os->sobject + 4;
  	if (os->objects)
  	    objects = (const char **) realloc ((void *) os->objects,
  					       s * sizeof (const char *));
  	else
  	    objects = (const char **) malloc (s * sizeof (const char *));
  	if (!objects)
  	    return FcFalse;
  	os->objects = objects;
  	os->sobject = s;
      }
      high = os->nobject - 1;
      low = 0;
      mid = 0;
      c = 1;
      object = strdup (object);
      while (low <= high)
      {
  	mid = (low + high) >> 1;
  	c = os->objects[mid] - object;
  	if (c == 0)
  	{
  	    FcFree (object);
  	    return FcTrue;
  	}
  	if (c < 0)
  	    low = mid + 1;
  	else
  	    high = mid - 1;
      }
      if (c < 0)
  	mid++;
      memmove (os->objects + mid + 1, os->objects + mid,
  	     (os->nobject - mid) * sizeof (const char *));
      os->objects[mid] = object;
      os->nobject++;
      return FcTrue;
  }
  
  void
  FcObjectSetDestroy (FcObjectSet *os)
  {
      int i;
  
      if (os->objects)
      {
  	for (i = 0; i < os->nobject; i++)
  	    FcFree (os->objects[i]);
  
  	free ((void *) os->objects);
      }
      free (os);
  }
  
  FcObjectSet *
  FcObjectSetVaBuild (const char *first, va_list va)
  {
      FcObjectSet    *ret;
  
      FcObjectSetVapBuild (ret, first, va);
      return ret;
  }
  
  FcObjectSet *
  FcObjectSetBuild (const char *first, ...)
  {
      va_list	    va;
      FcObjectSet    *os;
  
      va_start (va, first);
      FcObjectSetVapBuild (os, first, va);
      va_end (va);
      return os;
  }
  
  /*
   * Font must have a containing value for every value in the pattern
   */
  static FcBool
  FcListValueListMatchAny (FcValueListPtr patOrig,	    /* pattern */
  			 FcValueListPtr fntOrig)	    /* font */
  {
      FcValueListPtr	 pat, fnt;
  
      for (pat = patOrig; pat != NULL; pat = FcValueListNext(pat))
      {
  	for (fnt = fntOrig; fnt != NULL; fnt = FcValueListNext(fnt))
  	{
  	    /*
  	     * make sure the font 'contains' the pattern.
  	     * (OpListing is OpContains except for strings
  	     *  where it requires an exact match)
  	     */
  	    if (FcConfigCompareValue (&fnt->value,
  				      FC_OP (FcOpListing, FcOpFlagIgnoreBlanks),
  				      &pat->value))
  		break;
  	}
  	if (fnt == NULL)
  	    return FcFalse;
      }
      return FcTrue;
  }
  
  static FcBool
  FcListValueListEqual (FcValueListPtr v1orig,
  		      FcValueListPtr v2orig)
  {
      FcValueListPtr	    v1, v2;
  
      for (v1 = v1orig; v1 != NULL; v1 = FcValueListNext(v1))
      {
  	for (v2 = v2orig; v2 != NULL; v2 = FcValueListNext(v2))
  	    if (FcValueEqual (FcValueCanonicalize(&(v1)->value),
  			      FcValueCanonicalize(&(v2)->value)))
  		break;
  	if (v2 == NULL)
  	    return FcFalse;
      }
      for (v2 = v2orig; v2 != NULL; v2 = FcValueListNext(v2))
      {
  	for (v1 = v1orig; v1 != NULL; v1 = FcValueListNext(v1))
  	    if (FcValueEqual (FcValueCanonicalize(&v1->value),
  			      FcValueCanonicalize(&v2->value)))
  		break;
  	if (v1 == NULL)
  	    return FcFalse;
      }
      return FcTrue;
  }
  
  static FcBool
  FcListPatternEqual (FcPattern	*p1,
  		    FcPattern	*p2,
  		    FcObjectSet	*os)
  {
      int		    i;
      FcPatternElt    *e1, *e2;
  
      for (i = 0; i < os->nobject; i++)
      {
  	e1 = FcPatternObjectFindElt (p1, FcObjectFromName (os->objects[i]));
  	e2 = FcPatternObjectFindElt (p2, FcObjectFromName (os->objects[i]));
  	if (!e1 && !e2)
  	    continue;
  	if (!e1 || !e2)
  	    return FcFalse;
  	if (!FcListValueListEqual (FcPatternEltValues(e1),
  				   FcPatternEltValues(e2)))
  	    return FcFalse;
      }
      return FcTrue;
  }
  
  /*
   * FcTrue iff all objects in "p" match "font"
   */
  
  FcBool
  FcListPatternMatchAny (const FcPattern *p,
  		       const FcPattern *font)
  {
      int		    i;
  
      for (i = 0; i < p->num; i++)
      {
  	FcPatternElt	*pe = &FcPatternElts(p)[i];
  	FcPatternElt	*fe;
  
  	if (pe->object == FC_NAMELANG_OBJECT)
  	{
  	    /* "namelang" object is the alias object to change "familylang",
  	     * "stylelang" and "fullnamelang" object alltogether. it won't be
  	     * available on the font pattern. so checking its availability
  	     * causes no results. we should ignore it here.
  	     */
  	    continue;
  	}
  	fe = FcPatternObjectFindElt (font, pe->object);
  	if (!fe)
  	    return FcFalse;
  	if (!FcListValueListMatchAny (FcPatternEltValues(pe),    /* pat elts */
  				      FcPatternEltValues(fe)))   /* font elts */
  	    return FcFalse;
      }
      return FcTrue;
  }
  
  static FcChar32
  FcListMatrixHash (const FcMatrix *m)
  {
      int	    xx = (int) (m->xx * 100),
  	    xy = (int) (m->xy * 100),
  	    yx = (int) (m->yx * 100),
  	    yy = (int) (m->yy * 100);
  
      return ((FcChar32) xx) ^ ((FcChar32) xy) ^ ((FcChar32) yx) ^ ((FcChar32) yy);
  }
  
  static FcChar32
  FcListValueHash (FcValue    *value)
  {
      FcValue v = FcValueCanonicalize(value);
      switch (v.type) {
      case FcTypeVoid:
  	return 0;
      case FcTypeInteger:
  	return (FcChar32) v.u.i;
      case FcTypeDouble:
  	return (FcChar32) (int) v.u.d;
      case FcTypeString:
  	return FcStrHashIgnoreCase (v.u.s);
      case FcTypeBool:
  	return (FcChar32) v.u.b;
      case FcTypeMatrix:
  	return FcListMatrixHash (v.u.m);
      case FcTypeCharSet:
  	return FcCharSetCount (v.u.c);
      case FcTypeFTFace:
  	return (long) v.u.f;
      case FcTypeLangSet:
  	return FcLangSetHash (v.u.l);
      }
      return 0;
  }
  
  static FcChar32
  FcListValueListHash (FcValueListPtr list)
  {
      FcChar32	h = 0;
  
      while (list != NULL)
      {
  	h = h ^ FcListValueHash (&list->value);
  	list = FcValueListNext(list);
      }
      return h;
  }
  
  static FcChar32
  FcListPatternHash (FcPattern	*font,
  		   FcObjectSet	*os)
  {
      int		    n;
      FcPatternElt    *e;
      FcChar32	    h = 0;
  
      for (n = 0; n < os->nobject; n++)
      {
  	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[n]));
  	if (e)
  	    h = h ^ FcListValueListHash (FcPatternEltValues(e));
      }
      return h;
  }
  
  typedef struct _FcListBucket {
      struct _FcListBucket    *next;
      FcChar32		    hash;
      FcPattern		    *pattern;
  } FcListBucket;
  
  #define FC_LIST_HASH_SIZE   4099
  
  typedef struct _FcListHashTable {
      int		    entries;
      FcListBucket    *buckets[FC_LIST_HASH_SIZE];
  } FcListHashTable;
  
  static void
  FcListHashTableInit (FcListHashTable *table)
  {
      table->entries = 0;
      memset (table->buckets, '\0', sizeof (table->buckets));
  }
  
  static void
  FcListHashTableCleanup (FcListHashTable *table)
  {
      int	i;
      FcListBucket    *bucket, *next;
  
      for (i = 0; i < FC_LIST_HASH_SIZE; i++)
      {
  	for (bucket = table->buckets[i]; bucket; bucket = next)
  	{
  	    next = bucket->next;
  	    FcPatternDestroy (bucket->pattern);
  	    free (bucket);
  	}
  	table->buckets[i] = 0;
      }
      table->entries = 0;
  }
  
  static int
  FcGetDefaultObjectLangIndex (FcPattern *font, FcObject object, const FcChar8 *lang)
  {
      FcPatternElt   *e = FcPatternObjectFindElt (font, object);
      FcValueListPtr  v;
      FcValue         value;
      int             idx = -1;
      int             defidx = -1;
      int             i;
  
      if (e)
      {
  	for (v = FcPatternEltValues(e), i = 0; v; v = FcValueListNext(v), ++i)
  	{
  	    value = FcValueCanonicalize (&v->value);
  
  	    if (value.type == FcTypeString)
  	    {
  		FcLangResult res = FcLangCompare (value.u.s, lang);
  		if (res == FcLangEqual)
  		    return i;
  
  		if (res == FcLangDifferentCountry && idx < 0)
  		    idx = i;
  		if (defidx < 0)
  		{
  		    /* workaround for fonts that has non-English value
  		     * at the head of values.
  		     */
  		    res = FcLangCompare (value.u.s, (FcChar8 *)"en");
  		    if (res == FcLangEqual)
  			defidx = i;
  		}
  	    }
  	}
      }
  
      return (idx > 0) ? idx : (defidx > 0) ? defidx : 0;
  }
  
  static FcBool
  FcListAppend (FcListHashTable	*table,
  	      FcPattern		*font,
  	      FcObjectSet	*os,
  	      const FcChar8	*lang)
  {
      int		    o;
      FcPatternElt    *e;
      FcValueListPtr  v;
      FcChar32	    hash;
      FcListBucket    **prev, *bucket;
      int             familyidx = -1;
      int             fullnameidx = -1;
      int             styleidx = -1;
      int             defidx = 0;
      int             idx;
  
      hash = FcListPatternHash (font, os);
      for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
  	 (bucket = *prev); prev = &(bucket->next))
      {
  	if (bucket->hash == hash &&
  	    FcListPatternEqual (bucket->pattern, font, os))
  	    return FcTrue;
      }
      bucket = (FcListBucket *) malloc (sizeof (FcListBucket));
      if (!bucket)
  	goto bail0;
      bucket->next = 0;
      bucket->hash = hash;
      bucket->pattern = FcPatternCreate ();
      if (!bucket->pattern)
  	goto bail1;
  
      for (o = 0; o < os->nobject; o++)
      {
  	if (!strcmp (os->objects[o], FC_FAMILY) || !strcmp (os->objects[o], FC_FAMILYLANG))
  	{
  	    if (familyidx < 0)
  		familyidx = FcGetDefaultObjectLangIndex (font, FC_FAMILYLANG_OBJECT, lang);
  	    defidx = familyidx;
  	}
  	else if (!strcmp (os->objects[o], FC_FULLNAME) || !strcmp (os->objects[o], FC_FULLNAMELANG))
  	{
  	    if (fullnameidx < 0)
  		fullnameidx = FcGetDefaultObjectLangIndex (font, FC_FULLNAMELANG_OBJECT, lang);
  	    defidx = fullnameidx;
  	}
  	else if (!strcmp (os->objects[o], FC_STYLE) || !strcmp (os->objects[o], FC_STYLELANG))
  	{
  	    if (styleidx < 0)
  		styleidx = FcGetDefaultObjectLangIndex (font, FC_STYLELANG_OBJECT, lang);
  	    defidx = styleidx;
  	}
  	else
  	    defidx = 0;
  
  	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[o]));
  	if (e)
  	{
  	    for (v = FcPatternEltValues(e), idx = 0; v;
  		 v = FcValueListNext(v), ++idx)
  	    {
  		if (!FcPatternAdd (bucket->pattern,
  				   os->objects[o],
  				   FcValueCanonicalize(&v->value), defidx != idx))
  		    goto bail2;
  	    }
  	}
      }
      *prev = bucket;
      ++table->entries;
  
      return FcTrue;
  
  bail2:
      FcPatternDestroy (bucket->pattern);
  bail1:
      free (bucket);
  bail0:
      return FcFalse;
  }
  
  FcFontSet *
  FcFontSetList (FcConfig	    *config,
  	       FcFontSet    **sets,
  	       int	    nsets,
  	       FcPattern    *p,
  	       FcObjectSet  *os)
  {
      FcFontSet	    *ret;
      FcFontSet	    *s;
      int		    f;
      int		    set;
      FcListHashTable table;
      int		    i;
      FcListBucket    *bucket;
      int             destroy_os = 0;
  
      if (!config)
      {
  	if (!FcInitBringUptoDate ())
  	    goto bail0;
  
  	config = FcConfigGetCurrent ();
  	if (!config)
  	    goto bail0;
      }
      FcListHashTableInit (&table);
  
      if (!os)
      {
  	os = FcObjectGetSet ();
  	destroy_os = 1;
      }
  
      /*
       * Walk all available fonts adding those that
       * match to the hash table
       */
      for (set = 0; set < nsets; set++)
      {
  	s = sets[set];
  	if (!s)
  	    continue;
  	for (f = 0; f < s->nfont; f++)
  	    if (FcListPatternMatchAny (p,		/* pattern */
  				       s->fonts[f]))	/* font */
  	    {
  		FcChar8 *lang;
  
  		if (FcPatternObjectGetString (p, FC_NAMELANG_OBJECT, 0, &lang) != FcResultMatch)
  		{
  			lang = FcGetDefaultLang ();
  		}
  		if (!FcListAppend (&table, s->fonts[f], os, lang))
  		    goto bail1;
  	    }
      }
  #if 0
      {
  	int	max = 0;
  	int	full = 0;
  	int	ents = 0;
  	int	len;
  	for (i = 0; i < FC_LIST_HASH_SIZE; i++)
  	{
  	    if ((bucket = table.buckets[i]))
  	    {
  		len = 0;
  		for (; bucket; bucket = bucket->next)
  		{
  		    ents++;
  		    len++;
  		}
  		if (len > max)
  		    max = len;
  		full++;
  	    }
  	}
  	printf ("used: %d max: %d avg: %g\n", full, max,
  		(double) ents / FC_LIST_HASH_SIZE);
      }
  #endif
      /*
       * Walk the hash table and build
       * a font set
       */
      ret = FcFontSetCreate ();
      if (!ret)
  	goto bail0;
      for (i = 0; i < FC_LIST_HASH_SIZE; i++)
  	while ((bucket = table.buckets[i]))
  	{
  	    if (!FcFontSetAdd (ret, bucket->pattern))
  		goto bail2;
  	    table.buckets[i] = bucket->next;
  	    free (bucket);
  	}
  
      return ret;
  
  bail2:
      FcFontSetDestroy (ret);
  bail1:
      FcListHashTableCleanup (&table);
  bail0:
      if (destroy_os)
  	FcObjectSetDestroy (os);
      return 0;
  }
  
  FcFontSet *
  FcFontList (FcConfig	*config,
  	    FcPattern	*p,
  	    FcObjectSet *os)
  {
      FcFontSet	*sets[2];
      int		nsets;
  
      if (!config)
      {
  	if (!FcInitBringUptoDate ())
  	    return 0;
  
  	config = FcConfigGetCurrent ();
  	if (!config)
  	    return 0;
      }
      nsets = 0;
      if (config->fonts[FcSetSystem])
  	sets[nsets++] = config->fonts[FcSetSystem];
      if (config->fonts[FcSetApplication])
  	sets[nsets++] = config->fonts[FcSetApplication];
      return FcFontSetList (config, sets, nsets, p, os);
  }
  #define __fclist__
  #include "fcaliastail.h"
  #undef __fclist__
  