write by 九天雁翎(JTianLing) -- blog.csdn.net/vagrxie
讨论新闻组及文件
C语言中没有标准的容器,所以为了跨平台,Orx中自己实现了一套。
在Orx中作者分别实现了HashTable,List,Tree3个容器,虽然没有实现一个自己的String,但是为orxSTRING(实际为char*的typedef)实现了一堆的辅助函数。
下面分别来看看,为了不使本文成为一个类似algorithm in C的讲算法的文章,这里只看看使用和各容器的特性^^
List
以前有人说过,几乎每个程序员在职业生涯都会自己实现一个List,不知道是不是真这样,虽然我的确实现过。。。。。。。。。。
先看结构:
/*
* Node list structure
*/
typedef
struct
__orxLINKLIST_NODE_t
{
struct
__orxLINKLIST_NODE_t *pstNext; /*
*< Next node pointer : 4
*/
struct
__orxLINKLIST_NODE_t *pstPrevious; /*
*< Previous node pointer : 8
*/
struct
__orxLINKLIST_t *pstList; /*
*< Associated list pointer : 12
*/
} orxLINKLIST_NODE;
/*
* List structure
*/
typedef
struct
__orxLINKLIST_t
{
orxLINKLIST_NODE *pstFirst; /*
*< First node pointer : 4
*/
orxLINKLIST_NODE *pstLast;/*
*< Last node pointer : 8
*/
orxU32 u32Counter; /*
*< Node counter : 12
*/
} orxLINKLIST;
从结构看,我感觉实现的有些特殊,我以前看到的一般的list实现(自然是指C语言中的)一般用一个结构就解决一切了,都是用list的node本身(一般是头结点)来表示一个list,Orx这里额外特别的抽象出了一个List结构,然后node还反过来有指针指向list,有点奇怪的是,没有看到数据存在哪里。。。。。。。。。。。然后,突然发现,我没有看到list的Create函数。。。。。。。。看了一下Orx对List的使用,原来都是直接使用orxLINKLIST
。。。。。。。。。。。。
再然后,没有地方存储数据(比如类似pData的指针)的疑惑也解开了。。。。。。所有使用这个list的地方都用一个以orxLINKLIST_NODE
为第一个成员变量的结构,然后node的指针,就相当于整个结构的指针了。。。。。。。。。。。。。
比如下面这个config的结构:
typedef struct __orxCONFIG_SECTION_t
{
orxLINKLIST_NODE stNode; /**< List node : 12 */
orxBANK *pstEntryBank; /**< Entry bank : 16 */
orxSTRING zName; /**< Section name : 20 */
orxU32 u32ID; /**< Section ID (CRC) : 24 */
orxU32 u32ParentID; /**< Parent ID (CRC) : 28 */
orxS32 s32ProtectionCounter; /**< Protection counter : 32 */
orxLINKLIST stEntryList; /**< Entry list : 44 */
orxPAD(44)
} orxCONFIG_SECTION;
谜底解开了,总的来说,这个List很诡异。。。。。。。。。。。。
HashTable
一个HashTable容器拥有O(1)的查找效率,被誉为20世纪最重要的编程领域发明之一。。。。。(不记得在哪看到的了)
先看看结构:
#define orxHASHTABLE_KU32_INDEX_SIZE 256
/*
* Hash table cell definition.
*/
typedef
struct
__orxHASHTABLE_CELL_t
{
orxU32 u32Key; /*
*< Key element of a hash table : 4
*/
void
*pData;/*
*< Address of data : 8
*/
struct
__orxHASHTABLE_CELL_t *pstNext;/*
*< Next cell with the same index : 12
*/
orxPAD(12
)
} orxHASHTABLE_CELL;
/*
* Hash Table
*/
struct
__orxHASHTABLE_t
{
orxHASHTABLE_CELL *apstCell[orxHASHTABLE_KU32_INDEX_SIZE]; /*
*< Hash table
*/
orxBANK *pstBank;/*
*< Bank where are stored cells
*/
orxU32 u32Counter; /*
*< Hashtable item counter
*/
};
每个hashTable的数据自然是一个cell,存储在pData中,通过注释基本也能理解Orx的Hash table的结构了。
所有的数据通过apstCell[orxHASHTABLE_KU32_INDEX_SIZE];
数组来存储,并且通过某个较小的key(说明这个较小的key一定小于orxHASHTABLE_KU32_INDEX_SIZE
)来索引这个数据,假如有第一个较小的key冲突的情况,通过orxHASHTABLE_CELL
的*pstNext
变量来保存成链状,并通过u32Key
这个32位的key来区别。这个结构与一般C++ STL扩展中的hashTable实现原理基本一样。(HashTable目前还不是C++标准库的内容,所以只在扩展库中存在)
谁说看结构比看流程清晰来着?说的实在是太对了。当结构是这样定的时候,流程还能玩出啥花来?
用下面这样的代码来测试一下,同时验证想法。
orxHASHTABLE* hashTable = orxHashTable_Create(32
, orxHASHTABLE_KU32_FLAG_NONE, orxMEMORY_TYPE_MAIN);
char
* firstKey = "FirstKey"
;
char
* secondKey = "secondKey"
;
char
* thirdKey = "thirdKey"
;
orxHashTable_Add(hashTable, orxString_ToCRC(firstKey), firstKey);
orxHashTable_Add(hashTable, orxString_ToCRC(secondKey), secondKey);
orxHashTable_Set(hashTable, orxString_ToCRC(firstKey), secondKey);
orxHashTable_Set(hashTable, orxString_ToCRC(thirdKey), thirdKey);
char
* value = (char
*)orxHashTable_Get(hashTable, orxString_ToCRC(firstKey));
orxHashTable_Delete(hashTable);
printf("Value:
%s
"
, value);
解释:
orxHashTable_Create实际仅仅分配了内存而已。值得一提的仅仅是cell的内存使用上一节
提到的bank来分配的。
orxString_ToCRC用于将string进行CRC,没有啥好说的。只是不知道Orx的这个CRC效果怎么样,比如速度快不快,冲突几率高不高。
orxHashTable_Add中先判断是否有同样key的数据存在,存在的话会报错。
其中调用的下列函数非常关键,用于获取前面提到的较小的key,来合成数组的索引。原来就是取CRC出来的32位值的与orxHASHTABLE_KU32_INDEX_SIZE
匹配的低位而已。(虽然这里用取模会意思更加自然一些,但是一个取模操作比一个位操作慢的不是一点点)
static
orxINLINE orxU32 orxHashTable_FindIndex(const
orxHASHTABLE *_pstHashTable, orxU32 _u32Key)
{
/*
Checks
*/
orxASSERT(_pstHashTable != orxNULL);
/*
Computes the hash index
*/
return
(_u32Key & (orxHASHTABLE_KU32_INDEX_SIZE - 1
));
}
找到位置以后的操作就太自然了。
/*
Get the hash table index
*/
u32Index = orxHashTable_FindIndex(_pstHashTable, _u32Key);
/*
Allocate a new cell if possible
*/
pstCell = (orxHASHTABLE_CELL *)orxBank_Allocate(_pstHashTable->pstBank);
/*
If allocation succeed, insert the new cell
*/
if
(pstCell != orxNULL)
{
/*
Set datas
*/
pstCell->u32Key = _u32Key;
pstCell->pData = _pData;
pstCell->pstNext = _pstHashTable->apstCell[u32Index];
/*
Insert it
*/
_pstHashTable->apstCell[u32Index] = pstCell;
eStatus = orxSTATUS_SUCCESS;
/*
Updates counter
*/
_pstHashTable->u32Counter++;
}
由于iarwain的注释存在,我更加没有必要说太多了。值得一提的是可以看到这里面甚至没有判断这个数组索引所在的位置是否已经被占,然后进行冲突处理的操作。
原因在于先
pstCell->pstNext = _pstHashTable->apstCell[u32Index];
然后
_pstHashTable->apstCell[u32Index] = pstCell;
假如原来此位置为空,next也就是空了,假如原来此位置有原来的值(甚至可以是一个链),就将整个链接在现在新数据的后面。
然后看set函数:
/*
Traverse to find the key
*/
pstCell = _pstHashTable->apstCell[u32Index];
while
(pstCell != orxNULL && pstCell->u32Key != _u32Key)
{
/*
Try with next cell
*/
pstCell = pstCell->pstNext;
}
/*
Cell found ?
*/
if
(pstCell != orxNULL)
{
/*
Set associated datas
*/
pstCell->pData = _pData;
}
else
{
/*
Allocate a new cell if possible
*/
pstCell = (orxHASHTABLE_CELL *)orxBank_Allocate(_pstHashTable->pstBank);
/*
If allocation succeed, insert the new cell
*/
if
(pstCell != orxNULL)
{
/*
Set datas
*/
pstCell->u32Key = _u32Key;
pstCell->pData = _pData;
pstCell->pstNext = _pstHashTable->apstCell[u32Index];
/*
Insert it
*/
_pstHashTable->apstCell[u32Index] = pstCell;
}
}
/*
Done!
*/
return
orxSTATUS_SUCCESS;
用于在此数组位置进行进一步的索引,找到32位key完全一致的值。
while
(pstCell != orxNULL && pstCell->u32Key != _u32Key)
{
/*
Try with next cell
*/
pstCell = pstCell->pstNext;
}
而
/*
Cell found ?
*/
if
(pstCell != orxNULL)
{
/*
Set associated datas
*/
pstCell->pData = _pData;
}
else
{
.....
}
则完美回答了我博客中以前评论中的踢出来的问题,当hashTable 进行Set的时候,假如原来这个Key不存在会进行什么操作,很明显,不存在就Add。
到了这里,Get,Delete函数我感觉已经没有太多讲的必要了,只要对hashTable的概念还算熟悉的,对Orx的hashtable应该有足够的了解了,无论是实现的原理还是效率。
我小结一下:
1、Orx的HashTable定死了apstCell[orxHASHTABLE_KU32_INDEX_SIZE]这个数组的大小,orxHASHTABLE_KU32_INDEX_SIZE
等于256,所以,很自然的,此hashTable
在数量较小的时候才能保持较高的效率,(即HashTable的理论值O(1))假如数量远远超过256,那么查询效率几乎接近线性效率O(n)。
2、Orx这里的索引完全依赖于其String的32位CRC计算,但是很遗憾的,CRC的计算时会有冲突的,也就是会出现两个不同String但是计算出同样CRC的情况,我没有仔细了解这个CRC的计算,但是将整个HashTable的基础建立在这个不稳定的基石上,总的来说已经说明了这个HashTable存在问题。。。。。。。。。。。。。
Orx的HashTableKey是建立在String上的,为了提高String的比较效率,所以对String进行了CRC,效率是高了,但是引发了第2点说的问题。
但是这里其实不是没有解决方案的。
1。高效的方案:如暴雪的MPQ那样,不以一个CRC来决定一切,额外用2个来做保险,也就是进行3次不同的CRC运算,同时比较3个CRC都一样时才能确定一个真正的数据位置。此方法比Orx的方法多2次CRC计算,并且多2次整数比较,但是出错几率会比Orx的低的多。(在实际中,就算到几十万这个等级,我也没有碰到过3个CRC同时冲突)
2。而作为对比,C++中实现的hashTable(可以参考VS或者boost的hashMap实现),由于模板的存在,可以使用任何东西作为key,同时,在第一次快速索引时,使用一个hash值,当hash值冲突后,完全使用原来的key来进行比较,虽然假如是字符串的话会稍微慢一点,但是起码能保证绝对无错。
Tree
还是先看结构:
/*
* Tree node structure
*/
typedef
struct
__orxTREE_NODE_t
{
struct
__orxTREE_NODE_t *pstParent; /*
*< Parent node pointer : 4
*/
struct
__orxTREE_NODE_t *pstChild;/*
*< First child node pointer : 8
*/
struct
__orxTREE_NODE_t *pstSibling;/*
*< Next sibling node pointer : 12
*/
struct
__orxTREE_t *pstTree; /*
*< Associated tree pointer : 16
*/
} orxTREE_NODE;
/*
* Tree structure
*/
typedef
struct
__orxTREE_t
{
orxTREE_NODE *pstRoot;/*
*< Root node pointer : 4
*/
orxU32 u32Counter; /*
*< Node counter : 8
*/
} orxTREE;
看到结构的时候,从list的诡异中我诡异的理解了这个Tree的意思,也就是,这个tree的用法也和list类似了。。。。。。。。。。。。
我虽然以前学习数据结构的时候是以伪码和C++的实现为主,没有看过太多C语言实现的数据结构,但还真不是完全没有见过,我感觉Orx的实现是很诡异的。。。。。。使用方式也是在算不上正统,为了求证,以防止是因为自己的孤陋寡闻引起的笑话,特意求证glib实现。。。。。。
比如GList
typedef
struct
_GList GList;
struct
_GList
{
gpointer data;
GList *next;
GList *prev;
};
一看到结构。。。。。。。。。。。。我大呼。。。。。数据结构的书籍还是没有骗我的啊。。。。。。。。。。。。。。。。。诡异的还是Orx。。。。。。。。。哪有需要自己一定要用一个新结构来包含Node来用一个list/tree的话。。。。。我要保存一个整数怎么办?。。。。。。。。简单的说,Orx的这个容器实现的非主流,不推荐大家使用及学习。。。。我这里也仅仅为了了解Orx的源代码而看看吧。。。。。。。。
原创文章作者保留版权 转载请注明原作者 并给出链接
write by 九天雁翎(JTianLing) -- blog.csdn.net/vagrxie
分享到:
相关推荐
非典型2D游戏引擎 Orx 源码 收集完整的 源码包
ORX源码,这是学习2D游戏引擎必不可少的一道大餐
声音,图形,物理,输入处理等等可以由Orx用C语言处理,而游戏逻辑则用OCaml编写。 这些绑定根据获得。 要求 奥克斯 您将需要一个有效的Orx版本。 正式的包含有关在系统上安装Orx及其依赖项的说明。 确保$ORX环境...
Orx是一款轻便,轻巧,基于插件,数据驱动且非常易于使用的面向2D的游戏引擎。 由于orx是数据驱动的,因此它允许用户使用少量的代码行来创建游戏,并大大减少了开发时间。
C#实现类似淘宝图片局部放大功能源码,测试能用
Orx( )是一个开源的,可移植的,轻量级的,基于插件的,数据驱动的并且非常易于使用的面向2D的游戏引擎。 Orx为游戏开发提供了完整的框架,目前可在Windows(mingw和使用Visual Studio的本机),Linux(x86 / x86...
包装器包括两个部分: 低层包装器,每个ORX C标头基本上具有一个Nim模块,其中将近80个。 所有这些都被命名为o-xxx,例如oinput或oobject 。 每个低级包装器具有一个Nim模块的高级包装器。 当前,每个高级包装器也...
2017年java源码java-Order-System-Utility ORX Build 2.0 Beta ORX是一个简单,可移植但功能有限的订购系统。 Jentzen Paolo Ancheta Javier版权所有(C)2017 ORX绝对不提供保修。 这是一个免费软件,出于教育目的...
Suz-OrX-archive-refs-heads-master.zip
什么是ORx? ORx的名称为“ Oh-Rex”,代表Outernet ReceiverX。“ X”代表自制设备。支持的设备和配置请注意,Raspberry Pi v1是目前唯一受支持的版本。 v2具有不支持的ARM v7处理器。 此存储库中的脚本支持以下...
TexturePacker 4.3.1 x64、X86完美破解,破解步骤简单,已经验证完美破解可用
欧罗调色板用于HTML颜色的定义。... 包含之后,您可以通过@Colors.MediumOrchid直接引用颜色名称。... 当您的编辑器支持颜色的可视化并且您可以原型化而无需使用颜色选择器工具切换到绘画程序时,这是很好的。
rewrite 2.0 32位 64位,方便大家安装IIS的URL重写环境
htop工具安装源码; Htop是Linux系统中的一个互动的进程查看器,一个文本模式的应用程序(在控制台orX终端中),需要ncurses。与Linux传统的top相比,htop更加人性化。它可以让用户交互式操作,支持颜色主题,可横向...
(2)进入 U-Boot源码目录 #cd u-boot-1.3.1 (3)创建自己的开发板: #cd board #cp smdk2410 fs2410 –a #cd fs2410 #mv smdk2410.c fs2410.c #vi Makefile (将 smdk2410修改为 fs2410) #cd ../../...
Risk Taxonomy Risk Taxonomy Risk Taxonomy
win2008以上的服务器IIS设置URL规则组件,伪静态规则设置
20-向脚本传递参数.pdf shell编程
matlab中拟合中心线的代码关于OrX程序的注意事项: 最初由SR Kiihne撰写,2004年2月24日 定向的MAS nmr光谱 我最初是在来自Bruker实验的光谱上对此进行测试的:jr0203#22-26这些是31P MAS光谱,其自旋速率为500-...
Pa Pb RS功率计算de-boosting计算工具