x86_64_sse2_x87/fasm/source/map.inc

   1 \r
   2 ; this is a simple map used primarily for the source cache\r
   3 \r
   4 struct Map\r
   5         hash_mask dd ?\r
   6         linked_blocks dd ?\r
   7         free_space dd ?\r
   8         free_space_length dd ?\r
   9 ends\r
  10 \r
  11 struct MapEntry\r
  12         name dd ?\r
  13         name_length dd ?\r
  14         value dd ?\r
  15         next_entry dd ?\r
  16 ends\r
  17 \r
  18 create_string_map:\r
  19 ; in: cl = number of hash bits\r
  20 ; out: ebx - new map\r
  21 ; preserves: esi\r
  22         mov     ebx,1\r
  23         shl     ebx,cl\r
  24         shl     ebx,2\r
  25         lea     ecx,[sizeof.Map+ebx*4]\r
  26         call    malloc_fixed\r
  27         xchg    ebx,eax\r
  28         mov     ecx,eax\r
  29         dec     eax\r
  30         mov     [ebx+Map.hash_mask],eax\r
  31         lea     edi,[ebx+sizeof.Map]\r
  32         xor     eax,eax\r
  33         rep     stosd\r
  34         mov     ecx,1000h\r
  35         call    malloc_fixed\r
  36         mov     [ebx+Map.linked_blocks],eax\r
  37         xor     edx,edx\r
  38         mov     [eax],edx\r
  39         add     eax,10h\r
  40         mov     [ebx+Map.free_space],eax\r
  41         mov     [ebx+Map.free_space_length],1000h-10h\r
  42         retn\r
  43 \r
  44 destroy_string_map:\r
  45 ; in: ebx - map\r
  46 ; preserves: esi, edi\r
  47         mov     eax,ebx\r
  48         mov     ebx,[ebx+Map.linked_blocks]\r
  49         call    mfree\r
  50     free_map_blocks:\r
  51         test    ebx,ebx\r
  52         jz      string_map_destroyed\r
  53         mov     eax,ebx\r
  54         mov     ebx,[ebx]\r
  55         call    mfree\r
  56         jmp     free_map_blocks\r
  57     string_map_destroyed:\r
  58         retn\r
  59 \r
  60 get_from_map:\r
  61 ; in:\r
  62 ;  ebx - map\r
  63 ;  esi - string\r
  64 ;  ecx = string length, zero for ASCIIZ string\r
  65 ; out:\r
  66 ;  eax = value\r
  67 ;  cf set when no entry found\r
  68 ; preserves: ebx, [esi], edi\r
  69 ; note: when entry is found, esi is replaced with pointer to the same string in persistent storage\r
  70         call    get_bucket\r
  71         test    eax,eax\r
  72         jz      not_found_in_map\r
  73         call    find_map_entry\r
  74         jc      not_found_in_map\r
  75         mov     eax,[eax+MapEntry.value]\r
  76         retn\r
  77     get_bucket:\r
  78         call    hash_string\r
  79         and     edx,[ebx+Map.hash_mask]\r
  80         mov     eax,[ebx+sizeof.Map+edx*4]\r
  81         retn\r
  82     find_map_entry:\r
  83         cmp     [eax+MapEntry.name_length],ecx\r
  84         jne     next_map_entry\r
  85         push    edi\r
  86         mov     edi,[eax+MapEntry.name]\r
  87         test    edi,edi\r
  88         jz      not_this_map_entry\r
  89         push    ecx esi\r
  90         repe    cmpsb\r
  91         pop     esi ecx\r
  92         jne     not_this_map_entry\r
  93         mov     esi,edi\r
  94         sub     esi,ecx\r
  95         pop     edi\r
  96         clc\r
  97         retn\r
  98     not_this_map_entry:\r
  99         pop     edi\r
 100     next_map_entry:\r
 101         mov     eax,[eax+MapEntry.next_entry]\r
 102         test    eax,eax\r
 103         jnz     find_map_entry\r
 104     not_found_in_map:\r
 105         stc\r
 106         retn\r
 107 \r
 108 put_into_map:\r
 109 ; in:\r
 110 ;  ebx - map\r
 111 ;  esi - string\r
 112 ;  ecx = string length, zero for ASCIIZ string\r
 113 ;  eax = value\r
 114 ; preserves: ebx, [esi], edi\r
 115 ; note:\r
 116 ;  esi is replaced with pointer to the same string in persistent storage,\r
 117 ;  an ASCIIZ string is a key with length including the terminating zero\r
 118 ;  and when it is put into persistent storage, final zero is copied as well\r
 119         push    eax\r
 120         call    get_bucket\r
 121         test    eax,eax\r
 122         jz      new_bucket\r
 123         call    find_map_entry\r
 124         jnc     put_value_into_map_entry\r
 125         mov     eax,[ebx+sizeof.Map+edx*4]\r
 126     find_free_map_entry:\r
 127         cmp     [eax+MapEntry.name],0\r
 128         je      fill_map_entry\r
 129         mov     edx,eax\r
 130         mov     eax,[eax+MapEntry.next_entry]\r
 131         test    eax,eax\r
 132         jnz     find_free_map_entry\r
 133         call    allocate_map_entry\r
 134         mov     [edx+MapEntry.next_entry],eax\r
 135         jmp     new_map_entry\r
 136     new_bucket:\r
 137         call    allocate_map_entry\r
 138         mov     [ebx+sizeof.Map+edx*4],eax\r
 139     new_map_entry:\r
 140         mov     [eax+MapEntry.next_entry],0\r
 141     fill_map_entry:\r
 142         mov     [eax+MapEntry.name_length],ecx\r
 143         push    eax\r
 144         call    store_string\r
 145         pop     eax\r
 146         mov     [eax+MapEntry.name],esi\r
 147     put_value_into_map_entry:\r
 148         pop     [eax+MapEntry.value]\r
 149         retn\r
 150     allocate_map_entry:\r
 151         mov     eax,[ebx+Map.free_space]\r
 152         add     [ebx+Map.free_space],sizeof.MapEntry\r
 153         sub     [ebx+Map.free_space_length],sizeof.MapEntry\r
 154         jc      map_out_of_free_space\r
 155         retn\r
 156     map_out_of_free_space:\r
 157         push    ecx edx\r
 158         mov     ecx,1000h\r
 159         call    malloc_fixed\r
 160         mov     edx,eax\r
 161         xchg    [ebx+Map.linked_blocks],edx\r
 162         mov     [eax],edx\r
 163         add     eax,10h\r
 164         mov     [ebx+Map.free_space],eax\r
 165         mov     [ebx+Map.free_space_length],1000h-10h\r
 166         pop     edx ecx\r
 167         jmp     allocate_map_entry\r
 168 \r
 169 remove_from_map:\r
 170 ; in:\r
 171 ;  ebx - map\r
 172 ;  esi - string\r
 173 ;  ecx = string length, zero for ASCIIZ string\r
 174 ; preserves: ebx, [esi], edi\r
 175         call    get_bucket\r
 176         test    eax,eax\r
 177         jz      not_found_in_map\r
 178         call    find_map_entry\r
 179         jc      not_found_in_map\r
 180         mov     dword [eax+MapEntry.name],0\r
 181         retn\r
 182 \r
 183 iterate_through_map:\r
 184 ; in:\r
 185 ;  ebx - map\r
 186 ;  edi - callback function\r
 187 ; callback:\r
 188 ;  eax = value\r
 189 ;  esi - string\r
 190 ;  ecx = string length\r
 191 ;  edx - MapEntry\r
 192         mov     ecx,[ebx+Map.hash_mask]\r
 193         inc     ecx\r
 194         add     ebx,sizeof.Map\r
 195     iterate_through_hash_table:\r
 196         mov     edx,[ebx]\r
 197     iterate_through_bucket:\r
 198         test    edx,edx\r
 199         jz      end_of_bucket\r
 200         push    ebx ecx edx edi\r
 201         mov     eax,[edx+MapEntry.value]\r
 202         mov     esi,[edx+MapEntry.name]\r
 203         mov     ecx,[edx+MapEntry.name_length]\r
 204         call    edi\r
 205         pop     edi edx ecx ebx\r
 206         mov     edx,[edx+MapEntry.next_entry]\r
 207         jmp     iterate_through_bucket\r
 208     end_of_bucket:\r
 209         add     ebx,4\r
 210         loop    iterate_through_hash_table\r
 211         retn\r
 212 \r
 213 hash_string:\r
 214 ; in: esi - string, ecx = string length, zero for ASCIIZ string\r
 215 ; out: ecx = string length, edx = 32-bit hash\r
 216 ; preserves: ebx, esi, edi\r
 217         mov     edx,FNV_OFFSET\r
 218         jecxz   hash_asciiz\r
 219         mov     eax,ecx\r
 220     hash_known_length:\r
 221         xor     dl,[esi]\r
 222         inc     esi\r
 223         imul    edx,FNV_PRIME\r
 224         loop    hash_known_length\r
 225         mov     ecx,eax\r
 226         sub     esi,ecx\r
 227         retn\r
 228     hash_asciiz:\r
 229         inc     ecx\r
 230         lodsb\r
 231         xor     dl,al\r
 232         imul    edx,FNV_PRIME\r
 233         test    al,al\r
 234         jnz     hash_asciiz\r
 235     hash_ready:\r
 236         sub     esi,ecx\r
 237         retn\r