PostgreSQL Source Code  git master
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 {
125  text *arg = PG_GETARG_TEXT_PP(0);
126  Datum retval;
127  char *string;
130  tmp_ctx;
131 
132  /* Work in a temporary context to simplify cleanup. */
134  "daitch_mokotoff temporary context",
136  old_ctx = MemoryContextSwitchTo(tmp_ctx);
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);
150  PG_RETURN_NULL();
151  }
152 
153  retval = makeArrayResult(soundex, old_ctx);
154 
156  MemoryContextDelete(tmp_ctx);
157 
158  PG_RETURN_DATUM(retval);
159 }
ArrayBuildState * initArrayResult(Oid element_type, MemoryContext rcontext, bool subcontext)
Definition: arrayfuncs.c:5274
Datum makeArrayResult(ArrayBuildState *astate, MemoryContext rcontext)
Definition: arrayfuncs.c:5401
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:1824
MemoryContextSwitchTo(old_ctx)
Definition: c.h:687
#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:5331
static const dm_node start_node
static const dm_codes end_codes[2]
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
static const dm_codes * read_letter(const char *str, int *ix)
#define palloc_object(type)
Definition: fe_memutils.h:62
int i
Definition: isn.c:73
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:1474
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;
404  c = utf8_to_unicode(str);
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:74
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(), and soundex().

Referenced by update_leaves().

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().