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-07-23 Functions: 3 3 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.10

Generated at Wed, 23 Jul 2014 19:58:40 +0000 (12 hours ago)

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