collate.c revision bc09504ff1ed70f84c9713b732281f14a9ef49b2
/*
* Copyright 2014 Garrett D'Amore <garrett@damore.org>
* Copyright 2010 Nexenta Systems, Inc. All rights reserved.
* Copyright (c) 1995 Alex Tatmanjants <alex@elvisti.kiev.ua>
* at Electronni Visti IA, Kiev, Ukraine.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#include "lint.h"
#include "file64.h"
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>
#include <wchar.h>
#include <errno.h>
#include <unistd.h>
#include <ctype.h>
#include <unistd.h>
#include <fcntl.h>
#include <assert.h>
#include "collate.h"
#include "localeimpl.h"
/* Check file format vs libc runtime. (See collatefile.h) */
#error "COLL_WEIGHTS_MAX != COLLATE_WEIGHTS_MAX"
#endif
/*
* information. It would also be very helpful to have a copy of the
* POSIX standard for collation (in the locale format manual page)
* handy (www.opengroup.org).
*/
/*
* POSIX uses empty tables and falls down to strcmp.
*/
struct lc_collate lc_collate_posix = {
.lc_is_posix = 1,
};
struct locdata __posix_collate_locdata = {
.l_lname = "C",
.l_data = { &lc_collate_posix }
};
struct locdata *
__lc_collate_load(const char *locname)
{
int i, chains, z;
char *TMP;
char *map;
int fd;
struct lc_collate *lcc;
/*
* Slurp the locale file into the cache.
*/
return (NULL);
}
return (NULL);
}
return (NULL);
}
return (NULL);
}
return (NULL);
}
TMP += COLLATE_STR_LEN;
return (NULL);
}
(sizeof (collate_chain_t) * chains) +
for (z = 0; z < info->directive_count; z++) {
}
return (NULL);
}
return (NULL);
}
for (z = 0; z < COLL_WEIGHTS_MAX; z++) {
}
for (z = 0; z < lcc->lc_directive_count; z++) {
int count;
} else {
}
}
if (chains > 0) {
} else
if (lcc->lc_large_count > 0)
else
return (ldata);
}
static const int32_t *
{
const collate_subst_t *p;
if (n == 0)
return (NULL);
return (NULL);
if (!(key & COLLATE_SUBST_PRIORITY))
return (NULL);
return (p->pri);
}
/*
* Note: for performance reasons, we have expanded bsearch here. This avoids
* function call overhead with each comparison.
*/
static collate_chain_t *
{
int low;
int high;
collate_chain_t *p;
return (NULL);
low = 0;
if (compar == 0) {
if (compar == 0) {
*len = l;
return (p);
}
}
if (compar > 0)
else
}
return (NULL);
}
static collate_large_t *
{
int low = 0;
collate_large_t *p;
return (NULL);
if (compar == 0)
return (p);
if (compar > 0)
else
}
return (NULL);
}
void
{
int p, l;
const int *sptr;
/*
* If this is the "last" pass for the UNDEFINED, then
* we just return the priority itself.
*/
*pri = *t;
*len = 1;
return;
}
/*
* If we have remaining substitution data from a previous
* call, consume it first.
*/
sptr++;
*len = 0;
return;
}
/* No active substitutions */
*len = 1;
/*
* Check for composites such as dipthongs that collate as a
* single element (aka chains or collating-elements).
*/
*len = l;
*pri = p;
} else if (*t <= UCHAR_MAX) {
/*
* Character is a small (8-bit) character.
* We just look these up directly for speed.
*/
/*
* Character was found in the extended table.
*/
} else {
/*
* Character lacks a specific definition.
*/
/* Mask off sign bit to prevent ordering confusion. */
*pri = (*t & COLLATE_MAX_PRIORITY);
} else {
}
/* No substitutions for undefined characters! */
return;
}
/*
* Try substituting (expanding) the character. We are
* currently doing this *after* the chain compression. I
* think it should not matter, but this way might be slightly
* faster.
*
* We do this after the priority search, as this will help us
* to identify a single key value. In order for this to work,
* its important that the priority assigned to a given element
* to be substituted be unique for that level. The localedef
* code ensures this for us.
*/
sptr++;
}
}
}
/*
* This is the meaty part of wcsxfrm & strxfrm. Note that it does
* NOT NULL terminate. That is left to the caller.
*/
{
int pri;
int len;
const wchar_t *t;
int direc;
int pass;
if (pass != 0) {
/* insert level separator from the previous pass */
if (room) {
*xf++ = 1;
room--;
}
want++;
}
/* special pass for undefined */
} else {
}
t = src;
if (direc & DIRECTIVE_BACKWARD) {
if (tr)
goto fail;
}
c = *bp;
*fp-- = c;
}
}
if (direc & DIRECTIVE_POSITION) {
while (*t || state) {
&state);
t += len;
if (pri <= 0) {
if (pri < 0) {
goto fail;
}
}
if (room) {
room--;
}
want++;
}
} else {
while (*t || state) {
&state);
t += len;
if (pri <= 0) {
if (pri < 0) {
goto fail;
}
continue;
}
if (room) {
room--;
}
want++;
}
}
}
end:
if (tr)
return (need);
fail:
if (tr)
return ((size_t)(-1));
}
/*
* In the non-POSIX case, we transform each character into a string of
* characters representing the character's priority. Since char is usually
* signed, we are limited by 7 bits per byte. To avoid zero, we need to add
* XFRM_OFFSET, so we can't use a full 7 bits. For simplicity, we choose 6
* bits per byte.
*
* It turns out that we sometimes have real priorities that are
* 31-bits wide. (But: be careful using priorities where the high
* order bit is set -- i.e. the priority is negative. The sort order
* may be surprising!)
*
* TODO: This would be a good area to optimize somewhat. It turns out
* that real prioririties *except for the last UNDEFINED pass* are generally
* very small. We need the localedef code to precalculate the max
* priority for us, and ideally also give us a mask, and then we could
* severely limit what we expand to.
*/
#define XFRM_BYTES 6
#define XFRM_SHIFT 6
static int
{
/* we use unsigned to ensure zero fill on right shift */
int nc = 0;
while (val) {
pri >>= XFRM_SHIFT;
val >>= XFRM_SHIFT;
p++;
nc++;
}
return (nc);
}
{
int pri;
int len;
const wchar_t *t;
int direc;
int pass;
int b;
if (pass != 0) {
/* insert level separator from the previous pass */
if (room) {
room--;
}
want++;
}
/* special pass for undefined */
} else {
}
t = src;
if (direc & DIRECTIVE_BACKWARD) {
if (tr)
goto fail;
}
c = *bp;
*fp-- = c;
}
}
if (direc & DIRECTIVE_POSITION) {
while (*t || state) {
&state);
t += len;
if (pri <= 0) {
if (pri < 0) {
goto fail;
}
}
want += b;
if (room) {
while (b) {
b--;
if (room) {
room--;
}
}
}
}
} else {
while (*t || state) {
&state);
t += len;
if (pri <= 0) {
if (pri < 0) {
goto fail;
}
continue;
}
want += b;
if (room) {
while (b) {
b--;
if (room) {
room--;
}
}
}
}
}
}
end:
if (tr)
return (need);
fail:
if (tr)
return ((size_t)(-1));
}