PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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_nodefind_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.

183{
184 /* OR in index 1 or 2. */
185 node->next_code_index |= code_index;
186
187 if (!node->next_code_digits[0])
188 node->next_code_digits[0] = code_digit;
189 else if (node->next_code_digits[0] != code_digit)
190 node->next_code_digits[1] = code_digit;
191}
char next_code_digits[2]
int next_code_index

References dm_node::code_digit, 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.

124{
126 Datum retval;
127 char *string;
130 tmp_ctx;
131
132 /* Work in a temporary context to simplify cleanup. */
134 "daitch_mokotoff temporary context",
137
138 /* We must convert the string to UTF-8 if it isn't already. */
140 PG_UTF8);
141
142 /* The result is built in this ArrayBuildState. */
143 soundex = initArrayResult(TEXTOID, tmp_ctx, false);
144
145 if (!daitch_mokotoff_coding(string, soundex))
146 {
147 /* No encodable characters in input */
149 MemoryContextDelete(tmp_ctx);
151 }
152
154
156 MemoryContextDelete(tmp_ctx);
157
158 PG_RETURN_DATUM(retval);
159}
ArrayBuildState * initArrayResult(Oid element_type, MemoryContext rcontext, bool subcontext)
Definition: arrayfuncs.c:5293
Datum makeArrayResult(ArrayBuildState *astate, MemoryContext rcontext)
Definition: arrayfuncs.c:5420
static bool daitch_mokotoff_coding(const char *word, ArrayBuildState *soundex)
#define PG_GETARG_TEXT_PP(n)
Definition: fmgr.h:309
#define PG_RETURN_NULL()
Definition: fmgr.h:345
#define PG_RETURN_DATUM(x)
Definition: fmgr.h:353
Datum soundex(PG_FUNCTION_ARGS)
char * pg_server_to_any(const char *s, int len, int encoding)
Definition: mbutils.c:749
MemoryContext CurrentMemoryContext
Definition: mcxt.c:143
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:454
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:160
void * arg
@ PG_UTF8
Definition: pg_wchar.h:232
uintptr_t Datum
Definition: postgres.h:64
char string[11]
Definition: preproc-type.c:52
RT_SCOPE RT_RADIX_TREE *MemoryContext old_ctx
Definition: radixtree.h:1828
MemoryContextSwitchTo(old_ctx)
Definition: c.h:641
#define VARSIZE_ANY_EXHDR(PTR)
Definition: varatt.h:317
char * text_to_cstring(const text *t)
Definition: varlena.c:217

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, arg, CurrentMemoryContext, daitch_mokotoff_coding(), initArrayResult(), makeArrayResult(), MemoryContextDelete(), MemoryContextSwitchTo(), old_ctx, 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.

520{
521 int i = 0;
522 int letter_no = 0;
523 int ix_node = 0;
524 const dm_codes *codes,
525 *next_codes;
526 dm_node *first_node[2],
527 *node;
528
529 /* First letter. */
530 if (!(codes = read_letter(word, &i)))
531 {
532 /* No encodable character in input. */
533 return false;
534 }
535
536 /* Starting point. */
537 first_node[ix_node] = palloc_object(dm_node);
538 *first_node[ix_node] = start_node;
539
540 /*
541 * Loop until either the word input is exhausted, or all generated soundex
542 * codes are completed to six digits.
543 */
544 while (codes && first_node[ix_node])
545 {
546 next_codes = read_letter(word, &i);
547
548 /* Update leaf nodes. */
549 update_leaves(first_node, &ix_node, letter_no,
550 codes, next_codes ? next_codes : end_codes,
551 soundex);
552
553 codes = next_codes;
554 letter_no++;
555 }
556
557 /* Append all remaining (incomplete) soundex codes to output array. */
558 for (node = first_node[ix_node]; node; node = node->next[ix_node])
559 {
562
564 PointerGetDatum(out),
565 false,
566 TEXTOID,
568 }
569
570 return true;
571}
ArrayBuildState * accumArrayResult(ArrayBuildState *astate, Datum dvalue, bool disnull, Oid element_type, MemoryContext rcontext)
Definition: arrayfuncs.c:5350
static const dm_node start_node
static const dm_codes end_codes[2]
static const dm_codes * read_letter(const char *str, int *ix)
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)
#define DM_CODE_DIGITS
#define palloc_object(type)
Definition: fe_memutils.h:74
int i
Definition: isn.c:72
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
static void word(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition: regcomp.c:1476
struct dm_node * next[2]
char soundex[DM_CODE_DIGITS]
text * cstring_to_text_with_len(const char *s, int len)
Definition: varlena.c:196

References accumArrayResult(), cstring_to_text_with_len(), CurrentMemoryContext, DM_CODE_DIGITS, end_codes, 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.

218{
219 int i = code_digit - '0';
220 dm_node **nodes = parent->children;
221 dm_node *node = nodes[i];
222
223 if (node)
224 {
225 /* Found existing child node. Skip completed nodes. */
226 return node->soundex_length < DM_CODE_DIGITS ? node : NULL;
227 }
228
229 /* Create new child node. */
230 node = palloc_object(dm_node);
231 nodes[i] = node;
232
233 *node = start_node;
234 memcpy(node->soundex, parent->soundex, sizeof(parent->soundex));
235 node->soundex_length = parent->soundex_length;
236 node->soundex[node->soundex_length++] = code_digit;
237 node->code_digit = code_digit;
238 node->next_code_index = node->prev_code_index;
239
240 if (node->soundex_length < DM_CODE_DIGITS)
241 {
242 return node;
243 }
244 else
245 {
246 /* Append completed soundex code to output array. */
249
251 PointerGetDatum(out),
252 false,
253 TEXTOID,
255 return NULL;
256 }
257}
int soundex_length
struct dm_node * children[10]
int prev_code_index
char code_digit

References accumArrayResult(), dm_node::children, dm_node::code_digit, cstring_to_text_with_len(), CurrentMemoryContext, DM_CODE_DIGITS, 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.

165{
166 if (node->last_update < last_update)
167 {
168 node->prev_code_digits[0] = node->next_code_digits[0];
169 node->prev_code_digits[1] = node->next_code_digits[1];
170 node->next_code_digits[0] = '\0';
171 node->next_code_digits[1] = '\0';
172 node->prev_code_index = node->next_code_index;
173 node->next_code_index = 0;
174 node->is_leaf = 0;
175 node->last_update = last_update;
176 }
177}
char prev_code_digits[2]
int 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.

397{
398 /* Substitute character for skipped code points. */
399 const char na = '\x1a';
400 pg_wchar c;
401
402 /* Decode UTF-8 character to ISO 10646 code point. */
403 str += *ix;
405
406 /* Advance *ix, but (for safety) not if we've reached end of string. */
407 if (c)
408 *ix += pg_utf_mblen(str);
409
410 /* Convert. */
411 if (c >= (unsigned char) '[' && c <= (unsigned char) ']')
412 {
413 /* ASCII characters [, \, and ] are reserved for conversions below. */
414 return na;
415 }
416 else if (c < 0x60)
417 {
418 /* Other non-lowercase ASCII characters can be used as-is. */
419 return (char) c;
420 }
421 else if (c < 0x100)
422 {
423 /* ISO-8859-1 code point; convert to upper-case ASCII via table. */
424 return iso8859_1_to_ascii_upper[c - 0x60];
425 }
426 else
427 {
428 /* Conversion of non-ASCII characters in the coding chart. */
429 switch (c)
430 {
431 case 0x0104: /* LATIN CAPITAL LETTER A WITH OGONEK */
432 case 0x0105: /* LATIN SMALL LETTER A WITH OGONEK */
433 return '[';
434 case 0x0118: /* LATIN CAPITAL LETTER E WITH OGONEK */
435 case 0x0119: /* LATIN SMALL LETTER E WITH OGONEK */
436 return '\\';
437 case 0x0162: /* LATIN CAPITAL LETTER T WITH CEDILLA */
438 case 0x0163: /* LATIN SMALL LETTER T WITH CEDILLA */
439 case 0x021A: /* LATIN CAPITAL LETTER T WITH COMMA BELOW */
440 case 0x021B: /* LATIN SMALL LETTER T WITH COMMA BELOW */
441 return ']';
442 default:
443 return na;
444 }
445 }
446}
static const char iso8859_1_to_ascii_upper[]
const char * str
static pg_wchar utf8_to_unicode(const unsigned char *c)
Definition: mbprint.c:53
unsigned int pg_wchar
Definition: mbprint.c:31
#define pg_utf_mblen
Definition: pg_wchar.h:633
char * c

References 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.

468{
469 char c,
470 cmp;
471 int i,
472 j;
473 const dm_letter *letters;
474 const dm_codes *codes;
475
476 /* First letter in sequence. */
477 if ((c = read_valid_char(str, ix)) == '\0')
478 return NULL;
479
480 letters = &letter_[c - 'A'];
481 codes = letters->codes;
482 i = *ix;
483
484 /* Any subsequent letters in sequence. */
485 while ((letters = letters->letters) && (c = read_valid_char(str, &i)))
486 {
487 for (j = 0; (cmp = letters[j].letter); j++)
488 {
489 if (cmp == c)
490 {
491 /* Letter found. */
492 letters = &letters[j];
493 if (letters->codes)
494 {
495 /* Coding for letter sequence found. */
496 codes = letters->codes;
497 *ix = i;
498 }
499 break;
500 }
501 }
502 if (!cmp)
503 {
504 /* The sequence of letters has no coding. */
505 break;
506 }
507 }
508
509 return codes;
510}
static char read_valid_char(const char *str, int *ix)
int j
Definition: isn.c:73
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743

References cmp(), 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.

452{
453 char c;
454
455 while ((c = read_char((const unsigned char *) str, ix)) != '\0')
456 {
457 if (c >= 'A' && c <= ']')
458 break;
459 }
460
461 return c;
462}
static char read_char(const unsigned char *str, int *ix)

References 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.

198{
199 if (!node->is_leaf)
200 {
201 node->is_leaf = 1;
202
203 if (first_node[ix_node] == NULL)
204 first_node[ix_node] = node;
205 else
206 last_node[ix_node]->next[ix_node] = node;
207
208 last_node[ix_node] = node;
209 node->next[ix_node] = NULL;
210 }
211}

References 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.

335{
336 int i,
337 j,
338 code_index;
339 dm_node *node,
340 *last_node[2];
341 const dm_code *code,
342 *next_code;
343 int ix_node_next = (*ix_node + 1) & 1; /* Alternating index: 0, 1 */
344
345 /* Initialize for new linked list of leaves. */
346 first_node[ix_node_next] = NULL;
347 last_node[ix_node_next] = NULL;
348
349 /* Process all nodes. */
350 for (node = first_node[*ix_node]; node; node = node->next[*ix_node])
351 {
352 /* One or two alternate code sequences. */
353 for (i = 0; i < 2 && (code = codes[i]) && code[0][0]; i++)
354 {
355 /* Coding for previous letter - before vowel: 1, all other: 2 */
356 int prev_code_index = (code[0][0] > '1') + 1;
357
358 /* One or two alternate next code sequences. */
359 for (j = 0; j < 2 && (next_code = next_codes[j]) && next_code[0][0]; j++)
360 {
361 /* Determine which code to use. */
362 if (letter_no == 0)
363 {
364 /* This is the first letter. */
365 code_index = 0;
366 }
367 else if (next_code[0][0] <= '1')
368 {
369 /* The next letter is a vowel. */
370 code_index = 1;
371 }
372 else
373 {
374 /* All other cases. */
375 code_index = 2;
376 }
377
378 /* One or two sequential code digits. */
379 update_node(first_node, last_node, node, ix_node_next,
380 letter_no, prev_code_index, code_index,
381 code[code_index], 0,
382 soundex);
383 }
384 }
385 }
386
387 *ix_node = ix_node_next;
388}
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)

References 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.

267{
268 int i;
269 char next_code_digit = next_code_digits[digit_no];
270 int num_dirty_nodes = 0;
271 dm_node *dirty_nodes[2];
272
273 initialize_node(node, letter_no);
274
275 if (node->prev_code_index && !(node->prev_code_index & prev_code_index))
276 {
277 /*
278 * If the sound (vowel / consonant) of this letter encoding doesn't
279 * correspond to the coding index of the previous letter, we skip this
280 * letter encoding. Note that currently, only "J" can be either a
281 * vowel or a consonant.
282 */
283 return;
284 }
285
286 if (next_code_digit == 'X' ||
287 (digit_no == 0 &&
288 (node->prev_code_digits[0] == next_code_digit ||
289 node->prev_code_digits[1] == next_code_digit)))
290 {
291 /* The code digit is the same as one of the previous (i.e. not added). */
292 dirty_nodes[num_dirty_nodes++] = node;
293 }
294
295 if (next_code_digit != 'X' &&
296 (digit_no > 0 ||
297 node->prev_code_digits[0] != next_code_digit ||
298 node->prev_code_digits[1]))
299 {
300 /* The code digit is different from one of the previous (i.e. added). */
301 node = find_or_create_child_node(node, next_code_digit, soundex);
302 if (node)
303 {
304 initialize_node(node, letter_no);
305 dirty_nodes[num_dirty_nodes++] = node;
306 }
307 }
308
309 for (i = 0; i < num_dirty_nodes; i++)
310 {
311 /* Add code digit leading to the current node. */
312 add_next_code_digit(dirty_nodes[i], next_code_index, next_code_digit);
313
314 if (next_code_digits[++digit_no])
315 {
316 update_node(first_node, last_node, dirty_nodes[i], ix_node,
317 letter_no, prev_code_index, next_code_index,
318 next_code_digits, digit_no,
319 soundex);
320 }
321 else
322 {
323 /* Add incomplete leaf node to linked list. */
324 set_leaf(first_node, last_node, dirty_nodes[i], ix_node);
325 }
326 }
327}
static dm_node * find_or_create_child_node(dm_node *parent, char code_digit, ArrayBuildState *soundex)
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 void initialize_node(dm_node *node, int last_update)

References add_next_code_digit(), 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.

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.

Referenced by daitch_mokotoff_coding(), and find_or_create_child_node().