Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/perseant-stdc-iso10646]: src/lib/libc/citrus Fix issues with trie implem...
details: https://anonhg.NetBSD.org/src/rev/d15ec12d18bd
branches: perseant-stdc-iso10646
changeset: 850687:d15ec12d18bd
user: perseant <perseant%NetBSD.org@localhost>
date: Mon Jan 29 22:08:59 2018 +0000
description:
Fix issues with trie implementation. Now passes the locale tests when __STDC_ISO_10646__ is defined, with the exception of tests requiring LC_COLLATE support.
diffstat:
lib/libc/citrus/Makefile.inc | 4 +-
lib/libc/citrus/citrus_trie.c | 123 +-
lib/libc/citrus/citrus_trie.h | 13 +-
lib/libc/citrus/modules/citrus_big5.c | 8 +-
lib/libc/citrus/modules/citrus_big5_k2u.h | 15229 +++++++++++-
lib/libc/citrus/modules/citrus_big5_u2k.h | 22810 ++++++++++++++++-
lib/libc/citrus/modules/citrus_euc.c | 8 +-
lib/libc/citrus/modules/citrus_euc_k2u.h | 20452 ++++++++++++++-
lib/libc/citrus/modules/citrus_euc_u2k.h | 33244 ++++++++++++++++++++++++-
lib/libc/citrus/modules/citrus_iso2022.c | 8 +-
lib/libc/citrus/modules/citrus_iso2022_k2u.h | 23367 +++++++++++++++++-
lib/libc/citrus/modules/citrus_iso2022_u2k.h | 31391 ++++++++++++++++++++++-
lib/libc/citrus/modules/citrus_mskanji.c | 9 +-
lib/libc/citrus/modules/citrus_mskanji_k2u.h | 7906 +++++-
lib/libc/citrus/modules/citrus_mskanji_u2k.h | 21691 +++++++++++++++-
15 files changed, 170515 insertions(+), 5748 deletions(-)
diffs (truncated from 176565 to 300 lines):
diff -r 28f8e42e0462 -r d15ec12d18bd lib/libc/citrus/Makefile.inc
--- a/lib/libc/citrus/Makefile.inc Tue Jan 23 03:12:11 2018 +0000
+++ b/lib/libc/citrus/Makefile.inc Mon Jan 29 22:08:59 2018 +0000
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile.inc,v 1.8.40.1 2017/07/14 15:53:07 perseant Exp $
+# $NetBSD: Makefile.inc,v 1.8.40.2 2018/01/29 22:08:59 perseant Exp $
# sources
.PATH: ${ARCHDIR}/citrus ${.CURDIR}/citrus
@@ -10,7 +10,7 @@
citrus_db.c citrus_db_hash.c citrus_esdb.c citrus_hash.c \
citrus_iconv.c citrus_lookup.c \
citrus_mapper.c citrus_memstream.c citrus_mmap.c citrus_module.c \
- citrus_none.c citrus_stdenc.c
+ citrus_none.c citrus_stdenc.c citrus_trie.c
SRCS+= citrus_lc_ctype.c \
citrus_lc_monetary.c \
citrus_lc_numeric.c \
diff -r 28f8e42e0462 -r d15ec12d18bd lib/libc/citrus/citrus_trie.c
--- a/lib/libc/citrus/citrus_trie.c Tue Jan 23 03:12:11 2018 +0000
+++ b/lib/libc/citrus/citrus_trie.c Mon Jan 29 22:08:59 2018 +0000
@@ -6,7 +6,7 @@
static void citrus_trie_dump_table_recursive(citrus_trie_node_t, size_t, FILE *, int);
static void citrus_trie_load_table_recursive(citrus_trie_node_t, size_t, FILE *);
-static void citrus_trie_init_recursive(citrus_trie_node_t *, VALUE_TYPE *, int, int *, int *);
+static void citrus_trie_init_recursive(citrus_trie_node_t, size_t *, VALUE_TYPE *, int, int *, int *);
citrus_trie_header_t
citrus_trie_create(unsigned int flags, size_t bitwidth,
@@ -31,22 +31,23 @@
citrus_trie_node_t
citrus_trie_node_create(citrus_trie_header_t h, size_t level, size_t len)
{
- int i;
+ size_t i;
citrus_trie_node_t t;
t = (citrus_trie_node_t)citrus_trie_malloc(h, sizeof(*t));
t->tr_len = len;
if (len > 0) {
- t->tr_u = (union citrus_trie_node_union *)citrus_trie_malloc(h, len * sizeof(*t->tr_u));
if (level == 0) {
+ t->tr_u.u_value = (VALUE_TYPE *)citrus_trie_malloc(h, len * sizeof(*t->tr_u.u_value));
for (i = 0; i < len; i++)
- t->tr_u[i].u_value = INVALID_VALUE;
+ t->tr_u.u_value[i] = INVALID_VALUE;
} else {
+ t->tr_u.u_child = (citrus_trie_node_t *)citrus_trie_malloc(h, len * sizeof(*t->tr_u.u_child));
for (i = 0; i < len; i++)
- t->tr_u[i].u_child = NULL;
+ t->tr_u.u_child[i] = NULL;
}
} else
- t->tr_u = NULL;
+ t->tr_u.u_child = 0x0;
return t;
}
@@ -64,26 +65,32 @@
if (t->tr_len <= idx) {
olen = t->tr_len;
t->tr_len = idx + 1;
+ if (level == 0) {
#ifdef DEBUG_TRIE
- h->th_size += (t->tr_len - olen) * sizeof(*t->tr_u);
+ h->th_size += (t->tr_len - olen) * sizeof(*t->tr_u.u_value);
#endif
- t->tr_u = (union citrus_trie_node_union *)realloc(t->tr_u, t->tr_len * sizeof(*t->tr_u));
- for (i = olen; i < t->tr_len; i++) {
- if (level == 0)
- t->tr_u[i].u_value = INVALID_VALUE;
- else
- t->tr_u[i].u_child = NULL;
+ t->tr_u.u_value = (VALUE_TYPE *)realloc(t->tr_u.u_value, t->tr_len * sizeof(*t->tr_u.u_value));
+ for (i = olen; i < t->tr_len; i++)
+ t->tr_u.u_value[i] = INVALID_VALUE;
+ } else {
+#ifdef DEBUG_TRIE
+ h->th_size += (t->tr_len - olen) * sizeof(*t->tr_u.u_child);
+#endif
+ t->tr_u.u_child = (citrus_trie_node_t *)realloc(t->tr_u.u_child, t->tr_len * sizeof(*t->tr_u.u_child));
+ for (i = olen; i < t->tr_len; i++)
+ t->tr_u.u_child[i] = NULL;
}
}
if (level == 0) {
- t->tr_u[idx].u_value = value;
+ t->tr_u.u_value[idx] = value;
return 0;
} else {
- if (t->tr_u[idx].u_child == NULL)
- t->tr_u[idx].u_child = citrus_trie_node_create(h, level - 1, 0);
- return citrus_trie_node_insert(h, t->tr_u[idx].u_child, level - 1,
- key, value);
+ if (t->tr_u.u_child[idx] == NULL)
+ t->tr_u.u_child[idx] =
+ citrus_trie_node_create(h, level - 1, 0);
+ return citrus_trie_node_insert(h, t->tr_u.u_child[idx],
+ level - 1, key, value);
}
}
@@ -112,10 +119,11 @@
if (idx >= t->tr_len)
return INVALID_VALUE;
- if (level == 0) {
- return t->tr_u[idx].u_value;
- }
- return citrus_trie_node_lookup(h, t->tr_u[idx].u_child, level - 1, key);
+ if (level == 0)
+ return t->tr_u.u_value[idx];
+ if (t->tr_u.u_child[idx] == NULL)
+ return INVALID_VALUE;
+ return citrus_trie_node_lookup(h, t->tr_u.u_child[idx], level - 1, key);
}
VALUE_TYPE
@@ -128,9 +136,9 @@
* Assume VALUE_TYPE flat[N][2].
*/
citrus_trie_header_t
-citrus_trie_create_from_flat(VALUE_TYPE *flat, size_t bitwidth, int count) {
+citrus_trie_create_from_flat(VALUE_TYPE *flat, size_t bitwidth, size_t count) {
VALUE_TYPE ne_key;
- int i, j;
+ size_t i, j;
unsigned val;
citrus_trie_header_t h;
size_t bitmask = (1 << bitwidth) - 1;
@@ -170,8 +178,8 @@
if (level > 0)
for (i = 0; i < t->tr_len; i++)
- if (t->tr_u[i].u_child != NULL)
- citrus_trie_node_destroy(t->tr_u[i].u_child, level - 1);
+ if (t->tr_u.u_child[i] != NULL)
+ citrus_trie_node_destroy(t->tr_u.u_child[i], level - 1);
free(t);
}
@@ -190,38 +198,36 @@
if (mode == 0) {
/* Binary */
fwrite(t, sizeof(*t), 1, fp);
- fwrite(t->tr_u, sizeof(*t->tr_u), t->tr_len, fp);
+ fwrite(t->tr_u.u_child, sizeof(*t->tr_u.u_child), t->tr_len, fp);
} else if (mode == 1) {
- /* Header */
- fprintf(fp, " { %zu, NULL },\n", t->tr_len);
+ /* Table lengths */
+ fprintf(fp, " %zu,\n", t->tr_len);
} else {
/* Data */
- if (level == 0) {
- for (i = 0; i < t->tr_len; i++) {
- fprintf(fp, " %d,", t->tr_u[i].u_value);
- }
+ for (i = 0; i < t->tr_len; i++) {
+ fprintf(fp, " 0x%x,\n", ( level ? !!t->tr_u.u_child[i] : t->tr_u.u_value[i] ));
}
}
if (level)
for (i = 0; i < t->tr_len; i++)
- if (t->tr_u[i].u_child != NULL)
- citrus_trie_dump_table_recursive(t->tr_u[i].u_child, level - 1, fp, mode);
+ if (t->tr_u.u_child[i] != NULL)
+ citrus_trie_dump_table_recursive(t->tr_u.u_child[i], level - 1, fp, mode);
}
/* Load binary data only */
static void
citrus_trie_load_table_recursive(citrus_trie_node_t t, size_t level, FILE *fp)
{
- int i;
+ size_t i;
fread(t, sizeof(*t), 1, fp);
- t->tr_u = (union citrus_trie_node_union *)malloc(t->tr_len * sizeof(*t->tr_u));
- fread(t->tr_u, sizeof(*t->tr_u), t->tr_len, fp);
+ t->tr_u.u_child = (citrus_trie_node_t *)malloc(t->tr_len * sizeof(*t->tr_u.u_child));
+ fread(t->tr_u.u_child, sizeof(*t->tr_u.u_child), t->tr_len, fp);
if (level) {
for (i = 0; i < t->tr_len; i++) {
- if (t->tr_u[i].u_child != NULL) {
- t->tr_u[i].u_child = (citrus_trie_node_t)malloc(sizeof(*t));
- citrus_trie_load_table_recursive(t->tr_u[i].u_child, level - 1, fp);
+ if (t->tr_u.u_child[i] != NULL) {
+ t->tr_u.u_child[i] = (citrus_trie_node_t)malloc(sizeof(*t));
+ citrus_trie_load_table_recursive(t->tr_u.u_child[i], level - 1, fp);
}
}
}
@@ -256,7 +262,7 @@
prefix,
h->th_flags, h->th_bitwidth, h->th_bitmask, h->th_off, h->th_level);
/* Dump tree */
- fprintf(fp, "struct citrus_trie_node %s_nodes[] = {\n", prefix);
+ fprintf(fp, "size_t %s_sizes[] = {\n", prefix);
citrus_trie_dump_table_recursive(h->th_root, h->th_level, fp, 1);
fprintf(fp, "};\n");
/* Dump data */
@@ -269,29 +275,36 @@
/* Walk through the list of nodes, assigning tr_u to each. */
static void
-citrus_trie_init_recursive(citrus_trie_node_t *np, VALUE_TYPE *vp, int level, int *nidx, int *vidx)
+citrus_trie_init_recursive(citrus_trie_node_t t, size_t *sp, VALUE_TYPE *vp, int level, int *sidx, int *vidx)
{
- int i;
+ size_t i;
- for (i = 0; i < (*np)->tr_len; i++) {
- if (level) {
- (*np)->tr_u->u_child = *np + *nidx++;
- citrus_trie_init_recursive(np, vp, --level, nidx, vidx);
- } else {
- (*np)->tr_u->u_value = vp[*vidx];
- *vidx += (*np)->tr_len;
+ t->tr_len = sp[(*sidx)++];
+ if (level) {
+ t->tr_u.u_child = (citrus_trie_node_t *)malloc(t->tr_len * sizeof(*t->tr_u.u_child));
+ for (i = 0; i < t->tr_len; i++) {
+ if (vp[(*vidx)++])
+ t->tr_u.u_child[i] = (citrus_trie_node_t)malloc(sizeof(*t->tr_u.u_child[i]));
+ else
+ t->tr_u.u_child[i] = NULL;
}
+ for (i = 0; i < t->tr_len; i++)
+ if (t->tr_u.u_child[i] != NULL)
+ citrus_trie_init_recursive(t->tr_u.u_child[i], sp, vp, level - 1, sidx, vidx);
+ } else {
+ t->tr_u.u_value = vp + (*vidx);
+ *vidx += t->tr_len;
}
}
void
-citrus_trie_init(citrus_trie_header_t h, citrus_trie_node_t *np, VALUE_TYPE *vp)
+citrus_trie_init(citrus_trie_header_t h, size_t *sp, VALUE_TYPE *vp)
{
- int nidx = 0;
+ int sidx = 0;
int vidx = 0;
- h->th_root = *np;
- citrus_trie_init_recursive(np, vp, h->th_level, &nidx, &vidx);
+ h->th_root = (citrus_trie_node_t)malloc(sizeof(*h->th_root));
+ citrus_trie_init_recursive(h->th_root, sp, vp, h->th_level, &sidx, &vidx);
}
#ifdef DEBUG_TRIE
diff -r 28f8e42e0462 -r d15ec12d18bd lib/libc/citrus/citrus_trie.h
--- a/lib/libc/citrus/citrus_trie.h Tue Jan 23 03:12:11 2018 +0000
+++ b/lib/libc/citrus/citrus_trie.h Mon Jan 29 22:08:59 2018 +0000
@@ -11,7 +11,8 @@
*/
#ifndef VALUE_TYPE
# define VALUE_TYPE int32_t
-# define VALUE_TYPE_STRING "int32_t"
+# define STRINGIZE(s) #s
+# define VALUE_TYPE_STRING STRINGIZE(VALUE_TYPE) /* "int32_t" */
#endif
#define INVALID_VALUE 0xffffffff
@@ -32,9 +33,9 @@
typedef struct citrus_trie_node {
size_t tr_len;
union citrus_trie_node_union {
- struct citrus_trie_node *u_child;
- VALUE_TYPE u_value;
- } *tr_u;
+ struct citrus_trie_node **u_child;
+ VALUE_TYPE *u_value;
+ } tr_u;
} *citrus_trie_node_t;
#ifdef DEBUG_TRIE
@@ -49,11 +50,11 @@
int citrus_trie_insert(citrus_trie_header_t, citrus_trie_key_t, VALUE_TYPE);
VALUE_TYPE citrus_trie_node_lookup(citrus_trie_header_t, citrus_trie_node_t, size_t, citrus_trie_key_t);
VALUE_TYPE citrus_trie_lookup(citrus_trie_header_t, citrus_trie_key_t);
-citrus_trie_header_t citrus_trie_create_from_flat(VALUE_TYPE *, size_t, int);
+citrus_trie_header_t citrus_trie_create_from_flat(VALUE_TYPE *, size_t, size_t);
void citrus_trie_node_destroy(citrus_trie_node_t, size_t);
void citrus_trie_destroy(citrus_trie_header_t);
-void citrus_trie_init(citrus_trie_header_t, citrus_trie_node_t *, VALUE_TYPE *);
+void citrus_trie_init(citrus_trie_header_t, size_t *, VALUE_TYPE *);
void citrus_trie_dump(citrus_trie_header_t, char *, char *, int);
citrus_trie_header_t citrus_trie_load(char *);
#endif /* CITRUS_TRIE_H_ */
diff -r 28f8e42e0462 -r d15ec12d18bd lib/libc/citrus/modules/citrus_big5.c
--- a/lib/libc/citrus/modules/citrus_big5.c Tue Jan 23 03:12:11 2018 +0000
+++ b/lib/libc/citrus/modules/citrus_big5.c Mon Jan 29 22:08:59 2018 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: citrus_big5.c,v 1.15.18.4 2018/01/20 19:36:29 perseant Exp $ */
+/* $NetBSD: citrus_big5.c,v 1.15.18.5 2018/01/29 22:08:59 perseant Exp $ */
Home |
Main Index |
Thread Index |
Old Index