Cocos2d

爱蓝斯 2013-11-24

展开全文

在引擎开发中，通过名称或索引快速找到所对应的节点，资源，物体是最最基础的算法需求。如何更高效的满足引擎灵活的存储与查询需求，是任何一款引擎要考虑的问题，在诸多款开源或商业引擎中，都有过为了解决此类需求而专门设计的模版类或容器，它们通常被称为“词典”或“字典”。

我们在Cocos2d-x中的很多地方也遇到过词典类CCDictionary。它是利用哈希表算法来进行CCObject管理的一个类。学习它可以让我们对于Cocos2d-x的内部管理机制有更清晰的认识。同时也可以学习这种思想，帮助我们在以后的项目开发中设计出更棒的管理器架构。

CCDictionary中的元素是通过哈希表进行存储的，这个哈希表算法是放在uthash.h中的。其封装了大量的宏来进行相应的哈希表处理。

通过HASK_MAK_TABLE宏来创建一个原始的哈希表。默认的存储空间为32。这个数值是由宏HASH_INITIAL_NUM_BUCKETS定义的。每次往里面插入元素时会判断存储空间是否足够，如果不足会扩展为原来的2倍大小的内存空间，并将原来的哈希表数据放入其中。

其中比较重要的一些宏:

HASH_MAKE_TABLE:建立一个哈希表。

HASH_ADD:将元素放入哈希表。

HASH_FIND:查找元素。

HASH_FIND_STR: 通过名称字符串查询哈希表中的相应词汇。

HASH_FIND_INT: 通过索引查询哈希表中的相应词汇。

HASH_DELETE：从哈希表中删除元素。

HASH_EXPAND_BUCKETS: 扩展为原来的2倍大小的内存空间，并将原来的哈希表数据放入其中。

首先来看CCDictionary.h:

#ifndef __CCDICTIONARY_H__
#define __CCDICTIONARY_H__
//需要哈希表的支持
#include "support/data_support/uthash.h"
#include "CCObject.h"
#include "CCArray.h"
#include "CCString.h"
//Cocos2d命名空间
NS_CC_BEGIN
//声明一下CCDictionary类，因为CCDictElement要用到CCDictionary指针。
class CCDictionary;
//词典元素，或者简单理解就是词典中的一个词汇。我们从小查词典都知道，通过词汇名称或索引查找到对应的解释。解释与词汇名称或索引之间是一一对应的关系。与这种关系相同，在这个词汇类中存储一个字符串名称或一个索引以及与其相应的CCObject指针，这个CCObject指针就相当于是我们查出来的解释一样与字符串名称或索引构成了对应关系。
class CC_DLL CCDictElement
{
//定义字符串名称的长度.
#define MAX_KEY_LEN 256
public:
//构造函数。
//参1:字符串名称。
//参2:对应的CCObject指针。
CCDictElement(const char* pszKey, CCObject* pObject)
{
//初始化。
init();
m_pObject = pObject;
//
const char* pStart = pszKey;
//字符串的字节长度
int len = strlen(pszKey);
if (len > MAX_KEY_LEN )
{ //如果长度大于MAX_KEY_LEN，截取后面MAX_KEY_LEN长度字符串。
char* pEnd = (char*)&pszKey[len-1];
pStart = pEnd - (MAX_KEY_LEN-1);
}
//字符串COPY
strcpy(m_szKey, pStart);
}
//构造函数
//参1:所在哈希表中的索引
//参2:对应的CCObject指针。
CCDictElement(int iKey, CCObject* pObject)
{
init();
m_iKey = iKey;
m_pObject = pObject;
}
//取得名称字符串。
inline const char* getStrKey() const
{
CCAssert(m_szKey[0] != '\0', "Should not call this function for integer dictionary");
return m_szKey;
}
//取得哈希索引。
inline int getIntKey() const
{
CCAssert(m_szKey[0] == '\0', "Should not call this function for string dictionary");
return m_iKey;
}
//取得CCObject指针。
inline CCObject* getObject() const
{
return m_pObject;
}
private:
//初始化。
inline void init()
{
m_iKey = 0;
m_pObject = NULL;
memset(m_szKey, 0, sizeof(m_szKey));
memset(&hh, 0, sizeof(hh));
}
private:
char m_szKey[MAX_KEY_LEN+1]; //存储名称的字符数组。
int m_iKey; //哈希表索引
CCObject* m_pObject; //哈希值（CCObject指针）
public:
UT_hash_handle hh; //哈希表结构指针
friend class CCDictionary; //词典为友元类
};
//遍历词典中的所有词汇的一个宏，它内部调用HASH_ITER来进行for循环遍历链表。
#define CCDICT_FOREACH(__dict__, __el__) \
CCDictElement* pTmp##__dict__##__el__ = NULL; \
HASH_ITER(hh, (__dict__)->m_pElements, __el__, pTmp##__dict__##__el__)
//词典类，由CCObject派生
class CC_DLL CCDictionary : public CCObject
{
public:
//构造函数
CCDictionary();
//析构函数
~CCDictionary();
//取得所有词汇的数量。
unsigned int count();
//返回所有的查询关键字。
CCArray* allKeys();
//取得对应CCObject指针的所有关键字或索引值。
CCArray* allKeysForObject(CCObject* object);
//通过查询关键字取得对应CCObject指针
CCObject* objectForKey(const std::string& key);
//通过哈希索引值取得对应CCObject指针
CCObject* objectForKey(int key);
//通过查询关键字取得对应CCString指针
const CCString* valueForKey(const std::string& key);
//通过哈希索引值取得对应CCString指针
const CCString* valueForKey(int key);
//设置一个CCObject和对应的名称存入词典。
void setObject(CCObject* pObject, const std::string& key);
//设置一个CCObject和对应的哈希索引存入词典。
void setObject(CCObject* pObject, int key);
//按照查询关键字找到对应CCObject并删除。
void removeObjectForKey(const std::string& key);
//按照哈希索引找到对应CCObject并删除。
void removeObjectForKey(int key);
//按照容器中的查询关键字找到对应CCObject并删除。
void removeObjectsForKeys(CCArray* pKeyArray);
//从词典中删除相应的词汇。
void removeObjectForElememt(CCDictElement* pElement);
//从词典中清空所有的词汇。
void removeAllObjects();
//重载CCObject的拷贝函数。产生一个一模一样的词典。
virtual CCObject* copyWithZone(CCZone* pZone);
//静态函数，取得单例的词典。请改用create函数，因为这个函数以后将被删除掉。
CC_DEPRECATED_ATTRIBUTE static CCDictionary* dictionary();
//静态函数，取得一个指定词典的COPY，请改用createWithDictionary函数，因为这个函数以后将被删除掉。
CC_DEPRECATED_ATTRIBUTE static CCDictionary* dictionaryWithDictionary(CCDictionary* srcDict);
//静态函数:从一个plist文件中加载词典内容。此函数创建的词典是交由内存管理器来进行资源计数的，不需手动release。但请改用createWithContentsOfFile函数，因为这个函数以后也将被删除掉。
CC_DEPRECATED_ATTRIBUTE static CCDictionary* dictionaryWithContentsOfFile(const char *pFileName);
//静态函数：从一个plist文件中加载词典内容，但此函数是多线程安全的，另外此函数创建的词典需要手动release。请改用 createWithContentsOfFileThreadSafe函数，因为这个函数以后也将被删除掉。
CC_DEPRECATED_ATTRIBUTE static CCDictionary* dictionaryWithContentsOfFileThreadSafe(const char *pFileName);
//静态函数，创建一个新词典
static CCDictionary* create();
//静态函数，取得一个指定词典的COPY。
static CCDictionary* createWithDictionary(CCDictionary* srcDict);
//静态函数:从一个plist文件中加载词典内容。
static CCDictionary* createWithContentsOfFile(const char *pFileName);
//静态函数：从一个plist文件中加载词典内容，但此函数是多线程安全的，另外此函数创建的词典需要手动release。
static CCDictionary* createWithContentsOfFileThreadSafe(const char *pFileName);
private:
//将CCObject实例指针与对应的字符串名称存入哈希表。
void setObjectUnSafe(CCObject* pObject, const std::string& key);
//将CCObject实例指针与对应的索引值存入哈希表。
void setObjectUnSafe(CCObject* pObject, const int key);
public:
//词汇的哈希表头部结构指针。
CCDictElement* m_pElements;
private:
//词典查询类型。
enum CCDictType
{
kCCDictUnknown = 0,
kCCDictStr,//字符串名称
kCCDictInt //索引
};
CCDictType m_eDictType; //当前词典查询类型。一个词典实例要求只有一种固定词典查询类型。
CCDictType m_eOldDictType; //上次词典查询类型。这个变量是用来比对是否改变了词典查询类型。
};
NS_CC_END

复制代码

再看CCDictionary.cpp:

#include "CCDictionary.h"
#include "CCString.h"
#include "CCInteger.h"
using namespace std;
//使用Cocos2d命名空间
NS_CC_BEGIN
//构造函数
CCDictionary::CCDictionary()
: m_pElements(NULL)
, m_eDictType(kCCDictUnknown)
, m_eOldDictType(kCCDictUnknown)
{
}
//析构函数。
CCDictionary::~CCDictionary()
{
//请空词汇，释放所有词汇占用的内存。
removeAllObjects();
}
//取得词典中的所有词汇数量。
unsigned int CCDictionary::count()
{
//通过HASH_CONT宏来取得哈希表的元素数量。
return HASH_COUNT(m_pElements);
}
//返回所有的查询关键字。
CCArray* CCDictionary::allKeys()
{
//取得词汇的数量
int iKeyCount = this->count();
if (iKeyCount m_szKey);
pOneKey->autorelease();
pArray->addObject(pOneKey);
}
}
else if (m_eDictType == kCCDictInt)
{ //如果当前词典查询类型是通过索引。
//遍历所有词汇。
HASH_ITER(hh, m_pElements, pElement, tmp)
{
//取得每一个词汇的名称字符串放入CCArray中。
CCInteger* pOneKey = new CCInteger(pElement->m_iKey);
pOneKey->autorelease();
pArray->addObject(pOneKey);
}
}
return pArray;
}
//取得对应CCObject指针的所有关键字或索引值。
CCArray* CCDictionary::allKeysForObject(CCObject* object)
{
//取得词汇的数量
int iKeyCount = this->count();
if (iKeyCount m_pObject)
{
//如果与指定的词汇相同，将其名称字符串放入CCArray中。
CCString* pOneKey = new CCString(pElement->m_szKey);
pArray->addObject(pOneKey);
pOneKey->release();
}
}
}
else if (m_eDictType == kCCDictInt)
{ //如果当前词典查询类型是通过索引。
//遍历所有词汇。
HASH_ITER(hh, m_pElements, pElement, tmp)
{
//如果与指定的词汇相同，将其名称字符串放入CCArray中。
if (object == pElement->m_pObject)
{
CCInteger* pOneKey = new CCInteger(pElement->m_iKey);
pArray->addObject(pOneKey);
pOneKey->release();
}
}
}
return pArray;
}
//通过查询关键字取得对应CCObject指针
CCObject* CCDictionary::objectForKey(const std::string& key)
{
//当前词典查询类型值有效性判断。此处有错，应该改为:if (m_eDictType == kCCDictUnknown || m_eDictType == kCCDictInt) return NULL;
if (m_eDictType == kCCDictUnknown && m_eDictType == kCCDictUnknown) return NULL;
//要求当前词典查询类型为按字符串查询。
CCAssert(m_eDictType == kCCDictStr, "this dictionary does not use string as key.");
//定义临时词汇指针变量。
CCObject* pRetObject = NULL;
CCDictElement *pElement = NULL;
//通过名称字符串查询哈希表中的相应词汇
HASH_FIND_STR(m_pElements, key.c_str(), pElement);
if (pElement != NULL)
{
//如果查询到词汇，返回其对应的CCObject指针
pRetObject = pElement->m_pObject;
}
return pRetObject;
}
//通过查询索引取得对应CCObject指针
CCObject* CCDictionary::objectForKey(int key)
{
//当前词典查询类型值有效性判。此处有错，应该改为:if (m_eDictType == kCCDictUnknown || m_eDictType == kCCDictStr) return NULL;
if (m_eDictType == kCCDictUnknown && m_eDictType == kCCDictUnknown) return NULL;
//要求当前词典查询类型为按字符串查询。
CCAssert(m_eDictType == kCCDictInt, "this dictionary does not use integer as key.");
//定义临时词汇指针变量。
CCObject* pRetObject = NULL;
CCDictElement *pElement = NULL;
//通过索引查询哈希表中的相应词汇
HASH_FIND_INT(m_pElements, &key, pElement);
if (pElement != NULL)
{
//如果查询到词汇，返回其对应的CCObject指针
pRetObject = pElement->m_pObject;
}
return pRetObject;
}
//通过查询关键字取得对应CCString指针,其实即要求存入词汇的CCObject指针是CCString实例对象指针。
const CCString* CCDictionary::valueForKey(const std::string& key)
{
//将通过查询关键字取得对应CCString指针强转为CCString指针。
CCString* pStr = (CCString*)objectForKey(key);
if (pStr == NULL)
{
//如果没找到，返回空字符串
pStr = CCString::create("");
}
return pStr;
}
//通过查询索引取得对应CCString指针,即要求存入词汇的CCObject指针是CCString实例对象指针。
const CCString* CCDictionary::valueForKey(int key)
{
//将通过查询索引取得对应CCString指针强转为CCString指针。
CCString* pStr = (CCString*)objectForKey(key);
if (pStr == NULL)
{
//如果没找到，返回空字符串
pStr = CCString::create("");
}
return pStr;
}
//设置一个CCObject和对应的名称存入词典。
void CCDictionary::setObject(CCObject* pObject, const std::string& key)
{
//参数有效性判断
CCAssert(key.length() > 0 && pObject != NULL, "Invalid Argument!");
//如果是第一次存入，记录查询类型为字符串类型。
if (m_eOldDictType == kCCDictUnknown)
{
m_eOldDictType = kCCDictStr;
}
//将当前词典查询类型设为字符串查询类型。这个变量是可以省略的，因为要求词典查询类型为固定。只用m_eOldDictType就可以了。
m_eDictType = kCCDictStr;
CCAssert(m_eDictType == m_eOldDictType, "this dictionary does not use string as key.");
//定义临时指针变量从词典中取得对应名称的词汇。
CCDictElement *pElement = NULL;
HASH_FIND_STR(m_pElements, key.c_str(), pElement);
if (pElement == NULL)
{
//如果词典中没有此词汇，将此新词汇放入词典。
setObjectUnSafe(pObject, key);
}
else if (pElement->m_pObject != pObject)
{
//如果词典中已有此词汇，则删除老词汇放入新词汇。
CCObject* pTmpObj = pElement->m_pObject;
//此处调用retain对引用计数器加1可以避免在后面的删除函数中释放pTmpObj指向的CCObject。
pTmpObj->retain();
//删除此词汇
removeObjectForElememt(pElement);
//放入新词汇。
setObjectUnSafe(pObject, key);
//因为之前retain对引用计数器加1一次，所以必须release对引用计数器减1一次才能保证由内存管理器来进行内存释放时，pTempObj指向的CCObject可以正确的被释放掉。
pTmpObj->release();
}
}
//设置一个CCObject和对应的哈希索引存入词典。
void CCDictionary::setObject(CCObject* pObject, int key)
{
//参数有效性判断
CCAssert(pObject != NULL, "Invalid Argument!");
//如果是第一次存入，记录查询类型为索引类型。
if (m_eOldDictType == kCCDictUnknown)
{
m_eOldDictType = kCCDictInt;
}
//将当前词典查询类型设为索引查询类型。这个变量是可以省略的，因为要求词典查询类型为固定。只用m_eOldDictType就可以了。
m_eDictType = kCCDictInt;
//一致性判断
CCAssert(m_eDictType == m_eOldDictType, "this dictionary does not use integer as key.");
//定义临时指针变量从词典中取得对应名称的词汇。
CCDictElement *pElement = NULL;
HASH_FIND_INT(m_pElements, &key, pElement);
if (pElement == NULL)
{
//如果词典中没有此词汇，将此新词汇放入词典。
setObjectUnSafe(pObject, key);
}
else if (pElement->m_pObject != pObject)
{
//如果词典中已有此词汇，则删除老词汇放入新词汇。
CCObject* pTmpObj = pElement->m_pObject;
//此处调用retain对引用计数器加1可以避免在后面的删除函数中释放pTmpObj指向的CCObject。
pTmpObj->retain();
//删除此词汇
removeObjectForElememt(pElement);
//放入新词汇。
setObjectUnSafe(pObject, key);
//因为之前retain对引用计数器加1一次，所以必须release对引用计数器减1一次才能保证由内存管理器来进行内存释放时，pTempObj指向的CCObject可以正确的被释放掉。
pTmpObj->release();
}
}
//按照查询关键字找到对应CCObject并删除。
void CCDictionary::removeObjectForKey(const std::string& key)
{
//当前词典是否有效
if (m_eOldDictType == kCCDictUnknown)
{
return;
}
//当前词典的查询类型是否为字符串名称查询方式
CCAssert(m_eDictType == kCCDictStr, "this dictionary does not use string as its key");
//参数有效性判断
CCAssert(key.length() > 0, "Invalid Argument!");
//定义临时指针变量从词典中取得对应名称的词汇。
CCDictElement *pElement = NULL;
HASH_FIND_STR(m_pElements, key.c_str(), pElement);
//从词典中删除相应的词汇。
removeObjectForElememt(pElement);
}
void CCDictionary::removeObjectForKey(int key)
{
//当前词典是否有效
if (m_eOldDictType == kCCDictUnknown)
{
return;
}
//当前词典的查询类型是否为索引查询方式
CCAssert(m_eDictType == kCCDictInt, "this dictionary does not use integer as its key");
//定义临时指针变量从词典中取得对应索引的词汇。
CCDictElement *pElement = NULL;
HASH_FIND_INT(m_pElements, &key, pElement);
//从词典中删除相应的词汇。
removeObjectForElememt(pElement);
}
//将CCObject实例指针与对应的字符串名称存入哈希表。
void CCDictionary::setObjectUnSafe(CCObject* pObject, const std::string& key)
{
//对pObject指向的实例对像引用计数器加1,即告诉其被词典使用.避免万一其的其它使用者都不再使用时被内存管理器释放.
pObject->retain();
//由pObject和名称字符串产生一个新的词汇。
CCDictElement* pElement = new CCDictElement(key.c_str(), pObject);
//将新的词汇放入哈希表中。
HASH_ADD_STR(m_pElements, m_szKey, pElement);
}
//将CCObject实例指针与对应的索引存入哈希表。
void CCDictionary::setObjectUnSafe(CCObject* pObject, const int key)
{
//对pObject指向的实例对像引用计数器加1,即告诉其被词典使用.避免万一其的其它使用者都不再使用时被内存管理器释放.
pObject->retain();
//由pObject和名称字符串产生一个新的词汇。
CCDictElement* pElement = new CCDictElement(key, pObject);
//将新的词汇放入哈希表中。
HASH_ADD_INT(m_pElements, m_iKey, pElement);
}
//按照容器中的查询关键字找到对应CCObject并删除。
void CCDictionary::removeObjectsForKeys(CCArray* pKeyArray)
{
//遍历CCArray实例对像的所有名称字符串，查询与之对应的词汇。并删除。
CCObject* pObj = NULL;
CCARRAY_FOREACH(pKeyArray, pObj)
{
CCString* pStr = (CCString*)pObj;
removeObjectForKey(pStr->getCString());
}
}
//从词典中删除相应的词汇。
void CCDictionary::removeObjectForElememt(CCDictElement* pElement)
{
//参数有效性判断
if (pElement != NULL)
{
//从哈希表中删除pElement指向的词汇
HASH_DEL(m_pElements, pElement);
//前面在将词汇加入词典时对引用计数器加1，这里删除词汇是就应该对引用计数器减1。
pElement->m_pObject->release();
//释放词汇
CC_SAFE_DELETE(pElement);
}
}
//从词典中清空所有的词汇。
void CCDictionary::removeAllObjects()
{
//定义遍历哈希表所用的指针变量
CCDictElement *pElement, *tmp;
//遍历哈希表
HASH_ITER(hh, m_pElements, pElement, tmp)
{
//删除词汇并释放
HASH_DEL(m_pElements, pElement);
pElement->m_pObject->release();
CC_SAFE_DELETE(pElement);
}
}
//重载CCObject的拷贝函数。产生一个一模一样的词典。
CCObject* CCDictionary::copyWithZone(CCZone* pZone)
{
//参数有效性判断
CCAssert(pZone == NULL, "CCDirctionary should not be inherited.");
//创建一个新的词典
CCDictionary* pNewDict = new CCDictionary();
//定义用来遍历的临时变量
CCDictElement* pElement = NULL;
CCObject* pTmpObj = NULL;
//如果是索引查询方式
if (m_eDictType == kCCDictInt)
{
//遍历所有词汇
CCDICT_FOREACH(this, pElement)
{
//产生遍历词汇对应的CCObject的COPY,生成新的词汇放入新的词典中.
pTmpObj = pElement->getObject()->copy();
pNewDict->setObject(pTmpObj, pElement->getIntKey());
pTmpObj->release();
}
}
else if (m_eDictType == kCCDictStr)
{
//如果是名称字符串查询方式.
//遍历所有词汇
CCDICT_FOREACH(this, pElement)
{
//产生遍历词汇对应的CCObject的COPY,生成新的词汇放入新的词典中.
pTmpObj = pElement->getObject()->copy();
pNewDict->setObject(pTmpObj, pElement->getStrKey());
pTmpObj->release();
}
}
return pNewDict;
}
//静态函数，取得单例的词典,内部调用create函数。
CCDictionary* CCDictionary::dictionary()
{
return CCDictionary::create();
}
//静态函数，取得单例的词典。
CCDictionary* CCDictionary::create()
{
//创建一个新的词典
CCDictionary* pRet = new CCDictionary();
if (pRet != NULL)
{
//将其设为由引用计数器来判断释放时机.交由内存管理器进行管理.
pRet->autorelease();
}
//返回新创建的词典指针
return pRet;
}
//静态函数，取得一个指定词典的COPY,内部调用createWithDictionary函数.
CCDictionary* CCDictionary::dictionaryWithDictionary(CCDictionary* srcDict)
{
return CCDictionary::createWithDictionary(srcDict);
}
//静态函数，取得一个指定词典的COPY.
CCDictionary* CCDictionary::createWithDictionary(CCDictionary* srcDict)
{
//查生一个指定词典的COPY.
CCDictionary* pNewDict = (CCDictionary*)srcDict->copy();
pNewDict->autorelease();
return pNewDict;
}
//声明静态函数：从一个plist文件中加载词典内容，此函数是多线程安全的，其内部调用 createWithContentsOfFileThreadSafe函数。
extern CCDictionary* ccFileUtils_dictionaryWithContentsOfFileThreadSafe(const char *pFileName);
//静态函数：从一个plist文件中加载词典内容，此函数是多线程安全的.
CCDictionary* CCDictionary::dictionaryWithContentsOfFileThreadSafe(const char *pFileName)
{
return CCDictionary::createWithContentsOfFileThreadSafe(pFileName);
}
//静态函数：从一个plist文件中加载词典内容，此函数是多线程安全的.
CCDictionary* CCDictionary::createWithContentsOfFileThreadSafe(const char *pFileName)
{
//这里调用Cocos2d-x的文件函数集中的带多线程安全的从plist文件加载词典函数实现相应功能.
return ccFileUtils_dictionaryWithContentsOfFileThreadSafe(pFileName);
}
//静态函数：从一个plist文件中加载词典内容，其内部调用 createWithContentsOfFile函数。
CCDictionary* CCDictionary::dictionaryWithContentsOfFile(const char *pFileName)
{
return CCDictionary::createWithContentsOfFile(pFileName);
}
//静态函数：从一个plist文件中加载词典内容.
CCDictionary* CCDictionary::createWithContentsOfFile(const char *pFileName)
{
CCDictionary* pRet = createWithContentsOfFileThreadSafe(pFileName);
pRet->autorelease();
return pRet;
}
NS_CC_END