本篇内容主要讲解“PostgreSQL中hash_search_with_hash_value函数有什么作用”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“PostgreSQL中hash_search_with_hash_value函数有什么作用”吧!

BufferDesc
共享缓冲区的共享描述符(状态)数据

/**Flagsforbufferdescriptors*buffer描述器标记**Note:TAG_VALIDessentiallymeansthatthereisabufferhashtable*entryassociatedwiththebuffer'stag.*注意:TAG_VALID本质上意味着有一个与缓冲区的标记相关联的缓冲区散列表条目。*///bufferheader锁定#defineBM_LOCKED(1U<<22)/*bufferheaderislocked*///数据需要写入(标记为DIRTY)#defineBM_DIRTY(1U<<23)/*dataneedswriting*///数据是有效的#defineBM_VALID(1U<<24)/*dataisvalid*///已分配buffertag#defineBM_TAG_VALID(1U<<25)/*tagisassigned*///正在R/W#defineBM_IO_IN_PROGRESS(1U<<26)/*readorwriteinprogress*///上一个I/O出现错误#defineBM_IO_ERROR(1U<<27)/*previousI/Ofailed*///开始写则变DIRTY#defineBM_JUST_DIRTIED(1U<<28)/*dirtiedsincewritestarted*///存在等待solepin的其他进程#defineBM_PIN_COUNT_WAITER(1U<<29)/*havewaiterforsolepin*///checkpoint发生,必须刷到磁盘上#defineBM_CHECKPOINT_NEEDED(1U<<30)/*mustwriteforcheckpoint*///持久化buffer(不是unlogged或者初始化fork)#defineBM_PERMANENT(1U<<31)/*permanentbuffer(notunlogged,*orinitfork)*//**BufferDesc--shareddescriptor/statedataforasinglesharedbuffer.*BufferDesc--共享缓冲区的共享描述符(状态)数据**Note:Bufferheaderlock(BM_LOCKEDflag)mustbeheldtoexamineorchange*thetag,stateorwait_backend_pidfields.Ingeneral,bufferheaderlock*isaspinlockwhichiscombinedwithflags,refcountandusagecountinto*singleatomicvariable.Thislayoutallowustodosomeoperationsina*singleatomicoperation,withoutactuallyacquiringandreleasingspinlock;*forinstance,increaseordecreaserefcount.buf_idfieldneverchanges*afterinitialization,sodoesnotneedlocking.freeNextisprotectedby*thebuffer_strategy_locknotbufferheaderlock.TheLWLockcantakecare*ofitself.Thebufferheaderlockis*not*usedtocontrolaccesstothe*datainthebuffer!*注意:必须持有Bufferheader锁(BM_LOCKED标记)才能检查或修改tag/state/wait_backend_pid字段.*通常来说,bufferheaderlock是spinlock,它与标记位/参考计数/使用计数组合到单个原子变量中.*这个布局设计允许我们执行原子操作,而不需要实际获得或者释放spinlock(比如,增加或者减少参考计数).*buf_id字段在初始化后不会出现变化,因此不需要锁定.*freeNext通过buffer_strategy_lock锁而不是bufferheaderlock保护.*LWLock可以很好的处理自己的状态.*务请注意的是:bufferheaderlock不用于控制buffer中的数据访问!**It'sassumedthatnobodychangesthestatefieldwhilebufferheaderlock*isheld.Thusbufferheaderlockholdercandocomplexupdatesofthe*statevariableinsinglewrite,simultaneouslywithlockrelease(cleaning*BM_LOCKEDflag).Ontheotherhand,updatingofstatewithoutholding*bufferheaderlockisrestrictedtoCAS,whichinsurethatBM_LOCKEDflag*isnotset.Atomicincrement/decrement,OR/ANDetc.arenotallowed.*假定在持有bufferheaderlock的情况下,没有人改变状态字段.*持有bufferheaderlock的进程可以执行在单个写操作中执行复杂的状态变量更新,*同步的释放锁(清除BM_LOCKED标记).*换句话说,如果没有持有bufferheaderlock的状态更新,会受限于CAS,*这种情况下确保BM_LOCKED没有被设置.*比如原子的增加/减少(AND/OR)等操作是不允许的.**Anexceptionisthatifwehavethebufferpinned,itstagcan'tchange*underneathus,sowecanexaminethetagwithoutlockingthebufferheader.*Also,inplaceswedoone-timereadsoftheflagswithoutbotheringto*lockthebufferheader;thisisgenerallyforsituationswherewedon't*expecttheflagbitbeingtestedtobechanging.*一种例外情况是如果我们已有bufferpinned,该buffer的tag不能改变(在本进程之下),*因此不需要锁定bufferheader就可以检查tag了.*同时,在执行一次性的flags读取时不需要锁定bufferheader.*这种情况通常用于我们不希望正在测试的flagbit将被改变.**Wecan'tphysicallyremoveitemsfromadiskpageifanotherbackendhas*thebufferpinned.Hence,abackendmayneedtowaitforallotherpins*togoaway.ThisissignaledbystoringitsownPIDinto*wait_backend_pidandsettingflagbitBM_PIN_COUNT_WAITER.Atpresent,*therecanbeonlyonesuchwaiterperbuffer.*如果其他进程有bufferpinned,那么进程不能物理的从磁盘页面中删除items.*因此,后台进程需要等待其他pins清除.这可以通过存储它自己的PID到wait_backend_pid中,*并设置标记位BM_PIN_COUNT_WAITER.*目前,每个缓冲区只能由一个等待进程.**Weusethissamestructforlocalbufferheaders,butthelocksarenot*usedandnotalloftheflagbitsareusefuleither.Toavoidunnecessary*overhead,manipulationsofthestatefieldshouldbedonewithoutactual*atomicoperations(i.e.onlypg_atomic_read_u32()and*pg_atomic_unlocked_write_u32()).*本地缓冲头部使用同样的结构,但并不需要使用locks,而且并不是所有的标记位都使用.*为了避免不必要的负载,状态域的维护不需要实际的原子操作*(比如只有pg_atomic_read_u32()andpg_atomic_unlocked_write_u32())**Becarefultoavoidincreasingthesizeofthestructwhenaddingor*reorderingmembers.Keepingitbelow64bytes(themostcommonCPU*cachelinesize)isfairlyimportantforperformance.*在增加或者记录成员变量时,小心避免增加结构体的大小.*保持结构体大小在64字节内(通常的CPU缓存线大小)对于性能是非常重要的.*/typedefstructBufferDesc{//buffertagBufferTagtag;/*IDofpagecontainedinbuffer*///buffer索引编号(0开始),指向相应的bufferpoolslotintbuf_id;/*buffer'sindexnumber(from0)*//*stateofthetag,containingflags,refcountandusagecount*///tag状态,包括flags/refcount和usagecountpg_atomic_uint32state;//pin-count等待进程IDintwait_backend_pid;/*backendPIDofpin-countwaiter*///空闲链表链中下一个空闲的bufferintfreeNext;/*linkinfreelistchain*///缓冲区内容锁LWLockcontent_lock;/*tolockaccesstobuffercontents*/}BufferDesc;

BufferTag
Buffer tag标记了buffer存储的是磁盘中哪个block

/**Buffertagidentifieswhichdiskblockthebuffercontains.*Buffertag标记了buffer存储的是磁盘中哪个block**Note:theBufferTagdatamustbesufficienttodeterminewheretowritethe*block,withoutreferencetopg_classorpg_tablespaceentries.It's*possiblethatthebackendflushingthebufferdoesn'tevenbelievethe*relationisvisibleyet(itsxactmayhavestartedbeforethexactthat*createdtherel).Thestoragemanagermustbeabletocopeanyway.*注意:BufferTag必须足以确定如何写block而不需要参照pg_class或者pg_tablespace数据字典信息.*有可能后台进程在刷新缓冲区的时候深圳不相信关系是可见的(事务可能在创建rel的事务之前).*存储管理器必须可以处理这些事情.**Note:ifthere'sanypadbytesinthestruct,INIT_BUFFERTAGwillhave*tobefixedtozerothem,sincethisstructisusedasahashkey.*注意:如果在结构体中有填充的字节,INIT_BUFFERTAG必须将它们固定为零，因为这个结构体用作散列键.*/typedefstructbuftag{//物理relation标识符RelFileNodernode;/*physicalrelationidentifier*/ForkNumberforkNum;//相对于relation起始的块号BlockNumberblockNum;/*blknumrelativetobeginofreln*/}BufferTag;

HTAB
哈希表的顶层控制结构.

/**Topcontrolstructureforahashtable---inasharedtable,eachbackend*hasitsowncopy(OKsincenofieldschangeatruntime)*哈希表的顶层控制结构.*在这个共享哈希表中,每一个后台进程都有自己的拷贝*(之所以没有问题是因为fork出来后,在运行期没有字段会变化)*/structHTAB{//指向共享的控制信息HASHHDR*hctl;/*=>sharedcontrolinformation*///段开始目录HASHSEGMENT*dir;/*directoryofsegmentstarts*///哈希函数HashValueFunchash;/*hashfunction*///哈希键比较函数HashCompareFuncmatch;/*keycomparisonfunction*///哈希键拷贝函数HashCopyFunckeycopy;/*keycopyingfunction*///内存分配器HashAllocFuncalloc;/*memoryallocator*///内存上下文MemoryContexthcxt;/*memorycontextifdefaultallocatorused*///表名(用于错误信息)char*tabname;/*tablename(forerrormessages)*///如在共享内存中,则为Tboolisshared;/*trueiftableisinsharedmemory*///如为T,则固定大小不能扩展boolisfixed;/*iftrue,don'tenlarge*//*freezingasharedtableisn'tallowed,sowecankeepstatehere*///不允许冻结共享表,因此这里会保存相关状态boolfrozen;/*true=nomoreinsertsallowed*//*Wekeeplocalcopiesofthesefixedvaluestoreducecontention*///保存这些固定值的本地拷贝,以减少冲突//哈希键长度(以字节为单位)Sizekeysize;/*hashkeylengthinbytes*///段大小,必须为2的幂longssize;/*segmentsize---mustbepowerof2*///段偏移,ssize的对数intsshift;/*segmentshift=log2(ssize)*/};/**Headerstructureforahashtable---containsallchangeableinfo*哈希表的头部结构--存储所有可变信息**Inashared-memoryhashtable,theHASHHDRisinsharedmemory,while*eachbackendhasalocalHTABstruct.Foranon-sharedtable,thereisn't*anyfunctionaldifferencebetweenHASHHDRandHTAB,butweseparatethem*anywaytosharecodebetweensharedandnon-sharedtables.*在共享内存哈希表中,HASHHDR位于共享内存中,每一个后台进程都有一个本地HTAB结构.*对于非共享哈希表,HASHHDR和HTAB没有任何功能性的不同,*但无论如何,我们还是把它们区分为共享和非共享表.*/structHASHHDR{/**Thefreelistcanbecomeapointofcontentioninhigh-concurrencyhash*tables,soweuseanarrayoffreelists,eachwithitsownmutexand*nentriescount,insteadofjustasingleone.Althoughthefreelists*normallyoperateindependently,wewillscavengeentriesfromfreelists*otherthanahashcode'sdefaultfreelistwhennecessary.*在高并发的哈希表中,空闲链表会成为竞争热点,因此我们使用空闲链表数组,*数组中的每一个元素都有自己的mutex和条目统计,而不是使用一个.**Ifthehashtableisnotpartitioned,onlyfreeList[0]isusedandits*spinlockisnotusedatall;callers'lockingisassumedsufficient.*如果哈希表没有分区,那么只有freelist[0]元素是有用的,自旋锁没有任何用处;*调用者锁定被认为已足够OK.*/FreeListDatafreeList[NUM_FREELISTS];/*Thesefieldscanchange,butnotinapartitionedtable*///这些域字段可以改变,但不适用于分区表/*Also,dsizecan'tchangeinasharedtable,evenifunpartitioned*///同时,就算是非分区表,共享表的dsize也不能改变//目录大小longdsize;/*directorysize*///已分配的段大小(<=dbsize)longnsegs;/*numberofallocatedsegments(<=dsize)*///正在使用的最大桶IDuint32max_bucket;/*IDofmaximumbucketinuse*///进入整个哈希表的模掩码uint32high_mask;/*masktomodulointoentiretable*///进入低于半个哈希表的模掩码uint32low_mask;/*masktomodulointolowerhalfoftable*//*Thesefieldsarefixedathashtablecreation*///下面这些字段在哈希表创建时已固定//哈希键大小(以字节为单位)Sizekeysize;/*hashkeylengthinbytes*///所有用户元素大小(以字节为单位)Sizeentrysize;/*totaluserelementsizeinbytes*///分区个数(2的幂),或者为0longnum_partitions;/*#partitions(mustbepowerof2),or0*///目标的填充因子longffactor;/*targetfillfactor*///如目录是固定大小,则该值为dsize的上限值longmax_dsize;/*'dsize'limitifdirectoryisfixedsize*///段大小,必须是2的幂longssize;/*segmentsize---mustbepowerof2*///端偏移,ssize的对数intsshift;/*segmentshift=log2(ssize)*///一次性分配的条目个数intnelem_alloc;/*numberofentriestoallocateatonce*/#ifdefHASH_STATISTICS/**Countstatisticshere.NB:statscodedoesn'tbotherwithmutex,so*countscouldbecorruptedabitinapartitionedtable.*统计信息.*注意:统计相关的代码不会影响mutex,因此对于分区表,统计可能有一点点问题*/longaccesses;longcollisions;#endif};/**HASHELEMENTistheprivatepartofahashtableentry.Thecaller'sdata*followstheHASHELEMENTstructure(onaMAXALIGN'dboundary).Thehashkey*isexpectedtobeatthestartofthecaller'shashentrydatastructure.*HASHELEMENT是哈希表条目的私有部分.*调用者的数据按照HASHELEMENT结构组织(位于MAXALIGN的边界).*哈希键应位于调用者hash条目数据结构的开始位置.*/typedefstructHASHELEMENT{//链接到相同桶中的下一个条目structHASHELEMENT*link;/*linktonextentryinsamebucket*///该条目的哈希函数结果uint32hashvalue;/*hashfunctionresultforthisentry*/}HASHELEMENT;/*Hashtableheaderstructisanopaquetypeknownonlywithindynahash.c*///哈希表头部结构,非透明类型,用于dynahash.ctypedefstructHASHHDRHASHHDR;/*Hashtablecontrolstructisanopaquetypeknownonlywithindynahash.c*///哈希表控制结构,非透明类型,用于dynahash.ctypedefstructHTABHTAB;/*Parameterdatastructureforhash_create*///hash_create使用的参数数据结构/*Onlythosefieldsindicatedbyhash_flagsneedbeset*///根据hash_flags标记设置相应的字段typedefstructHASHCTL{//分区个数(必须是2的幂)longnum_partitions;/*#partitions(mustbepowerof2)*///段大小longssize;/*segmentsize*///初始化目录大小longdsize;/*(initial)directorysize*///dsize上限longmax_dsize;/*limittodsizeifdirsizeislimited*///填充因子longffactor;/*fillfactor*///哈希键大小(字节为单位)Sizekeysize;/*hashkeylengthinbytes*///参见上述数据结构注释Sizeentrysize;/*totaluserelementsizeinbytes*///HashValueFunchash;/*hashfunction*/HashCompareFuncmatch;/*keycomparisonfunction*/HashCopyFunckeycopy;/*keycopyingfunction*/HashAllocFuncalloc;/*memoryallocator*/MemoryContexthcxt;/*memorycontexttouseforallocations*///共享内存中的哈希头部结构地址HASHHDR*hctl;/*locationofheaderinsharedmem*/}HASHCTL;/*AhashbucketisalinkedlistofHASHELEMENTs*///哈希桶是HASHELEMENTs链表typedefHASHELEMENT*HASHBUCKET;/*Ahashsegmentisanarrayofbucketheaders*///hashsegment是桶数组typedefHASHBUCKET*HASHSEGMENT;/**Hashfunctionsmusthavethissignature.*Hash函数必须有它自己的标识*/typedefuint32(*HashValueFunc)(constvoid*key,Sizekeysize);/**Keycomparisonfunctionsmusthavethissignature.Comparisonfunctions*returnzeroformatch,nonzerofornomatch.(Thecomparisonfunction*definitionisdesignedtoallowmemcmp()andstrncmp()tobeuseddirectly*askeycomparisonfunctions.)*哈希键对比函数必须有自己的标识.*如匹配则对比函数返回0,不匹配返回非0.*(对比函数定义被设计为允许在对比键值时可直接使用memcmp()和strncmp())*/typedefint(*HashCompareFunc)(constvoid*key1,constvoid*key2,Sizekeysize);/**Keycopyingfunctionsmusthavethissignature.Thereturnvalueisnot*used.(Thedefinitionissetuptoallowmemcpy()andstrlcpy()tobe*useddirectly.)*键拷贝函数必须有自己的标识.*返回值无用.*/typedefvoid*(*HashCopyFunc)(void*dest,constvoid*src,Sizekeysize);/**Spaceallocationfunctionforahashtable---designedtomatchmalloc().*Note:thereisnofreefunctionAPI;can'tdestroyahashtableunlessyou*usethedefaultallocator.*哈希表的恐惧分配函数--被设计为与malloc()函数匹配.*注意:这里没有释放函数API;不能销毁哈希表,除非使用默认的分配器.*/typedefvoid*(*HashAllocFunc)(Sizerequest);

FreeListData
在一个分区哈希表中,每一个空闲链表与特定的hashcodes集合相关,通过下面的FREELIST_IDX()宏进行定义.
nentries跟踪有这些hashcodes的仍存活的hashtable条目个数.

/**Per-freelistdata.*空闲链表数据.**Inapartitionedhashtable,eachfreelistisassociatedwithaspecific*setofhashcodes,asdeterminedbytheFREELIST_IDX()macrobelow.*nentriestracksthenumberoflivehashtableentrieshavingthosehashcodes*(NOTthenumberofentriesinthefreelist,asyoumightexpect).*在一个分区哈希表中,每一个空闲链表与特定的hashcodes集合相关,通过下面的FREELIST_IDX()宏进行定义.*nentries跟踪有这些hashcodes的仍存活的hashtable条目个数.*(注意不要搞错,不是空闲的条目个数)**Thecoverageofafreelistmightbemoreorlessthanonepartition,soit*needsitsownlockratherthanrelyingoncallerlocking.Relyingonthat*wouldn'tworkevenifthecoveragewasthesame,becauseoftheoccasional*needto"borrow"entriesfromanotherfreelist;seeget_hash_entry().*空闲链表的覆盖范围可能比一个分区多或少,因此需要自己的锁而不能仅仅依赖调用者的锁.*依赖调用者锁在覆盖面一样的情况下也不会起效,因为偶尔需要从另一个自由列表“借用”条目,详细参见get_hash_entry()**UsinganarrayofFreeListDatainsteadofseparatearraysofmutexes,*nentriesandfreeListshelpstoreducesharingofcachelinesbetween*differentmutexes.*使用FreeListData数组而不是一个独立的mutexes,nentries和freelists数组有助于减少不同mutexes之间的缓存线共享.*/typedefstruct{//该空闲链表的自旋锁slock_tmutex;/*spinlockforthisfreelist*///相关桶中的条目个数longnentries;/*numberofentriesinassociatedbuckets*///空闲元素链HASHELEMENT*freeList;/*chainoffreeelements*/}FreeListData;

BufferLookupEnt

/*entryforbufferlookuphashtable*///检索hash表的条目typedefstruct{//磁盘page的tagBufferTagkey;/*Tagofadiskpage*///相关联的bufferIDintid;/*AssociatedbufferID*/}BufferLookupEnt;二、源码解读

hash_search_with_hash_value函数,根据给定tag和buffer ID,插入到哈希表中,如该tag相应的条目已存在,则不处理.
其主要实现逻辑如下:
1.初始化相关变量,如根据hash值获取idx等
2.如action为插入,检查是否需要分裂哈希桶
3.执行相关初始化检索,计算桶号/段号/段内编号等
4.沿着哈希键冲突链搜索匹配键,根据搜索结果给foundPtr赋值
5.根据输入action执行相应的逻辑
5.1HASH_FIND,搜索
5.2HASH_REMOVE,移除
5.3HASH_ENTER_NULL,验证分配器,转至HASH_ENTER
5.4HASH_ENTER,如找到,则返回现存的元素,否则创建一个
6.找不到,则报错,返回NULL

void*hash_search_with_hash_value(HTAB*hashp,constvoid*keyPtr,uint32hashvalue,HASHACTIONaction,bool*foundPtr){HASHHDR*hctl=hashp->hctl;//获取HASHHDRintfreelist_idx=FREELIST_IDX(hctl,hashvalue);//根据hash值获取idxSizekeysize;//键值大小uint32bucket;//桶号longsegment_num;//段号longsegment_ndx;//HASHSEGMENTsegp;//段HASHBUCKETcurrBucket;//当前桶号HASHBUCKET*prevBucketPtr;//上一个桶号HashCompareFuncmatch;//是否match?#ifHASH_STATISTICS//统计信息hash_accesses++;hctl->accesses++;#endif/**Ifinserting,checkifitistimetosplitabucket.*如正插入,检查是否需要分裂哈希桶**NOTE:failuretoexpandtableisnotafatalerror,itjustmeanswe*havetorunathigherfillfactorthanwewanted.However,ifwe're*usingthepallocallocatorthenitwillthrowerroranywayon*out-of-memory,sowemustdothisbeforemodifyingthetable.*注意:扩展哈希表出现问题不是致命错误,只是意味着我们不得不执行比我们期望更高更高的填充因子.*但是,如果我们正在使用palloc分配器,那么只要出现内存溢出则会抛出错误,*因此我们不需在更新表前完成这个事情.*/if(action==HASH_ENTER||action==HASH_ENTER_NULL){/**Can'tsplitifrunninginpartitionedmode,noriffrozen,norif*tableisthesubjectofanyactivehash_seq_searchscans.Strange*orderofthesetestsistotrytocheckcheaperconditionsfirst.*如在分区模式/冻结/处于其他活动hash_seq_search扫描期间,则不能进行分裂.*奇怪的是,这些测试的顺序是先尝试检查成本更低的条件.*/if(!IS_PARTITIONED(hctl)&&!hashp->frozen&&hctl->freeList[0].nentries/(long)(hctl->max_bucket+1)>=hctl->ffactor&&!has_seq_scans(hashp))(void)expand_table(hashp);}/**Dotheinitiallookup*执行初始化检索*///计算桶号bucket=calc_bucket(hctl,hashvalue);//计算段号和段内编号segment_num=bucket>>hashp->sshift;segment_ndx=MOD(bucket,hashp->ssize);//获取directorysegp=hashp->dir[segment_num];if(segp==NULL)hash_corrupted(hashp);//记录桶号prevBucketPtr=&segp[segment_ndx];currBucket=*prevBucketPtr;/**Followcollisionchainlookingformatchingkey*沿着哈希键冲突链搜索匹配键*///匹配函数match=hashp->match;/*saveonefetchininnerloop*///键大小keysize=hashp->keysize;/*ditto*/while(currBucket!=NULL){if(currBucket->hashvalue==hashvalue&&match(ELEMENTKEY(currBucket),keyPtr,keysize)==0)break;prevBucketPtr=&(currBucket->link);currBucket=*prevBucketPtr;#ifHASH_STATISTICShash_collisions++;hctl->collisions++;#endif}//结果赋值if(foundPtr)*foundPtr=(bool)(currBucket!=NULL);/**OK,nowwhat?*根据action执行相关操作*/switch(action){caseHASH_FIND://搜索if(currBucket!=NULL)return(void*)ELEMENTKEY(currBucket);returnNULL;caseHASH_REMOVE://移除if(currBucket!=NULL){/*ifpartitioned,mustlocktotouchnentriesandfreeList*///如分区,在访问条目入口和空闲链表时必须先请求锁if(IS_PARTITIONED(hctl))SpinLockAcquire(&(hctl->freeList[freelist_idx].mutex));/*deletetherecordfromtheappropriatenentriescounter.*///修改nentries计数器Assert(hctl->freeList[freelist_idx].nentries>0);hctl->freeList[freelist_idx].nentries--;/*removerecordfromhashbucket'schain.*///在哈希桶中链中删除记录*prevBucketPtr=currBucket->link;/*addtherecordtotheappropriatefreelist.*///添加记录到正确的空闲链表上currBucket->link=hctl->freeList[freelist_idx].freeList;hctl->freeList[freelist_idx].freeList=currBucket;if(IS_PARTITIONED(hctl))//释放锁SpinLockRelease(&hctl->freeList[freelist_idx].mutex);/**betterhopethecallerissynchronizingaccesstothis*element,becausesomeoneelseisgoingtoreuseitthenext*timesomethingisaddedtothetable*调用者最好是同步访问元素,因为其他进程在下一次添加到哈希表可以复用.*/return(void*)ELEMENTKEY(currBucket);}returnNULL;caseHASH_ENTER_NULL:/*ENTER_NULLdoesnotworkwithpalloc-basedallocator*///验证分配器Assert(hashp->alloc!=DynaHashAlloc);/*FALLTHRU*///继续往下执行caseHASH_ENTER:/*Returnexistingelementiffound,elsecreateone*///如找到,则返回现存的元素,否则创建一个if(currBucket!=NULL)return(void*)ELEMENTKEY(currBucket);/*disallowinsertsiffrozen*///如冻结,则不允许插入,报错if(hashp->frozen)elog(ERROR,"cannotinsertintofrozenhashtable\"%s\"",hashp->tabname);//获取当前桶currBucket=get_hash_entry(hashp,freelist_idx);if(currBucket==NULL){//如为NULL/*outofmemory*///内存溢出if(action==HASH_ENTER_NULL)returnNULL;/*reportagenericmessage*///报错if(hashp->isshared)ereport(ERROR,(errcode(ERRCODE_OUT_OF_MEMORY),errmsg("outofsharedmemory")));elseereport(ERROR,(errcode(ERRCODE_OUT_OF_MEMORY),errmsg("outofmemory")));}//正常/*linkintohashbucketchain*///连接到哈希桶链中*prevBucketPtr=currBucket;currBucket->link=NULL;/*copykeyintorecord*///拷贝键到记录中currBucket->hashvalue=hashvalue;hashp->keycopy(ELEMENTKEY(currBucket),keyPtr,keysize);/**Callerisexpectedtofillthedatafieldonreturn.DONOT*insertanycodethatcouldpossiblythrowerrorhere,asdoing*sowouldleavethetableentryincompleteandhencecorruptthe*caller'sdatastructure.*调用者期望在返回时已填充了数据.*不要插入有可能抛出异常的代码,因为这样做可能会导致哈希表条目不完整并因此破坏调用者的数据结构*/return(void*)ELEMENTKEY(currBucket);}//如执行到这里,那程序就有问题了.elog(ERROR,"unrecognizedhashactioncode:%d",(int)action);//返回NULL,让编译器shutupreturnNULL;/*keepcompilerquiet*/}/*Convertahashvaluetoabucketnumber*///转换hash值为桶号staticinlineuint32calc_bucket(HASHHDR*hctl,uint32hash_val){uint32bucket;//桶号bucket=hash_val&hctl->high_mask;//执行&操作if(bucket>hctl->max_bucket)//大于最大桶号,则返回low_maskbucket=bucket&hctl->low_mask;returnbucket;}/**Allocateanewhashtableentryifpossible;returnNULLifoutofmemory.*(Or,iftheunderlyingspaceallocatorthrowserrorforout-of-memory,*wewon'treturnatall.)*如可能,分配一个新的哈希表条目.如内存溢出则返回NULL.*(或者,如果依赖的空间分配器因为内存溢出抛出错误,则不会返回任何信息)*/staticHASHBUCKETget_hash_entry(HTAB*hashp,intfreelist_idx){HASHHDR*hctl=hashp->hctl;HASHBUCKETnewElement;for(;;){//循环/*ifpartitioned,mustlocktotouchnentriesandfreeList*///如为分区哈希表,在访问条目和空闲链表时,必须锁定if(IS_PARTITIONED(hctl))SpinLockAcquire(&hctl->freeList[freelist_idx].mutex);/*trytogetanentryfromthefreelist*///从空闲链表中尝试获取一个条目newElement=hctl->freeList[freelist_idx].freeList;if(newElement!=NULL)break;if(IS_PARTITIONED(hctl))SpinLockRelease(&hctl->freeList[freelist_idx].mutex);/**Nofreeelementsinthisfreelist.Inapartitionedtable,there*mightbeentriesinotherfreelists,buttoreducecontentionwe*prefertofirsttrytogetanotherchunkofbucketsfromthemain*shmemallocator.Ifthatfails,though,we*MUST*rootthroughall*theotherfreelistsbeforegivingup.Therearemultiplecallers*thatassumethattheycanallocateeveryelementintheinitially*requestedtablesize,orthatdeletinganelementguaranteesthey*caninsertanewelement,evenifsharedmemoryisentirelyfull.*Failingbecausetheneededelementisinadifferentfreelistis*notacceptable.*在空闲链表中没有空闲条目.在分区哈希表中,在其他空闲链表中可能存在条目,*但为了减少争用,我们期望首先尝试从主shmem分配器中获取桶中的其他chunk.*如果失败,我们必须在放弃之前从根节点开始遍历所有其他空闲链表.*存在多个调用者假定它们可以在初始的请求哈希表大小内分配每一个元素,*或者甚至在共享内存全满的情况下删除元素可以保证它们可以插入一个新元素.*之所以失败是因为所需要的元素在不同的空闲链表中是不可接受的.*/if(!element_alloc(hashp,hctl->nelem_alloc,freelist_idx)){//本空闲链表不能分配内存intborrow_from_idx;if(!IS_PARTITIONED(hctl))//非分区哈希表,返回NULL,意味着内存溢出了.returnNULL;/*outofmemory*//*trytoborrowelementfromanotherfreelist*///尝试从其他空闲链表浏览元素borrow_from_idx=freelist_idx;for(;;){//-------开始遍历其他空闲链表borrow_from_idx=(borrow_from_idx+1)%NUM_FREELISTS;if(borrow_from_idx==freelist_idx)//已经完成整个空闲链表的遍历,退出break;/*examinedallfreelists,fail*///获取自旋锁SpinLockAcquire(&(hctl->freeList[borrow_from_idx].mutex));newElement=hctl->freeList[borrow_from_idx].freeList;if(newElement!=NULL){hctl->freeList[borrow_from_idx].freeList=newElement->link;SpinLockRelease(&(hctl->freeList[borrow_from_idx].mutex));/*careful:countthenewelementinitsproperfreelist*///小心:在合适的空闲链表上统计新的元素SpinLockAcquire(&hctl->freeList[freelist_idx].mutex);hctl->freeList[freelist_idx].nentries++;SpinLockRelease(&hctl->freeList[freelist_idx].mutex);returnnewElement;}SpinLockRelease(&(hctl->freeList[borrow_from_idx].mutex));}/*noelementsavailabletoborroweither,sooutofmemory*///已无元素,内存溢出returnNULL;}}/*removeentryfromfreelist,bumpnentries*///从空闲链表中移除条目,bumpnentrieshctl->freeList[freelist_idx].freeList=newElement->link;hctl->freeList[freelist_idx].nentries++;if(IS_PARTITIONED(hctl))SpinLockRelease(&hctl->freeList[freelist_idx].mutex);returnnewElement;}三、跟踪分析

测试脚本

10:44:12(xdb@[local]:5432)testdb=#select*fromt1limit10;

设置断点,跟踪

(gdb)bhash_search_with_hash_valueBreakpoint1at0xa3a4d7:filedynahash.c,line925.(gdb)cContinuing.Breakpoint2,hash_search_with_hash_value(hashp=0x13af8f8,keyPtr=0x7ffdb7d63e40,hashvalue=3920871586,action=HASH_ENTER,foundPtr=0x7ffdb7d63e3f)atdynahash.c:925925HASHHDR*hctl=hashp->hctl;(gdb)

输入参数

(gdb)p*hashp$3={hctl=0x13af990,dir=0x13afda8,hash=0xa3bf74<tag_hash>,match=0x4791a0<memcmp@plt>,keycopy=0x479690<memcpy@plt>,alloc=0xa39589<DynaHashAlloc>,hcxt=0x13af7e0,tabname=0x13af958"LOCALLOCKhash",isshared=false,isfixed=false,frozen=false,keysize=20,ssize=256,sshift=8}(gdb)p*hashp->hctl$4={freeList={{mutex=0'\000',nentries=0,freeList=0x13b1378},{mutex=0'\000',nentries=0,freeList=0x0}<repeats31times>},dsize=256,nsegs=1,max_bucket=15,high_mask=31,low_mask=15,keysize=20,entrysize=80,num_partitions=0,ffactor=1,max_dsize=-1,ssize=256,sshift=8,nelem_alloc=42}(gdb)p*(int*)keyPtr$5=16402

1.初始化相关变量,如根据hash值获取idx等

(gdb)n926intfreelist_idx=FREELIST_IDX(hctl,hashvalue);(gdb)949if(action==HASH_ENTER||action==HASH_ENTER_NULL)(gdb)pfreelist_idx$6=0(gdb)p*hctl->freeList[0].freeList$7={link=0x13b1318,hashvalue=3920871586}(gdb)(gdb)phctl->freeList[0]$8={mutex=0'\000',nentries=0,freeList=0x13b1378}

2.如action为插入,检查是否需要分裂哈希桶

(gdb)n956if(!IS_PARTITIONED(hctl)&&!hashp->frozen&&(gdb)957hctl->freeList[0].nentries/(long)(hctl->max_bucket+1)>=hctl->ffactor&&(gdb)956if(!IS_PARTITIONED(hctl)&&!hashp->frozen&&(gdb)

3.执行相关初始化检索,计算桶号/段号/段内编号等

(gdb)pbucket$9=2(gdb)psegment_num$10=0(gdb)psegment_ndx$11=2(gdb)psegp$12=(HASHSEGMENT)0x13b05c0(gdb)p*segp$13=(HASHBUCKET)0x0(gdb)(gdb)n975prevBucketPtr=&segp[segment_ndx];(gdb)976currBucket=*prevBucketPtr;(gdb)p$14=(HASHBUCKET)0x0(gdb)n981match=hashp->match;/*saveonefetchininnerloop*/(gdb)pcurrBucket$15=(HASHBUCKET)0x0(gdb)

4.沿着哈希键冲突链搜索匹配键,根据搜索结果给foundPtr赋值

(gdb)n982keysize=hashp->keysize;/*ditto*/(gdb)984while(currBucket!=NULL)(gdb)pkeysize$16=20(gdb)pmatch$17=(HashCompareFunc)0x4791a0<memcmp@plt>(gdb)pcurrBucket$18=(HASHBUCKET)0x0(gdb)n997if(foundPtr)(gdb)998*foundPtr=(bool)(currBucket!=NULL);(gdb)

5.根据输入action执行相应的逻辑
5.1HASH_FIND,搜索
5.2HASH_REMOVE,移除
5.3HASH_ENTER_NULL,验证分配器,转至HASH_ENTER
5.4HASH_ENTER,如找到,则返回现存的元素,否则创建一个

(gdb)1003switch(action)(gdb)paction$19=HASH_ENTER(gdb)n1047if(currBucket!=NULL)(gdb)1051if(hashp->frozen)(gdb)1055currBucket=get_hash_entry(hashp,freelist_idx);(gdb)

进入get_hash_entry,如可能,分配一个新的哈希表条目.如内存溢出则返回NULL.

1055currBucket=get_hash_entry(hashp,freelist_idx);(gdb)stepget_hash_entry(hashp=0x13af8f8,freelist_idx=0)atdynahash.c:12521252HASHHDR*hctl=hashp->hctl;(gdb)(gdb)n1258if(IS_PARTITIONED(hctl))(gdb)p*hctl$20={freeList={{mutex=0'\000',nentries=0,freeList=0x13b1378},{mutex=0'\000',nentries=0,freeList=0x0}<repeats31times>},dsize=256,nsegs=1,max_bucket=15,high_mask=31,low_mask=15,keysize=20,entrysize=80,num_partitions=0,ffactor=1,max_dsize=-1,ssize=256,sshift=8,nelem_alloc=42}(gdb)n1262newElement=hctl->freeList[freelist_idx].freeList;(gdb)1264if(newElement!=NULL)(gdb)pnewElement$21=(HASHBUCKET)0x13b1378(gdb)p*newElement$22={link=0x13b1318,hashvalue=3920871586}(gdb)n1265break;(gdb)1322hctl->freeList[freelist_idx].freeList=newElement->link;(gdb)1323hctl->freeList[freelist_idx].nentries++;(gdb)1325if(IS_PARTITIONED(hctl))(gdb)p*newElement->link$23={link=0x13b12b8,hashvalue=2593617408}(gdb)n1328returnnewElement;(gdb)1329}(gdb)

回到hash_search_with_hash_value

hash_search_with_hash_value(hashp=0x13af8f8,keyPtr=0x7ffdb7d63e40,hashvalue=3920871586,action=HASH_ENTER,foundPtr=0x7ffdb7d63e3f)atdynahash.c:10561056if(currBucket==NULL)(gdb)n1073*prevBucketPtr=currBucket;(gdb)p*currBucket$24={link=0x13b1318,hashvalue=3920871586}(gdb)n1074currBucket->link=NULL;(gdb)1077currBucket->hashvalue=hashvalue;(gdb)1078hashp->keycopy(ELEMENTKEY(currBucket),keyPtr,keysize);(gdb)p*currBucket$25={link=0x0,hashvalue=3920871586}(gdb)p*prevBucketPtr$26=(HASHBUCKET)0x13b1378(gdb)p**prevBucketPtr$27={link=0x0,hashvalue=3920871586}(gdb)n1087return(void*)ELEMENTKEY(currBucket);(gdb)p(void*)ELEMENTKEY(currBucket)$28=(void*)0x13b1388

找到entry,返回

(gdb)n1093}(gdb)hash_search(hashp=0x13af8f8,keyPtr=0x7ffdb7d63e40,action=HASH_ENTER,foundPtr=0x7ffdb7d63e3f)atdynahash.c:916916}(gdb)

到此，相信大家对“PostgreSQL中hash_search_with_hash_value函数有什么作用”有了更深的了解，不妨来实际操作一番吧！这里是亿速云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！