Return to levenshtein.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / standard

Annotation of embedaddon/php/ext/standard/levenshtein.c, revision 1.1

1.1     ! misho       1: /*
        !             2:    +----------------------------------------------------------------------+
        !             3:    | PHP Version 5                                                        |
        !             4:    +----------------------------------------------------------------------+
        !             5:    | Copyright (c) 1997-2012 The PHP Group                                |
        !             6:    +----------------------------------------------------------------------+
        !             7:    | This source file is subject to version 3.01 of the PHP license,      |
        !             8:    | that is bundled with this package in the file LICENSE, and is        |
        !             9:    | available through the world-wide-web at the following url:           |
        !            10:    | http://www.php.net/license/3_01.txt                                  |
        !            11:    | If you did not receive a copy of the PHP license and are unable to   |
        !            12:    | obtain it through the world-wide-web, please send a note to          |
        !            13:    | license@php.net so we can mail you a copy immediately.               |
        !            14:    +----------------------------------------------------------------------+
        !            15:    | Author: Hartmut Holzgraefe <hholzgra@php.net>                        |
        !            16:    +----------------------------------------------------------------------+
        !            17:  */
        !            18: /* $Id: levenshtein.c 321634 2012-01-01 13:15:04Z felipe $ */
        !            19: 
        !            20: #include "php.h"
        !            21: #include <stdlib.h>
        !            22: #include <errno.h>
        !            23: #include <ctype.h>
        !            24: #include "php_string.h"
        !            25: 
        !            26: #define LEVENSHTEIN_MAX_LENGTH 255
        !            27: 
        !            28: /* {{{ reference_levdist
        !            29:  * reference implementation, only optimized for memory usage, not speed */
        !            30: static int reference_levdist(const char *s1, int l1, const char *s2, int l2, int cost_ins, int cost_rep, int cost_del )
        !            31: {
        !            32:        int *p1, *p2, *tmp;
        !            33:        int i1, i2, c0, c1, c2;
        !            34: 
        !            35:        if (l1 == 0) {
        !            36:                return l2 * cost_ins;
        !            37:        }
        !            38:        if (l2 == 0) {
        !            39:                return l1 * cost_del;
        !            40:        }
        !            41: 
        !            42:        if ((l1 > LEVENSHTEIN_MAX_LENGTH) || (l2 > LEVENSHTEIN_MAX_LENGTH)) {
        !            43:                return -1;
        !            44:        }
        !            45:        p1 = safe_emalloc((l2 + 1), sizeof(int), 0);
        !            46:        p2 = safe_emalloc((l2 + 1), sizeof(int), 0);
        !            47: 
        !            48:        for (i2 = 0; i2 <= l2; i2++) {
        !            49:                p1[i2] = i2 * cost_ins;
        !            50:        }
        !            51:        for (i1 = 0; i1 < l1 ; i1++) {
        !            52:                p2[0] = p1[0] + cost_del;
        !            53: 
        !            54:                for (i2 = 0; i2 < l2; i2++) {
        !            55:                        c0 = p1[i2] + ((s1[i1] == s2[i2]) ? 0 : cost_rep);
        !            56:                        c1 = p1[i2 + 1] + cost_del;
        !            57:                        if (c1 < c0) {
        !            58:                                c0 = c1;
        !            59:                        }
        !            60:                        c2 = p2[i2] + cost_ins;
        !            61:                        if (c2 < c0) {
        !            62:                                c0 = c2;
        !            63:                        }
        !            64:                        p2[i2 + 1] = c0;
        !            65:                }
        !            66:                tmp = p1;
        !            67:                p1 = p2;
        !            68:                p2 = tmp;
        !            69:        }
        !            70:        c0 = p1[l2];
        !            71: 
        !            72:        efree(p1);
        !            73:        efree(p2);
        !            74: 
        !            75:        return c0;
        !            76: }
        !            77: /* }}} */
        !            78: 
        !            79: /* {{{ custom_levdist
        !            80:  */
        !            81: static int custom_levdist(char *str1, char *str2, char *callback_name TSRMLS_DC)
        !            82: {
        !            83:        php_error_docref(NULL TSRMLS_CC, E_WARNING, "The general Levenshtein support is not there yet");
        !            84:        /* not there yet */
        !            85: 
        !            86:        return -1;
        !            87: }
        !            88: /* }}} */
        !            89: 
        !            90: /* {{{ proto int levenshtein(string str1, string str2[, int cost_ins, int cost_rep, int cost_del])
        !            91:    Calculate Levenshtein distance between two strings */
        !            92: PHP_FUNCTION(levenshtein)
        !            93: {
        !            94:        int argc = ZEND_NUM_ARGS();
        !            95:        char *str1, *str2;
        !            96:        char *callback_name;
        !            97:        int str1_len, str2_len, callback_len;
        !            98:        long cost_ins, cost_rep, cost_del;
        !            99:        int distance = -1;
        !           100: 
        !           101:        switch (argc) {
        !           102:                case 2: /* just two strings: use maximum performance version */
        !           103:                        if (zend_parse_parameters(2 TSRMLS_CC, "ss", &str1, &str1_len, &str2, &str2_len) == FAILURE) {
        !           104:                                return;
        !           105:                        }
        !           106:                        distance = reference_levdist(str1, str1_len, str2, str2_len, 1, 1, 1);
        !           107:                        break;
        !           108: 
        !           109:                case 5: /* more general version: calc cost by ins/rep/del weights */
        !           110:                        if (zend_parse_parameters(5 TSRMLS_CC, "sslll", &str1, &str1_len, &str2, &str2_len, &cost_ins, &cost_rep, &cost_del) == FAILURE) {
        !           111:                                return;
        !           112:                        }
        !           113:                        distance = reference_levdist(str1, str1_len, str2, str2_len, cost_ins, cost_rep, cost_del);
        !           114:                        break;
        !           115: 
        !           116:                case 3: /* most general version: calc cost by user-supplied function */
        !           117:                        if (zend_parse_parameters(3 TSRMLS_CC, "sss", &str1, &str1_len, &str2, &str2_len, &callback_name, &callback_len) == FAILURE) {
        !           118:                                return;
        !           119:                        }
        !           120:                        distance = custom_levdist(str1, str2, callback_name TSRMLS_CC);
        !           121:                        break;
        !           122: 
        !           123:                default:
        !           124:                        WRONG_PARAM_COUNT;
        !           125:        }
        !           126: 
        !           127:        if (distance < 0 && /* TODO */ ZEND_NUM_ARGS() != 3) {
        !           128:                php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument string(s) too long");
        !           129:        }
        !           130: 
        !           131:        RETURN_LONG(distance);
        !           132: }
        !           133: /* }}} */
        !           134: 
        !           135: /*
        !           136:  * Local variables:
        !           137:  * tab-width: 4
        !           138:  * c-basic-offset: 4
        !           139:  * End:
        !           140:  * vim600: sw=4 ts=4 fdm=marker
        !           141:  * vim<600: sw=4 ts=4
        !           142:  */