文档章节

Lua1.0 代码分析 hash.c

晓寒
 晓寒
发布于 2014/08/30 16:51
字数 1075
阅读 689
收藏 3

hash.c 代码分析

Lua 中最重要的一个数据结构及相关操作。

主要看下几个对外的接口。

/*
** Create a new hash. Return the hash pointer or NULL on error.
*/
Hash *lua_hashcreate (unsigned int nhash)
{
 Hash *t = new (Hash);
 if (t == NULL)
 {
  lua_error ("not enough memory");
  return NULL;
 }
 nhash(t) = nhash;
 markarray(t) = 0;
 nodelist(t) = newvector (nhash, Node*);
 if (nodelist(t) == NULL)
 {
  lua_error ("not enough memory");
  return NULL;
 }
 return t;
}

新建一个关联数组,入参是关联数组的大小。
新建一个关联数组。
设置大小。
打标记。
新建指针数组。

void lua_hashdelete (Hash *h);
释放关联数组。


/*
** If the hash node is present, return its pointer, otherwise create a new
** node for the given reference and also return its pointer.
** On error, return NULL.
*/
Object *lua_hashdefine (Hash *t, Object *ref)
{
 int h;
 Node *n;
 h = head (t, ref);
 if (h < 0) return NULL;
 n = present(t, ref, h);
 if (n == NULL)
 {
  n = new(Node);
  if (n == NULL)
  {
   lua_error ("not enough memory");
   return NULL;
  }
  n->ref = *ref;
  tag(&n->val) = T_NIL;
  n->next = list(t,h); /* link node to head of list */
  list(t,h) = n;
 }
 return (&n->val);
}

在关联数组中查看指定项是否存在,如果存在,返回它的指针。
如果不存在,新建一个结点,也同样返回它的指针。
返回关联引用在关联数组中的头。
跟据关联数组的头,查看引用在关联数组中是否存在:
如果不存在,新建一个结点,设置其引用为传入的参数,同时设置其值为空,把新建的结点插入到表头。
如果存在,直接返回它的值。

来看看 head 和 present 的实现:

static int head (Hash *t, Object *ref) /* hash function */
{
 if (tag(ref) == T_NUMBER) return (((int)nvalue(ref))%nhash(t));
 else if (tag(ref) == T_STRING)
 {
  int h;
  char *name = svalue(ref);
  for (h=0; *name!=0; name++) /* interpret name as binary number */
  {
   h <<= 8;
   h += (unsigned char) *name; /* avoid sign extension */
   h %= nhash(t); /* make it a valid index */
  }
  return h;
 }
 else
 {
  lua_reportbug ("unexpected type to index table");
  return -1;
 }
}

关联数组分为两个部分,数值部分和引用部分。
数值部分的下标是通过数值的大小和关联数组的大小取余得到的。
而引用部分目前只支持字符串类型。
字符串部分是通过一个算法得到它的散列值的。
具体算法是把字符串的 ASCII 码左移 8 位后相加之和与关联数组的大小取余。

再看 present 的实现

static Node *present(Hash *t, Object *ref, int h)
{
 Node *n=NULL, *p;
 if (tag(ref) == T_NUMBER)
 {
  for (p=NULL,n=list(t,h); n!=NULL; p=n, n=n->next)
   if (ref_tag(n) == T_NUMBER && nvalue(ref) == ref_nvalue(n)) break;
 }
 else if (tag(ref) == T_STRING)
 {
  for (p=NULL,n=list(t,h); n!=NULL; p=n, n=n->next)
   if (ref_tag(n) == T_STRING && streq(svalue(ref),ref_svalue(n))) break;
 }
 if (n==NULL) /* name not present */
  return NULL;
#if 0
 if (p!=NULL) /* name present but not first */
 {
  p->next=n->next; /* move-to-front self-organization */
  n->next=list(t,h);
  list(t,h)=n;
 }
#endif
 return n;
}

通过数组和下标找到相应的链表,在链表中查找是否有指定的值。如果有,返回结点,如果没有,返回空。

void lua_hashmark (Hash *h)
标记关联数组中所有的结点。

再看看 lua_next 的实现

void lua_next (void)
{
 Hash *a;
 Object *o = lua_getparam (1);
 Object *r = lua_getparam (2);
 if (o == NULL || r == NULL)
 { lua_error ("too few arguments to function `next'"); return; }
 if (lua_getparam (3) != NULL)
 { lua_error ("too many arguments to function `next'"); return; }
 if (tag(o) != T_ARRAY)
 { lua_error ("first argument of function `next' is not a table"); return; }
 a = avalue(o);
 if (tag(r) == T_NIL)
 {
  firstnode (a, 0);
  return;
 }
 else
 {
  int h = head (a, r);
  if (h >= 0)
  {
   Node *n = list(a,h);
   while (n)
   {
    if (memcmp(&n->ref,r,sizeof(Object)) == 0)
    {
     if (n->next == NULL)
     {
      firstnode (a, h+1);
      return;
     }
     else if (tag(&n->next->val) != T_NIL)
     {
      lua_pushobject (&n->next->ref);
      lua_pushobject (&n->next->val);
      return;
     }
     else
     {
      Node *next = n->next->next;
      while (next != NULL && tag(&next->val) == T_NIL) next = next->next;
      if (next == NULL)
      {
       firstnode (a, h+1);
       return;
      }
      else
      {
       lua_pushobject (&next->ref);
       lua_pushobject (&next->val);
      }
      return;
     }
    }
    n = n->next;
   }
   if (n == NULL)
    lua_error ("error in function 'next': reference not found");
  }
 }
}

在 Lua 脚本中调用 next 时调用的就是它。作用是数组遍历。
给定一个数组和引用,返回数组中给定引用的下一个结点。
如果给的是一个空值,返回数组的头一个结点。
否则返回数组中该值的下一个非空结点。
这里返回了两个值到 Lua 的脚本中。
看下自带的一个用到它的测试程序(array.lua):

a = @()
i=0
while i<10 do
 a[i] = i*i
 i=i+1
end
r,v = next(a,nil)
while r ~= nil do
 print ("array["..r.."] = "..v)
 r,v = next(a,r)
end

这个程序会打印出以下:
array[0] = 0
array[1] = 1
array[2] = 4
array[3] = 9
array[4] = 16
array[5] = 25
array[6] = 36
array[7] = 49
array[8] = 64
array[9] = 81

© 著作权归作者所有

晓寒
粉丝 35
博文 119
码字总数 133745
作品 0
海淀
私信 提问
Lua1.1 公开发布的第一版

Lua1.1 是官方公开发布的第一版,是事实上的第一版 ,也是最早发布的一版。 代码从这里 www.lua.org/ftp/lua-1.1.tar.gz 下载,事实上在 www.lua.org/versions.html 页面,有所有的可以下下载...

晓寒
2014/09/02
0
1
Lua1.0 代码分析 opcode.c

opcode.c 代码分析 Lua1.0 虚拟机的实现,语法分析中生成的字节码交给它 luaexecute 来执行。 这个文件的主要部分就是 luaexecute 函数,而它就是很大的 switch case,Lua1.0 中定义的字节码...

晓寒
2014/08/31
0
0
[讨论]php 排序系列的函数内部的C实现是用了哪种排序算法?

ext/standard/php_array.h https://github.com/php/php-src/blob/master/ext/standard/php_array.h 上面定义的排序函数: arsort -- 对数组进行逆向排序并保持索引关系 asort -- 对数组进行排...

justjavac
2013/08/16
163
1
Lua1.0 代码分析 inout.c

inout.c 代码分析 主要看下对于文件的处理 /*** Function to open a file to be input unit.** Return 0 on success or 1 on error.*/int lua_openfile (char *fn){ lua_linenumber = 1; lu......

晓寒
2014/08/28
0
0
Lua1.0 代码分析 table.c

table.c 代码分析 全局符号,常量,字符串,关联数组,文件列表的定义。 全局符号: 初始有 5 个基本的符号,Lua 预设的函数和库函数都注册在里面。 常量: 初始的几个常量是 Lua 中 type 的...

晓寒
2014/08/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

NIO基于长度域的报文在Netty下的解码

1, 先复习一下粘包/拆包 1.1, 粘包/拆包的含义 TCP是个“流”协议, 并不了解上层业务数据的具体含义, 它会根据TCP缓冲区的实际情况进行包的划分,所以在业务上认为,一个完整的包可能会被TCP...

老菜鸟0217
今天
8
0
从零开始搭建spring-cloud(2) ----ribbon

在微服务架构中,业务都会被拆分成一个独立的服务,服务与服务的通讯是基于http restful的。Spring cloud有两种服务调用方式,一种是ribbon+restTemplate,另一种是feign。 其实我们已经在上...

Vincent-Duan
今天
17
0
get和post的区别?

doGet:路径传参。效率高,安全性差(get的传送数据量有限制,不能大于2Kb) doPOST:实体传参。效率低,安全性好 建议: 1、get方式的安全性较Post方式要差些,包含机密信息的话,建议用Pos...

花无谢
昨天
4
0
当谈论迭代器时,我谈些什么?

当谈论迭代器时,我谈些什么? 花下猫语:之前说过,我对于编程语言跟其它学科的融合非常感兴趣,但我还说漏了一点,就是我对于 Python 跟其它编程语言的对比学习,也很感兴趣。所以,我一直...

豌豆花下猫
昨天
14
0
10天学Python直接做项目,我做了这5件事

初学者如何尽快上手python? 市面上关于如何学python的资料很多,但是讲的都太复杂。 我就是很简单的几句话,从小白到开发工程师,我只做了五件事。 我觉得任何商业计划书如果不能用几句话讲...

Python派森
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部