daitch_mokotoff.c File Reference

#include "postgres.h"
#include "catalog/pg_type.h"
#include "mb/pg_wchar.h"
#include "utils/array.h"
#include "utils/builtins.h"
#include "utils/memutils.h"
#include "daitch_mokotoff.h"

Include dependency graph for daitch_mokotoff.c:

Go to the source code of this file.

Data Structures
struct	dm_node

Macros
#define	DM_CODE_DIGITS   6

Typedefs
typedef struct dm_node	dm_node

Functions
static bool	daitch_mokotoff_coding (const char *word, ArrayBuildState *soundex)
	PG_FUNCTION_INFO_V1 (daitch_mokotoff)
Datum	daitch_mokotoff (PG_FUNCTION_ARGS)
static void	initialize_node (dm_node *node, int last_update)
static void	add_next_code_digit (dm_node *node, int code_index, char code_digit)
static void	set_leaf (dm_node *first_node[2], dm_node *last_node[2], dm_node *node, int ix_node)
static dm_node *	find_or_create_child_node (dm_node *parent, char code_digit, ArrayBuildState *soundex)
static void	update_node (dm_node *first_node[2], dm_node *last_node[2], dm_node *node, int ix_node, int letter_no, int prev_code_index, int next_code_index, const char *next_code_digits, int digit_no, ArrayBuildState *soundex)
static void	update_leaves (dm_node *first_node[2], int *ix_node, int letter_no, const dm_codes *codes, const dm_codes *next_codes, ArrayBuildState *soundex)
static char	read_char (const unsigned char *str, int *ix)
static char	read_valid_char (const char *str, int *ix)
static const dm_codes *	read_letter (const char *str, int *ix)

Variables
static const dm_node	start_node
static const dm_codes	end_codes [2]
static const char	iso8859_1_to_ascii_upper []

Macro Definition Documentation

DM_CODE_DIGITS

#define DM_CODE_DIGITS   6

Definition at line 61 of file daitch_mokotoff.c.

Typedef Documentation

dm_node

typedef struct dm_node dm_node

Function Documentation

add_next_code_digit()

static void add_next_code_digit ( dm_node *  node, int  code_index, char  code_digit  )

static

Definition at line 182 of file daitch_mokotoff.c.

{
    /* OR in index 1 or 2. */
    node->next_code_index |= code_index;
 
    if (!node->next_code_digits[0])
        node->next_code_digits[0] = code_digit;
    else if (node->next_code_digits[0] != code_digit)
        node->next_code_digits[1] = code_digit;
}

References dm_node::code_digit, fb(), dm_node::next_code_digits, and dm_node::next_code_index.

Referenced by update_node().

daitch_mokotoff()

Datum daitch_mokotoff

(

PG_FUNCTION_ARGS

)

Definition at line 123 of file daitch_mokotoff.c.

{
    text       *arg = PG_GETARG_TEXT_PP(0);
    Datum       retval;
    char       *string;
    ArrayBuildState *soundex;
    MemoryContext old_ctx,
                tmp_ctx;
 
    /* Work in a temporary context to simplify cleanup. */
    tmp_ctx = AllocSetContextCreate(CurrentMemoryContext,
                                    "daitch_mokotoff temporary context",
                                    ALLOCSET_DEFAULT_SIZES);
    old_ctx = MemoryContextSwitchTo(tmp_ctx);
 
    /* We must convert the string to UTF-8 if it isn't already. */
    string = pg_server_to_any(text_to_cstring(arg), VARSIZE_ANY_EXHDR(arg),
                              PG_UTF8);
 
    /* The result is built in this ArrayBuildState. */
    soundex = initArrayResult(TEXTOID, tmp_ctx, false);
 
    if (!daitch_mokotoff_coding(string, soundex))
    {
        /* No encodable characters in input */
        MemoryContextSwitchTo(old_ctx);
        MemoryContextDelete(tmp_ctx);
        PG_RETURN_NULL();
    }
 
    retval = makeArrayResult(soundex, old_ctx);
 
    MemoryContextSwitchTo(old_ctx);
    MemoryContextDelete(tmp_ctx);
 
    PG_RETURN_DATUM(retval);
}

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, arg, CurrentMemoryContext, daitch_mokotoff_coding(), fb(), initArrayResult(), makeArrayResult(), MemoryContextDelete(), MemoryContextSwitchTo(), PG_GETARG_TEXT_PP, PG_RETURN_DATUM, PG_RETURN_NULL, pg_server_to_any(), PG_UTF8, soundex(), text_to_cstring(), and VARSIZE_ANY_EXHDR().

daitch_mokotoff_coding()

static bool daitch_mokotoff_coding ( const char *  word, ArrayBuildState *  soundex  )

static

Definition at line 519 of file daitch_mokotoff.c.

{
    int         i = 0;
    int         letter_no = 0;
    int         ix_node = 0;
    const dm_codes *codes,
               *next_codes;
    dm_node    *first_node[2],
               *node;
 
    /* First letter. */
    if (!(codes = read_letter(word, &i)))
    {
        /* No encodable character in input. */
        return false;
    }
 
    /* Starting point. */
    first_node[ix_node] = palloc_object(dm_node);
    *first_node[ix_node] = start_node;
 
    /*
     * Loop until either the word input is exhausted, or all generated soundex
     * codes are completed to six digits.
     */
    while (codes && first_node[ix_node])
    {
        next_codes = read_letter(word, &i);
 
        /* Update leaf nodes. */
        update_leaves(first_node, &ix_node, letter_no,
                      codes, next_codes ? next_codes : end_codes,
                      soundex);
 
        codes = next_codes;
        letter_no++;
    }
 
    /* Append all remaining (incomplete) soundex codes to output array. */
    for (node = first_node[ix_node]; node; node = node->next[ix_node])
    {
        text       *out = cstring_to_text_with_len(node->soundex,
                                                   DM_CODE_DIGITS);
 
        accumArrayResult(soundex,
                         PointerGetDatum(out),
                         false,
                         TEXTOID,
                         CurrentMemoryContext);
    }
 
    return true;
}

References accumArrayResult(), cstring_to_text_with_len(), CurrentMemoryContext, DM_CODE_DIGITS, end_codes, fb(), i, dm_node::next, palloc_object, PointerGetDatum(), read_letter(), soundex(), dm_node::soundex, start_node, update_leaves(), and word().

Referenced by daitch_mokotoff().

find_or_create_child_node()

static dm_node * find_or_create_child_node ( dm_node *  parent, char  code_digit, ArrayBuildState *  soundex  )

static

Definition at line 216 of file daitch_mokotoff.c.

{
    int         i = code_digit - '0';
    dm_node   **nodes = parent->children;
    dm_node    *node = nodes[i];
 
    if (node)
    {
        /* Found existing child node. Skip completed nodes. */
        return node->soundex_length < DM_CODE_DIGITS ? node : NULL;
    }
 
    /* Create new child node. */
    node = palloc_object(dm_node);
    nodes[i] = node;
 
    *node = start_node;
    memcpy(node->soundex, parent->soundex, sizeof(parent->soundex));
    node->soundex_length = parent->soundex_length;
    node->soundex[node->soundex_length++] = code_digit;
    node->code_digit = code_digit;
    node->next_code_index = node->prev_code_index;
 
    if (node->soundex_length < DM_CODE_DIGITS)
    {
        return node;
    }
    else
    {
        /* Append completed soundex code to output array. */
        text       *out = cstring_to_text_with_len(node->soundex,
                                                   DM_CODE_DIGITS);
 
        accumArrayResult(soundex,
                         PointerGetDatum(out),
                         false,
                         TEXTOID,
                         CurrentMemoryContext);
        return NULL;
    }
}

References accumArrayResult(), dm_node::children, dm_node::code_digit, cstring_to_text_with_len(), CurrentMemoryContext, DM_CODE_DIGITS, fb(), i, dm_node::next_code_index, palloc_object, PointerGetDatum(), dm_node::prev_code_index, soundex(), dm_node::soundex, dm_node::soundex_length, and start_node.

Referenced by update_node().

initialize_node()

static void initialize_node ( dm_node *  node, int  last_update  )

static

Definition at line 164 of file daitch_mokotoff.c.

{
    if (node->last_update < last_update)
    {
        node->prev_code_digits[0] = node->next_code_digits[0];
        node->prev_code_digits[1] = node->next_code_digits[1];
        node->next_code_digits[0] = '\0';
        node->next_code_digits[1] = '\0';
        node->prev_code_index = node->next_code_index;
        node->next_code_index = 0;
        node->is_leaf = 0;
        node->last_update = last_update;
    }
}

References dm_node::is_leaf, dm_node::last_update, dm_node::next_code_digits, dm_node::next_code_index, dm_node::prev_code_digits, and dm_node::prev_code_index.

Referenced by update_node().

PG_FUNCTION_INFO_V1()

PG_FUNCTION_INFO_V1

(

daitch_mokotoff

)

read_char()

static char read_char ( const unsigned char *  str, int *  ix  )

static

Definition at line 396 of file daitch_mokotoff.c.

{
    /* Substitute character for skipped code points. */
    const char  na = '\x1a';
    pg_wchar    c;
 
    /* Decode UTF-8 character to ISO 10646 code point. */
    str += *ix;
    c = utf8_to_unicode(str);
 
    /* Advance *ix, but (for safety) not if we've reached end of string. */
    if (c)
        *ix += pg_utf_mblen(str);
 
    /* Convert. */
    if (c >= (unsigned char) '[' && c <= (unsigned char) ']')
    {
        /* ASCII characters [, \, and ] are reserved for conversions below. */
        return na;
    }
    else if (c < 0x60)
    {
        /* Other non-lowercase ASCII characters can be used as-is. */
        return (char) c;
    }
    else if (c < 0x100)
    {
        /* ISO-8859-1 code point; convert to upper-case ASCII via table. */
        return iso8859_1_to_ascii_upper[c - 0x60];
    }
    else
    {
        /* Conversion of non-ASCII characters in the coding chart. */
        switch (c)
        {
            case 0x0104:        /* LATIN CAPITAL LETTER A WITH OGONEK */
            case 0x0105:        /* LATIN SMALL LETTER A WITH OGONEK */
                return '[';
            case 0x0118:        /* LATIN CAPITAL LETTER E WITH OGONEK */
            case 0x0119:        /* LATIN SMALL LETTER E WITH OGONEK */
                return '\\';
            case 0x0162:        /* LATIN CAPITAL LETTER T WITH CEDILLA */
            case 0x0163:        /* LATIN SMALL LETTER T WITH CEDILLA */
            case 0x021A:        /* LATIN CAPITAL LETTER T WITH COMMA BELOW */
            case 0x021B:        /* LATIN SMALL LETTER T WITH COMMA BELOW */
                return ']';
            default:
                return na;
        }
    }
}

References fb(), iso8859_1_to_ascii_upper, pg_utf_mblen, str, and utf8_to_unicode().

Referenced by read_valid_char().

read_letter()

static const dm_codes * read_letter ( const char *  str, int *  ix  )

static

Definition at line 467 of file daitch_mokotoff.c.

{
    char        c,
                cmp;
    int         i,
                j;
    const dm_letter *letters;
    const dm_codes *codes;
 
    /* First letter in sequence. */
    if ((c = read_valid_char(str, ix)) == '\0')
        return NULL;
 
    letters = &letter_[c - 'A'];
    codes = letters->codes;
    i = *ix;
 
    /* Any subsequent letters in sequence. */
    while ((letters = letters->letters) && (c = read_valid_char(str, &i)))
    {
        for (j = 0; (cmp = letters[j].letter); j++)
        {
            if (cmp == c)
            {
                /* Letter found. */
                letters = &letters[j];
                if (letters->codes)
                {
                    /* Coding for letter sequence found. */
                    codes = letters->codes;
                    *ix = i;
                }
                break;
            }
        }
        if (!cmp)
        {
            /* The sequence of letters has no coding. */
            break;
        }
    }
 
    return codes;
}

References cmp(), fb(), i, j, read_valid_char(), and str.

Referenced by daitch_mokotoff_coding().

read_valid_char()

static char read_valid_char ( const char *  str, int *  ix  )

static

Definition at line 451 of file daitch_mokotoff.c.

{
    char        c;
 
    while ((c = read_char((const unsigned char *) str, ix)) != '\0')
    {
        if (c >= 'A' && c <= ']')
            break;
    }
 
    return c;
}

References fb(), read_char(), and str.

Referenced by read_letter().

set_leaf()

static void set_leaf ( dm_node *  first_node[2], dm_node *  last_node[2], dm_node *  node, int  ix_node  )

static

Definition at line 196 of file daitch_mokotoff.c.

{
    if (!node->is_leaf)
    {
        node->is_leaf = 1;
 
        if (first_node[ix_node] == NULL)
            first_node[ix_node] = node;
        else
            last_node[ix_node]->next[ix_node] = node;
 
        last_node[ix_node] = node;
        node->next[ix_node] = NULL;
    }
}

References fb(), dm_node::is_leaf, and dm_node::next.

Referenced by update_node().

update_leaves()

static void update_leaves ( dm_node *  first_node[2], int *  ix_node, int  letter_no, const dm_codes *  codes, const dm_codes *  next_codes, ArrayBuildState *  soundex  )

static

Definition at line 332 of file daitch_mokotoff.c.

{
    int         i,
                j,
                code_index;
    dm_node    *node,
               *last_node[2];
    const dm_code *code,
               *next_code;
    int         ix_node_next = (*ix_node + 1) & 1;  /* Alternating index: 0, 1 */
 
    /* Initialize for new linked list of leaves. */
    first_node[ix_node_next] = NULL;
    last_node[ix_node_next] = NULL;
 
    /* Process all nodes. */
    for (node = first_node[*ix_node]; node; node = node->next[*ix_node])
    {
        /* One or two alternate code sequences. */
        for (i = 0; i < 2 && (code = codes[i]) && code[0][0]; i++)
        {
            /* Coding for previous letter - before vowel: 1, all other: 2 */
            int         prev_code_index = (code[0][0] > '1') + 1;
 
            /* One or two alternate next code sequences. */
            for (j = 0; j < 2 && (next_code = next_codes[j]) && next_code[0][0]; j++)
            {
                /* Determine which code to use. */
                if (letter_no == 0)
                {
                    /* This is the first letter. */
                    code_index = 0;
                }
                else if (next_code[0][0] <= '1')
                {
                    /* The next letter is a vowel. */
                    code_index = 1;
                }
                else
                {
                    /* All other cases. */
                    code_index = 2;
                }
 
                /* One or two sequential code digits. */
                update_node(first_node, last_node, node, ix_node_next,
                            letter_no, prev_code_index, code_index,
                            code[code_index], 0,
                            soundex);
            }
        }
    }
 
    *ix_node = ix_node_next;
}

References fb(), i, j, dm_node::next, dm_node::prev_code_index, soundex(), and update_node().

Referenced by daitch_mokotoff_coding().

update_node()

static void update_node ( dm_node *  first_node[2], dm_node *  last_node[2], dm_node *  node, int  ix_node, int  letter_no, int  prev_code_index, int  next_code_index, const char *  next_code_digits, int  digit_no, ArrayBuildState *  soundex  )

static

Definition at line 262 of file daitch_mokotoff.c.

{
    int         i;
    char        next_code_digit = next_code_digits[digit_no];
    int         num_dirty_nodes = 0;
    dm_node    *dirty_nodes[2];
 
    initialize_node(node, letter_no);
 
    if (node->prev_code_index && !(node->prev_code_index & prev_code_index))
    {
        /*
         * If the sound (vowel / consonant) of this letter encoding doesn't
         * correspond to the coding index of the previous letter, we skip this
         * letter encoding. Note that currently, only "J" can be either a
         * vowel or a consonant.
         */
        return;
    }
 
    if (next_code_digit == 'X' ||
        (digit_no == 0 &&
         (node->prev_code_digits[0] == next_code_digit ||
          node->prev_code_digits[1] == next_code_digit)))
    {
        /* The code digit is the same as one of the previous (i.e. not added). */
        dirty_nodes[num_dirty_nodes++] = node;
    }
 
    if (next_code_digit != 'X' &&
        (digit_no > 0 ||
         node->prev_code_digits[0] != next_code_digit ||
         node->prev_code_digits[1]))
    {
        /* The code digit is different from one of the previous (i.e. added). */
        node = find_or_create_child_node(node, next_code_digit, soundex);
        if (node)
        {
            initialize_node(node, letter_no);
            dirty_nodes[num_dirty_nodes++] = node;
        }
    }
 
    for (i = 0; i < num_dirty_nodes; i++)
    {
        /* Add code digit leading to the current node. */
        add_next_code_digit(dirty_nodes[i], next_code_index, next_code_digit);
 
        if (next_code_digits[++digit_no])
        {
            update_node(first_node, last_node, dirty_nodes[i], ix_node,
                        letter_no, prev_code_index, next_code_index,
                        next_code_digits, digit_no,
                        soundex);
        }
        else
        {
            /* Add incomplete leaf node to linked list. */
            set_leaf(first_node, last_node, dirty_nodes[i], ix_node);
        }
    }
}

References add_next_code_digit(), fb(), find_or_create_child_node(), i, initialize_node(), dm_node::next_code_digits, dm_node::next_code_index, dm_node::prev_code_digits, dm_node::prev_code_index, set_leaf(), soundex(), and update_node().

Referenced by update_leaves(), and update_node().

Variable Documentation

end_codes

const dm_codes end_codes[2]

static

Initial value:

=
{
    {
        "X", "X", "X"
    }
}

Definition at line 105 of file daitch_mokotoff.c.

{
    {
        "X", "X", "X"
    }
};

Referenced by daitch_mokotoff_coding().

iso8859_1_to_ascii_upper

const char iso8859_1_to_ascii_upper[]

static

Initial value:

=
"`ABCDEFGHIJKLMNOPQRSTUVWXYZ{|}~                                  !                             ?AAAAAAECEEEEIIIIDNOOOOO*OUUUUYDSAAAAAAECEEEEIIIIDNOOOOO/OUUUUYDY"

Definition at line 113 of file daitch_mokotoff.c.

Referenced by read_char().

start_node

const dm_node start_node

static

Initial value:

= {
    .soundex_length = 0,
    .soundex = "000000",        
    .is_leaf = 0,
    .last_update = 0,
    .code_digit = '\0',
    .prev_code_digits = {'\0', '\0'},
    .next_code_digits = {'\0', '\0'},
    .prev_code_index = 0,
    .next_code_index = 0,
    .children = {NULL},
    .next = {NULL}
}

Definition at line 90 of file daitch_mokotoff.c.

                                  {
    .soundex_length = 0,
    .soundex = "000000",        /* Six digits */
    .is_leaf = 0,
    .last_update = 0,
    .code_digit = '\0',
    .prev_code_digits = {'\0', '\0'},
    .next_code_digits = {'\0', '\0'},
    .prev_code_index = 0,
    .next_code_index = 0,
    .children = {NULL},
    .next = {NULL}
};

Referenced by daitch_mokotoff_coding(), and find_or_create_child_node().