当前位置: 首页 > Database, postgresql > 正文

二叉树关键字查找

postgresql 中二叉树查找关键字的算法 src/backend/parser/kwlookup.c

关键字的存储结构

    typedef struct ScanKeyword
    {
	    const char *name;
	    int			value;
        ...
        ... 其他结构
    } ScanKeyword;

将所有的关键字按照字符顺序排列成为一个数组

    static const ScanKeyword ScanCKeywords[] = {
	    {"VARCHAR", VARCHAR},
	    {"auto", S_AUTO},
	    {"bool", SQL_BOOL},
	    {"char", CHAR_P},
	    {"const", S_CONST},
	    {"enum", ENUM_P},
	    {"extern", S_EXTERN},
	    {"float", FLOAT_P}
        ... //所有的关键字
    }

查找函数

    const ScanKeyword *
    ScanKeywordLookup(const char *text,
		      const ScanKeyword *keywords,
		      int num_keywords)
    {
	    int		       len,
			       i;
	    char	       word[NAMEDATALEN];
	    const ScanKeyword *low;
	    const ScanKeyword *high;

	    len = strlen(text);
	    if (len >= NAMEDATALEN)
		    return NULL;
	    //如果需要查找的关键字比最长的关键字还要长,很明显,不用找了

	    for (i = 0; i < len; i++)
	    {
		    char		ch = text[i];

		    if (ch >= 'A' && ch <= 'Z')
			    ch += 'a' - 'A';
		    word[i] = ch;
	    }
	    word[len] = '\0';
	    //将关键字转换为大写

	    low = keywords;
	    high = keywords + (num_keywords - 1);
	    while (low <= high)
	    {
		    const ScanKeyword *middle;
		    int			difference;

		    middle = low + (high - low) / 2;
		    difference = strcmp(middle->name, word);
		    if (difference == 0)
			    return middle;
		    else if (difference < 0)
			    low = middle + 1;
		    else
			    high = middle - 1;
	    }
            //二叉树查找

	    return NULL;
    }

怎么样,是不是平时使用的算法弱爆了?

    分享到:

本文固定链接: http://klwang.info/keywords-search-use-btree/ | 数据库|Linux|软件开发

该日志由 klwang 于2014年02月24日发表在 Database, postgresql 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 二叉树关键字查找 | 数据库|Linux|软件开发

二叉树关键字查找:等您坐沙发呢!

发表评论

*
快捷键:Ctrl+Enter