Darwin中OSRef和OSHashTable类的使用

2024-02-22 04:32
文章标签 使用 darwin oshashtable osref

本文主要是介绍Darwin中OSRef和OSHashTable类的使用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//哈希表被设计成模版类的形式

#include "../WinNTSupport/Win32header.h"#include <iostream>
using namespace std;
#include <string>#include <OSCond.h>
#include <OSRef.h>
#include "getopt.h"
#include "FilePrefsSource.h"#include "RunServer.h"
#include "QTSServer.h"
#include "QTSSExpirationDate.h"
#include "GenerateXMLPrefs.h"// #include "OSHashTable.h"
#include "MyAssert.h"
typedef OSHashTable<OSRef, OSRefKey> OSRefHashTable;
typedef OSHashTableIter<OSRef,OSRefKey> OSRefHashTableIter;
int main(int argc, char * argv[]) 
{OSRefHashTable fTable(1000);
for (int i=0; i< 5 ;i ++)
{char *buf = new char[100];
memset(buf,0,100);sprintf(buf,"%d%d%d%d",i,i,i,i);
StrPtrLen ptr(buf);OSRef *fRef = new OSRef;
fRef->Set(ptr,NULL);
OSRefKey key(fRef->GetString());
OSRef* duplicateRef = fTable.Map(&key);
if (duplicateRef != NULL)
{
continue;
}
fTable.Add(fRef);
}OSRefHashTableIter tableIter(&fTable);
OSRef *pTemp = NULL;
while((pTemp = tableIter.GetCurrent()) != NULL)
{
char *pbuf  = pTemp->GetString()->GetAsCString();
cout << pbuf <<"   index:"<<tableIter.GetCurIndex()<< endl;
tableIter.Next();
}return 0;
}





template<class T, class K>
class OSHashTable {
public:OSHashTable( UInt32 size ) //构造函数{fHashTable = new ( T*[size] );//初始化大小Assert( fHashTable );memset( fHashTable, 0, sizeof(T*) * size );//设置初始值fSize = size;/*下面的代码决定用哪种方式为哈希表的键值计算索引；
如果哈希表的大小不是2的幂，只好采用对fSize求余的方法；
否则可以直接用掩码的方式，这种方式相对速度更快*/      fMask = fSize - 1;if((fMask & fSize) != 0)//判断是不是2的幂，确定使用何种哈希函数（ComputeIndex）fMask = 0;fNumEntries = 0;}~OSHashTable() //析构{delete [] fHashTable;}voidAdd( T* entry ) { //加入元素，有标记代码可以看出，此处解决冲突的方式采用了链地址法Assert( entry->fNextHashEntry == NULL );Kkey( entry );UInt32 theIndex = ComputeIndex( key.GetHashKey() );entry->fNextHashEntry = fHashTable[theIndex ];fHashTable[ theIndex ] = entry;fNumEntries++;}voidRemove( T* entry )//移除元素{Kkey( entry );UInt32 theIndex = ComputeIndex( key.GetHashKey() );T*elem = fHashTable[ theIndex ];T*last = NULL;while (elem && elem != entry) {last = elem;elem = elem->fNextHashEntry;}if( elem ) // sometimes remove is called 2x ( swap, then un register ){Assert(elem);if (last)last->fNextHashEntry = elem->fNextHashEntry;elsefHashTable[ theIndex ] =elem->fNextHashEntry;elem->fNextHashEntry = NULL;fNumEntries--;}}T* Map(K* key ) //查找对象{UInt32 theIndex = ComputeIndex( key->GetHashKey() );T*elem = fHashTable[ theIndex ];while (elem) {K elemKey( elem );if (elemKey == *key)break;elem = elem->fNextHashEntry;}return elem;}UInt64GetNumEntries() { return fNumEntries; }UInt32GetTableSize() { return fSize; }T*GetTableEntry( int i ) { return fHashTable[i]; }private:T**fHashTable;UInt32fSize;UInt32fMask;UInt64fNumEntries;UInt32 ComputeIndex(UInt32 hashKey ){if (fMask)return( hashKey & fMask );//掩码方式elsereturn( hashKey % fSize );// 除留取余法}
};
//实现了一个hash表迭代器的功能
template<class T, class K>
class OSHashTableIter {
public:OSHashTableIter( OSHashTable<T,K>* table ){fHashTable = table;First();}voidFirst(){for(fIndex = 0; fIndex < fHashTable->GetTableSize(); fIndex++) {fCurrent = fHashTable->GetTableEntry( fIndex );if (fCurrent)break;}}voidNext(){fCurrent = fCurrent->fNextHashEntry;if(!fCurrent) {for (fIndex = fIndex + 1; fIndex < fHashTable->GetTableSize();fIndex++) {fCurrent =fHashTable->GetTableEntry( fIndex );if (fCurrent)break;}}}Bool16IsDone(){return( fCurrent == NULL );}T*GetCurrent() { return fCurrent; }private:OSHashTable<T,K>* fHashTable;T*fCurrent;UInt32fIndex;


[html]  view plain copy
  1. class OSRefKey;  
  2. class OSRefTableUtils  
  3. {  
  4.    private:  
  5.        static UInt32  HashString(StrPtrLen* inString);     
  6.        friend class OSRef;  
  7.        friend class OSRefKey;  
  8. };  
  9. class OSRef  
  10. {  
  11.     public:  
  12.        OSRef() :   fObjectP(NULL),fRefCount(0), fNextHashEntry(NULL)  
  13.            {      
  14.            }  
  15.        OSRef(const StrPtrLen &inString, void* inObjectP)  
  16.                                 : fRefCount(0),fNextHashEntry(NULL)  
  17.                                     {   Set(inString, inObjectP); }  
  18.        ~OSRef() {}  
  19.         void Set(const StrPtrLen& inString,void* inObjectP)  
  20.            {       
  21.                fString = inString; fObjectP = inObjectP;  
  22.                fHashValue = OSRefTableUtils::HashString(&fString);  
  23.            }  
  24.        void**  GetObjectPtr()  { return &fObjectP; }  
  25.        void*   GetObject()     { return fObjectP; }  
  26.        UInt32  GetRefCount()   { return fRefCount; }  
  27.        StrPtrLen *GetString()  { return&fString; }  
  28.    private:  
  29.        //value  
  30.        void*   fObjectP;  
  31.        //key  
  32.        StrPtrLen   fString;  
  33.        //refcounting  
  34.         UInt32  fRefCount;  
  35. #if DEBUG  
  36.        Bool16  fInATable;  
  37.        Bool16  fSwapCalled;  
  38. #endif  
  39.        OSCond  fCond;//to block threadswaiting for this ref.  
  40.        UInt32              fHashValue;  
  41.        OSRef*             fNextHashEntry;  
  42.         friend class OSRefKey;  
  43.        friend class OSHashTable<OSRef, OSRefKey>;  
  44.        friend class OSHashTableIter<OSRef, OSRefKey>;  
  45.        friend class OSRefTable;  
  46. };  
  47. class OSRefKey  
  48. {  
  49. public:  
  50.    //CONSTRUCTOR / DESTRUCTOR:  
  51.    OSRefKey(StrPtrLen* inStringP)  
  52.        :   fStringP(inStringP)  
  53.          {fHashValue = OSRefTableUtils::HashString(inStringP); }  
  54.    ~OSRefKey() {}  
  55.    //ACCESSORS:  
  56.    StrPtrLen*  GetString()         { return fStringP; }  
  57. private:  
  58.    //PRIVATE ACCESSORS:     
  59.    SInt32      GetHashKey()        { return fHashValue; }  
  60.     //thesefunctions are only used by the hash table itself. This constructor  
  61.     //willbreak the "Set" functions.  
  62.    OSRefKey(OSRef *elem) : fStringP(&elem->fString),  
  63.                            fHashValue(elem->fHashValue) {}                    
  64.     friendint operator ==(const OSRefKey &key1, const OSRefKey &key2)  
  65.     {  
  66.         if(key1.fStringP->Equal(*key2.fStringP))  
  67.            return true;  
  68.        return false;  
  69.     }  
  70.     //data:  
  71.    StrPtrLen *fStringP;  
  72.    UInt32  fHashValue;  
  73.     friendclass OSHashTable<OSRef, OSRefKey>;  
  74. };  
  75. typedef OSHashTable<OSRef, OSRefKey>OSRefHashTable;  
  76. typedef OSHashTableIter<OSRef, OSRefKey>OSRefHashTableIter;  
  77. class OSRefTable  
  78. {  
  79.     public:  
  80.        enum  
  81.         {  
  82.            kDefaultTableSize = 1193 //UInt32  
  83.         };  
  84.        //tableSize doesn't indicate the max number of Refs that can be added  
  85.        //(it's unlimited), but is rather just how big to make the hash table  
  86.        OSRefTable(UInt32 tableSize = kDefaultTableSize) : fTable(tableSize),fMutex() {}  
  87.        ~OSRefTable() {}  
  88.        //Allows access to the mutex in case you need to lock the table down  
  89.        //between operations  
  90.        OSMutex*    GetMutex()      { return &fMutex; }  
  91.        OSRefHashTable* GetHashTable() { return &fTable;   
  92.        //Registers a Ref in the table. Once the Ref is in, clients may resolve  
  93.        //the ref by using its string ID. You must setup the Ref before passingit  
  94.        //in here, ie., setup the string and object pointers  
  95.        //This function will succeed unless the string identifier is not unique,  
  96.        //in which case it will return QTSS_DupName  
  97.         //This function is atomic wrt this reftable.  
  98.        OS_Error        Register(OSRef*ref);  
  99.         //RegisterOrResolve  
  100.         //If the ID of the input ref is unique, this function is equivalent to  
  101.         //Register, and returns NULL.  
  102.         // If there is a duplicate ID already inthe map, this funcion  
  103.         //leave it, resolves it, and returns it.  
  104.        OSRef*             RegisterOrResolve(OSRef* inRef);  
  105.        //This function may block. You can only remove a Ref from the table  
  106.        //when the refCount drops to the level specified. If several threadshave  
  107.        //the ref currently, the calling thread will wait until the otherthreads  
  108.        //stop using the ref (by calling Release, below)  
  109.        //This function is atomic wrt this ref table.  
  110.        void        UnRegister(OSRef* ref,UInt32 refCount = 0);  
  111.         //Same as UnRegister, but guarenteed not to block. Will return  
  112.         //true if ref was sucessfully unregistered, false otherwise  
  113.        Bool16      TryUnRegister(OSRef*ref, UInt32 refCount = 0);  
  114.        //Resolve. This function uses the provided key string to identify andgrab  
  115.        //the Ref keyed by that string. Once the Ref is resolved, it is safe touse  
  116.        //(it cannot be removed from the Ref table) until you call Release.Because  
  117.        //of that, you MUST call release in a timely manner, and be aware ofpotential  
  118.        //deadlocks because you now own a resource being contended over.  
  119.        //This function is atomic wrt this ref table.  
  120.        OSRef*     Resolve(StrPtrLen*  inString);  
  121.        //Release. Release a Ref, and drops its refCount. After calling this,the  
  122.        //Ref is no longer safe to use, as it may be removed from the ref table.  
  123.         void       Release(OSRef*  inRef);  
  124.         //Swap. This atomically removes any existing Ref in the table with the new  
  125.         //ref's ID, and replaces it with this new Ref. If there is no matching Ref  
  126.         //already in the table, this function does nothing.  
  127.         //  
  128.         //Be aware that this creates a situation where clients may have a Ref resolved  
  129.         //that is no longer in the table. The old Ref must STILL be UnRegisterednormally.  
  130.         //Once Swap completes sucessfully, clients that call resolve on the ID will get  
  131.         //the new OSRef object.  
  132.        void        Swap(OSRef* newRef);  
  133.        UInt32      GetNumRefsInTable() {UInt64 result =  fTable.GetNumEntries();Assert(result < kUInt32_Max); return (UInt32) result; }  
  134.    private:  
  135.        //all this object needs to do its job is an atomic hashtable  
  136.        OSRefHashTable  fTable;  
  137.        OSMutex         fMutex;  
  138. };  
  139. class OSRefReleaser  
  140. {  
  141.     public:  
  142.        OSRefReleaser(OSRefTable* inTable, OSRef* inRef) : fOSRefTable(inTable),fOSRef(inRef) {}  
  143.        ~OSRefReleaser() { fOSRefTable->Release(fOSRef); }  
  144.        OSRef*          GetRef() { returnfOSRef; }  
  145.    private:  
  146.        OSRefTable*     fOSRefTable;  
  147.        OSRef*          fOSRef;  
  148. };  
  149.    

};

 

引用表头文件定义，详细的代码请参考源码，此处只结合实例讲解几个主要的函数


//结合实例说明常用的方法

服务器网络模型中有个很重要的类EventContext, EventContext.h中包含EventContext类和EventThread类的定义

每一个EventContext类中都有一个引用对象，如下图

在每次执行RequestEvent函数时，就会执行以下代码（EventContext.cpp182行）

if (!compare_and_store(8192, WM_USER,&sUniqueID))

           fUniqueID = (PointerSizedInt)atomic_add(&sUniqueID, 1);      //获取一个唯一标识  

fRef.Set(fUniqueIDStr, this);//对引用对象赋值

void Set(const StrPtrLen&inString, void* inObjectP)

            {

                fString = inString; fObjectP =inObjectP;

                fHashValue =OSRefTableUtils::HashString(&fString);

            }

fString作为索引，fObjectP保存对象，fHashValue根据索引计算出一个hash值

fEventThread->fRefTable.Register(&fRef);//把这个引用对象加入到EventThread中的引用表中（其实就是hash表），fRefTable是OSRefTable类的实例，而类中操作的表是OSRefHashTable类型（typedef OSHashTable<OSRef, OSRefKey>OSRefHashTable;）

OS_ErrorOSRefTable::Register(OSRef* inRef)

{

       if (inRef == NULL)

        return EPERM;

   OSMutexLocker locker(&fMutex);

   if (inRef->fString.Ptr == NULL || inRef->fString.Len == 0)

   {         return EPERM;

   }

   // Check for a duplicate. In this function, if there is a duplicate,

   // return an error, don't resolve the duplicate

   OSRefKey key(&inRef->fString);

   OSRef* duplicateRef = fTable.Map(&key);//查找有没有重复的，没有则加入到hash表中

   if (duplicateRef != NULL)

        return EPERM;

       

   // There is no duplicate, so add this ref into the table

   fTable.Add(inRef);

   return OS_NoErr;

}

::memset( &fEventReq, '\0',sizeof(fEventReq));//下面的代码其实就是把socket加入到select监视中，由于本文主要讲解下引用表相关类的使用，所以此处不再详细描述

 fEventReq.er_type = EV_FD;

 fEventReq.er_handle = fFileDesc;

 fEventReq.er_eventbits = theMask;

 fEventReq.er_data = (void*)fUniqueID;

if (select_watchevent(&fEventReq, theMask) !=0)

 

========以上代码描述了构造一个ref，然后加入reftable中的操作

 

在EventThread的线程执行函数Entry中，使用了reftable查找EventContext对象

当select返回一个可操作的socket时，执行了以下代码，

if (theCurrentEvent.er_data != NULL)// theCurrentEvent就是select返回的数据

        {

        

           StrPtrLen idStr((char*)&theCurrentEvent.er_data,sizeof(theCurrentEvent.er_data));

//返回的数据用于构造一个id，这个id其实就是在上一步中得到的唯一标识，如下图

           OSRef* ref = fRefTable.Resolve(&idStr);//根据这个唯一标识获取到引用对象，其实就是通过hash类中map函数去查找对象，然后把引用对象的引用计数+1

           if (ref != NULL)

           {

               EventContext* theContext = (EventContext*)ref->GetObject();

               theContext->ProcessEvent(theCurrentEvent.er_eventbits);

               fRefTable.Release(ref);//把引用对象的引用计数-1，然后设置事件为有信号，确保唤醒等待该资源被释放的对象

           }

        }

以上说明是通过darwin中一个使用实例，为了方面理解引用表和哈希表的使用（OSRef和OSHashTable）

这篇关于Darwin中OSRef和OSHashTable类的使用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/734136。

相关文章

使用Python和OpenCV库实现实时颜色识别系统

使用Python和OpenCV库实现实时颜色识别系统

《使用Python和OpenCV库实现实时颜色识别系统》：本文主要介绍使用Python和OpenCV库实现的实时颜色识别系统,这个系统能够通过摄像头捕捉视频流,并在视频中指定区域内识别主要颜色（红... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间详解
阅读更多...
Windows下C++使用SQLitede的操作过程

Windows下C++使用SQLitede的操作过程

《Windows下C++使用SQLitede的操作过程》本文介绍了Windows下C++使用SQLite的安装配置、CppSQLite库封装优势、核心功能（如数据库连接、事务管理）、跨平台支持及性能优... 目录Windows下C++使用SQLite1、安装2、代码示例CppSQLite：C++轻松操作SQ
阅读更多...
Python常用命令提示符使用方法详解

Python常用命令提示符使用方法详解

《Python常用命令提示符使用方法详解》在学习python的过程中,我们需要用到命令提示符(CMD)进行环境的配置,：本文主要介绍Python常用命令提示符使用方法的相关资料,文中通过代码介绍的... 目录一、python环境基础命令【Windows】1、检查Python是否安装2、 查看Python的安
阅读更多...
Python并行处理实战之如何使用ProcessPoolExecutor加速计算

Python并行处理实战之如何使用ProcessPoolExecutor加速计算

《Python并行处理实战之如何使用ProcessPoolExecutor加速计算》Python提供了多种并行处理的方式,其中concurrent.futures模块的ProcessPoolExecu... 目录简介完整代码示例代码解释1. 导入必要的模块2. 定义处理函数3. 主函数4. 生成数字列表5.
阅读更多...
Python中help()和dir()函数的使用

Python中help()和dir()函数的使用

《Python中help()和dir()函数的使用》我们经常需要查看某个对象（如模块、类、函数等）的属性和方法,Python提供了两个内置函数help()和dir(),它们可以帮助我们快速了解代... 目录1. 引言2. help() 函数2.1 作用2.2 使用方法2.3 示例(1) 查看内置函数的帮助(
阅读更多...
Linux脚本(shell)的使用方式

Linux脚本(shell)的使用方式

《Linux脚本(shell)的使用方式》：本文主要介绍Linux脚本(shell)的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录概述语法详解数学运算表达式Shell变量变量分类环境变量Shell内部变量自定义变量：定义、赋值自定义变量：引用、修改、删
阅读更多...
Java使用HttpClient实现图片下载与本地保存功能

Java使用HttpClient实现图片下载与本地保存功能

《Java使用HttpClient实现图片下载与本地保存功能》在当今数字化时代,网络资源的获取与处理已成为软件开发中的常见需求,其中,图片作为网络上最常见的资源之一,其下载与保存功能在许多应用场景中都... 目录引言一、Apache HttpClient简介二、技术栈与环境准备三、实现图片下载与保存功能1.
阅读更多...
Python中使用uv创建环境及原理举例详解

Python中使用uv创建环境及原理举例详解

《Python中使用uv创建环境及原理举例详解》uv是Astral团队开发的高性能Python工具,整合包管理、虚拟环境、Python版本控制等功能,：本文主要介绍Python中使用uv创建环境及... 目录一、uv工具简介核心特点：二、安装uv1. 通过pip安装2. 通过脚本安装验证安装：配置镜像源（可
阅读更多...
LiteFlow轻量级工作流引擎使用示例详解

LiteFlow轻量级工作流引擎使用示例详解

《LiteFlow轻量级工作流引擎使用示例详解》：本文主要介绍LiteFlow是一个灵活、简洁且轻量的工作流引擎,适合用于中小型项目和微服务架构中的流程编排,本文给大家介绍LiteFlow轻量级工... 目录1. LiteFlow 主要特点2. 工作流定义方式3. LiteFlow 流程示例4. LiteF
阅读更多...
使用Python开发一个现代化屏幕取色器

使用Python开发一个现代化屏幕取色器

《使用Python开发一个现代化屏幕取色器》在UI设计、网页开发等场景中,颜色拾取是高频需求,：本文主要介绍如何使用Python开发一个现代化屏幕取色器,有需要的小伙伴可以参考一下... 目录一、项目概述二、核心功能解析2.1 实时颜色追踪2.2 智能颜色显示三、效果展示四、实现步骤详解4.1 环境配置4.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2