当前位置：首页 > 编程日记 > 正文

PHP源代码分析－字符串搜索系列函数实现详解

编程日记 2024-10-28 01:50:00

今天和同事在讨论关键字过虑的算法实现，前几天刚看过布隆过滤算法，于是就想起我们公司内部的查找关键字程序，好奇是怎么实现的。于是查找了一下源代码，原来可以简单地用stripos函数查找，
stripos原型如下：
int stripos ( string $haystack, string $needle [, int $offset] )
一般地都会建一个关键词库，然后把用户输入的内容作为haystack，然后循环遍历一下关键词库，把每个关键词作为needle，如果存在的话则会返回关键字在输入的内容中的位置。
于是查找了一下PHP源代码关于这个函数的实现，如果想知道一个函数在PHP的哪个模块的话可以简单写一个函数get_module. php

<?php

if(substr(php_sapi_name(),0,6)=='cli'){
    //命令行模式

    global $argv;
    $function = $argv[1];
}else{
       //网页方式

       $function = $_GET['name'];
}
$extensions = get_loaded_extensions();
foreach($extensions as $t){
    $modules_funcs = get_extension_funcs($t);
    if(in_array($function, (array)$modules_funcs)){
        $is_found = true;
        echo "$function is in $t module\n";
    }
}
if(!$is_found)echo "$function not found";

?>

字符串系列的函数属于PHP的标准模块，在ext/standard目录下，string.c 文件。

PHP_FUNCTION(stripos)
{
    char *found = NULL;
    char *haystack;
    int haystack_len;
    long offset = 0;
    char *needle_dup = NULL, *haystack_dup;
    char needle_char[2];
    zval *needle;

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "sz|l", &haystack, &haystack_len, &needle, &offset) == FAILURE) {
        return;
    }
        检查参数，第一第二个是必选参数，第三个是可选，|表示后面的参数都是可选的。

    if (offset < 0 || offset > haystack_len) {
        php_error_docref(NULL TSRMLS_CC, E_WARNING, "Offset not contained in string");
        RETURN_FALSE;
    }

    if (haystack_len == 0) {
        RETURN_FALSE;
    }

    haystack_dup = estrndup(haystack, haystack_len);
        //与大小写无关,所以先把字符全部转换成小写

    php_strtolower(haystack_dup, haystack_len);

    if (Z_TYPE_P(needle) == IS_STRING) {
               //第二个参数如果是字符串

        if (Z_STRLEN_P(needle) == 0 || Z_STRLEN_P(needle) > haystack_len) {
            efree(haystack_dup);
            RETURN_FALSE;
        }

        needle_dup = estrndup(Z_STRVAL_P(needle), Z_STRLEN_P(needle));
        php_strtolower(needle_dup, Z_STRLEN_P(needle));
                //这个是关键,由php_memnstr实现

        found = php_memnstr(haystack_dup + offset, needle_dup, Z_STRLEN_P(needle), haystack_dup + haystack_len);
    } else {
               //第二个参数是数字的话,则强制转换成(char)类型

        switch (Z_TYPE_P(needle)) {
            case IS_LONG:
            case IS_BOOL:
                needle_char[0] = tolower((char) Z_LVAL_P(needle));
                break;
            case IS_DOUBLE:
                needle_char[0] = tolower((char) Z_DVAL_P(needle));
                break;
            default:
                php_error_docref(NULL TSRMLS_CC, E_WARNING, "needle is not a string or an integer");
                efree(haystack_dup);
                RETURN_FALSE;
                break;

        }
        needle_char[1] = '\0';
        found = php_memnstr(haystack_dup + offset,
                            needle_char,
                            sizeof(needle_char) - 1,
                            haystack_dup + haystack_len);
    }

    efree(haystack_dup);
    if (needle_dup) {
        efree(needle_dup);
    }

    if (found) {
                //如何找到,则返回在这个字符串中的位置

        RETURN_LONG(found - haystack_dup);
    } else {
        RETURN_FALSE;
    }
}

查找函数是由php_memstr实现的,在main目录下的php.h文件
#define php_memnstr zend_memnstr

所以真正的函数是zend_memnstr,在zend/目录下面的zend_operators.h，

static inline char *
zend_memnstr(char *haystack, char *needle, int needle_len, char *end)
{
    char *p = haystack;
    char ne = needle[needle_len-1];

    end -= needle_len;

    while (p <= end) {
        if ((p = (char *)memchr(p, *needle, (end-p+1))) && ne == p[needle_len-1]) {
            if (!memcmp(needle, p, needle_len-1)) {
                return p;
            }
        }

        if (p == NULL) {
            return NULL;
        }

        p++;
    }

    return NULL;
}

查到这里就能看到实现搜索的原理了，主要用了一个while循环和两个C的函数memchr和memcmp。
先用第一个函数查找needle的第一个字符在haystack中出现的位置，然后调用memcmp，从这个位置开始比较needle和haystack，如果相同就返回这个位置，没有的话再把指针指向haystack的下一位再进行比较，一直到最后。
不过这个搜索只是简单地调用了memchr和memcmp函数，至于memcmp用了什么算法比较两个字符串就不太清楚，我们知道在一个长度为n的字符串里面查找字符串为m的字符串，那么最坏的时间复杂度是O(n*m)，上网搜了一下memcmp，不过没有找到他的实现原理。后来想了一下发现这个其实就是最简单的两次循环遍历进行比较。看了一下PHP的其他几个字符串查找函数strstr,stristr,strpos,strrpos,strripos 等函数都是调用zend_memnstr这个函数实现的，只是在返回的时候内容不同而已。

https://www.dkcj.cn/info/24956.html

麻省理工研究：深度图像分类器，居然还会过度解读

作者 | 青苹果来源 | 数据实战派某些情况下，深度学习方法能识别出一些在人类看来毫无意义的图像，而这些图像恰恰也是医疗和自动驾驶决策的潜在隐患所在。换句话说，深度图像分类器可以使用图像的边界，而非对象本身，以超…

编程日记2024/10/28 01:40:00

Oracle 查询转换之子查询展开

概念:子查询展开（Subquery Unnesting）是优化器处理带子查询的目标sql的一种优化手段，它是指优化器不再将目标sql中子查询当作一个独立的处理单元来单独执行，而是将该子查询转换为它自身和外部查询之间等价的表连接。这种等价连接转…

编程日记2024/10/28 01:30:00

Xcode中通过删除原先版本的程序来复位App

可以在Xcode菜单中点击 Product->Clean Build Folder (按住Option键,在windows键盘中是Alt键.) 此时Xcode将会从设备中删除(卸载uninstall)任何该app之前部署的版本. 接下来重启Xcode,再试一下,有时这可以修复非常奇怪(really weird)的问题.

编程日记2024/10/28 01:20:00

深入理解PHP之OpCode

OpCode是一种PHP脚本编译后的中间语言，就像Java的ByteCode,或者.NET的MSL。此文主要基于《 Understanding OPcode》和网络，根据个人的理解和修改，特记录下来 ：PHP代码： <?phpecho "Hello World";$a 1…

编程日记2024/10/28 01:10:00

关于 AIOps 的过去与未来，微软亚洲研究院给我们讲了这些故事

作者 | 贾凯强出品 | AI科技大本营（ID:rgznai100）在过去的15年里，云计算实现了飞速发展，而这种发展也为诸多的前沿技术奠定了基础，AIOps便在此环境中获得了良好的发展契机。在数字化转型的浪潮下，云计算已经…

编程日记2024/10/28 01:00:00

JS 正则表达式 0.001 ~99.999

^(0|[1-9][0-9]?)(\.[0-9]{0,2}[1-9])?$转载于:https://www.cnblogs.com/wahaha603/p/9050130.html

编程日记2024/10/28 00:50:00

深入浅出PHP(Exploring PHP)

一直以来，横观国内的PHP现状，很少有专门介绍PHP内部机制的书。呵呵，我会随时记录下研究的心得，有机会的时候，汇总成书。:) 今天这篇，我内心是想打算做为一个导论： PHP是一个被广泛应用的脚本语言…

编程日记2024/10/28 00:40:00

懒人神器！一个创意十足的 Python 命令行工具

作者 | 写代码的明哥来源 | Python编程时光当听到某些人说 xx 库非常好用的时候，我们总是忍不住想要去亲自试试。有一些库，之所以好用，是对一些库做了更高级的封闭，你装了这个库，就会附带装了 n 多依赖库，就…

编程日记2024/10/28 00:30:00

Regular Expression Matching

正则匹配 Regular Expression Matching Implement regular expression matching with support for . and *. . Matches any single character. * Matches zero or more of the preceding element.The matching should cover the entire input string (not partial).The functio…

编程日记2024/10/28 00:20:00

PI校正环节的程序实现推导过程

PI校正环节在经典控制论中非常有用，特别是对负反馈控制系统，基本上都有PI校正环节。1.下面分别说明比例环节和积分环节的作用，以阶跃信号为例。①比例环节单独作用以上分析说明，若只有比例环节的控制系统，阶跃响应也是…

编程日记2024/10/28 00:10:00

几行 Python 代码实现邮件解析，超赞~

作者 | Yunlor来源 | CSDN博客前言如何通过python实现邮件解析？邮件的格式十分复杂，主要是mime协议，本文主要是从实现出发，具体原理可以自行研究。一、安装通过mailgun开源的Flanker库实现邮件解析。该库包含了邮件地址解析和邮件…

编程日记2024/10/28 00:00:00

深入理解PHP原理之变量(Variables inside PHP)

或许你知道，或许你不知道，PHP是一个弱类型，动态的脚本语言。所谓弱类型，就是说PHP并不严格验证变量类型(严格来讲，PHP是一个中强类型语言,这部分内容会在以后的文章中叙述)，在申明一个变量的时候&#xff0…

编程日记2024/10/27 23:50:00

jQuery中的.height()、.innerHeight()和.outerHeight()

jQuery中的.height()、.innerHeight()和.outerHeight()和W3C的盒模型相关的几个获取元素尺寸的方法。对应的宽度获取方法分别为.width()、.innerWidth()和.outerWidth()，在此不详述。1. .height()获取匹配元素集合中的第一个元素的当前计算高度值或设置每一个匹配…

编程日记2024/10/27 23:40:00

Python实战之logging模块使用详解

用Python写代码的时候，在想看的地方写个print xx 就能在控制台上显示打印信息，这样子就能知道它是什么了，但是当我需要看大量的地方或者在一个文件中查看的时候，这时候print就不大方便了，所以Python引入了logging模块来…

编程日记2024/10/27 23:30:00

深入理解PHP原理之变量作用域

作者:laruence(http://www.laruence.com/)地址: http://www.laruence.com/2008/08/26/463.html PHP变量的内部表示是如何和用户脚本中的变量联系起来的呢？也就是说，如果我在脚本中写下：<?php $var"laruen…

编程日记2024/10/27 23:20:00

Azure AI的又一里程碑，Neural TTS新模型呈现真人般情感饱满的AI语音

在人与人之间的对话中，即使是同样的字句，也会因为所处情景和情感的不同而表现出丰富的抑扬顿挫，而这种动态性恰恰是各种AI合成语音的“软肋”。相比于人类讲话时丰富多变的语气，AI语音的“心平气和”往往给人带来明显的违和感。 …

编程日记2024/10/27 23:10:00

VS2010中“工具选项中的VC++目录编辑功能已被否决”解决方法

http://blog.csdn.net/chaijunkun/article/details/6658923 这是VS2010的改变，不能够在“工具-选项”中看到“VC目录”了。但是呢，我们可以在另外一个地方找到它，请看下边的对比照片。 VS2008中： VS2010中： 打开方式非…

编程日记2024/10/27 23:00:00

Bminer 7.0.0 ETH挖矿教程(Linux 64)

Bminer产品介绍Bminer是目前最快的挖矿程序，Bminer是基于NVIDIA GPU深度优化的挖矿软件。Bminer支持Equihash和Ethash两种算法的虚拟币，包括：ETH（以太坊)，ETC，ZEC（零币），…

编程日记2024/10/27 22:50:00

深入理解PHP原理之变量分离/引用(Variables Separation)

引自: http://www.laruence.com/ [风雪之隅 ]在前面的文章中我已经介绍了PHP的变量的内部表示(深入理解PHP原理之变量(Variables inside PHP))，以及PHP中作用域的实现机制(深入理解PHP原理之变量作用域(Scope inside PHP))。这节我们就接着前面的文章，继…

编程日记2024/10/27 22:40:00

C# 属性、索引

属性（property）: public string Name {get{return _name;}set{_name value;} } 简写为： public string Name { set; get;} 索引器（index）： 索引器为C#程序语言中泪的一种成员，它是的对象可…

编程日记2024/10/27 22:30:00

分享几段祖传的 Python 代码，拿来直接使用！

作者 | 周萝卜来源 | 萝卜大杂烩今天分享几段工作生活中常用的代码，都是最为基础的功能和操作，而且大多还都是出现频率比较高的，很多都是可以拿来直接使用或者简单修改就可以放到自己的项目当中日期生成很多时候我们需要批量生成日期&#xf…

编程日记2024/10/27 22:20:00

JVM——Java虚拟机架构

Java虚拟机（Java virtualmachine）实现了Java语言最重要的特征：即平台无关性。平台无关性原理：编译后的 Java程序（.class文件）由 JVM执行。JVM屏蔽了与具体平台相关的信息，使程序可以在多种平台…

编程日记2024/10/27 22:10:00

深入理解PHP之数组遍历

本文地址: http://www.laruence.com/2009/08/23/1065.html 经常会有人问我, PHP的数组, 如果用foreach来访问, 遍历的顺序是固定的么? 以什么顺序遍历呢? 比如: <?php$arr[laruence] huixinchen;$arr[yahoo] 2007;$arr[baidu] 2008;foreach ($arr as $key >…

编程日记2024/10/27 22:00:00

Github 年度最受欢迎的 TOP30 Python 项目，超值

作者 | 俊欣来源 | 关于数据分析与可视化今天小编整理归纳了2021年Github上面最受欢迎的30个Python项目，帮助大家在打磨技术与提升自我上面更进一步。通过代码来获取Github官网有开源的接口，因此数据的获取也就方便了许多，代码如下url https…

编程日记2024/10/27 21:50:00

Linux字符设备驱动程序的框架（新写法）

这是老版本内核的的Linux驱动注册函数写法： major register_chrdev(0, "hello", &hello_fops); /* (major, 0), (major, 1), ..., (major, 255)都对应hello_fops */ 新版本内核Linux驱动注册函数写法#define MAJOR(devid) ((unsigned int) ((devid…

编程日记2024/10/27 21:40:00

将一个普通的java项目转化为maven项目

在学习Spring事务时，我参考的书的源码不是maven项目，整本书依赖的100多个jar包都在一个文件夹里，我本来对spring每个模块的学习源码都放在一个Github仓库里，每一个项目都是maven项目，这样想要将项目转化为maven项目&am…

编程日记2024/10/27 21:30:00

深入理解PHP内存管理之谁动了我的内存

本文地址: http://www.laruence.com/2011/03/04/1894.html转载请注明出处首先让我们看一个问题: 如下代码的输出, var_dump(memory_get_usage());$a "laruence";var_dump(memory_get_usage());unset($a);var_dump(memory_get_usage()); 输出(在我的个人电脑上, 可能…

编程日记2024/10/27 21:20:00

蓝懿教育九月二十七日记录

将VIew移动做成动画效果这种动画效果没有中间的位移可以添加动画的View属性center，frame，alpha，transform , backgroundColor//继续做消失的动画[UIView animateWithDuration:1 animations:^{iv.alpha 0;} completion:^(BOOL finished) …

编程日记2024/10/27 21:10:00

新年快到了，让我们一起用 Python 编织中国结吧

作者 | FrigidWinter来源 | CSDN博客新年快到了，今天博主教大家用Python编织中国结~中国结的组成部分中国结是一种手工编织工艺品，它身上所显示的情致与智慧正是汉族古老文明中的一个侧面。因为其外观对称精致，可以代表汉族悠久的历史&#x…

编程日记2024/10/27 21:00:00

pwa+webpack，初探与踩坑

0.前言我们都知道pwa是一个新技术.，依靠缓存，离线了还能正常跑，而且秒开。我把以前原生写的小游戏迁移到react，再迁移到webpackreact，最后再升级到pwa。具体介绍不多说，我们开始撸吧。 1.webpack webpack攻…

编程日记2024/10/27 20:50:00

相关文章：