do { size_t cnt[act_size]; struct element_t *elem[act_size]; size_t act_planes = 1;  memset (cnt, '\0', sizeof cnt); memset (elem, '\0', sizeof elem);  runp = collate->start; while (runp != NULL) { if (runp->wcs != NULL) { size_t nr = runp->wcs[0] % act_size; struct element_t *elemp = elem[nr];  while (elemp != NULL)
do { size_t cnt[act_size]; struct element_t *elem[act_size]; size_t act_planes = 1;  memset (cnt, '\0', sizeof cnt); memset (elem, '\0', sizeof elem);  runp = collate->start; while (runp != NULL) { if (runp->wcs != NULL)
collate_finish (struct localedef_t *locale, struct charmap_t *charmap){  /* Now is the time when we can assign the individual collation     values for all the symbols.  We have possibly different values     for the wide- and the multibyte-character symbols.  This is done     since it might make a difference in the encoding if there is in     some cases no multibyte-character but there are wide-characters.     (The other way around it is not important since theencoded     collation value in the wide-character case is 32 bits wide and     therefore requires no encoding).     The lowest collation value assigned is 2.  Zero is reserved for     the NUL byte terminating the strings in the `strxfrm'/`wcsxfrm'     functions and 1 is used to separate the individual passes for the     different rules.     We also have to construct is list with all the bytes/words which     can come first in a sequence, followed by all the elements which     also start with this byte/word.  The order is reverse which has     among others the important effect that longer strings are located     first in the list.  This is required for the output data since     the algorithm used in `strcoll' etc depends on this.     The multibyte case is easy.  We simply sort into an array with     256 elements.  */  struct locale_collate_t *collate = locale->categories[LC_COLLATE].collate;  int mbact[nrules];  int wcact;  int mbseqact;  int wcseqact;  struct element_t *runp;  int i;  int need_undefined = 0;  struct section_list *sect;  int ruleidx;  int nr_wide_elems = 0;  size_t min_total;  size_t act_size;  if (collate == NULL)    {      /* No data, no check.  */      if (! be_quiet)	error (0, 0, _("No definition for %s category found"), "LC_COLLATE");      return;    }  /* If this assertion is hit change the type in `element_t'.  */  assert (nrules <= sizeof (runp->used_in_level) * 8);  /* Make sure that the `position' rule is used either in all sections     or in none.  */  for (i = 0; i < nrules; ++i)    for (sect = collate->sections; sect != NULL; sect = sect->next)      if (sect->rules != NULL	  && ((sect->rules[i] & sort_position)	      != (collate->sections->rules[i] & sort_position)))	{	  error (0, 0, _("\%s: `position' must be used for a specific level in all sections or none"),		 "LC_COLLATE");	  break;	}  /* Find out which elements are used at which level.  At the same     time we find out whether we have any undefined symbols.  */  runp = collate->start;  while (runp != NULL)    {      if (runp->mbs != NULL)	{	  for (i = 0; i < nrules; ++i)	    {	      int j;	      for (j = 0; j < runp->weights[i].cnt; ++j)		/* A NULL pointer as the weight means IGNORE.  */		if (runp->weights[i].w[j] != NULL)		  {		    if (runp->weights[i].w[j]->weights == NULL)		      {			error_at_line (0, 0, runp->file, runp->line,				       _("symbol `%s' not defined"),				       runp->weights[i].w[j]->name);			need_undefined = 1;			runp->weights[i].w[j] = &collate->undefined;		      }		    else		      /* Set the bit for the level.  */		      runp->weights[i].w[j]->used_in_level |= 1 << i;		  }	    }	}      /* Up to the next entry.  */      runp = runp->next;    }  /* Walk through the list of defined sequences and assign weights.  Also     create the data structure which will allow generating the single byte     character based tables.     Since at each time only the weights for each of the rules are     only compared to other weights for this rule it is possible to     assign more compact weight values than simply counting all     weights in sequence.  We can assign weights from 3, one for each     rule individually and only for those elements, which are actually     used for this rule.     Why is this important?  It is not for the wide char table.  But     it is for the singlebyte output since here larger numbers have to     be encoded to make it possible to emit the value as a byte     string.  */  for (i = 0; i < nrules; ++i)    mbact[i] = 2;  wcact = 2;  mbseqact = 0;  wcseqact = 0;  runp = collate->start;  while (runp != NULL)    {      /* Determine the order.  */      if (runp->used_in_level != 0)	{	  runp->mborder = (int *) obstack_alloc (&collate->mempool,						 nrules * sizeof (int));	  for (i = 0; i < nrules; ++i)	    if ((runp->used_in_level & (1 << i)) != 0)	      runp->mborder[i] = mbact[i]++;	    else	      runp->mborder[i] = 0;	}      if (runp->mbs != NULL)	{	  struct element_t **eptr;	  struct element_t *lastp = NULL;	  /* Find the point where to insert in the list.  */	  eptr = &collate->mbheads[((unsigned char *) runp->mbs)[0]];	  while (*eptr != NULL)	    {	      if ((*eptr)->nmbs < runp->nmbs)		break;	      if ((*eptr)->nmbs == runp->nmbs)		{		  int c = memcmp ((*eptr)->mbs, runp->mbs, runp->nmbs);		  if (c == 0)		    {		      /* This should not happen.  It means that we have			 to symbols with the same byte sequence.  It is			 of course an error.  */		      error_at_line (0, 0, (*eptr)->file, (*eptr)->line,				     _("symbol `%s' has the same encoding as"),				     (*eptr)->name);		      error_at_line (0, 0, runp->file, runp->line,				     _("symbol `%s'"), runp->name);		      goto dont_insert;		    }		  else if (c < 0)		    /* Insert it here.  */		    break;		}	      /* To the next entry.  */	      lastp = *eptr;	      eptr = &(*eptr)->mbnext;	    }	  /* Set the pointers.  */	  runp->mbnext = *eptr;	  runp->mblast = lastp;	  if (*eptr != NULL)	    (*eptr)->mblast = runp;	  *eptr = runp;	dont_insert:	}      if (runp->used_in_level)	{	  runp->wcorder = wcact++;	  /* We take the opportunity to count the elements which have	     wide characters.  */	  ++nr_wide_elems;	}      if (runp->is_character)	{	  if (runp->nmbs == 1)	    collate->mbseqorder[((unsigned char *) runp->mbs)[0]] = mbseqact++;	  runp->wcseqorder = wcseqact++;	}      /* Up to the next entry.  */      runp = runp->next;    }  /* Find out whether any of the `mbheads' entries is unset.  In this     case we use the UNDEFINED entry.  */  for (i = 1; i < 256; ++i)    if (collate->mbheads[i] == NULL)      {	need_undefined = 1;	collate->mbheads[i] = &collate->undefined;      }  /* Now to the wide character case.  Here we have to find first a good     mapping function to get the wide range of wide character values     (0x00000000 to 0x7fffffff) to a managable table.  This might take     some time so we issue a warning.     We use a very trivial hashing function to store the sparse     table.  CH % TABSIZE is used as an index.  To solve multiple hits     we have N planes.  This guarantees a fixed search time for a     character [N / 2].  In the following code we determine the minimum     value for TABSIZE * N, where TABSIZE >= 256.     Some people complained that this algorithm takes too long.  Well,     go on, improve it.  But changing the step size is *not* an     option.  Some people changed this to use only sizes of prime     numbers.  Think again, do some math.  We are looking for the     optimal solution, not something which works in general.  Unless     somebody can provide a dynamic programming solution I think this     implementation is as good as it can get.  */  if (nr_wide_elems > 512 && !be_quiet)    fputs (_("\Computing table size for collation table might take a while..."),	   stderr);  min_total = UINT_MAX;  act_size = 256;  /* While we want to have a small total size we are willing to use a     little bit larger table if this reduces the number of layers.     Therefore we add a little penalty to the number of planes.     Maybe this constant has to be adjusted a bit.  */#define PENALTY 128  do    {      size_t cnt[act_size];      struct element_t *elem[act_size];      size_t act_planes = 1;      memset (cnt, '\0', sizeof cnt);      memset (elem, '\0', sizeof elem);      runp = collate->start;      while (runp != NULL)	{	  if (runp->wcs != NULL)	    {	      size_t nr = runp->wcs[0] % act_size;	      struct element_t *elemp = elem[nr];	      while (elemp != NULL)		{		  if (elemp->wcs[0] == runp->wcs[0])		    break;		  elemp = elemp->wcnext;		}	      if (elemp == NULL && ++cnt[nr] > act_planes)		{		  act_planes = cnt[nr];		  runp->wcnext = elem[nr];		  elem[nr] = runp;		  if ((act_size + PENALTY) * act_planes >= min_total)		    break;		}	    }	  /* Up to the next entry.  */	  runp = runp->next;	}      if ((act_size + PENALTY) * act_planes < min_total)	{	  min_total = (act_size + PENALTY) * act_planes;	  collate->plane_size = act_size;	  collate->plane_cnt = act_planes;	}      ++act_size;    }  while (act_size < min_total);  if (nr_wide_elems > 512 && !be_quiet)    fputs (_(" done\n"), stderr);  /* Now that we know how large the table has to be we are able to     allocate the array and start adding the characters to the lists     in the same way we did it for the multibyte characters.  */  collate->wcheads = (struct element_t **)    obstack_alloc (&collate->mempool, (collate->plane_size				       * collate->plane_cnt				       * sizeof (struct element_t *)));  memset (collate->wcheads, '\0', (collate->plane_size				   * collate->plane_cnt				   * sizeof (struct element_t *)));  collate->wcseqorder = (uint32_t *)    obstack_alloc (&collate->mempool, (collate->plane_size				       * collate->plane_cnt				       * sizeof (uint32_t)));  memset (collate->wcseqorder, '\0', (collate->plane_size				      * collate->plane_cnt				      * sizeof (uint32_t)));  /* Start adding.  */  runp = collate->start;  while (runp != NULL)    {      if (runp->wcs != NULL)	{	  struct element_t **eptr;	  struct element_t *lastp = NULL;	  size_t idx;	  /* Find a free index.  */	  idx = runp->wcs[0] % collate->plane_size;	  while (collate->wcheads[idx] != NULL)	    {	      /* Stop if this is an entry with the same starting character.  */	      if (collate->wcheads[idx]->wcs[0] == runp->wcs[0])		break;	      idx += collate->plane_size;	    }	  /* Insert the collation sequence value.  */	  collate->wcseqorder[idx] = runp->wcseqorder;	  /* Find the point where to insert in the list.  */	  eptr = &collate->wcheads[idx];	  while (*eptr != NULL)	    {	      if ((*eptr)->nwcs < runp->nwcs)		break;	      if ((*eptr)->nwcs == runp->nwcs)		{		  int c = wmemcmp ((wchar_t *) (*eptr)->wcs,				   (wchar_t *) runp->wcs, runp->nwcs);		  if (c == 0)		    {		      /* This should not happen.  It means that we have			 to symbols with the same byte sequence.  It is			 of course an error.  */		      error_at_line (0, 0, (*eptr)->file, (*eptr)->line,				     _("symbol `%s' has the same encoding as"),				     (*eptr)->name);		      error_at_line (0, 0, runp->file, runp->line,				     _("symbol `%s'"), runp->name);		      goto dont_insertwc;		    }		  else if (c < 0)		    /* Insert it here.  */		    break;		}	      /* To the next entry.  */	      lastp = *eptr;	      eptr = &(*eptr)->wcnext;	    }	  /* Set the pointers.  */	  runp->wcnext = *eptr;	  runp->wclast = lastp;	  if (*eptr != NULL)	    (*eptr)->wclast = runp;	  *eptr = runp;	dont_insertwc:	}      /* Up to the next entry.  */      runp = runp->next;    }  /* Now determine whether the UNDEFINED entry is needed and if yes,     whether it was defined.  */  collate->undefined.used_in_level = need_undefined ? ~0ul : 0;  if (collate->undefined.file == NULL)    {      if (need_undefined)	{	  /* This seems not to be enforced by recent standards.  Don't	     emit an error, simply append UNDEFINED at the end.  */	  if (0)	    error (0, 0, _("no definition of `UNDEFINED'"));	  /* Add UNDEFINED at the end.  */	  collate->undefined.mborder =	    (int *) obstack_alloc (&collate->mempool, nrules * sizeof (int));	  for (i = 0; i < nrules; ++i)	    collate->undefined.mborder[i] = mbact[i]++;	}      /* In any case we will need the definition for the wide character	 case.  But we will not complain that it is missing since the	 specification strangely enough does not seem to account for	 this.  */      collate->undefined.wcorder = wcact++;    }  /* Finally, try to unify the rules for the sections.  Whenever the rules     for a section are the same as those for another section give the     ruleset the same index.  Since there are never many section we can     use an O(n^2) algorithm here.  */  sect = collate->sections;  while (sect != NULL && sect->rules == NULL)    sect = sect->next;  assert (sect != NULL);  ruleidx = 0;  do    {      struct section_list *osect = collate->sections;      while (osect != sect)	if (osect->rules != NULL	    && memcmp (osect->rules, sect->rules, nrules) == 0)	  break;	else	  osect = osect->next;      if (osect == sect)	sect->ruleidx = ruleidx++;      else	sect->ruleidx = osect->ruleidx;      /* Next section.  */      do	sect = sect->next;      while (sect != NULL && sect->rules == NULL);    }  while (sect != NULL);  /* We are currently not prepared for more than 256 rulesets.  But this     should never really be a problem.  */  assert (ruleidx <= 256);}