[thirdparty/glibc.git] / string / strcoll_l.c

/* Copyright (C) 1995-2024 Free Software Foundation, Inc.
   This file is part of the GNU C Library.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, see
   <https://www.gnu.org/licenses/>.  */


#include <assert.h>
#include <langinfo.h>
#include <locale.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include <sys/param.h>
#include <libc-diag.h>

#ifndef STRING_TYPE
# define STRING_TYPE char
# define USTRING_TYPE unsigned char
# define STRCOLL __strcoll_l
# define STRCMP strcmp
# define WEIGHT_H "../locale/weight.h"
# define SUFFIX	MB
# define L(arg) arg
#endif

#define CONCAT(a,b) CONCAT1(a,b)
#define CONCAT1(a,b) a##b

#include "../locale/localeinfo.h"
#include WEIGHT_H

/* Track status while looking for sequences in a string.  */
typedef struct
{
  int len;			/* Length of the current sequence.  */
  size_t val;			/* Position of the sequence relative to the
				   previous non-ignored sequence.  */
  size_t idxmax;		/* Maximum index in sequences.  */
  size_t idxcnt;		/* Current count of indices.  */
  size_t backw;			/* Current Backward sequence index.  */
  size_t backw_stop;		/* Index where the backward sequences stop.  */
  const USTRING_TYPE *us;	/* The string.  */
  unsigned char rule;		/* Saved rule for the first sequence.  */
  int32_t idx;			/* Index to weight of the current sequence.  */
  int32_t save_idx;		/* Save looked up index of a forward
				   sequence after the last backward
				   sequence.  */
  const USTRING_TYPE *back_us;	/* Beginning of the backward sequence.  */
} coll_seq;

/* Get next sequence.  Traverse the string as required.  */
static __always_inline void
get_next_seq (coll_seq *seq, int nrules, const unsigned char *rulesets,
	      const USTRING_TYPE *weights, const int32_t *table,
	      const USTRING_TYPE *extra, const int32_t *indirect,
	      int pass)
{
  size_t val = seq->val = 0;
  int len = seq->len;
  size_t backw_stop = seq->backw_stop;
  size_t backw = seq->backw;
  size_t idxcnt = seq->idxcnt;
  size_t idxmax = seq->idxmax;
  int32_t idx = seq->idx;
  const USTRING_TYPE *us = seq->us;

  while (len == 0)
    {
      ++val;
      if (backw_stop != ~0ul)
	{
	  /* There is something pushed.  */
	  if (backw == backw_stop)
	    {
	      /* The last pushed character was handled.  Continue
		 with forward characters.  */
	      if (idxcnt < idxmax)
		{
		  idx = seq->save_idx;
		  backw_stop = ~0ul;
		}
	      else
		{
		  /* Nothing anymore.  The backward sequence ended with
		     the last sequence in the string.  Note that len is
		     still zero.  */
		  idx = 0;
		  break;
	        }
	    }
	  else
	    {
	      /* XXX Traverse BACKW sequences from the beginning of
		 BACKW_STOP to get the next sequence.  Is there a quicker way
	         to do this?  */
	      size_t i = backw_stop;
	      us = seq->back_us;
	      while (i < backw)
		{
		  int32_t tmp = findidx (table, indirect, extra, &us, -1);
		  idx = tmp & 0xffffff;
		  i++;
		}
	      --backw;
	      us = seq->us;
	    }
	}
      else
	{
	  backw_stop = idxmax;
	  int32_t prev_idx = idx;

	  while (*us != L('\0'))
	    {
	      int32_t tmp = findidx (table, indirect, extra, &us, -1);
	      unsigned char rule = tmp >> 24;
	      prev_idx = idx;
	      idx = tmp & 0xffffff;
	      idxcnt = idxmax++;

	      /* Save the rule for the first sequence.  */
	      if (__glibc_unlikely (idxcnt == 0))
	        seq->rule = rule;

	      if ((rulesets[rule * nrules + pass]
		   & sort_backward) == 0)
		/* No more backward characters to push.  */
		break;
	      ++idxcnt;
	    }

	  if (backw_stop >= idxcnt)
	    {
	      /* No sequence at all or just one.  */
	      if (idxcnt == idxmax || backw_stop > idxcnt)
		/* Note that len is still zero.  */
		break;

	      backw_stop = ~0ul;
	    }
	  else
	    {
	      /* We pushed backward sequences.  If the stream ended with the
		 backward sequence, then we process the last sequence we
		 found.  Otherwise we process the sequence before the last
		 one since the last one was a forward sequence.  */
	      seq->back_us = seq->us;
	      seq->us = us;
	      backw = idxcnt;
	      if (idxmax > idxcnt)
		{
		  backw--;
		  seq->save_idx = idx;
		  idx = prev_idx;
		}
	      if (backw > backw_stop)
		backw--;
	    }
	}

      /* With GCC 5.3 when compiling with -Os the compiler complains
	 that idx, taken from seq->idx (seq1 or seq2 from STRCOLL) may
	 be used uninitialized.  In general this can't possibly be true
	 since seq1.idx and seq2.idx are initialized to zero in the
	 outer function.  Only one case where seq->idx is restored from
	 seq->save_idx might result in an uninitialized idx value, but
	 it is guarded by a sequence of checks against backw_stop which
	 ensures that seq->save_idx was saved to first and contains a
	 valid value.  */
      DIAG_PUSH_NEEDS_COMMENT;
      DIAG_IGNORE_Os_NEEDS_COMMENT (5, "-Wmaybe-uninitialized");
      len = weights[idx++];
      DIAG_POP_NEEDS_COMMENT;
      /* Skip over indices of previous levels.  */
      for (int i = 0; i < pass; i++)
	{
	  idx += len;
	  len = weights[idx];
	  idx++;
	}
    }

  /* Update the structure.  */
  seq->val = val;
  seq->len = len;
  seq->backw_stop = backw_stop;
  seq->backw = backw;
  seq->idxcnt = idxcnt;
  seq->idxmax = idxmax;
  seq->us = us;
  seq->idx = idx;
}

/* Compare two sequences.  */
static __always_inline int
do_compare (coll_seq *seq1, coll_seq *seq2, int position,
	    const USTRING_TYPE *weights)
{
  int seq1len = seq1->len;
  int seq2len = seq2->len;
  size_t val1 = seq1->val;
  size_t val2 = seq2->val;
  int idx1 = seq1->idx;
  int idx2 = seq2->idx;
  int result = 0;

  /* Test for position if necessary.  */
  if (position && val1 != val2)
    {
      result = val1 > val2 ? 1 : -1;
      goto out;
    }

  /* Compare the two sequences.  */
  do
    {
      if (weights[idx1] != weights[idx2])
	{
	  /* The sequences differ.  */
	  result = weights[idx1] - weights[idx2];
	  goto out;
	}

      /* Increment the offsets.  */
      ++idx1;
      ++idx2;

      --seq1len;
      --seq2len;
    }
  while (seq1len > 0 && seq2len > 0);

  if (position && seq1len != seq2len)
    result = seq1len - seq2len;

out:
  seq1->len = seq1len;
  seq2->len = seq2len;
  seq1->idx = idx1;
  seq2->idx = idx2;
  return result;
}

int
STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, locale_t l)
{
  struct __locale_data *current = l->__locales[LC_COLLATE];
  uint32_t nrules = current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;
  /* We don't assign the following values right away since it might be
     unnecessary in case there are no rules.  */
  const unsigned char *rulesets;
  const int32_t *table;
  const USTRING_TYPE *weights;
  const USTRING_TYPE *extra;
  const int32_t *indirect;

  if (nrules == 0)
    return STRCMP (s1, s2);

  /* Catch empty strings.  */
  if (__glibc_unlikely (*s1 == '\0') || __glibc_unlikely (*s2 == '\0'))
    return (*s1 != '\0') - (*s2 != '\0');

  rulesets = (const unsigned char *)
    current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
  table = (const int32_t *)
    current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
  weights = (const USTRING_TYPE *)
    current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
  extra = (const USTRING_TYPE *)
    current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
  indirect = (const int32_t *)
    current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;

  assert (((uintptr_t) table) % __alignof__ (table[0]) == 0);
  assert (((uintptr_t) weights) % __alignof__ (weights[0]) == 0);
  assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
  assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);

  int result = 0, rule = 0;

  /* With GCC 7 when compiling with -Os the compiler warns that
     seq1.back_us and seq2.back_us might be used uninitialized.
     Sometimes this warning appears at locations in locale/weightwc.h
     where the actual use is, but on architectures other than x86_64,
     x86 and s390x, a warning appears at the definitions of seq1 and
     seq2.  This uninitialized use is impossible for the same reason
     as described in comments in locale/weightwc.h.  */
  DIAG_PUSH_NEEDS_COMMENT;
  DIAG_IGNORE_Os_NEEDS_COMMENT (7, "-Wmaybe-uninitialized");
  coll_seq seq1, seq2;
  DIAG_POP_NEEDS_COMMENT;
  seq1.len = 0;
  seq1.idxmax = 0;
  seq1.rule = 0;
  seq2.len = 0;
  seq2.idxmax = 0;

  for (int pass = 0; pass < nrules; ++pass)
    {
      seq1.idxcnt = 0;
      seq1.idx = 0;
      seq2.idx = 0;
      seq1.backw_stop = ~0ul;
      seq1.backw = ~0ul;
      seq2.idxcnt = 0;
      seq2.backw_stop = ~0ul;
      seq2.backw = ~0ul;

      /* We need the elements of the strings as unsigned values since they
	 are used as indices.  */
      seq1.us = (const USTRING_TYPE *) s1;
      seq2.us = (const USTRING_TYPE *) s2;

      /* We assume that if a rule has defined `position' in one section
	 this is true for all of them.  Please note that the localedef programs
	 makes sure that `position' is not used at the first level.  */

      int position = rulesets[rule * nrules + pass] & sort_position;

      while (1)
	{
	  get_next_seq (&seq1, nrules, rulesets, weights, table,
				    extra, indirect, pass);
	  get_next_seq (&seq2, nrules, rulesets, weights, table,
				    extra, indirect, pass);
	  /* See whether any or both strings are empty.  */
	  if (seq1.len == 0 || seq2.len == 0)
	    {
	      if (seq1.len == seq2.len)
		{
		  /* Both strings ended and are equal at this level.  Do a
		     byte-level comparison to ensure that we don't waste time
		     going through multiple passes for totally equal strings
		     before proceeding to subsequent passes.  */
		  if (pass == 0 && STRCMP (s1, s2) == 0)
		    return result;
		  else
		    break;
	        }

	      /* This means one string is shorter than the other.  Find out
		 which one and return an appropriate value.  */
	      return seq1.len == 0 ? -1 : 1;
	    }

	  result = do_compare (&seq1, &seq2, position, weights);
	  if (result != 0)
	    return result;
	}

      rule = seq1.rule;
    }

  return result;
}
libc_hidden_def (STRCOLL)

#ifndef WIDE_CHAR_VERSION
weak_alias (__strcoll_l, strcoll_l)
#endif
Commit	Line	Data
dff8da6b	1	/* Copyright (C) 1995-2024 Free Software Foundation, Inc.
c84142e8	2	This file is part of the GNU C Library.
c84142e8 UD	3
c84142e8 UD	4	The GNU C Library is free software; you can redistribute it and/or
41bdb6e2 AJ	5	modify it under the terms of the GNU Lesser General Public
	6	License as published by the Free Software Foundation; either
	7	version 2.1 of the License, or (at your option) any later version.
c84142e8 UD	8
	9	The GNU C Library is distributed in the hope that it will be useful,
	10	but WITHOUT ANY WARRANTY; without even the implied warranty of
	11	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
41bdb6e2	12	Lesser General Public License for more details.
c84142e8	13
41bdb6e2	14	You should have received a copy of the GNU Lesser General Public
59ba27a6	15	License along with the GNU C Library; if not, see
5a82c748	16	<https://www.gnu.org/licenses/>. */
c84142e8	17
1ab62b32	18
ccadf7b5 UD	19	#include <assert.h>
	20	#include <langinfo.h>
	21	#include <locale.h>
	22	#include <stddef.h>
	23	#include <stdint.h>
ccadf7b5	24	#include <string.h>
43d5c02c	25	#include <sys/param.h>
f54d8f73	26	#include <libc-diag.h>
ccadf7b5 UD	27
	28	#ifndef STRING_TYPE
	29	# define STRING_TYPE char
	30	# define USTRING_TYPE unsigned char
	31	# define STRCOLL __strcoll_l
	32	# define STRCMP strcmp
ccadf7b5 UD	33	# define WEIGHT_H "../locale/weight.h"
	34	# define SUFFIX MB
	35	# define L(arg) arg
	36	#endif
	37
	38	#define CONCAT(a,b) CONCAT1(a,b)
	39	#define CONCAT1(a,b) a##b
	40
	41	#include "../locale/localeinfo.h"
8c0ab919	42	#include WEIGHT_H
ccadf7b5	43
1326ba1a SP	44	/* Track status while looking for sequences in a string. */
	45	typedef struct
	46	{
	47	int len; /* Length of the current sequence. */
141f3a77	48	size_t val; /* Position of the sequence relative to the
1326ba1a	49	previous non-ignored sequence. */
1326ba1a SP	50	size_t idxmax; /* Maximum index in sequences. */
	51	size_t idxcnt; /* Current count of indices. */
	52	size_t backw; /* Current Backward sequence index. */
	53	size_t backw_stop; /* Index where the backward sequences stop. */
	54	const USTRING_TYPE us; / The string. */
141f3a77 SP	55	unsigned char rule; /* Saved rule for the first sequence. */
	56	int32_t idx; /* Index to weight of the current sequence. */
	57	int32_t save_idx; /* Save looked up index of a forward
	58	sequence after the last backward
	59	sequence. */
	60	const USTRING_TYPE back_us; / Beginning of the backward sequence. */
1326ba1a SP	61	} coll_seq;
1326ba1a SP	62
1326ba1a	63	/* Get next sequence. Traverse the string as required. */
5d178c37	64	static __always_inline void
1326ba1a	65	get_next_seq (coll_seq seq, int nrules, const unsigned char rulesets,
33cc770b SP	66	const USTRING_TYPE weights, const int32_t table,
	67	const USTRING_TYPE extra, const int32_t indirect,
	68	int pass)
141f3a77	69	{
141f3a77 SP	70	size_t val = seq->val = 0;
	71	int len = seq->len;
	72	size_t backw_stop = seq->backw_stop;
	73	size_t backw = seq->backw;
	74	size_t idxcnt = seq->idxcnt;
	75	size_t idxmax = seq->idxmax;
	76	int32_t idx = seq->idx;
	77	const USTRING_TYPE *us = seq->us;
	78
	79	while (len == 0)
	80	{
	81	++val;
	82	if (backw_stop != ~0ul)
	83	{
	84	/* There is something pushed. */
	85	if (backw == backw_stop)
	86	{
	87	/* The last pushed character was handled. Continue
	88	with forward characters. */
	89	if (idxcnt < idxmax)
	90	{
	91	idx = seq->save_idx;
	92	backw_stop = ~0ul;
	93	}
	94	else
	95	{
	96	/* Nothing anymore. The backward sequence ended with
	97	the last sequence in the string. Note that len is
	98	still zero. */
	99	idx = 0;
	100	break;
	101	}
	102	}
	103	else
	104	{
	105	/* XXX Traverse BACKW sequences from the beginning of
7f0d9e61	106	BACKW_STOP to get the next sequence. Is there a quicker way
141f3a77 SP	107	to do this? */
	108	size_t i = backw_stop;
	109	us = seq->back_us;
	110	while (i < backw)
	111	{
8c0ab919	112	int32_t tmp = findidx (table, indirect, extra, &us, -1);
141f3a77 SP	113	idx = tmp & 0xffffff;
	114	i++;
	115	}
	116	--backw;
	117	us = seq->us;
	118	}
	119	}
	120	else
	121	{
	122	backw_stop = idxmax;
	123	int32_t prev_idx = idx;
	124
	125	while (*us != L('\0'))
	126	{
8c0ab919	127	int32_t tmp = findidx (table, indirect, extra, &us, -1);
141f3a77 SP	128	unsigned char rule = tmp >> 24;
	129	prev_idx = idx;
	130	idx = tmp & 0xffffff;
	131	idxcnt = idxmax++;
	132
	133	/* Save the rule for the first sequence. */
	134	if (__glibc_unlikely (idxcnt == 0))
	135	seq->rule = rule;
	136
	137	if ((rulesets[rule * nrules + pass]
	138	& sort_backward) == 0)
	139	/* No more backward characters to push. */
	140	break;
	141	++idxcnt;
	142	}
	143
	144	if (backw_stop >= idxcnt)
	145	{
	146	/* No sequence at all or just one. */
	147	if (idxcnt == idxmax \|\| backw_stop > idxcnt)
	148	/* Note that len is still zero. */
	149	break;
	150
	151	backw_stop = ~0ul;
	152	}
	153	else
	154	{
	155	/* We pushed backward sequences. If the stream ended with the
	156	backward sequence, then we process the last sequence we
	157	found. Otherwise we process the sequence before the last
	158	one since the last one was a forward sequence. */
	159	seq->back_us = seq->us;
	160	seq->us = us;
	161	backw = idxcnt;
	162	if (idxmax > idxcnt)
	163	{
	164	backw--;
	165	seq->save_idx = idx;
	166	idx = prev_idx;
	167	}
	168	if (backw > backw_stop)
	169	backw--;
	170	}
	171	}
	172
93fe09cb CD	173	/* With GCC 5.3 when compiling with -Os the compiler complains
	174	that idx, taken from seq->idx (seq1 or seq2 from STRCOLL) may
	175	be used uninitialized. In general this can't possibly be true
	176	since seq1.idx and seq2.idx are initialized to zero in the
	177	outer function. Only one case where seq->idx is restored from
	178	seq->save_idx might result in an uninitialized idx value, but
	179	it is guarded by a sequence of checks against backw_stop which
	180	ensures that seq->save_idx was saved to first and contains a
	181	valid value. */
	182	DIAG_PUSH_NEEDS_COMMENT;
	183	DIAG_IGNORE_Os_NEEDS_COMMENT (5, "-Wmaybe-uninitialized");
141f3a77	184	len = weights[idx++];
93fe09cb	185	DIAG_POP_NEEDS_COMMENT;
141f3a77 SP	186	/* Skip over indices of previous levels. */
	187	for (int i = 0; i < pass; i++)
	188	{
	189	idx += len;
	190	len = weights[idx];
	191	idx++;
	192	}
	193	}
	194
	195	/* Update the structure. */
	196	seq->val = val;
	197	seq->len = len;
	198	seq->backw_stop = backw_stop;
	199	seq->backw = backw;
	200	seq->idxcnt = idxcnt;
	201	seq->idxmax = idxmax;
	202	seq->us = us;
	203	seq->idx = idx;
	204	}
	205
0742aef6	206	/* Compare two sequences. */
5d178c37	207	static __always_inline int
0742aef6	208	do_compare (coll_seq seq1, coll_seq seq2, int position,
33cc770b	209	const USTRING_TYPE *weights)
141f3a77 SP	210	{
	211	int seq1len = seq1->len;
	212	int seq2len = seq2->len;
	213	size_t val1 = seq1->val;
	214	size_t val2 = seq2->val;
	215	int idx1 = seq1->idx;
	216	int idx2 = seq2->idx;
	217	int result = 0;
	218
	219	/* Test for position if necessary. */
	220	if (position && val1 != val2)
	221	{
	222	result = val1 > val2 ? 1 : -1;
	223	goto out;
	224	}
	225
	226	/* Compare the two sequences. */
	227	do
	228	{
	229	if (weights[idx1] != weights[idx2])
	230	{
	231	/* The sequences differ. */
	232	result = weights[idx1] - weights[idx2];
	233	goto out;
	234	}
	235
	236	/* Increment the offsets. */
	237	++idx1;
	238	++idx2;
	239
	240	--seq1len;
	241	--seq2len;
	242	}
	243	while (seq1len > 0 && seq2len > 0);
	244
	245	if (position && seq1len != seq2len)
	246	result = seq1len - seq2len;
	247
	248	out:
	249	seq1->len = seq1len;
	250	seq2->len = seq2len;
	251	seq1->idx = idx1;
	252	seq2->idx = idx2;
	253	return result;
	254	}
	255
ccadf7b5	256	int
af85385f	257	STRCOLL (const STRING_TYPE s1, const STRING_TYPE s2, locale_t l)
ccadf7b5	258	{
f095bb72	259	struct __locale_data *current = l->__locales[LC_COLLATE];
535e935a	260	uint32_t nrules = current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;
ccadf7b5 UD	261	/* We don't assign the following values right away since it might be
	262	unnecessary in case there are no rules. */
	263	const unsigned char *rulesets;
	264	const int32_t *table;
	265	const USTRING_TYPE *weights;
	266	const USTRING_TYPE *extra;
	267	const int32_t *indirect;
ccadf7b5 UD	268
	269	if (nrules == 0)
	270	return STRCMP (s1, s2);
	271
0742aef6 LH	272	/* Catch empty strings. */
	273	if (__glibc_unlikely (s1 == '\0') \|\| __glibc_unlikely (s2 == '\0'))
	274	return (s1 != '\0') - (s2 != '\0');
	275
ccadf7b5 UD	276	rulesets = (const unsigned char *)
	277	current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
	278	table = (const int32_t *)
	279	current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
	280	weights = (const USTRING_TYPE *)
	281	current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
	282	extra = (const USTRING_TYPE *)
	283	current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
	284	indirect = (const int32_t *)
	285	current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
ccadf7b5 UD	286
	287	assert (((uintptr_t) table) % __alignof__ (table[0]) == 0);
	288	assert (((uintptr_t) weights) % __alignof__ (weights[0]) == 0);
	289	assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
	290	assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
	291
0742aef6	292	int result = 0, rule = 0;
1326ba1a	293
f54d8f73 JM	294	/* With GCC 7 when compiling with -Os the compiler warns that
	295	seq1.back_us and seq2.back_us might be used uninitialized.
	296	Sometimes this warning appears at locations in locale/weightwc.h
	297	where the actual use is, but on architectures other than x86_64,
	298	x86 and s390x, a warning appears at the definitions of seq1 and
	299	seq2. This uninitialized use is impossible for the same reason
	300	as described in comments in locale/weightwc.h. */
	301	DIAG_PUSH_NEEDS_COMMENT;
	302	DIAG_IGNORE_Os_NEEDS_COMMENT (7, "-Wmaybe-uninitialized");
1326ba1a	303	coll_seq seq1, seq2;
f54d8f73	304	DIAG_POP_NEEDS_COMMENT;
ef635a29 LH	305	seq1.len = 0;
	306	seq1.idxmax = 0;
	307	seq1.rule = 0;
	308	seq2.len = 0;
	309	seq2.idxmax = 0;
1326ba1a	310
1326ba1a	311	for (int pass = 0; pass < nrules; ++pass)
ccadf7b5	312	{
1326ba1a	313	seq1.idxcnt = 0;
141f3a77 SP	314	seq1.idx = 0;
141f3a77 SP	315	seq2.idx = 0;
1326ba1a SP	316	seq1.backw_stop = ~0ul;
	317	seq1.backw = ~0ul;
	318	seq2.idxcnt = 0;
	319	seq2.backw_stop = ~0ul;
	320	seq2.backw = ~0ul;
	321
141f3a77 SP	322	/* We need the elements of the strings as unsigned values since they
	323	are used as indices. */
	324	seq1.us = (const USTRING_TYPE *) s1;
	325	seq2.us = (const USTRING_TYPE *) s2;
	326
ccadf7b5	327	/* We assume that if a rule has defined `position' in one section
0742aef6 LH	328	this is true for all of them. Please note that the localedef programs
	329	makes sure that `position' is not used at the first level. */
	330
141f3a77	331	int position = rulesets[rule * nrules + pass] & sort_position;
ccadf7b5 UD	332
	333	while (1)
	334	{
0742aef6	335	get_next_seq (&seq1, nrules, rulesets, weights, table,
141f3a77	336	extra, indirect, pass);
0742aef6	337	get_next_seq (&seq2, nrules, rulesets, weights, table,
141f3a77	338	extra, indirect, pass);
ccadf7b5	339	/* See whether any or both strings are empty. */
1326ba1a	340	if (seq1.len == 0 \|\| seq2.len == 0)
ccadf7b5	341	{
1326ba1a	342	if (seq1.len == seq2.len)
0742aef6 LH	343	{
	344	/* Both strings ended and are equal at this level. Do a
	345	byte-level comparison to ensure that we don't waste time
	346	going through multiple passes for totally equal strings
	347	before proceeding to subsequent passes. */
87701a58	348	if (pass == 0 && STRCMP (s1, s2) == 0)
0742aef6 LH	349	return result;
	350	else
	351	break;
	352	}
ccadf7b5 UD	353
	354	/* This means one string is shorter than the other. Find out
	355	which one and return an appropriate value. */
0742aef6	356	return seq1.len == 0 ? -1 : 1;
ccadf7b5 UD	357	}
ccadf7b5 UD	358
0742aef6	359	result = do_compare (&seq1, &seq2, position, weights);
1326ba1a	360	if (result != 0)
0742aef6	361	return result;
ccadf7b5	362	}
141f3a77	363
0742aef6	364	rule = seq1.rule;
ccadf7b5 UD	365	}
ccadf7b5 UD	366
ccadf7b5 UD	367	return result;
	368	}
	369	libc_hidden_def (STRCOLL)
	370
	371	#ifndef WIDE_CHAR_VERSION
1ab62b32	372	weak_alias (__strcoll_l, strcoll_l)
ccadf7b5	373	#endif