PHP  
 PHP: Test and Code Coverage Analysis
downloads | QA | documentation | faq | getting help | mailing lists | reporting bugs | php.net sites | links | my php.net 
 

LCOV - code coverage report
Current view: top level - ext/standard - levenshtein.c (source / functions) Hit Total Coverage
Test: PHP Code Coverage Lines: 50 52 96.2 %
Date: 2014-11-10 Functions: 3 3 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*
       2             :    +----------------------------------------------------------------------+
       3             :    | PHP Version 7                                                        |
       4             :    +----------------------------------------------------------------------+
       5             :    | Copyright (c) 1997-2014 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$ */
      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          50 : static zend_long reference_levdist(const char *s1, size_t l1, const char *s2, size_t l2, zend_long cost_ins, zend_long cost_rep, zend_long cost_del )
      31             : {
      32             :         zend_long *p1, *p2, *tmp;
      33             :         zend_long c0, c1, c2;
      34             :         size_t i1, i2;
      35             : 
      36          50 :         if (l1 == 0) {
      37           6 :                 return l2 * cost_ins;
      38             :         }
      39          44 :         if (l2 == 0) {
      40           2 :                 return l1 * cost_del;
      41             :         }
      42             : 
      43          42 :         if ((l1 > LEVENSHTEIN_MAX_LENGTH) || (l2 > LEVENSHTEIN_MAX_LENGTH)) {
      44           2 :                 return -1;
      45             :         }
      46          40 :         p1 = safe_emalloc((l2 + 1), sizeof(zend_long), 0);
      47          40 :         p2 = safe_emalloc((l2 + 1), sizeof(zend_long), 0);
      48             : 
      49         476 :         for (i2 = 0; i2 <= l2; i2++) {
      50         436 :                 p1[i2] = i2 * cost_ins;
      51             :         }
      52         438 :         for (i1 = 0; i1 < l1 ; i1++) {
      53         398 :                 p2[0] = p1[0] + cost_del;
      54             : 
      55        1536 :                 for (i2 = 0; i2 < l2; i2++) {
      56        1138 :                         c0 = p1[i2] + ((s1[i1] == s2[i2]) ? 0 : cost_rep);
      57        1138 :                         c1 = p1[i2 + 1] + cost_del;
      58        1138 :                         if (c1 < c0) {
      59         439 :                                 c0 = c1;
      60             :                         }
      61        1138 :                         c2 = p2[i2] + cost_ins;
      62        1138 :                         if (c2 < c0) {
      63         405 :                                 c0 = c2;
      64             :                         }
      65        1138 :                         p2[i2 + 1] = c0;
      66             :                 }
      67         398 :                 tmp = p1;
      68         398 :                 p1 = p2;
      69         398 :                 p2 = tmp;
      70             :         }
      71          40 :         c0 = p1[l2];
      72             : 
      73          40 :         efree(p1);
      74          40 :         efree(p2);
      75             : 
      76          40 :         return c0;
      77             : }
      78             : /* }}} */
      79             : 
      80             : /* {{{ custom_levdist
      81             :  */
      82           1 : static int custom_levdist(char *str1, char *str2, char *callback_name TSRMLS_DC)
      83             : {
      84           1 :         php_error_docref(NULL TSRMLS_CC, E_WARNING, "The general Levenshtein support is not there yet");
      85             :         /* not there yet */
      86             : 
      87           1 :         return -1;
      88             : }
      89             : /* }}} */
      90             : 
      91             : /* {{{ proto int levenshtein(string str1, string str2[, int cost_ins, int cost_rep, int cost_del])
      92             :    Calculate Levenshtein distance between two strings */
      93          53 : PHP_FUNCTION(levenshtein)
      94             : {
      95          53 :         int argc = ZEND_NUM_ARGS();
      96             :         char *str1, *str2;
      97             :         char *callback_name;
      98             :         size_t str1_len, str2_len, callback_len;
      99             :         zend_long cost_ins, cost_rep, cost_del;
     100          53 :         zend_long distance = -1;
     101             : 
     102          53 :         switch (argc) {
     103             :                 case 2: /* just two strings: use maximum performance version */
     104          37 :                         if (zend_parse_parameters(2 TSRMLS_CC, "ss", &str1, &str1_len, &str2, &str2_len) == FAILURE) {
     105           1 :                                 return;
     106             :                         }
     107          36 :                         distance = reference_levdist(str1, str1_len, str2, str2_len, 1, 1, 1);
     108          36 :                         break;
     109             : 
     110             :                 case 5: /* more general version: calc cost by ins/rep/del weights */
     111          14 :                         if (zend_parse_parameters(5 TSRMLS_CC, "sslll", &str1, &str1_len, &str2, &str2_len, &cost_ins, &cost_rep, &cost_del) == FAILURE) {
     112           0 :                                 return;
     113             :                         }
     114          14 :                         distance = reference_levdist(str1, str1_len, str2, str2_len, cost_ins, cost_rep, cost_del);
     115          14 :                         break;
     116             : 
     117             :                 case 3: /* most general version: calc cost by user-supplied function */
     118           1 :                         if (zend_parse_parameters(3 TSRMLS_CC, "sss", &str1, &str1_len, &str2, &str2_len, &callback_name, &callback_len) == FAILURE) {
     119           0 :                                 return;
     120             :                         }
     121           1 :                         distance = custom_levdist(str1, str2, callback_name TSRMLS_CC);
     122           1 :                         break;
     123             : 
     124             :                 default:
     125           1 :                         WRONG_PARAM_COUNT;
     126             :         }
     127             : 
     128          51 :         if (distance < 0 && /* TODO */ ZEND_NUM_ARGS() != 3) {
     129           2 :                 php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument string(s) too long");
     130             :         }
     131             : 
     132          51 :         RETURN_LONG(distance);
     133             : }
     134             : /* }}} */
     135             : 
     136             : /*
     137             :  * Local variables:
     138             :  * tab-width: 4
     139             :  * c-basic-offset: 4
     140             :  * End:
     141             :  * vim600: sw=4 ts=4 fdm=marker
     142             :  * vim<600: sw=4 ts=4
     143             :  */

Generated by: LCOV version 1.10

Generated at Mon, 10 Nov 2014 22:46:49 +0000 (9 days ago)

Copyright © 2005-2014 The PHP Group
All rights reserved.