| 站点地图 | 联系我
| www.asm32.net | 2006版 | 资料中心 | linux | asm/asm32 | C/C++ | VC++ | java | 书签 | ASP.Net书签 | 上善若水 厚德载物
 现在位置 :: 主页 >> 资料中心 >> ROOT / CODE / ASM/ASM32 / Win32汇编编程 /
 

WIN32汇编实现的HashTable

来源(cloudandy的专栏 - CSDN博客)

From: http://blog.csdn.net/cloudandy/archive/2008/11/14/3298015.aspx

HashTableAdd proto pHashStruct:dword,pKey:dword,pValue:dword

.data

 HashSizeTable  dword 11,23,47,97,197,397,797,1597,3203,6421,12853,25717,51437,102877,205759,411527

   HashPrimeTable dword 103,101,97,91,89,87,83,79,73,71,67,61,59,57,53,51,47,43,41,39,37,31,29,23,\
         19,17,13,11,7,5,2,1

 HashStruct struct
  curSize   dword 0
  curMaxSize   dword 11
  curSizeIndex dword 0
  cSizeTable  dword 16
  pSizeTable  dword offset HashSizeTable
  pPrimeTable  dword offset HashPrimeTable
  pInteralArray dword 0
 HashStruct ends

.code

CreateInteralArray proc pHashStruct:dword

 ;invoke INFODEBUG,SADD("CreateInteralArray")

 ;create addr array with the init size to save addr of keys and addr of values
 mov edx,pHashStruct
 mov ecx,(HashStruct ptr [edx]).curMaxSize
 shl ecx,3 ;mul 8(=4+4)
 push edx
 invoke GlobalAlloc,GMEM_FIXED or GMEM_ZEROINIT,ecx
 pop edx
 mov (HashStruct ptr [edx]).pInteralArray,eax
 ret
CreateInteralArray endp

ResizeInteralArrayAndReHashIt proc pHashStruct:dword

 LOCAL oldSize:dword
 LOCAL oldParray:dword
 LOCAL newParray:dword

 ;invoke INFODEBUG,SADD("ResizeInteralArrayAndReHashIt")

 mov edx,pHashStruct

 mov eax,(HashStruct ptr [edx]).pInteralArray
 mov oldParray,eax
 mov eax,(HashStruct ptr [edx]).curMaxSize
 mov oldSize,eax

 ;;;;create new array
 mov ecx,(HashStruct ptr [edx]).curSizeIndex
 mov ebx,(HashStruct ptr [edx]).pSizeTable

 inc ecx
 mov eax,(HashStruct ptr [edx]).cSizeTable
 .if  ecx >= eax
  jmp overmax         ;数组大小到达了最大值
 .endif



 mov (HashStruct ptr [edx]).curSizeIndex,ecx ;set new sizeindex

 mov eax,[ebx+ecx*4]       ;ebx+ecx*4 = new size addr
 mov (HashStruct ptr [edx]).curMaxSize,eax ;and set


 shl eax,3         ;mul 8(=4+4)
 invoke GlobalAlloc,GMEM_FIXED or GMEM_ZEROINIT,eax ;new array with new size
 mov newParray,eax


 mov edx,pHashStruct
 mov (HashStruct ptr [edx]).pInteralArray,eax;set new array
 xor eax,eax
 mov (HashStruct ptr [edx]).curSize,eax;set new array's item count to 0

 ;;;;rehash old data and copy  to new array

 mov ecx,oldSize   ;COUNT
 mov edx,oldParray  ;START
 xor ebx,ebx    ;INIT COUNT

 .while ebx < ecx
  mov eax,[edx+ebx*8]
  .if eax == 0   ;for check pkey
   inc ebx
   .continue
  .endif

  pusha
  mov ebx,[edx+ebx*8+4] ;pval
  invoke HashTableAdd,pHashStruct,eax,ebx ;call Interap with each Item
  popa

  inc ebx
 .endw


 ;invoke INFODEBUG,SADD("ResizeInteralArrayAndReHashIt to ")
 mov edx,pHashStruct
 invoke INFODEBUG2,(HashStruct ptr [edx]).curMaxSize

 invoke GlobalFree,oldParray
 mov eax,newParray ;return the pointer of the resized InteralArray
 ret
overmax:
 ;invoke INFODEBUG,SADD("数组大小到达了最大值")
 mov eax,0
 ret
ResizeInteralArrayAndReHashIt endp


FreeHashTable proc pHashStruct:dword
 local pArray:dword
 mov edx,pHashStruct
 mov eax,(HashStruct ptr [edx]).pInteralArray
 mov pArray,eax

 invoke GlobalFree,pArray
 invoke GlobalFree,pHashStruct
 xor eax,eax
 ret
FreeHashTable endp

CreateHashTable proc
 local pHashStruct:dword

 ;invoke INFODEBUG,SADD("CreateHashTable")

 invoke GlobalAlloc,GMEM_FIXED or GMEM_ZEROINIT,sizeof HashStruct
 mov pHashStruct,eax

 mov (HashStruct ptr [eax]).curSize,0
 mov (HashStruct ptr [eax]).curMaxSize,11
 mov (HashStruct ptr [eax]).curSizeIndex,0
 mov (HashStruct ptr [eax]).cSizeTable,16
 mov (HashStruct ptr [eax]).pSizeTable,offset HashSizeTable
 mov (HashStruct ptr [eax]).pPrimeTable,offset HashPrimeTable
 mov (HashStruct ptr [eax]).pInteralArray,0


 invoke CreateInteralArray,pHashStruct

 mov eax,pHashStruct
 ret
CreateHashTable endp


HashFunc proc pHashStruct:dword,pKey:dword
 LOCAL ttl:DWORD
 LOCAL prms:DWORD
 LOCAL cnt:DWORD

  ;invoke INFODEBUG,SADD("HashFunc")

 mov edx,pHashStruct
 mov eax,(HashStruct ptr [edx]).pPrimeTable
 mov prms,eax
 mov eax,(HashStruct ptr [edx]).curMaxSize
 mov cnt,eax

    push ebx
    push esi
    push edi

    mov ttl, 0                  ; total

    mov esi, pKey
    mov edi, prms               ; array of primes address in EDI
    xor ecx, ecx                ; zero character counter
    xor ebx, ebx                ; prevent stall in EBX
  @@:
    movzx eax, BYTE PTR [esi+ecx]
    add ecx, 1                  ; increment the character position counter
    mov ebx, [edi+ecx*4]        ; get value of prime from character position
    imul bx                     ; mul char ascii value by prime
    add ttl, eax                ; add result to total

    cmp eax, 0
    jne @B

  ; -------------------------------
  ; added to deliver larger numbers
  ; -------------------------------
    mov ecx, ttl
    shl ecx, 13
    add ttl, ecx



  ; ------------------------------------------------------------
  ; divide total by array count and return the remainder in EAX
  ; ------------------------------------------------------------
    xor edx, edx
    mov eax, ttl
    div cnt

    mov eax, edx


    pop edi
    pop esi
    pop ebx

 ret   ;return the hashcode of the key pointerd by pKey
HashFunc endp

HashTableAdd proc pHashStruct:dword,pKey:dword,pValue:dword

    LOCAL hkey:DWORD
    LOCAL pArray:DWORD
    LOCAL cnt:DWORD

 ;invoke INFODEBUG,SADD("HashTableAdd")

    ;
    ;.if pHashStruct.curSize > curMaxSize * 72 / 100
    ; invoke ResizeInteralArray,pHashStruct
    ;.endif

    mov edx,pHashStruct
 mov eax,(HashStruct ptr [edx]).pInteralArray
 mov pArray,eax
 mov eax,(HashStruct ptr [edx]).curMaxSize
 mov cnt,eax

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;check size decide if need to resieze  InteralArray
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 mov ecx,72
 imul ecx  ;eax*ecx = curMaxSize * 72
 mov ecx,eax  ;save to ecx

 mov edx,pHashStruct
 mov eax,(HashStruct ptr [edx]).curSize
 mov edx,100
 imul edx  ;eax*edx = curSize * 100
     ;save to eax
 .if eax > ecx
  jmp toresize
 .endif

resized:
    invoke HashFunc,pHashStruct,pKey
    mov hkey,eax
  wttstart:
   mov eax,hkey
    mov edx, pArray     ;
    xor ecx,ecx
    mov ecx,dword ptr [edx+eax*8]            ; get  key addr which index of eax

    .if ecx == 0              ; the index of  hkey is blanck then
     jmp write_string             ; jump to "write string"
    .endif

    invoke lstrcmp,ecx,pKey   ; compare the old key in the same index with the newKey
    .if eax == 0
     ;invoke INFODEBUG,SADD("已经存在")
     jmp wtEnd                    ; exit procedure if the same
    .endif ;//

    add hkey, 1                     ; if collision,
    ;invoke INFODEBUG,SADD("+1")

    mov eax,hkey
    .if eax == cnt
    ;invoke INFODEBUG,SADD("最大,跳到0")
    mov hkey,0
   .endif ;
    jmp wttstart                    ; try next location in hash table

  write_string:

   mov eax,hkey
   mov edx,pArray

    mov ecx,pValue
    mov [edx+eax*8+4],ecx
    mov ecx,pKey         ; write pkey to location in hash table
    mov [edx+eax*8],ecx

   mov edx,pHashStruct
 mov ecx,(HashStruct ptr [edx]).curSize
 inc ecx
 mov (HashStruct ptr [edx]).curSize,ecx

;  PUSHA
;   invoke INFODEBUG21,ecx
;   invoke INFODEBUG11,SADD(":")
;   invoke INFODEBUG21,hkey
;   invoke INFODEBUG11,SADD(";")
;   invoke INFODEBUG11,pKey
;   invoke INFODEBUG11,SADD(":")
;   invoke INFODEBUG,pValue
;  popa

 xor eax,eax ;ok
 ret


toresize:

 invoke ResizeInteralArrayAndReHashIt,pHashStruct
 .if eax == 0
  invoke FreeHashTable,pHashStruct
  jmp wtEnd
 .endif ;//

 mov edx,pHashStruct
 mov eax,(HashStruct ptr [edx]).pInteralArray
 mov pArray,eax
 mov eax,(HashStruct ptr [edx]).curMaxSize
 mov cnt,eax


 jmp resized

  wtEnd:
 mov eax,1 ;exists
 ret


HashTableAdd endp


HashGethkeyForRead proc pHashStruct:dword,pKey:dword
 LOCAL item:DWORD
    LOCAL hkey:DWORD
    LOCAL pArray:DWORD
    LOCAL cnt:DWORD

     ;invoke INFODEBUG,SADD("HashGethkeyForRead")

 mov edx,pHashStruct
 mov eax,(HashStruct ptr [edx]).curMaxSize
 mov cnt,eax
 mov eax,(HashStruct ptr [edx]).pInteralArray
 mov pArray,eax

    invoke HashFunc,pHashStruct,pKey
    mov hkey,eax

wttstart:
 mov eax,hkey
   .if eax == cnt
    mov hkey,0
    mov eax,hkey
   .endif ;//

    mov edx, pArray     ;
    mov ecx, [edx+eax*8]            ; get  key addr which index of eax

    cmp ecx, 0              ; the index of  hkey is blanck then
    je no_exists                    ; jump to "no_exists"

 invoke lstrcmp,ecx,pKey
    .if eax != 0     ; compare the old key in the same index with the newKey
     jmp refind                      ; refind if not same
    .else
     mov eax,hkey
     ret
    .endif

 refind:

  add hkey, 1                     ;
  mov eax,hkey
  inc eax
  .if eax < cnt     ;
     jmp wttstart                     ;
  .endif        ; no find
 no_exists:
 mov eax,0      ;
 ret
HashGethkeyForRead endp

HashTableGet proc pHashStruct:dword,pKey:dword

;invoke INFODEBUG,SADD("HashTableGet")

 invoke HashGethkeyForRead,pHashStruct,pKey
 .if eax == 0
  ret
 .endif
 mov ecx,eax

 mov edx,pHashStruct
 mov ebx,(HashStruct ptr [edx]).pInteralArray

 mov eax,[ebx+ecx*8+4] ;pInteralArray + phkey*8 + 4 = addr of pval

 ret



HashTableGet endp



HashTableExists proc pHashStruct:dword,pKey:dword
 invoke HashGethkeyForRead,pHashStruct,pKey

 ret
HashTableExists endp

HashTableDel proc pHashStruct:dword,pKey:dword
 invoke HashGethkeyForRead,pHashStruct,pKey
 cmp eax,0
 je nofind

 mov edx,pHashStruct
 mov ebx,(HashStruct ptr [edx]).pInteralArray

 mov dword ptr [ebx+eax*8],0  ;pInteralArray + phkey*8  = addr of pkey
 mov dword ptr [ebx+eax*8+4],0 ;pInteralArray + phkey*8 + 4 = addr of pval

 mov ecx,(HashStruct ptr [edx]).curSize
 dec ecx
 mov (HashStruct ptr [edx]).curSize,ecx

 xor eax,eax  ;deled
 ret
nofind:
 mov eax,1
 ret
HashTableDel endp

HashTableEach proc pHashStruct:dword,pInterap:dword
    mov edx,pHashStruct

 mov ecx,(HashStruct ptr [edx]).curMaxSize  ;COUNT
 mov eax,(HashStruct ptr [edx]).pInteralArray ;POINTER
 mov edx,eax

 xor ebx,ebx          ;INIT COUNT
 .while ebx < ecx
  mov eax,[edx+ebx*8]
  .if eax == 0   ;for check if exists
   inc ebx
   .continue
  .endif

  push ecx
  push edx
  push ebx

  ;;edx+ebx*8
  mov eax,ebx
  shl eax,3
  add eax,edx

  add eax,4
  push eax
  sub eax,4
  push eax  ;call Interap with each  addr of the addr of pkey

  call pInterap


  pop ebx
  pop edx
  pop ecx

  inc ebx
 .endw

 ret
HashTableEach endp



本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/cloudandy/archive/2008/11/14/3298015.aspx

Link: http://www.asm32.net/article_details.aspx?id=4590


浏览次数 53 发布时间 2009/9/26 14:44:49 从属分类 Win32汇编编程 【评论】【 】【打印】【关闭
 
| www.asm32.net | 2006版 | 资料中心 | linux | asm/asm32 | C/C++ | VC++ | java | 书签 | ASP.Net书签 | 京ICP备09029108号-1