Back to index

php5  5.3.10
Defines | Functions
levenshtein.c File Reference
#include "php.h"
#include <stdlib.h>
#include <errno.h>
#include <ctype.h>
#include "php_string.h"

Go to the source code of this file.

Defines

#define LEVENSHTEIN_MAX_LENGTH   255

Functions

static int reference_levdist (const char *s1, int l1, const char *s2, int l2, int cost_ins, int cost_rep, int cost_del)
static int custom_levdist (char *str1, char *str2, char *callback_name TSRMLS_DC)
 PHP_FUNCTION (levenshtein)

Define Documentation

#define LEVENSHTEIN_MAX_LENGTH   255

Definition at line 26 of file levenshtein.c.


Function Documentation

static int custom_levdist ( char *  str1,
char *  str2,
char *callback_name  TSRMLS_DC 
) [static]

Definition at line 81 of file levenshtein.c.

{
       php_error_docref(NULL TSRMLS_CC, E_WARNING, "The general Levenshtein support is not there yet");
       /* not there yet */

       return -1;
}

Here is the caller graph for this function:

PHP_FUNCTION ( levenshtein  )

Definition at line 92 of file levenshtein.c.

{
       int argc = ZEND_NUM_ARGS();
       char *str1, *str2;
       char *callback_name;
       int str1_len, str2_len, callback_len;
       long cost_ins, cost_rep, cost_del;
       int distance = -1;

       switch (argc) {
              case 2: /* just two strings: use maximum performance version */
                     if (zend_parse_parameters(2 TSRMLS_CC, "ss", &str1, &str1_len, &str2, &str2_len) == FAILURE) {
                            return;
                     }
                     distance = reference_levdist(str1, str1_len, str2, str2_len, 1, 1, 1);
                     break;

              case 5: /* more general version: calc cost by ins/rep/del weights */
                     if (zend_parse_parameters(5 TSRMLS_CC, "sslll", &str1, &str1_len, &str2, &str2_len, &cost_ins, &cost_rep, &cost_del) == FAILURE) {
                            return;
                     }
                     distance = reference_levdist(str1, str1_len, str2, str2_len, cost_ins, cost_rep, cost_del);
                     break;

              case 3: /* most general version: calc cost by user-supplied function */
                     if (zend_parse_parameters(3 TSRMLS_CC, "sss", &str1, &str1_len, &str2, &str2_len, &callback_name, &callback_len) == FAILURE) {
                            return;
                     }
                     distance = custom_levdist(str1, str2, callback_name TSRMLS_CC);
                     break;

              default:
                     WRONG_PARAM_COUNT;
       }

       if (distance < 0 && /* TODO */ ZEND_NUM_ARGS() != 3) {
              php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument string(s) too long");
       }

       RETURN_LONG(distance);
}

Here is the call graph for this function:

static int reference_levdist ( const char *  s1,
int  l1,
const char *  s2,
int  l2,
int  cost_ins,
int  cost_rep,
int  cost_del 
) [static]

Definition at line 30 of file levenshtein.c.

{
       int *p1, *p2, *tmp;
       int i1, i2, c0, c1, c2;

       if (l1 == 0) {
              return l2 * cost_ins;
       }
       if (l2 == 0) {
              return l1 * cost_del;
       }

       if ((l1 > LEVENSHTEIN_MAX_LENGTH) || (l2 > LEVENSHTEIN_MAX_LENGTH)) {
              return -1;
       }
       p1 = safe_emalloc((l2 + 1), sizeof(int), 0);
       p2 = safe_emalloc((l2 + 1), sizeof(int), 0);

       for (i2 = 0; i2 <= l2; i2++) {
              p1[i2] = i2 * cost_ins;
       }
       for (i1 = 0; i1 < l1 ; i1++) {
              p2[0] = p1[0] + cost_del;

              for (i2 = 0; i2 < l2; i2++) {
                     c0 = p1[i2] + ((s1[i1] == s2[i2]) ? 0 : cost_rep);
                     c1 = p1[i2 + 1] + cost_del;
                     if (c1 < c0) {
                            c0 = c1;
                     }
                     c2 = p2[i2] + cost_ins;
                     if (c2 < c0) {
                            c0 = c2;
                     }
                     p2[i2 + 1] = c0;
              }
              tmp = p1;
              p1 = p2;
              p2 = tmp;
       }
       c0 = p1[l2];

       efree(p1);
       efree(p2);

       return c0;
}

Here is the caller graph for this function: