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

/* Copyright (C) 1995, 1996, 1997, 1998, 1999 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public License as
   published by the Free Software Foundation; either version 2 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
   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public
   License along with the GNU C Library; see the file COPYING.LIB.  If not,
   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.  */

#include <endian.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#ifndef STRING_TYPE
# define STRING_TYPE char
# define USTRING_TYPE unsigned char
# ifdef USE_IN_EXTENDED_LOCALE_MODEL
#  define STRCOLL __strcoll_l
# else
#  define STRCOLL strcoll
# endif
# define STRCMP strcmp
#endif

#ifndef USE_IN_EXTENDED_LOCALE_MODEL
int
STRCOLL (s1, s2)
     const STRING_TYPE *s1;
     const STRING_TYPE *s2;
#else
int
STRCOLL (s1, s2, l)
     const STRING_TYPE *s1;
     const STRING_TYPE *s2;
     __locale_t l;
#endif
{
  return STRCMP (s1, s2);
}

#if 0
/* Include the shared helper functions.  `strxfrm'/`wcsxfrm' also use
   these functions.  */
#include "../locale/weight.h"


/* Compare S1 and S2, returning less than, equal to or
   greater than zero if the collated form of S1 is lexicographically
   less than, equal to or greater than the collated form of S2.  */
#ifndef USE_IN_EXTENDED_LOCALE_MODEL
int
STRCOLL (s1, s2)
     const STRING_TYPE *s1;
     const STRING_TYPE *s2;
#else
int
STRCOLL (s1, s2, l)
     const STRING_TYPE *s1;
     const STRING_TYPE *s2;
     __locale_t l;
#endif
{
#ifdef USE_IN_EXTENDED_LOCALE_MODEL
  struct locale_data *current = l->__locales[LC_COLLATE];
# if BYTE_ORDER == BIG_ENDIAN
  const uint32_t *collate_table = (const uint32_t *)
    current->values[_NL_ITEM_INDEX (_NL_COLLATE_TABLE_EB)].string;
  const uint32_t *collate_extra = (const uint32_t *)
    current->values[_NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EB)].string;
# elif BYTE_ORDER == LITTLE_ENDIAN
  const uint32_t *collate_table = (const uint32_t *)
    current->values[_NL_ITEM_INDEX (_NL_COLLATE_TABLE_EL)].string;
  const uint32_t *collate_extra = (const uint32_t *)
    current->values[_NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EL)].string;
# else
#  error bizarre byte order
# endif
#endif
  weight_t *s1forw = NULL;
  weight_t *s1backw = NULL;
  weight_t *s2forw = NULL;
  weight_t *s2backw = NULL;
  size_t pass;

  /* If the current locale does not specify locale data we use normal
     8-bit string comparison.  */
  if (collate_nrules == 0)
    return STRCMP (s1, s2);

  /* Handle empty strings as a special case.  */
  if (*s1 == '\0')
    return *s2 == '\0' ? 0 : -1;
  else if (*s2 == '\0')
    return 1;

  /* Get full information about the strings.  This means we get
     information for all passes in a special data structure.  */
  get_string (s1, s1forw, s1backw);
  get_string (s2, s2forw, s2backw);

  /* Now we have all the information.  In at most the given number of
     passes we can finally decide about the order.  */
  for (pass = 0; pass < collate_nrules; ++pass)
    {
      int forward = (collate_rules[pass] & sort_forward) != 0;
      const weight_t *s1run = forward ? s1forw : s1backw;
      const weight_t *s2run = forward ? s2forw : s2backw;
      int s1idx = forward ? 0 : s1run->data[pass].number - 1;
      int s2idx = forward ? 0 : s2run->data[pass].number - 1;

      while (1)
	{
	  int s1ignore = 0;
	  int s2ignore = 0;
	  uint32_t w1 = 0;
	  uint32_t w2 = 0;

	  /* Here we have to check for IGNORE entries.  If these are
	     found we count them and go on with the next value.  */
	  while (s1run != NULL
		 && ((w1 = s1run->data[pass].value[s1idx])
		     == (uint32_t) IGNORE_CHAR))
	    {
	      ++s1ignore;
	      if (forward
		  ? ++s1idx >= s1run->data[pass].number
		  : --s1idx < 0)
		{
		  weight_t *nextp = forward ? s1run->next : s1run->prev;
		  if (nextp == NULL)
		    {
		      w1 = 0;
		      /* No more non-INGOREd elements means lowest
			 possible value.  */
		      s1ignore = -1;
		    }
		  else
		    s1idx = forward ? 0 : nextp->data[pass].number - 1;
		  s1run = nextp;
		}
	    }

	  while (s2run != NULL
		 && ((w2 = s2run->data[pass].value[s2idx])
		     == (uint32_t) IGNORE_CHAR))
	    {
	      ++s2ignore;
	      if (forward
		  ? ++s2idx >= s2run->data[pass].number
		  : --s2idx < 0)
		{
		  weight_t *nextp = forward ? s2run->next : s2run->prev;
		  if (nextp == NULL)
		    {
		      w2 = 0;
		      /* No more non-INGOREd elements means lowest
			 possible value.  */
		      s2ignore = -1;
		    }
		  else
		    s2idx = forward ? 0 : nextp->data[pass].number - 1;
		  s2run = nextp;
		}
	    }

	  /* If one string is completely processed stop.  */
	  if (s1run == NULL || s2run == NULL)
	    break;

	  /* Now we have information of the number of ignored
	     weights and the value of the next weight.  */
	  if ((collate_rules[pass] & sort_position) != 0
	      && s1ignore != s2ignore && (w1 != 0 || w2 != 0))
	    return s1ignore < s2ignore ? -1 : 1;

	  if (w1 != w2)
	    return w1 < w2 ? -1 : 1;

	  /* We have to increment the index counters.  */
	  if (forward)
	    {
	      if (++s1idx >= s1run->data[pass].number)
		{
		  s1run = s1run->next;
		  s1idx = 0;
		}
	      if (++s2idx >= s2run->data[pass].number)
		{
		  s2run = s2run->next;
		  s2idx = 0;
		}
	    }
	  else
	    {
	      if (--s1idx < 0)
		{
		  s1run = s1run->prev;
		  if (s1run != NULL)
		    s1idx = s1run->data[pass].number - 1;
		}
	      if (--s2idx < 0)
		{
		  s2run = s2run->prev;
		  if (s2run != NULL)
		    s2idx = s2run->data[pass].number - 1;
		}
	    }
	}

      if (s1run != s2run)
	return s1run != NULL ? 1 : -1;
    }

  return 0;
}
#endif
Commit	Line	Data
4b10dd6c	1	/* Copyright (C) 1995, 1996, 1997, 1998, 1999 Free Software Foundation, Inc.
c84142e8 UD	2	This file is part of the GNU C Library.
c84142e8 UD	3	Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.
28f540f4	4
c84142e8 UD	5	The GNU C Library is free software; you can redistribute it and/or
	6	modify it under the terms of the GNU Library General Public License as
	7	published by the Free Software Foundation; either version 2 of the
	8	License, or (at your option) any later version.
28f540f4	9
c84142e8 UD	10	The GNU C Library is distributed in the hope that it will be useful,
	11	but WITHOUT ANY WARRANTY; without even the implied warranty of
	12	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	13	Library General Public License for more details.
28f540f4	14
c84142e8 UD	15	You should have received a copy of the GNU Library General Public
	16	License along with the GNU C Library; see the file COPYING.LIB. If not,
	17	write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
	18	Boston, MA 02111-1307, USA. */
28f540f4	19
c84142e8	20	#include <endian.h>
28f540f4	21	#include <stddef.h>
0d4acd0f	22	#include <stdint.h>
28f540f4 RM	23	#include <stdlib.h>
28f540f4 RM	24	#include <string.h>
19bc17a9 RM	25
	26	#ifndef STRING_TYPE
	27	# define STRING_TYPE char
	28	# define USTRING_TYPE unsigned char
c84142e8 UD	29	# ifdef USE_IN_EXTENDED_LOCALE_MODEL
	30	# define STRCOLL __strcoll_l
	31	# else
	32	# define STRCOLL strcoll
	33	# endif
75cd5204	34	# define STRCMP strcmp
19bc17a9 RM	35	#endif
19bc17a9 RM	36
4b10dd6c UD	37	#ifndef USE_IN_EXTENDED_LOCALE_MODEL
	38	int
	39	STRCOLL (s1, s2)
	40	const STRING_TYPE *s1;
	41	const STRING_TYPE *s2;
	42	#else
	43	int
	44	STRCOLL (s1, s2, l)
	45	const STRING_TYPE *s1;
	46	const STRING_TYPE *s2;
	47	__locale_t l;
	48	#endif
	49	{
	50	return STRCMP (s1, s2);
	51	}
	52
	53	#if 0
19bc17a9 RM	54	/* Include the shared helper functions. `strxfrm'/`wcsxfrm' also use
19bc17a9 RM	55	these functions. */
0393dfd6	56	#include "../locale/weight.h"
28f540f4 RM	57
	58
	59	/* Compare S1 and S2, returning less than, equal to or
19bc17a9	60	greater than zero if the collated form of S1 is lexicographically
28f540f4	61	less than, equal to or greater than the collated form of S2. */
c84142e8	62	#ifndef USE_IN_EXTENDED_LOCALE_MODEL
28f540f4	63	int
19bc17a9 RM	64	STRCOLL (s1, s2)
	65	const STRING_TYPE *s1;
	66	const STRING_TYPE *s2;
c84142e8 UD	67	#else
	68	int
	69	STRCOLL (s1, s2, l)
	70	const STRING_TYPE *s1;
	71	const STRING_TYPE *s2;
	72	__locale_t l;
	73	#endif
28f540f4	74	{
c84142e8 UD	75	#ifdef USE_IN_EXTENDED_LOCALE_MODEL
	76	struct locale_data *current = l->__locales[LC_COLLATE];
	77	# if BYTE_ORDER == BIG_ENDIAN
0d4acd0f	78	const uint32_t collate_table = (const uint32_t )
c84142e8	79	current->values[_NL_ITEM_INDEX (_NL_COLLATE_TABLE_EB)].string;
0d4acd0f	80	const uint32_t collate_extra = (const uint32_t )
c84142e8 UD	81	current->values[_NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EB)].string;
c84142e8 UD	82	# elif BYTE_ORDER == LITTLE_ENDIAN
0d4acd0f	83	const uint32_t collate_table = (const uint32_t )
c84142e8	84	current->values[_NL_ITEM_INDEX (_NL_COLLATE_TABLE_EL)].string;
0d4acd0f	85	const uint32_t collate_extra = (const uint32_t )
c84142e8 UD	86	current->values[_NL_ITEM_INDEX (_NL_COLLATE_EXTRA_EL)].string;
	87	# else
	88	# error bizarre byte order
	89	# endif
	90	#endif
19bc17a9 RM	91	weight_t *s1forw = NULL;
	92	weight_t *s1backw = NULL;
	93	weight_t *s2forw = NULL;
	94	weight_t *s2backw = NULL;
	95	size_t pass;
	96
	97	/* If the current locale does not specify locale data we use normal
	98	8-bit string comparison. */
	99	if (collate_nrules == 0)
75cd5204	100	return STRCMP (s1, s2);
19bc17a9	101
a7ab2023 UD	102	/* Handle empty strings as a special case. */
	103	if (*s1 == '\0')
	104	return *s2 == '\0' ? 0 : -1;
	105	else if (*s2 == '\0')
	106	return 1;
	107
19bc17a9 RM	108	/* Get full information about the strings. This means we get
	109	information for all passes in a special data structure. */
	110	get_string (s1, s1forw, s1backw);
	111	get_string (s2, s2forw, s2backw);
	112
	113	/* Now we have all the information. In at most the given number of
	114	passes we can finally decide about the order. */
	115	for (pass = 0; pass < collate_nrules; ++pass)
	116	{
	117	int forward = (collate_rules[pass] & sort_forward) != 0;
	118	const weight_t *s1run = forward ? s1forw : s1backw;
	119	const weight_t *s2run = forward ? s2forw : s2backw;
	120	int s1idx = forward ? 0 : s1run->data[pass].number - 1;
	121	int s2idx = forward ? 0 : s2run->data[pass].number - 1;
	122
5a97622d	123	while (1)
19bc17a9 RM	124	{
	125	int s1ignore = 0;
	126	int s2ignore = 0;
0d4acd0f UD	127	uint32_t w1 = 0;
0d4acd0f UD	128	uint32_t w2 = 0;
19bc17a9 RM	129
19bc17a9 RM	130	/* Here we have to check for IGNORE entries. If these are
e4cf5070	131	found we count them and go on with the next value. */
5a97622d UD	132	while (s1run != NULL
5a97622d UD	133	&& ((w1 = s1run->data[pass].value[s1idx])
0d4acd0f	134	== (uint32_t) IGNORE_CHAR))
19bc17a9 RM	135	{
19bc17a9 RM	136	++s1ignore;
6e4c40ba UD	137	if (forward
	138	? ++s1idx >= s1run->data[pass].number
	139	: --s1idx < 0)
19bc17a9 RM	140	{
	141	weight_t *nextp = forward ? s1run->next : s1run->prev;
	142	if (nextp == NULL)
	143	{
	144	w1 = 0;
5a97622d UD	145	/* No more non-INGOREd elements means lowest
	146	possible value. */
	147	s1ignore = -1;
19bc17a9	148	}
5a97622d UD	149	else
5a97622d UD	150	s1idx = forward ? 0 : nextp->data[pass].number - 1;
19bc17a9	151	s1run = nextp;
19bc17a9 RM	152	}
	153	}
	154
5a97622d UD	155	while (s2run != NULL
5a97622d UD	156	&& ((w2 = s2run->data[pass].value[s2idx])
0d4acd0f	157	== (uint32_t) IGNORE_CHAR))
19bc17a9 RM	158	{
19bc17a9 RM	159	++s2ignore;
6e4c40ba UD	160	if (forward
	161	? ++s2idx >= s2run->data[pass].number
	162	: --s2idx < 0)
19bc17a9 RM	163	{
	164	weight_t *nextp = forward ? s2run->next : s2run->prev;
	165	if (nextp == NULL)
	166	{
	167	w2 = 0;
5a97622d UD	168	/* No more non-INGOREd elements means lowest
	169	possible value. */
	170	s2ignore = -1;
19bc17a9	171	}
5a97622d UD	172	else
5a97622d UD	173	s2idx = forward ? 0 : nextp->data[pass].number - 1;
19bc17a9	174	s2run = nextp;
19bc17a9 RM	175	}
	176	}
	177
5a97622d UD	178	/* If one string is completely processed stop. */
	179	if (s1run == NULL \|\| s2run == NULL)
	180	break;
	181
19bc17a9 RM	182	/* Now we have information of the number of ignored
	183	weights and the value of the next weight. */
	184	if ((collate_rules[pass] & sort_position) != 0
	185	&& s1ignore != s2ignore && (w1 != 0 \|\| w2 != 0))
	186	return s1ignore < s2ignore ? -1 : 1;
	187
	188	if (w1 != w2)
	189	return w1 < w2 ? -1 : 1;
	190
	191	/* We have to increment the index counters. */
04795ad9	192	if (forward)
94b78bb2	193	{
04795ad9	194	if (++s1idx >= s1run->data[pass].number)
94b78bb2 UD	195	{
	196	s1run = s1run->next;
	197	s1idx = 0;
	198	}
04795ad9	199	if (++s2idx >= s2run->data[pass].number)
94b78bb2	200	{
04795ad9 UD	201	s2run = s2run->next;
04795ad9 UD	202	s2idx = 0;
94b78bb2 UD	203	}
94b78bb2 UD	204	}
04795ad9	205	else
94b78bb2	206	{
04795ad9	207	if (--s1idx < 0)
94b78bb2	208	{
04795ad9 UD	209	s1run = s1run->prev;
	210	if (s1run != NULL)
	211	s1idx = s1run->data[pass].number - 1;
94b78bb2	212	}
04795ad9	213	if (--s2idx < 0)
94b78bb2 UD	214	{
	215	s2run = s2run->prev;
	216	if (s2run != NULL)
	217	s2idx = s2run->data[pass].number - 1;
	218	}
	219	}
19bc17a9	220	}
19bc17a9 RM	221
	222	if (s1run != s2run)
	223	return s1run != NULL ? 1 : -1;
	224	}
	225
	226	return 0;
28f540f4	227	}
4b10dd6c	228	#endif