; ------------------------------------------------------------------------
; HeavyThing x86_64 assembly language library and showcase programs
; Copyright © 2015-2018 2 Ton Digital
; Homepage: https://2ton.com.au/
; Author: Jeff Marrison <jeff@2ton.com.au>
;
; This file is part of the HeavyThing library.
;
; HeavyThing is free software: you can redistribute it and/or modify
; it under the terms of the GNU General Public License, or
; (at your option) any later version.
;
; HeavyThing is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
; GNU General Public License for more details.
;
; You should have received a copy of the GNU General Public License along
; with the HeavyThing library. If not, see <http://www.gnu.org/licenses/>.
; ------------------------------------------------------------------------
;
; maps.inc: avl tree for int,unsigned,double,string
; no user-supplied comparator on purpose; the internals of this are messy
;
; for common-to-all-variants functions, we simply add the other symbols
; due to the way we declare public symbols though, it doesn't actually
; make a dirtier symbol table...
; probably should make a cleaner/better way to do this
avlnode_size = 68
_avlofs_parent = 0
_avlofs_key = 8
_avlofs_left = 16
_avlofs_right = 24
_avlofs_trunk = 32
_avlofs_next = 40
_avlofs_prev = 48
_avlofs_value = 56
_avlofs_flags = 64 ; dd
profile_map_internals = 0
if used intmap$new | used unsignedmap$new | used doublemap$new | used stringmap$new | defined include_everything
; single argument: bool in edi for insert_order (!edi == sort order)
; NOTE: insert_order causes lower_bound/upper_bound/equal_range obviously to be jacked up
falign
mapcommon$new:
if used intmap$new | defined include_everything
intmap$new:
end if
if used unsignedmap$new | defined include_everything
unsignedmap$new:
end if
if used doublemap$new | defined include_everything
doublemap$new:
end if
if used stringmap$new | defined include_everything
stringmap$new:
end if
prolog mapcommon$new
push rdi
mov edi, avlnode_size
call heap$alloc
pop rdi
xor edx, edx
mov qword [rax+_avlofs_parent], rdx ; root node
mov qword [rax+_avlofs_left], rdx
mov qword [rax+_avlofs_right], rdx ; node count
mov qword [rax+_avlofs_next], rdx ; first
mov qword [rax+_avlofs_prev], rdx ; last
mov qword [rax+_avlofs_trunk], rdx
mov qword [rax+_avlofs_key], rdx
mov qword [rax+_avlofs_value], rdx
mov dword [rax+_avlofs_flags], edi
epilog
end if
; single argument: rdi == map
; NOTE: we do not iterate and destroy the map, all we do is call heap$free wiht it
; to really get rid of your map, use map$clear first, then heap$free the map pointer
if used intmap$destroy | used unsignedmap$destroy | used doublemap$destroy | used stringmap$destroy | defined include_everything
falign
mapcommon$destroy:
if used intmap$destroy | defined include_everything
intmap$destroy:
end if
if used unsignedmap$destroy | defined include_everything
unsignedmap$destroy:
end if
if used doublemap$destroy | defined include_everything
doublemap$destroy:
end if
if used stringmap$destroy | defined include_everything
stringmap$destroy:
end if
prolog mapcommon$destroy
call heap$free
epilog
end if
if used intmap$clear | used unsignedmap$clear | used stringmap$clear | defined include_everything
; two parameters: rdi == map, rsi == optional function to call (will pass key and value to it)
; we do _not_ delete keys or values, only the nodes themselves
; so if you need a cleaner to destroy keys/values, pass a function to do so in rsi
; NOTE: doublemap is separate because its args to the optional function to call get passed in xmm0,rdi instead of rdi,rsi
falign
map$clear:
if used intmap$clear | defined include_everything
intmap$clear:
end if
if used unsignedmap$clear | defined include_everything
unsignedmap$clear:
end if
if used stringmap$clear | defined include_everything
stringmap$clear:
end if
prolog map$clear
cmp qword [rdi+_avlofs_next], 0
je .alldone
test rsi, rsi
jz .nofunc
push rbx r12 r13
mov rbx, rdi
mov r12, rsi
mov r13, [rbx+_avlofs_next]
calign
.iter:
mov rdi, [r13+_avlofs_key]
mov rsi, [r13+_avlofs_value]
call r12
mov rdi, r13
mov r13, [r13+_avlofs_next]
call heap$free
test r13, r13
jnz .iter
; so at this point, we freed every node, clear the map structure itself
xor edx, edx
mov qword [rbx+_avlofs_parent], rdx ; root node
mov qword [rbx+_avlofs_right], rdx ; node count
mov qword [rbx+_avlofs_next], rdx ; first
mov qword [rbx+_avlofs_prev], rdx ; last
mov qword [rbx+_avlofs_trunk], rdx
mov qword [rbx+_avlofs_key], rdx
mov qword [rbx+_avlofs_value], rdx
pop r13 r12 rbx
epilog
calign
.alldone:
epilog
calign
.nofunc:
push rbx r13
mov rbx, rdi
mov r13, [rbx+_avlofs_next]
calign
.iter2:
mov rdi, r13
mov r13, [r13+_avlofs_next]
call heap$free
test r13, r13
jnz .iter2
; so at this point, we freed every node, clear the map structure itself
xor edx, edx
mov qword [rbx+_avlofs_parent], rdx ; root node
mov qword [rbx+_avlofs_right], rdx ; node count
mov qword [rbx+_avlofs_next], rdx ; first
mov qword [rbx+_avlofs_prev], rdx ; last
mov qword [rbx+_avlofs_trunk], rdx
mov qword [rbx+_avlofs_key], rdx
mov qword [rbx+_avlofs_value], rdx
pop r13 rbx
epilog
end if
if used doublemap$clear | defined include_everything
falign
doublemap$clear:
prolog doublemap$clear
cmp qword [rdi+_avlofs_next], 0
je .alldone
test rsi, rsi
jz .nofunc
push rbx r12 r13
mov rbx, rdi
mov r12, rsi
mov r13, [rbx+_avlofs_next]
calign
.iter:
movsd xmm0, [r13+_avlofs_key]
mov rdi, [r13+_avlofs_value]
call r12
mov rdi, r13
mov r13, [r13+_avlofs_next]
call heap$free
test r13, r13
jnz .iter
; so at this point, we freed every node, clear the map structure itself
xor edx, edx
mov qword [rbx+_avlofs_parent], rdx ; root node
mov qword [rbx+_avlofs_right], rdx ; node count
mov qword [rbx+_avlofs_next], rdx ; first
mov qword [rbx+_avlofs_prev], rdx ; last
mov qword [rbx+_avlofs_trunk], rdx
mov qword [rbx+_avlofs_key], rdx
mov qword [rbx+_avlofs_value], rdx
pop r13 r12 rbx
epilog
calign
.alldone:
epilog
calign
.nofunc:
push rbx r13
mov rbx, rdi
mov r13, [rbx+_avlofs_next]
calign
.iter2:
mov rdi, r13
mov r13, [r13+_avlofs_next]
call heap$free
test r13, r13
jnz .iter2
; so at this point, we freed every node, clear the map structure itself
xor edx, edx
mov qword [rbx+_avlofs_parent], rdx ; root node
mov qword [rbx+_avlofs_right], rdx ; node count
mov qword [rbx+_avlofs_next], rdx ; first
mov qword [rbx+_avlofs_prev], rdx ; last
mov qword [rbx+_avlofs_trunk], rdx
mov qword [rbx+_avlofs_key], rdx
mov qword [rbx+_avlofs_value], rdx
pop r13 rbx
epilog
end if
if used intmap$find_value | defined include_everything
; two args: rdi == map, rsi == key
; returns bool in eax as to whether we found it or not, and value in rdx if so
falign
intmap$find_value:
prolog intmap$find_value
call _intmap_locate_node
; normal return from _intmap_locate_node is in rax, but we know that r8 is the actual return, so go ahead and blast rax
test r9d, avl_status_found
jnz .found
xor eax, eax
epilog
calign
.found:
mov eax, 1
mov rdx, [r8+_avlofs_value]
epilog
end if
if used intmap$find | defined include_everything
; two args: rdi == map, rsi == key
; returns NODE in rax (zero if jacked up)
falign
intmap$find:
prolog intmap$find
call _intmap_locate_node
test r9d, avl_status_found
jnz .found
xor eax, eax
epilog
calign
.found:
mov rax, r8
epilog
end if
if used unsignedmap$find_value | defined include_everything
; two args: rdi == map, rsi == key
; returns bool in eax as to whether we found it or not, and value in rdx if so
falign
unsignedmap$find_value:
prolog unsignedmap$find_value
call _unsignedmap_locate_node
test r9d, avl_status_found
jnz .found
xor eax, eax
epilog
calign
.found:
mov eax, 1
mov rdx, [r8+_avlofs_value]
epilog
end if
if used unsignedmap$find | defined include_everything
; two args: rdi == map, rsi == key
; returns NODE in rax (zero if jacked up)
if defined unsignedmap_notinline
falign
unsignedmap$find:
prolog unsignedmap$find
call _unsignedmap_locate_node
test r9d, avl_status_found
jnz .found
xor eax, eax
epilog
calign
.found:
mov rax, r8
epilog
else
falign
unsignedmap$find:
prolog unsignedmap$find
mov rax, [rdi+_avlofs_parent] ; root node
test rax, rax
jz .locate_found
if align_inner
mov rdx, [rax+_avlofs_key]
mov r10, [rax+_avlofs_left]
mov r11, [rax+_avlofs_right]
cmp rsi, rdx
je .locate_found
cmovb rax, r10
cmova rax, r11
test rax, rax
jnz .locate_while
; if we made it here, we didn't find it, and the value in rax is already clear
epilog
end if
calign
.locate_while:
mov rdx, [rax+_avlofs_key]
mov r10, [rax+_avlofs_left]
mov r11, [rax+_avlofs_right]
cmp rsi, rdx
je .locate_found
cmovb rax, r10
cmova rax, r11
test rax, rax
jnz .locate_while
; if we made it here, we didn't find it, and the value in rax is already clear
epilog
calign
.locate_found:
epilog
end if
end if
if used unsignedmap$lowerbound | defined include_everything
; two args: rdi == map, rsi == key
; returns NODE in rax (zero if jacked up)
falign
unsignedmap$lowerbound:
prolog unsignedmap$lowerbound
mov rdx, [rdi+_avlofs_parent]
xor eax, eax
calign
.while:
test rdx, rdx
jz .do_ret
mov rcx, [rdx+_avlofs_key]
cmp rcx, rsi
ja .leftside
mov rdx, [rdx+_avlofs_right]
jmp .while
calign
.leftside:
mov rax, rdx
mov rdx, [rdx+_avlofs_left]
jmp .while
calign
.do_ret:
; whatever is in rax is sweet
epilog
end if
if used stringmap$find_value | defined include_everything
; two args: rdi == map, rsi == key
; returns bool in eax as to whether we found it or not, and value in rdx if so
falign
stringmap$find_value:
prolog stringmap$find_value
call _stringmap_locate_node
test r9d, avl_status_found
jnz .found
xor eax, eax
epilog
calign
.found:
mov eax, 1
mov rdx, [r8+_avlofs_value]
epilog
end if
if used stringmap$find | defined include_everything
; two args: rdi == map, rsi == key
; returns NODE in rax (zero if jacked up)
falign
stringmap$find:
prolog stringmap$find
call _stringmap_locate_node
test r9d, avl_status_found
jnz .found
xor eax, eax
epilog
calign
.found:
mov rax, r8
epilog
end if
if used doublemap$find_value | defined include_everything
; two args: rdi == map, xmm0 == key
; returns bool in eax as to whether we found it or not, and value in xmm0 if so
falign
doublemap$find_value:
prolog doublemap$find_value
call _doublemap_locate_node
test r9d, avl_status_found
jnz .found
xor eax, eax
epilog
calign
.found:
mov eax, 1
movq xmm0, [r8+_avlofs_value]
epilog
end if
if used doublemap$find | defined include_everything
; two args: rdi == map, xmm0 == key
; returns NODE in rax (zero if jacked up)
falign
doublemap$find:
prolog doublemap$find
call _doublemap_locate_node
test r9d, avl_status_found
jnz .found
xor eax, eax
epilog
calign
.found:
mov rax, r8
epilog
end if
if used intmap$foreach | used unsignedmap$foreach | used stringmap$foreach | defined include_everything
; two args: rdi == map, rsi == function to call with two args, rdi == key, rsi == value
; if the map is empty, nothing much happens
; note again, doublemap is separate, cuz of its use of xmm0 as the key argument
falign
map$foreach:
if used intmap$foreach | defined include_everything
intmap$foreach:
end if
if used unsignedmap$foreach | defined include_everything
unsignedmap$foreach:
end if
if used stringmap$foreach | defined include_everything
stringmap$foreach:
end if
prolog map$foreach
cmp qword [rdi+_avlofs_next], 0
je .alldone
push r12 r13
mov r12, rsi
mov r13, [rdi+_avlofs_next]
calign
.iter:
mov rdi, [r13+_avlofs_key]
mov rsi, [r13+_avlofs_value]
call r12
mov r13, [r13+_avlofs_next]
test r13, r13
jnz .iter
pop r13 r12
epilog
calign
.alldone:
epilog
end if
if used intmap$foreach_arg | used unsignedmap$foreach_arg | used stringmap$foreach_arg | defined include_everything
; three args: rdi == map, rsi == function to call with THREE args, rdx is arbitary arg... called func gets: rdi == key, rsi == value, rdx == arbitrary arg
falign
map$foreach_arg:
if used intmap$foreach_arg | defined include_everything
intmap$foreach_arg:
end if
if used unsignedmap$foreach_arg | defined include_everything
unsignedmap$foreach_arg:
end if
if used stringmap$foreach_arg | defined include_everything
stringmap$foreach_arg:
end if
prolog map$foreach_arg
cmp qword [rdi+_avlofs_next], 0
je .alldone
push rbx r12 r13
mov rbx, rdx ; save our arbitrary argument
mov r12, rsi
mov r13, [rdi+_avlofs_next]
calign
.iter:
mov rdi, [r13+_avlofs_key]
mov rsi, [r13+_avlofs_value]
mov rdx, rbx
call r12
mov r13, [r13+_avlofs_next]
test r13, r13
jnz .iter
pop r13 r12 rbx
epilog
calign
.alldone:
epilog
end if
if used doublemap$foreach | defined include_everything
falign
doublemap$foreach:
prolog doublemap$foreach
cmp qword [rdi+_avlofs_next], 0
je .alldone
push r12 r13
mov r12, rsi
mov r13, [rdi+_avlofs_next]
calign
.iter:
movsd xmm0, [r13+_avlofs_key]
mov rdi, [r13+_avlofs_value]
call r12
mov r13, [r13+_avlofs_next]
test r13, r13
jnz .iter
pop r13 r12
epilog
calign
.alldone:
epilog
end if
if used intmap$reverse_foreach | used unsignedmap$reverse_foreach | used stringmap$reverse_foreach | defined include_everything
; same as foreach, only we travel the list backward
falign
map$reverse_foreach:
if used intmap$reverse_foreach | defined include_everything
intmap$reverse_foreach:
end if
if used unsignedmap$reverse_foreach | defined include_everything
unsignedmap$reverse_foreach:
end if
if used stringmap$reverse_foreach | defined include_everything
stringmap$reverse_foreach:
end if
prolog map$reverse_foreach
cmp qword [rdi+_avlofs_prev], 0
je .alldone
push r12 r13
mov r12, rsi
mov r13, [rdi+_avlofs_prev]
calign
.iter:
mov rdi, [r13+_avlofs_key]
mov rsi, [r13+_avlofs_value]
call r12
mov r13, [r13+_avlofs_prev]
test r13, r13
jnz .iter
pop r13 r12
epilog
calign
.alldone:
epilog
end if
if used intmap$reverse_foreach_arg | used unsignedmap$reverse_foreach_arg | used stringmap$reverse_foreach_arg | defined include_everything
; same as foreach_arg, only we travel the list backward
falign
map$reverse_foreach_arg:
if used intmap$reverse_foreach_arg | defined include_everything
intmap$reverse_foreach_arg:
end if
if used unsignedmap$reverse_foreach_arg | defined include_everything
unsignedmap$reverse_foreach_arg:
end if
if used stringmap$reverse_foreach_arg | defined include_everything
stringmap$reverse_foreach_arg:
end if
prolog map$reverse_foreach_arg
cmp qword [rdi+_avlofs_prev], 0
je .alldone
push r12 r13 r14
mov r12, rsi
mov r13, [rdi+_avlofs_prev]
mov r14, rdx
calign
.iter:
mov rdi, [r13+_avlofs_key]
mov rsi, [r13+_avlofs_value]
mov rdx, r14
call r12
mov r13, [r13+_avlofs_prev]
test r13, r13
jnz .iter
pop r14 r13 r12
epilog
calign
.alldone:
epilog
end if
if used doublemap$reverse_foreach | defined include_everything
falign
doublemap$reverse_foreach:
prolog doublemap$reverse_foreach
cmp qword [rdi+_avlofs_prev], 0
je .alldone
push r12 r13
mov r12, rsi
mov r13, [rdi+_avlofs_prev]
calign
.iter:
movsd xmm0, [r13+_avlofs_key]
mov rdi, [r13+_avlofs_value]
call r12
mov r13, [r13+_avlofs_prev]
test r13, r13
jnz .iter
pop r13 r12
epilog
calign
.alldone:
epilog
end if
if used intmap$keys_to_array | used unsignedmap$keys_to_array | used doublemap$keys_to_array | used stringmap$keys_to_array | defined include_everything
; single arg: rdi == map
; returns a single heap$alloc'd block of adjacent keys from our map (iterates it to place them)
; if the map is empty, NULL is returned.
; (note: we are not type-specified here, just the 8 bytes stored in our key is placed)
; up to the caller to distinguish what the key might actually be
; note: this one is the same for all four variants
falign
map$keys_to_array:
if used intmap$keys_to_array | defined include_everything
intmap$keys_to_array:
end if
if used unsignedmap$keys_to_array | defined include_everything
unsignedmap$keys_to_array:
end if
if used doublemap$keys_to_array | defined include_everything
doublemap$keys_to_array:
end if
if used stringmap$keys_to_array | defined include_everything
stringmap$keys_to_array:
end if
prolog map$keys_to_array
cmp qword [rdi+_avlofs_right], 0 ; node count
je .nullret
push rdi
mov rdi, qword [rdi+_avlofs_right] ; node count
shl rdi, 3 ; x 8
call heap$alloc
pop rdi
; return now sitting in rax
mov rdx, [rdi+_avlofs_next] ; first
mov rcx, rax ; our rolling buffer
calign
.iter:
mov r8, [rdx+_avlofs_key]
mov [rcx], r8
add rcx, 8
mov rdx, [rdx+_avlofs_next]
test rdx, rdx
jnz .iter
epilog
calign
.nullret:
xor eax, eax
epilog
end if
if used intmap$values_to_array | used unsignedmap$values_to_array | used doublemap$values_to_array | used stringmap$values_to_array | defined include_everything
; single arg: rdi == map
; returns a single heap$alloc'd block of adjacent values from our map (iterates it to place them)
; if the map is empty, NULL is returned.
falign
map$values_to_array:
if used intmap$values_to_array | defined include_everything
intmap$values_to_array:
end if
if used unsignedmap$values_to_array | defined include_everything
unsignedmap$values_to_array:
end if
if used doublemap$values_to_array | defined include_everything
doublemap$values_to_array:
end if
if used stringmap$values_to_array | defined include_everything
stringmap$values_to_array:
end if
prolog map$values_to_array
cmp qword [rdi+_avlofs_right], 0 ; node count
je .nullret
push rdi
mov rdi, qword [rdi+_avlofs_right] ; node count
shl rdi, 3 ; x 8
call heap$alloc
pop rdi
; return now sitting in rax
mov rdx, [rdi+_avlofs_next] ; first
mov rcx, rax ; our rolling buffer
calign
.iter:
mov r8, [rdx+_avlofs_value]
mov [rcx], r8
add rcx, 8
mov rdx, [rdx+_avlofs_next]
test rdx, rdx
jnz .iter
epilog
calign
.nullret:
xor eax, eax
epilog
end if
if used intmap$keys_to_list | used unsignedmap$keys_to_list | used unsignedmap$keys_to_list | used stringmap$keys_to_list | defined include_everything
; single arg: rdi == map
; returns a list$new list of keys from our map (iterates it to list$push_back)
; if the map is empty, an empty list is returned (still list$new regardless)
; this one is also the same for all four variants
falign
map$keys_to_list:
if used intmap$keys_to_list | defined include_everything
intmap$keys_to_list:
end if
if used unsignedmap$keys_to_list | defined include_everything
unsignedmap$keys_to_list:
end if
if used doublemap$keys_to_list | defined include_everything
doublemap$keys_to_list:
end if
if used stringmap$keys_to_list | defined include_everything
stringmap$keys_to_list:
end if
prolog map$keys_to_list
push rdi
call list$new
pop rdi
cmp qword [rdi+_avlofs_right], 0 ; node count
je .alldone
push rbx r12
mov rbx, rax ; save our list
mov r12, [rdi+_avlofs_next] ; first
calign
.iter:
mov rdi, rbx
mov rsi, [r12+_avlofs_key]
call list$push_back
mov r12, [r12+_avlofs_next]
test r12, r12
jnz .iter
mov rax, rbx
pop r12 rbx
epilog
calign
.alldone:
; list$new is sitting in rax already, outta here
epilog
end if
if used intmap$values_to_list | used unsignedmap$values_to_list | used doublemap$values_to_list | used stringmap$values_to_list | defined include_everything
; single arg: rdi == map
; returns a list$new list of values from our map (iterates it to list$push_back)
; if the map is empty, an empty list is returned (still list$new regardless)
; this one is also the same for all four variants
falign
map$values_to_list:
if used intmap$values_to_list | defined include_everything
intmap$values_to_list:
end if
if used unsignedmap$values_to_list | defined include_everything
unsignedmap$values_to_list:
end if
if used doublemap$values_to_list | defined include_everything
doublemap$values_to_list:
end if
if used stringmap$values_to_list | defined include_everything
stringmap$values_to_list:
end if
prolog map$values_to_list
push rdi
call list$new
pop rdi
cmp qword [rdi+_avlofs_right], 0 ; node count
je .alldone
push rbx r12
mov rbx, rax ; save our list
mov r12, [rdi+_avlofs_next] ; first
calign
.iter:
mov rdi, rbx
mov rsi, [r12+_avlofs_value]
call list$push_back
mov r12, [r12+_avlofs_next]
test r12, r12
jnz .iter
mov rax, rbx
pop r12 rbx
epilog
calign
.alldone:
; list$new is sitting in rax already, outta here
epilog
end if
avl_unbalanced = 0x1
avl_unb_left = 0x2
avl_unb_heavy = 0x4
avl_unb_mask = 0x7
avl_left_heavy = 0x7
avl_left_balanced = 0x3
avl_abs_balanced = 0
avl_right_balanced = 0x1
avl_right_heavy = 0x5
avl_trav_left = 0x8
avl_all = 0xf
avl_status_found = 0x4
avl_status_left = 0x8
avl_status_lcop = 0x10
if used _intmap_locate_node | defined include_everything
falign
_intmap_locate_node:
if profile_map_internals
prolog _intmap_locate_node
else
prolog_noprofile_silent _intmap_locate_node
end if
xor r8d, r8d
xor r9d, r9d
xor r10d, r10d
xor ecx, ecx
mov rax, [rdi+_avlofs_parent] ; start with our root node
calign
.while:
test rax, rax
jz .done
mov r8, rax
mov rdx, [rax+_avlofs_key]
sub rdx, rsi
jz .found
jl .follow_right
bts r10d, ecx
add ecx, 1
or r9d, avl_status_left
mov rax, [rax+_avlofs_left]
jmp .while
calign
.follow_right:
and r9d, 0xffff - avl_status_left
add ecx, 1
mov rax, [rax+_avlofs_right]
jmp .while
calign
.found:
or r9d, avl_status_found
mov rax, r8
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.done:
mov rax, r8
if profile_map_internals
epilog
else
epilog_noprofile
end if
end if
if used _unsignedmap_locate_node | defined include_everything
falign
_unsignedmap_locate_node:
if profile_map_internals
prolog _unsignedmap_locate_node
else
prolog_noprofile_silent _unsignedmap_locate_node
end if
xor r8d, r8d
xor r9d, r9d
xor r10d, r10d
xor ecx, ecx
mov rax, [rdi+_avlofs_parent] ; start with our root node
calign
.while:
test rax, rax
jz .done
mov r8, rax
cmp rsi, [rax+_avlofs_key]
je .found
ja .follow_right
bts r10d, ecx
add ecx, 1
or r9d, avl_status_left
mov rax, [rax+_avlofs_left]
jmp .while
calign
.follow_right:
and r9d, 0xffff - avl_status_left
add ecx, 1
mov rax, [rax+_avlofs_right]
jmp .while
calign
.found:
or r9d, avl_status_found
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.done:
mov rax, r8
if profile_map_internals
epilog
else
epilog_noprofile
end if
end if
if used _unsignedmap_locate_node_specific | defined include_everything
; rdi == our map, rsi == key, rdx == _value_ (not node, but we'll convert it to the node before we return)
falign
_unsignedmap_locate_node_specific:
if profile_map_internals
prolog _unsignedmap_locate_node_specific
else
prolog_noprofile_silent _unsignedmap_locate_node_specific
end if
xor r8d, r8d
xor r9d, r9d
xor r10d, r10d
xor ecx, ecx
mov rax, [rdi+_avlofs_parent] ; start with our root node
calign
.while:
test rax, rax
jz .done
mov r8, rax
push rdx
mov rdx, [rax+_avlofs_key]
cmp rdx, rsi
je .found
jb .follow_right
pop rdx
bts r10d, ecx
add ecx, 1
or r9d, avl_status_left
mov rax, [rax+_avlofs_left]
jmp .while
calign
.follow_right:
pop rdx
and r9d, 0xffff - avl_status_left
add ecx, 1
mov rax, [rax+_avlofs_right]
jmp .while
calign
.found:
pop rdx
cmp [r8+_avlofs_value], rdx
je .found_at_top
cmp qword [r8+_avlofs_trunk], 0
je .done
; else, we need to loop with _rax_ and not r8 and find our value
calign
.searchtop:
mov rax, [rax+_avlofs_trunk]
test rax, rax
jz .done
cmp [rax+_avlofs_value], rdx
jne .searchtop
mov rdx, rax ; this is the specific node we are deleting
or r9d, avl_status_found
mov rax, r8
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.found_at_top:
mov rdx, r8 ; this is the specific node we are deleting
or r9d, avl_status_found
mov rax, r8
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.done:
mov rax, r8
if profile_map_internals
epilog
else
epilog_noprofile
end if
end if
if used _doublemap_locate_node | defined include_everything
falign
_doublemap_locate_node:
if profile_map_internals
prolog _doublemap_locate_node
else
prolog_noprofile_silent _doublemap_locate_node
end if
xor r8d, r8d
xor r9d, r9d
xor r10d, r10d
xor ecx, ecx
mov rax, [rdi+_avlofs_parent] ; start with our root node
calign
.while:
test rax, rax
jz .done
mov r8, rax
movq xmm1, [rax+_avlofs_key]
comisd xmm0, xmm1
je .found
ja .follow_right
bts r10d, ecx
add ecx, 1
or r9d, avl_status_left
mov rax, [rax+_avlofs_left]
jmp .while
calign
.follow_right:
and r9d, 0xffff - avl_status_left
add ecx, 1
mov rax, [rax+_avlofs_right]
jmp .while
calign
.found:
or r9d, avl_status_found
mov rax, r8
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.done:
mov rax, r8
if profile_map_internals
epilog
else
epilog_noprofile
end if
end if
if used _stringmap_locate_node | defined include_everything
falign
_stringmap_locate_node:
if profile_map_internals
prolog _stringmap_locate_node
else
prolog_noprofile_silent _stringmap_locate_node
end if
xor r8d, r8d
xor r9d, r9d
xor r10d, r10d
xor ecx, ecx
mov rax, [rdi+_avlofs_parent] ; start with our root node
calign
.while:
test rax, rax
jz .done
mov r8, rax
; we have to preserve nearly all of our regs here... TODO: redo using stackvars?
push rdi rsi r8 r9 r10 rcx rax
mov rdi, [rax+_avlofs_key]
call string$compare
mov rdx, rax
pop rax rcx r10 r9 r8 rsi rdi
cmp rdx, 0
je .found
jl .follow_right
bts r10d, ecx
add ecx, 1
or r9d, avl_status_left
mov rax, [rax+_avlofs_left]
jmp .while
calign
.follow_right:
and r9d, 0xffff - avl_status_left
add ecx, 1
mov rax, [rax+_avlofs_right]
jmp .while
calign
.found:
or r9d, avl_status_found
mov rax, r8
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.done:
mov rax, r8
if profile_map_internals
epilog
else
epilog_noprofile
end if
end if
if used _map_successor | defined include_everything
falign
_map_successor:
if profile_map_internals
prolog _map_successor
else
prolog_noprofile_silent _map_successor
end if
mov r9, rsi
mov rax, [r9+_avlofs_right]
test rax, rax
jz .exit_ok
mov rsi, [rax+_avlofs_left]
test rsi, rsi
jz .exit_ok
mov rax, rsi
jmp .follow_left
calign
.follow_left:
mov rsi, [rax+_avlofs_left]
test rsi, rsi
jz .exit_ok
mov rax, rsi
jmp .follow_left
calign
.exit_ok:
if profile_map_internals
epilog
else
epilog_noprofile
end if
end if
if used _map_left_lighter | defined include_everything
; rdi: map, rsi: node
; profiling intentionally disabled here cuz we jump around between them, and is thus encapsed in the calling funcs
falign
_map_left_lighter:
mov r11, rsi
; left_lighter_iteration fallthrough copy to avoid 2 large nops
mov esi, [rsi+_avlofs_flags]
test esi, avl_unb_mask
jz _map_left_lighter_make_rb
test esi, avl_unb_left
jz _map_left_lighter_make_rh
and dword [r11+_avlofs_flags], 0xffff - avl_unb_mask
cmp qword [r11+_avlofs_parent], 0
je _map_left_lighter_exit_ok
; left_lighter_subtree fallthrough copy to avoid nopfill
mov rax, r11
mov r11, [r11+_avlofs_parent]
cmp rax, [r11+_avlofs_left]
je _map_left_lighter_iteration
jmp _map_right_lighter_iteration
falign
_map_left_lighter_iteration:
mov esi, [r11+_avlofs_flags]
test esi, avl_unb_mask
jz _map_left_lighter_make_rb
test esi, avl_unb_left
jz _map_left_lighter_make_rh
and dword [r11+_avlofs_flags], 0xffff - avl_unb_mask
cmp qword [r11+_avlofs_parent], 0
je _map_left_lighter_exit_ok
; left_lighter_subtree fallthrough copy to avoid nopfill
mov rax, r11
mov r11, [r11+_avlofs_parent]
cmp rax, [r11+_avlofs_left]
je _map_left_lighter_iteration
jmp _map_right_lighter_iteration
falign
_map_left_lighter_subtree:
mov rax, r11
mov r11, [r11+_avlofs_parent]
cmp rax, [r11+_avlofs_left]
je _map_left_lighter_iteration
jmp _map_right_lighter_iteration
falign
_map_left_lighter_make_rh:
and dword [r11+_avlofs_flags], 0xffff - avl_unb_mask
or dword [r11+_avlofs_flags], avl_right_heavy
mov rax, r11
push r11
mov rsi, r11
call _map_rebalance
pop r11
mov r11, [r11+_avlofs_parent]
cmp r11, [rdi+_avlofs_parent]
je _map_left_lighter_exit_ok
test dword [r11+_avlofs_flags], avl_unbalanced
jnz _map_left_lighter_exit_ok
jmp _map_left_lighter_subtree
falign
_map_left_lighter_make_rb:
and dword [r11+_avlofs_flags], 0xffff - avl_unb_mask
or dword [r11+_avlofs_flags], avl_right_balanced
ret
falign
_map_left_lighter_exit_ok:
ret
end if
if used _map_right_lighter | defined include_everything
falign
_map_right_lighter:
mov r11, rsi
; map_right_lighter_iteration fallthrough copy to avoid two large nop fills
mov esi, [rsi+_avlofs_flags]
test esi, avl_unb_mask
jz _map_right_lighter_make_lb
test esi, avl_unb_left
jnz _map_right_lighter_make_lh
and dword [r11+_avlofs_flags], 0xffff - avl_unb_mask
cmp qword [r11+_avlofs_parent], 0
je _map_right_lighter_exit_ok
; map_right_lighter_subtree fallthrough copy to avoid nop fills
mov rax, r11
mov r11, [r11+_avlofs_parent]
cmp rax, [r11+_avlofs_left]
je _map_left_lighter_iteration
jmp _map_right_lighter_iteration
calign
_map_right_lighter_iteration:
mov esi, [r11+_avlofs_flags]
test esi, avl_unb_mask
jz _map_right_lighter_make_lb
test esi, avl_unb_left
jnz _map_right_lighter_make_lh
and dword [r11+_avlofs_flags], 0xffff - avl_unb_mask
cmp qword [r11+_avlofs_parent], 0
je _map_right_lighter_exit_ok
; map_right_lighter_subtree fallthrough copy to avoid nop fills
mov rax, r11
mov r11, [r11+_avlofs_parent]
cmp rax, [r11+_avlofs_left]
je _map_left_lighter_iteration
jmp _map_right_lighter_iteration
calign
_map_right_lighter_subtree:
mov rax, r11
mov r11, [r11+_avlofs_parent]
cmp rax, [r11+_avlofs_left]
je _map_left_lighter_iteration
jmp _map_right_lighter_iteration
calign
_map_right_lighter_make_lh:
and dword [r11+_avlofs_flags], 0xffff - avl_unb_mask
or dword [r11+_avlofs_flags], avl_left_heavy
mov rax, r11
push r11
mov rsi, r11
call _map_rebalance
pop r11
mov r11, [r11+_avlofs_parent]
cmp r11, [rdi+_avlofs_parent]
je _map_right_lighter_exit_ok
test dword [r11+_avlofs_flags], avl_unbalanced
jnz _map_right_lighter_exit_ok
jmp _map_right_lighter_subtree
calign
_map_right_lighter_make_lb:
and dword [r11+_avlofs_flags], 0xffff - avl_unb_mask
or dword [r11+_avlofs_flags], avl_left_balanced
ret
calign
_map_right_lighter_exit_ok:
ret
end if
if used _map_rebalance | defined include_everything
; rdi: map, rsi: node to rebalance, edx: [search]flags
falign
_map_rebalance:
if profile_map_internals
prolog _map_rebalance
else
prolog_noprofile_silent _map_rebalance
end if
mov rcx, rsi
mov r11, [rsi+_avlofs_parent]
mov r8, [rsi+_avlofs_left]
mov r10, [rsi+_avlofs_right]
test r11, r11
jz .parent_ok
and edx, 0xffff - avl_status_lcop
cmp rcx, [r11+_avlofs_right]
je .parent_ok
or edx, avl_status_lcop
; parent_ok fallthrough copy
test dword [rcx+_avlofs_flags], avl_unb_left
jz .right
mov eax, [r8+_avlofs_flags]
mov r9, r8
; mov r9, [rcx+_avlofs_left]
test eax, avl_unbalanced
; test dword [r9+_avlofs_flags], avl_unbalanced
jz .ll
test eax, avl_unb_left
; test dword [r9+_avlofs_flags], avl_unb_left
jz .lr
jmp .ll
calign
.parent_ok:
test dword [rcx+_avlofs_flags], avl_unb_left
jz .right
mov eax, [r8+_avlofs_flags]
mov r9, r8
; mov r9, [rcx+_avlofs_left]
test eax, avl_unbalanced
; test dword [r9+_avlofs_flags], avl_unbalanced
jz .ll
test eax, avl_unb_left
; test dword [r9+_avlofs_flags], avl_unb_left
jz .lr
jmp .ll
calign
.right:
mov eax, [r10+_avlofs_flags]
mov r9, r10
; mov r9, [rcx+_avlofs_right]
test eax, avl_unbalanced
; test dword [r9+_avlofs_flags], avl_unbalanced
jz .rr
test eax, avl_unb_left
; test dword [r9+_avlofs_flags], avl_unb_left
jz .rr
jmp .rl
calign
.ll:
mov r10, [r9+_avlofs_right]
test r11, r11
jz .ll_new_root
test edx, avl_status_lcop
jz .ll2
mov [r11+_avlofs_left], r9
jmp .ll3
calign
.ll2:
mov [r11+_avlofs_right], r9
if align_inner
; ll3 fallthrough copy to avoid nop fill
mov [rcx+_avlofs_parent], r9
mov [rcx+_avlofs_left], r10
mov [r9+_avlofs_parent], r11
mov [r9+_avlofs_right], rcx
test r10, r10
jz .ll4
mov [r10+_avlofs_parent], rcx
; ll4 fallthrough copy to avoid nop fill
test dword [r9+_avlofs_flags], avl_unb_mask
jz .ll5
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
if profile_map_internals
epilog
else
epilog_noprofile
end if
end if
calign
.ll3:
mov [rcx+_avlofs_parent], r9
mov [rcx+_avlofs_left], r10
mov [r9+_avlofs_parent], r11
mov [r9+_avlofs_right], rcx
test r10, r10
jz .ll4
mov [r10+_avlofs_parent], rcx
if align_inner
; ll4 fallthrough copy to avoid nop fill
test dword [r9+_avlofs_flags], avl_unb_mask
jz .ll5
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
if profile_map_internals
epilog
else
epilog_noprofile
end if
end if
calign
.ll4:
test dword [r9+_avlofs_flags], avl_unb_mask
jz .ll5
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.ll5:
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
or dword [r9+_avlofs_flags], avl_right_balanced
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rcx+_avlofs_flags], avl_left_balanced
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.lr:
mov r10, [r9+_avlofs_right]
mov r8, [r10+_avlofs_left]
test r11, r11
jz .lr_new_root
test edx, avl_status_lcop
jz .lr2
mov [r11+_avlofs_left], r10
jmp .lr3
calign
.lr2:
mov [r11+_avlofs_right], r10
if align_inner
; lr3 fallthrough copy to avoid nop fill
mov [r10+_avlofs_parent], r11
mov r11, [r10+_avlofs_right]
mov [r10+_avlofs_left], r9
mov [r10+_avlofs_right], rcx
mov [rcx+_avlofs_parent], r10
mov [rcx+_avlofs_left], r11
mov [r9+_avlofs_parent], r10
mov [r9+_avlofs_right], r8
test r8, r8
jz .lr4
mov [r8+_avlofs_parent], r9
; lr4 fallthrough copy to avoid nop fill
test r11, r11
jz .lr5
mov [r11+_avlofs_parent], rcx
; lr5 fallthrough copy to avoid nop fill
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
test dword [r10+_avlofs_flags], avl_unbalanced
jz .lr7
test dword [r10+_avlofs_flags], avl_unb_left
jz .lr6
or dword [rcx+_avlofs_flags], avl_right_balanced
jmp .lr7
end if
calign
.lr3:
mov [r10+_avlofs_parent], r11
mov r11, [r10+_avlofs_right]
mov [r10+_avlofs_left], r9
mov [r10+_avlofs_right], rcx
mov [rcx+_avlofs_parent], r10
mov [rcx+_avlofs_left], r11
mov [r9+_avlofs_parent], r10
mov [r9+_avlofs_right], r8
test r8, r8
jz .lr4
mov [r8+_avlofs_parent], r9
if align_inner
; lr4 fallthrough copy to avoid nop fill
test r11, r11
jz .lr5
mov [r11+_avlofs_parent], rcx
; lr5 fallthrough copy to avoid nop fill
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
test dword [r10+_avlofs_flags], avl_unbalanced
jz .lr7
test dword [r10+_avlofs_flags], avl_unb_left
jz .lr6
or dword [rcx+_avlofs_flags], avl_right_balanced
jmp .lr7
end if
calign
.lr4:
test r11, r11
jz .lr5
mov [r11+_avlofs_parent], rcx
if align_inner
; lr5 fallthrough copy to avoid nop fill
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
test dword [r10+_avlofs_flags], avl_unbalanced
jz .lr7
test dword [r10+_avlofs_flags], avl_unb_left
jz .lr6
or dword [rcx+_avlofs_flags], avl_right_balanced
jmp .lr7
end if
calign
.lr5:
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
test dword [r10+_avlofs_flags], avl_unbalanced
jz .lr7
test dword [r10+_avlofs_flags], avl_unb_left
jz .lr6
or dword [rcx+_avlofs_flags], avl_right_balanced
jmp .lr7
calign
.lr6:
or dword [r9+_avlofs_flags], avl_left_balanced
and dword [r10+_avlofs_flags], 0xffff - avl_unb_mask
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.lr7:
and dword [r10+_avlofs_flags], 0xffff - avl_unb_mask
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.rl:
mov r10, [r9+_avlofs_left]
mov r8, [r10+_avlofs_right]
test r11, r11
jz .rl_new_root
test edx, avl_status_lcop
jz .rl2
mov [r11+_avlofs_left], r10
jmp .rl3
calign
.rl2:
mov [r11+_avlofs_right], r10
if align_inner
; rl3 fallthrough copy to avoid nop fill
mov [r10+_avlofs_parent], r11
mov r11, [r10+_avlofs_left]
mov [r10+_avlofs_right], r9
mov [r10+_avlofs_left], rcx
mov [rcx+_avlofs_parent], r10
mov [rcx+_avlofs_right], r11
mov [r9+_avlofs_parent], r10
mov [r9+_avlofs_left], r8
test r8, r8
jz .rl4
mov [r8+_avlofs_parent], r9
; rl4 fallthrough copy to avoid nop fill
test r11, r11
jz .rl5
mov [r11+_avlofs_parent], rcx
; rl5 fallthrough copy to avoid nop fill
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
test dword [r10+_avlofs_flags], avl_unbalanced
jz .rl7
test dword [r10+_avlofs_flags], avl_unb_left
jnz .rl6
or dword [rcx+_avlofs_flags], avl_left_balanced
jmp .rl7
end if
calign
.rl3:
mov [r10+_avlofs_parent], r11
mov r11, [r10+_avlofs_left]
mov [r10+_avlofs_right], r9
mov [r10+_avlofs_left], rcx
mov [rcx+_avlofs_parent], r10
mov [rcx+_avlofs_right], r11
mov [r9+_avlofs_parent], r10
mov [r9+_avlofs_left], r8
test r8, r8
jz .rl4
mov [r8+_avlofs_parent], r9
if align_inner
; rl4 fallthrough copy to avoid nop fill
test r11, r11
jz .rl5
mov [r11+_avlofs_parent], rcx
; rl5 fallthrough copy to avoid nop fill
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
test dword [r10+_avlofs_flags], avl_unbalanced
jz .rl7
test dword [r10+_avlofs_flags], avl_unb_left
jnz .rl6
or dword [rcx+_avlofs_flags], avl_left_balanced
jmp .rl7
end if
calign
.rl4:
test r11, r11
jz .rl5
mov [r11+_avlofs_parent], rcx
if align_inner
; rl5 fallthrough copy to avoid nop fill
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
test dword [r10+_avlofs_flags], avl_unbalanced
jz .rl7
test dword [r10+_avlofs_flags], avl_unb_left
jnz .rl6
or dword [rcx+_avlofs_flags], avl_left_balanced
jmp .rl7
end if
calign
.rl5:
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
test dword [r10+_avlofs_flags], avl_unbalanced
jz .rl7
test dword [r10+_avlofs_flags], avl_unb_left
jnz .rl6
or dword [rcx+_avlofs_flags], avl_left_balanced
jmp .rl7
calign
.rl6:
or dword [r9+_avlofs_flags], avl_right_balanced
if align_inner
; rl7 fallthrough copy to avoid nop fill
and dword [r10+_avlofs_flags], 0xffff - avl_unb_mask
if profile_map_internals
epilog
else
epilog_noprofile
end if
end if
calign
.rl7:
and dword [r10+_avlofs_flags], 0xffff - avl_unb_mask
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.rr:
mov r10, [r9+_avlofs_left]
test r11, r11
jz .rr_new_root
test edx, avl_status_lcop
jz .rr2
mov [r11+_avlofs_left], r9
jmp .rr3
calign
.rr2:
mov [r11+_avlofs_right], r9
if align_inner
; rr3 fallthrough copy to avoid nop fill
mov [rcx+_avlofs_parent], r9
mov [rcx+_avlofs_right], r10
mov [r9+_avlofs_parent], r11
mov [r9+_avlofs_left], rcx
test r10, r10
jz .rr4
mov [r10+_avlofs_parent], rcx
; rr4 fallthrough copy to avoid nop fill
test dword [r9+_avlofs_flags], avl_unb_mask
jz .rr5
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
if profile_map_internals
epilog
else
epilog_noprofile
end if
end if
calign
.rr3:
mov [rcx+_avlofs_parent], r9
mov [rcx+_avlofs_right], r10
mov [r9+_avlofs_parent], r11
mov [r9+_avlofs_left], rcx
test r10, r10
jz .rr4
mov [r10+_avlofs_parent], rcx
if align_inner
; rr4 fallthrough copy to avoid nop fill
test dword [r9+_avlofs_flags], avl_unb_mask
jz .rr5
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
if profile_map_internals
epilog
else
epilog_noprofile
end if
end if
calign
.rr4:
test dword [r9+_avlofs_flags], avl_unb_mask
jz .rr5
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.rr5:
and dword [r9+_avlofs_flags], 0xffff - avl_unb_mask
or dword [r9+_avlofs_flags], avl_left_balanced
and dword [rcx+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rcx+_avlofs_flags], avl_right_balanced
if profile_map_internals
epilog
else
epilog_noprofile
end if
calign
.ll_new_root:
mov [rdi+_avlofs_parent], r9
jmp .ll3
calign
.lr_new_root:
mov [rdi+_avlofs_parent], r10
jmp .lr3
calign
.rl_new_root:
mov [rdi+_avlofs_parent], r10
jmp .rl3
calign
.rr_new_root:
mov [rdi+_avlofs_parent], r9
jmp .rr3
end if
; this causes a bit of code bloat using modified copies of each of these
; for each variant... TODO: function pointers instead?
if used intmap$insert_unique | defined include_everything
; rdi == map, rsi == key, rdx == value
; rax == bool as to whether the insert succeeded or not (unique constraint violated)
falign
intmap$insert_unique:
prolog intmap$insert_unique
push rdi rsi rdx
mov edi, avlnode_size
call heap$alloc
pop rdx rsi rdi
xor ecx, ecx
mov [rax+_avlofs_key], rsi
mov [rax+_avlofs_value], rdx
mov [rax+_avlofs_left], rcx
mov [rax+_avlofs_right], rcx
mov [rax+_avlofs_trunk], rcx
mov dword [rax+_avlofs_flags], 0
add qword [rdi+_avlofs_right], 1 ; increment our list node count
cmp qword [rdi+_avlofs_parent], 0
je .no_root
; so at this point, rdi still has our map, rsi still has our key, rdx has our value but we don't care about it anymore
; and rax has our spanking new node
push rax
call _intmap_locate_node
; normal return from _intmap_locate_node is in rax, but we know that r8 is the actual return, so go ahead and blast rax
pop rax
test r9d, avl_status_found
jnz .node_is_equal
; rdi still our map, rsi still our key, though we don't care about it anymore either, rax is our new node, r8 is our return
; from _intmap_locate_node, r9d is flags, r10d pathflags, ecx is pathcount
mov [rax+_avlofs_parent], r8 ; link our parent with the return
test r9d, avl_status_left
jz .node_b_right
mov [r8+_avlofs_left], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
mov [rax+_avlofs_next], r8
mov rdx, [r8+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
mov [r8+_avlofs_prev], rax
test rdx, rdx
jz .linkleft_setlast
mov [rdx+_avlofs_next], rax
jmp .check_balance
calign
.linkleft_setlast:
mov [rdi+_avlofs_next], rax
jmp .check_balance
calign
.link_insert_order:
mov qword [rax+_avlofs_next], 0
mov rdx, [rdi+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
test rdx, rdx
jz .linkleft_set_first
mov [rdx+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.linkleft_set_first:
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.node_b_right:
mov [r8+_avlofs_right], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
test rdx, rdx
jz .linkright_setlast
mov [rdx+_avlofs_prev], rax
jmp .check_balance
calign
.linkright_setlast:
mov [rdi+_avlofs_prev], rax
calign
.check_balance:
sub ecx, 1
mov rax, [rax+_avlofs_parent]
mov r8d, dword [rax+_avlofs_flags]
and r8d, avl_unb_mask
bt r10d, ecx
jnc .trav_right
; trav_left:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r8d, 1
or r8d, r11d
mov r9d, r8d
shl r8d, 1
shl r11d, 2
add r8d, r9d
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
test r8d, avl_unb_left
jz .exit_ok
jmp .check_heavy
calign
.trav_right:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r11d, 1
and r8d, r11d
shl r8d, 2
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
mov r9d, r8d
and r9d, avl_unb_left + avl_unbalanced
xor r9d, avl_unbalanced
test r9d, r9d
jnz .exit_ok
calign
.check_heavy:
test dword [rax+_avlofs_flags], avl_unb_heavy
jnz .node_is_heavy
cmp rax, [rdi+_avlofs_parent]
je .exit_ok
jmp .check_balance
calign
.node_is_heavy:
mov rsi, rax
mov edx, r9d
call _map_rebalance
mov eax, 1 ; return true
epilog
calign
.exit_ok:
mov eax, 1
epilog
calign
.no_root:
mov [rdi+_avlofs_parent], rax
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
mov qword [rax+_avlofs_parent], 0
mov qword [rax+_avlofs_next], 0
mov qword [rax+_avlofs_prev], 0
mov eax, 1
epilog
calign
.node_is_equal:
sub qword [rdi+_avlofs_right], 1 ; decrement our count again
mov rdi, rax
call heap$free
xor eax, eax ; 0 ret
epilog
end if
if used unsignedmap$insert_unique | defined include_everything
; rdi == map, rsi == key, rdx == value
; rax == bool as to whether the insert succeeded or not (unique constraint violated)
falign
unsignedmap$insert_unique:
prolog unsignedmap$insert_unique
push rdi rsi rdx
mov edi, avlnode_size
call heap$alloc
pop rdx rsi rdi
xor ecx, ecx
mov [rax+_avlofs_key], rsi
mov [rax+_avlofs_value], rdx
mov [rax+_avlofs_left], rcx
mov [rax+_avlofs_right], rcx
mov [rax+_avlofs_trunk], rcx
mov dword [rax+_avlofs_flags], ecx
add qword [rdi+_avlofs_right], 1 ; increment the map's nodecount
cmp qword [rdi+_avlofs_parent], 0
je .no_root
; so at this point, rdi still has our map, rsi still has our key, rdx has our value but we don't care about it anymore
; and rax has our spanking new node
push rax
call _unsignedmap_locate_node
pop rax
test r9d, avl_status_found
jnz .node_is_equal
; normal return from _unsignedmap_locate_node is in rax, but we know that r8 is the actual return
; rdi still our map, rsi still our key, though we don't care about it anymore either, rax is our new node, r8 is our return
; from _unsignedmap_locate_node, r9d is flags, r10d pathflags, ecx is pathcount
mov [rax+_avlofs_parent], r8 ; link our parent with the return
test r9d, avl_status_left
jz .node_b_right
mov [r8+_avlofs_left], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
mov [rax+_avlofs_next], r8
mov rdx, [r8+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
mov [r8+_avlofs_prev], rax
test rdx, rdx
jz .linkleft_setlast
mov [rdx+_avlofs_next], rax
calign
.check_balance:
sub ecx, 1
mov rax, [rax+_avlofs_parent]
mov r8d, dword [rax+_avlofs_flags]
and r8d, avl_unb_mask
bt r10d, ecx
jnc .trav_right
; trav_left:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r8d, 1
or r8d, r11d
mov r9d, r8d
shl r8d, 1
shl r11d, 2
add r8d, r9d
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
test r8d, avl_unb_left
jz .exit_ok
; check_heavy fallthrough copy
test dword [rax+_avlofs_flags], avl_unb_heavy
jnz .node_is_heavy
cmp rax, [rdi+_avlofs_parent]
je .exit_ok
jmp .check_balance
calign
.node_b_right:
mov [r8+_avlofs_right], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
test rdx, rdx
jz .linkright_setlast
mov [rdx+_avlofs_prev], rax
jmp .check_balance
calign
.link_insert_order:
mov qword [rax+_avlofs_next], 0
mov rdx, [rdi+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
test rdx, rdx
jz .linkleft_set_first
mov [rdx+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.linkright_setlast:
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.trav_right:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r11d, 1
and r8d, r11d
shl r8d, 2
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
mov r9d, r8d
and r9d, avl_unb_left + avl_unbalanced
xor r9d, avl_unbalanced
test r9d, r9d
jnz .exit_ok
; check_heavy fallthrough copy
test dword [rax+_avlofs_flags], avl_unb_heavy
jnz .node_is_heavy
cmp rax, [rdi+_avlofs_parent]
je .exit_ok
jmp .check_balance
calign
.node_is_heavy:
mov rsi, rax
mov edx, r9d
call _map_rebalance
mov eax, 1 ; return true
epilog
calign
.linkleft_setlast:
mov [rdi+_avlofs_next], rax
jmp .check_balance
calign
.linkleft_set_first:
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.exit_ok:
mov eax, 1
epilog
calign
.no_root:
mov [rdi+_avlofs_parent], rax
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
mov qword [rax+_avlofs_parent], 0
mov qword [rax+_avlofs_next], 0
mov qword [rax+_avlofs_prev], 0
mov eax, 1
epilog
calign
.node_is_equal:
sub qword [rdi+_avlofs_right], 1 ; decrement our count again
mov rdi, rax
call heap$free
xor eax, eax ; 0 ret
epilog
end if
if used doublemap$insert_unique | defined include_everything
; rdi == map, xmm0 == key, rsi == value
; rax == bool as to whether the insert succeeded or not (unique constraint violated)
falign
doublemap$insert_unique:
prolog doublemap$insert_unique
push rdi rsi rdx
mov edi, avlnode_size
call heap$alloc
pop rdx rsi rdi
xor ecx, ecx
movq [rax+_avlofs_key], xmm0
mov [rax+_avlofs_value], rsi
mov [rax+_avlofs_left], rcx
mov [rax+_avlofs_right], rcx
mov [rax+_avlofs_trunk], rcx
mov dword [rax+_avlofs_flags], 0
add qword [rdi+_avlofs_right], 1 ; increment our list node count
cmp qword [rdi+_avlofs_parent], 0
je .no_root
; so at this point, rdi still has our map, rsi still has our key, rdx has our value but we don't care about it anymore
; and rax has our spanking new node
push rax
call _doublemap_locate_node
; normal return from _doublemap_locate_node is in rax, but we know that r8 is the actual return, so go ahead and blast rax
pop rax
test r9d, avl_status_found
jnz .node_is_equal
; rdi still our map, rsi still our key, though we don't care about it anymore either, rax is our new node, r8 is our return
; from _doublemap_locate_node, r9d is flags, r10d pathflags, ecx is pathcount
mov [rax+_avlofs_parent], r8 ; link our parent with the return
test r9d, avl_status_left
jz .node_b_right
mov [r8+_avlofs_left], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
mov [rax+_avlofs_next], r8
mov rdx, [r8+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
mov [r8+_avlofs_prev], rax
test rdx, rdx
jz .linkleft_setlast
mov [rdx+_avlofs_next], rax
jmp .check_balance
calign
.linkleft_setlast:
mov [rdi+_avlofs_next], rax
jmp .check_balance
calign
.link_insert_order:
mov qword [rax+_avlofs_next], 0
mov rdx, [rdi+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
test rdx, rdx
jz .linkleft_set_first
mov [rdx+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.linkleft_set_first:
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.node_b_right:
mov [r8+_avlofs_right], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
test rdx, rdx
jz .linkright_setlast
mov [rdx+_avlofs_prev], rax
jmp .check_balance
calign
.linkright_setlast:
mov [rdi+_avlofs_prev], rax
calign
.check_balance:
sub ecx, 1
mov rax, [rax+_avlofs_parent]
mov r8d, dword [rax+_avlofs_flags]
and r8d, avl_unb_mask
bt r10d, ecx
jnc .trav_right
; trav_left:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r8d, 1
or r8d, r11d
mov r9d, r8d
shl r8d, 1
shl r11d, 2
add r8d, r9d
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
test r8d, avl_unb_left
jz .exit_ok
jmp .check_heavy
calign
.trav_right:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r11d, 1
and r8d, r11d
shl r8d, 2
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
mov r9d, r8d
and r9d, avl_unb_left + avl_unbalanced
xor r9d, avl_unbalanced
test r9d, r9d
jnz .exit_ok
calign
.check_heavy:
test dword [rax+_avlofs_flags], avl_unb_heavy
jnz .node_is_heavy
cmp rax, [rdi+_avlofs_parent]
je .exit_ok
jmp .check_balance
calign
.node_is_heavy:
mov rsi, rax
mov edx, r9d
call _map_rebalance
mov eax, 1 ; return true
epilog
calign
.exit_ok:
mov eax, 1
epilog
calign
.no_root:
mov [rdi+_avlofs_parent], rax
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
mov qword [rax+_avlofs_parent], 0
mov qword [rax+_avlofs_next], 0
mov qword [rax+_avlofs_prev], 0
mov eax, 1
epilog
calign
.node_is_equal:
sub qword [rdi+_avlofs_right], 1 ; decrement our count again
mov rdi, rax
call heap$free
xor eax, eax ; 0 ret
epilog
end if
if used stringmap$insert_unique | defined include_everything
; rdi == map, rsi == key, rdx == value
; rax == bool as to whether the insert succeeded or not (unique constraint violated)
; with r8 being leftover as the node that was equal if it failed
falign
stringmap$insert_unique:
prolog stringmap$insert_unique
push rdi rsi rdx
mov edi, avlnode_size
call heap$alloc
pop rdx rsi rdi
xor ecx, ecx
mov [rax+_avlofs_key], rsi
mov [rax+_avlofs_value], rdx
mov [rax+_avlofs_left], rcx
mov [rax+_avlofs_right], rcx
mov [rax+_avlofs_trunk], rcx
mov dword [rax+_avlofs_flags], ecx
add qword [rdi+_avlofs_right], 1 ; increment the map's nodecount
cmp qword [rdi+_avlofs_parent], 0
je .no_root
; so at this point, rdi still has our map, rsi still has our key, rdx has our value but we don't care about it anymore
; and rax has our spanking new node
push rax
call _stringmap_locate_node
pop rax
test r9d, avl_status_found
jnz .node_is_equal
; normal return from _unsignedmap_locate_node is in rax, but we know that r8 is the actual return
; rdi still our map, rsi still our key, though we don't care about it anymore either, rax is our new node, r8 is our return
; from _unsignedmap_locate_node, r9d is flags, r10d pathflags, ecx is pathcount
mov [rax+_avlofs_parent], r8 ; link our parent with the return
test r9d, avl_status_left
jz .node_b_right
mov [r8+_avlofs_left], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
mov [rax+_avlofs_next], r8
mov rdx, [r8+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
mov [r8+_avlofs_prev], rax
test rdx, rdx
jz .linkleft_setlast
mov [rdx+_avlofs_next], rax
calign
.check_balance:
sub ecx, 1
mov rax, [rax+_avlofs_parent]
mov r8d, dword [rax+_avlofs_flags]
and r8d, avl_unb_mask
bt r10d, ecx
jnc .trav_right
; trav_left:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r8d, 1
or r8d, r11d
mov r9d, r8d
shl r8d, 1
shl r11d, 2
add r8d, r9d
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
test r8d, avl_unb_left
jz .exit_ok
; check_heavy fallthrough copy
test dword [rax+_avlofs_flags], avl_unb_heavy
jnz .node_is_heavy
cmp rax, [rdi+_avlofs_parent]
je .exit_ok
jmp .check_balance
calign
.node_b_right:
mov [r8+_avlofs_right], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
test rdx, rdx
jz .linkright_setlast
mov [rdx+_avlofs_prev], rax
jmp .check_balance
calign
.link_insert_order:
mov qword [rax+_avlofs_next], 0
mov rdx, [rdi+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
test rdx, rdx
jz .linkleft_set_first
mov [rdx+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.linkright_setlast:
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.trav_right:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r11d, 1
and r8d, r11d
shl r8d, 2
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
mov r9d, r8d
and r9d, avl_unb_left + avl_unbalanced
xor r9d, avl_unbalanced
test r9d, r9d
jnz .exit_ok
; check_heavy fallthrough copy
test dword [rax+_avlofs_flags], avl_unb_heavy
jnz .node_is_heavy
cmp rax, [rdi+_avlofs_parent]
je .exit_ok
jmp .check_balance
calign
.node_is_heavy:
mov rsi, rax
mov edx, r9d
call _map_rebalance
mov eax, 1 ; return true
epilog
calign
.linkleft_setlast:
mov [rdi+_avlofs_next], rax
jmp .check_balance
calign
.linkleft_set_first:
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.exit_ok:
mov eax, 1
epilog
calign
.no_root:
mov [rdi+_avlofs_parent], rax
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
mov qword [rax+_avlofs_parent], 0
mov qword [rax+_avlofs_next], 0
mov qword [rax+_avlofs_prev], 0
mov eax, 1
epilog
calign
.node_is_equal:
sub qword [rdi+_avlofs_right], 1 ; decrement our count again
mov rdi, rax
call heap$free
xor eax, eax ; 0 ret
epilog
end if
; -------------- non-unique insert varieties ---------------
if used intmap$insert | defined include_everything
; rdi == map, rsi == key, rdx == value
; will accept duplicate keys (aka multimap)
falign
intmap$insert:
prolog intmap$insert
push rdi rsi rdx
mov edi, avlnode_size
call heap$alloc
pop rdx rsi rdi
xor ecx, ecx
mov [rax+_avlofs_key], rsi
mov [rax+_avlofs_value], rdx
mov [rax+_avlofs_left], rcx
mov [rax+_avlofs_right], rcx
mov [rax+_avlofs_trunk], rcx
mov dword [rax+_avlofs_flags], 0
add qword [rdi+_avlofs_right], 1 ; increment our list node count
cmp qword [rdi+_avlofs_parent], 0
je .no_root
; so at this point, rdi still has our map, rsi still has our key, rdx has our value but we don't care about it anymore
; and rax has our spanking new node
push rax
call _intmap_locate_node
; normal return from _intmap_locate_node is in rax, but we know that r8 is the actual return, so go ahead and blast rax
pop rax
; rdi still our map, rsi still our key, though we don't care about it anymore either, rax is our new node, r8 is our return
; from _intmap_locate_node, r9d is flags, r10d pathflags, ecx is pathcount
mov [rax+_avlofs_parent], r8 ; link our parent with the return
test r9d, avl_status_found
jnz .node_is_equal
test r9d, avl_status_left
jz .node_b_right
mov [r8+_avlofs_left], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
mov [rax+_avlofs_next], r8
mov rdx, [r8+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
mov [r8+_avlofs_prev], rax
test rdx, rdx
jz .linkleft_setlast
mov [rdx+_avlofs_next], rax
jmp .check_balance
calign
.linkleft_setlast:
mov [rdi+_avlofs_next], rax
jmp .check_balance
calign
.link_insert_order:
mov qword [rax+_avlofs_next], 0
mov rdx, [rdi+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
test rdx, rdx
jz .linkleft_set_first
mov [rdx+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.linkleft_set_first:
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.node_b_right:
mov [r8+_avlofs_right], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
; special requirement here: we set our prev to r8, but it may be the top of a trunk
; in which case, we need to link our prev not to the top of the trunk, but to its bottom-most
push r8
calign
.find_trunk_bottom_loop:
cmp qword [r8+_avlofs_trunk], 0
je .found_trunk_bottom
mov r8, [r8+_avlofs_trunk]
jmp .find_trunk_bottom_loop
calign
.found_trunk_bottom:
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
pop r8
test rdx, rdx
jz .linkright_setlast
mov [rdx+_avlofs_prev], rax
jmp .check_balance
calign
.linkright_setlast:
mov [rdi+_avlofs_prev], rax
calign
.check_balance:
sub ecx, 1
mov rax, [rax+_avlofs_parent]
mov r8d, dword [rax+_avlofs_flags]
and r8d, avl_unb_mask
bt r10d, ecx
jnc .trav_right
; trav_left:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r8d, 1
or r8d, r11d
mov r9d, r8d
shl r8d, 1
shl r11d, 2
add r8d, r9d
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
test r8d, avl_unb_left
jz .exit_ok
jmp .check_heavy
calign
.trav_right:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r11d, 1
and r8d, r11d
shl r8d, 2
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
mov r9d, r8d
and r9d, avl_unb_left + avl_unbalanced
xor r9d, avl_unbalanced
test r9d, r9d
jnz .exit_ok
calign
.check_heavy:
test dword [rax+_avlofs_flags], avl_unb_heavy
jnz .node_is_heavy
cmp rax, [rdi+_avlofs_parent]
je .exit_ok
jmp .check_balance
calign
.node_is_heavy:
mov rsi, rax
mov edx, r9d
call _map_rebalance
epilog
calign
.exit_ok:
epilog
calign
.no_root:
mov [rdi+_avlofs_parent], rax
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
mov qword [rax+_avlofs_parent], 0
mov qword [rax+_avlofs_next], 0
mov qword [rax+_avlofs_prev], 0
epilog
calign
.node_is_equal:
mov [rax+_avlofs_parent], r8
mov rdx, [r8+_avlofs_trunk]
mov [rax+_avlofs_trunk], rdx
mov [r8+_avlofs_trunk], rax
test rdx, rdx
jz .noprevioustrunk
mov [rdx+_avlofs_parent], rax
; list linkage next
test dword [rdi+_avlofs_flags], 1
jnz .trunklink_insert_order
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
test rdx, rdx
jz .trunklinkright_setlast
mov [rdx+_avlofs_prev], rax
epilog
calign
.trunklinkright_setlast:
mov [rdi+_avlofs_prev], rax
epilog
calign
.noprevioustrunk:
test dword [rdi+_avlofs_flags], 1
jnz .trunklink_insert_order
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
test rdx, rdx
jz .trunklinkright_setlast
mov [rdx+_avlofs_prev], rax
epilog
calign
.trunklink_insert_order:
mov qword [rax+_avlofs_next], 0
mov rdx, [rdi+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
test rdx, rdx
jz .trunklinkleft_set_first
mov [rdx+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
epilog
calign
.trunklinkleft_set_first:
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
epilog
end if
if used unsignedmap$insert | defined include_everything
; rdi == map, rsi == key, rdx == value
; will accept duplicate keys (aka multimap)
falign
unsignedmap$insert:
prolog unsignedmap$insert
push rdi rsi rdx
mov edi, avlnode_size
call heap$alloc
pop rdx rsi rdi
xor ecx, ecx
mov [rax+_avlofs_key], rsi
mov [rax+_avlofs_value], rdx
mov [rax+_avlofs_left], rcx
mov [rax+_avlofs_right], rcx
mov [rax+_avlofs_trunk], rcx
mov dword [rax+_avlofs_flags], 0
add qword [rdi+_avlofs_right], 1 ; increment our list node count
cmp qword [rdi+_avlofs_parent], 0
je .no_root
; so at this point, rdi still has our map, rsi still has our key, rdx has our value but we don't care about it anymore
; and rax has our spanking new node
push rax
call _unsignedmap_locate_node
; normal return from _unsignedmap_locate_node is in rax, but we know that r8 is the actual return, so go ahead and blast rax
pop rax
; rdi still our map, rsi still our key, though we don't care about it anymore either, rax is our new node, r8 is our return
; from _unsignedmap_locate_node, r9d is flags, r10d pathflags, ecx is pathcount
mov [rax+_avlofs_parent], r8 ; link our parent with the return
test r9d, avl_status_found
jnz .node_is_equal
test r9d, avl_status_left
jz .node_b_right
mov [r8+_avlofs_left], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
; link us before r8
mov [rax+_avlofs_next], r8
mov rdx, [r8+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
mov [r8+_avlofs_prev], rax
test rdx, rdx
jz .linkleft_setlast
mov [rdx+_avlofs_next], rax
jmp .check_balance
calign
.linkleft_setlast:
mov [rdi+_avlofs_next], rax
jmp .check_balance
calign
.link_insert_order:
mov qword [rax+_avlofs_next], 0
mov rdx, [rdi+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
test rdx, rdx
jz .linkleft_set_first
mov [rdx+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.linkleft_set_first:
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.node_b_right:
mov [r8+_avlofs_right], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
; link us after r8...
; special requirement here: we set our prev to r8, but it may be the top of a trunk
; in which case, we need to link our prev not to the top of the trunk, but to its bottom-most
push r8
calign
.find_trunk_bottom_loop:
cmp qword [r8+_avlofs_trunk], 0
je .found_trunk_bottom
mov r8, [r8+_avlofs_trunk]
jmp .find_trunk_bottom_loop
calign
.found_trunk_bottom:
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
pop r8
test rdx, rdx
jz .linkright_setlast
mov [rdx+_avlofs_prev], rax
jmp .check_balance
calign
.linkright_setlast:
mov [rdi+_avlofs_prev], rax
calign
.check_balance:
sub ecx, 1
mov rax, [rax+_avlofs_parent]
mov r8d, dword [rax+_avlofs_flags]
and r8d, avl_unb_mask
bt r10d, ecx
jnc .trav_right
; trav_left:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r8d, 1
or r8d, r11d
mov r9d, r8d
shl r8d, 1
shl r11d, 2
add r8d, r9d
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
test r8d, avl_unb_left
jz .exit_ok
jmp .check_heavy
calign
.trav_right:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r11d, 1
and r8d, r11d
shl r8d, 2
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
mov r9d, r8d
and r9d, avl_unb_left + avl_unbalanced
xor r9d, avl_unbalanced
test r9d, r9d
jnz .exit_ok
calign
.check_heavy:
test dword [rax+_avlofs_flags], avl_unb_heavy
jnz .node_is_heavy
cmp rax, [rdi+_avlofs_parent]
je .exit_ok
jmp .check_balance
calign
.node_is_heavy:
mov rsi, rax
mov edx, r9d
call _map_rebalance
mov eax, 1 ; return true
epilog
calign
.exit_ok:
mov eax, 1
epilog
calign
.no_root:
mov [rdi+_avlofs_parent], rax
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
mov qword [rax+_avlofs_parent], 0
mov qword [rax+_avlofs_next], 0
mov qword [rax+_avlofs_prev], 0
mov eax, 1
epilog
calign
.node_is_equal:
; rax == a
; r8 == b
mov [rax+_avlofs_parent], r8
mov rdx, [r8+_avlofs_trunk]
mov [rax+_avlofs_trunk], rdx
mov [r8+_avlofs_trunk], rax
test rdx, rdx
jz .noprevioustrunk
mov [rdx+_avlofs_parent], rax
; list linkage next
test dword [rdi+_avlofs_flags], 1
jnz .trunklink_insert_order
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
test rdx, rdx
jz .trunklinkright_setlast
mov [rdx+_avlofs_prev], rax
mov eax, 1
epilog
calign
.trunklinkright_setlast:
mov [rdi+_avlofs_prev], rax
mov eax, 1
epilog
calign
.noprevioustrunk:
test dword [rdi+_avlofs_flags], 1
jnz .trunklink_insert_order
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
test rdx, rdx
jz .trunklinkright_setlast
mov [rdx+_avlofs_prev], rax
mov eax, 1
epilog
calign
.trunklink_insert_order:
mov qword [rax+_avlofs_next], 0
mov rdx, [rdi+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
test rdx, rdx
jz .trunklinkleft_set_first
mov [rdx+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
mov eax, 1
epilog
calign
.trunklinkleft_set_first:
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
mov eax, 1
epilog
end if
if used doublemap$insert | defined include_everything
; rdi == map, xmm0 == key, rsi == value
; will accept duplicate keys (aka multimap)
falign
doublemap$insert:
prolog doublemap$insert
push rdi rsi rdx
mov edi, avlnode_size
call heap$alloc
pop rdx rsi rdi
xor ecx, ecx
movq [rax+_avlofs_key], xmm0
mov [rax+_avlofs_value], rsi
mov [rax+_avlofs_left], rcx
mov [rax+_avlofs_right], rcx
mov [rax+_avlofs_trunk], rcx
mov dword [rax+_avlofs_flags], 0
add qword [rdi+_avlofs_right], 1 ; increment our list node count
cmp qword [rdi+_avlofs_parent], 0
je .no_root
; so at this point, rdi still has our map, rsi still has our key, rdx has our value but we don't care about it anymore
; and rax has our spanking new node
push rax
call _doublemap_locate_node
; normal return from _doublemap_locate_node is in rax, but we know that r8 is the actual return, so go ahead and blast rax
pop rax
; rdi still our map, rsi still our key, though we don't care about it anymore either, rax is our new node, r8 is our return
; from _doublemap_locate_node, r9d is flags, r10d pathflags, ecx is pathcount
mov [rax+_avlofs_parent], r8 ; link our parent with the return
test r9d, avl_status_found
jnz .node_is_equal
test r9d, avl_status_left
jz .node_b_right
mov [r8+_avlofs_left], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
mov [rax+_avlofs_next], r8
mov rdx, [r8+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
mov [r8+_avlofs_prev], rax
test rdx, rdx
jz .linkleft_setlast
mov [rdx+_avlofs_next], rax
jmp .check_balance
calign
.linkleft_setlast:
mov [rdi+_avlofs_next], rax
jmp .check_balance
calign
.link_insert_order:
mov qword [rax+_avlofs_next], 0
mov rdx, [rdi+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
test rdx, rdx
jz .linkleft_set_first
mov [rdx+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.linkleft_set_first:
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.node_b_right:
mov [r8+_avlofs_right], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
; special requirement here: we set our prev to r8, but it may be the top of a trunk
; in which case, we need to link our prev not to the top of the trunk, but to its bottom-most
push r8
calign
.find_trunk_bottom_loop:
cmp qword [r8+_avlofs_trunk], 0
je .found_trunk_bottom
mov r8, [r8+_avlofs_trunk]
jmp .find_trunk_bottom_loop
calign
.found_trunk_bottom:
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
pop r8
test rdx, rdx
jz .linkright_setlast
mov [rdx+_avlofs_prev], rax
jmp .check_balance
calign
.linkright_setlast:
mov [rdi+_avlofs_prev], rax
calign
.check_balance:
sub ecx, 1
mov rax, [rax+_avlofs_parent]
mov r8d, dword [rax+_avlofs_flags]
and r8d, avl_unb_mask
bt r10d, ecx
jnc .trav_right
; trav_left:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r8d, 1
or r8d, r11d
mov r9d, r8d
shl r8d, 1
shl r11d, 2
add r8d, r9d
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
test r8d, avl_unb_left
jz .exit_ok
jmp .check_heavy
calign
.trav_right:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r11d, 1
and r8d, r11d
shl r8d, 2
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
mov r9d, r8d
and r9d, avl_unb_left + avl_unbalanced
xor r9d, avl_unbalanced
test r9d, r9d
jnz .exit_ok
calign
.check_heavy:
test dword [rax+_avlofs_flags], avl_unb_heavy
jnz .node_is_heavy
cmp rax, [rdi+_avlofs_parent]
je .exit_ok
jmp .check_balance
calign
.node_is_heavy:
mov rsi, rax
mov edx, r9d
call _map_rebalance
mov eax, 1 ; return true
epilog
calign
.exit_ok:
mov eax, 1
epilog
calign
.no_root:
mov [rdi+_avlofs_parent], rax
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
mov qword [rax+_avlofs_parent], 0
mov qword [rax+_avlofs_next], 0
mov qword [rax+_avlofs_prev], 0
mov eax, 1
epilog
calign
.node_is_equal:
mov [rax+_avlofs_parent], r8
mov rdx, [r8+_avlofs_trunk]
mov [rax+_avlofs_trunk], rdx
mov [r8+_avlofs_trunk], rax
test rdx, rdx
jz .noprevioustrunk
mov [rdx+_avlofs_parent], rax
; list linkage next
test dword [rdi+_avlofs_flags], 1
jnz .trunklink_insert_order
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
test rdx, rdx
jz .trunklinkright_setlast
mov [rdx+_avlofs_prev], rax
epilog
calign
.trunklinkright_setlast:
mov [rdi+_avlofs_prev], rax
epilog
calign
.noprevioustrunk:
test dword [rdi+_avlofs_flags], 1
jnz .trunklink_insert_order
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
test rdx, rdx
jz .trunklinkright_setlast
mov [rdx+_avlofs_prev], rax
epilog
calign
.trunklink_insert_order:
mov qword [rax+_avlofs_next], 0
mov rdx, [rdi+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
test rdx, rdx
jz .trunklinkleft_set_first
mov [rdx+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
epilog
calign
.trunklinkleft_set_first:
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
epilog
end if
if used stringmap$insert | defined include_everything
; rdi == map, rsi == key, rdx == value
; will accept duplicate keys (aka multimap)
falign
stringmap$insert:
prolog stringmap$insert
push rdi rsi rdx
mov edi, avlnode_size
call heap$alloc
pop rdx rsi rdi
xor ecx, ecx
mov [rax+_avlofs_key], rsi
mov [rax+_avlofs_value], rdx
mov [rax+_avlofs_left], rcx
mov [rax+_avlofs_right], rcx
mov [rax+_avlofs_trunk], rcx
mov dword [rax+_avlofs_flags], 0
add qword [rdi+_avlofs_right], 1 ; increment our list node count
cmp qword [rdi+_avlofs_parent], 0
je .no_root
; so at this point, rdi still has our map, rsi still has our key, rdx has our value but we don't care about it anymore
; and rax has our spanking new node
push rax
call _stringmap_locate_node
; normal return from _stringmap_locate_node is in rax, but we know that r8 is the actual return, so go ahead and blast rax
pop rax
; rdi still our map, rsi still our key, though we don't care about it anymore either, rax is our new node, r8 is our return
; from _stringmap_locate_node, r9d is flags, r10d pathflags, ecx is pathcount
mov [rax+_avlofs_parent], r8 ; link our parent with the return
test r9d, avl_status_found
jnz .node_is_equal
test r9d, avl_status_left
jz .node_b_right
mov [r8+_avlofs_left], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
mov [rax+_avlofs_next], r8
mov rdx, [r8+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
mov [r8+_avlofs_prev], rax
test rdx, rdx
jz .linkleft_setlast
mov [rdx+_avlofs_next], rax
jmp .check_balance
calign
.linkleft_setlast:
mov [rdi+_avlofs_next], rax
jmp .check_balance
calign
.link_insert_order:
mov qword [rax+_avlofs_next], 0
mov rdx, [rdi+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
test rdx, rdx
jz .linkleft_set_first
mov [rdx+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.linkleft_set_first:
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
jmp .check_balance
calign
.node_b_right:
mov [r8+_avlofs_right], rax
; link up our list
test dword [rdi+_avlofs_flags], 1
jnz .link_insert_order
; special requirement here: we set our prev to r8, but it may be the top of a trunk
; in which case, we need to link our prev not to the top of the trunk, but to its bottom-most
push r8
calign
.find_trunk_bottom_loop:
cmp qword [r8+_avlofs_trunk], 0
je .found_trunk_bottom
mov r8, [r8+_avlofs_trunk]
jmp .find_trunk_bottom_loop
calign
.found_trunk_bottom:
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
pop r8
test rdx, rdx
jz .linkright_setlast
mov [rdx+_avlofs_prev], rax
jmp .check_balance
calign
.linkright_setlast:
mov [rdi+_avlofs_prev], rax
calign
.check_balance:
sub ecx, 1
mov rax, [rax+_avlofs_parent]
mov r8d, dword [rax+_avlofs_flags]
and r8d, avl_unb_mask
bt r10d, ecx
jnc .trav_right
; trav_left:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r8d, 1
or r8d, r11d
mov r9d, r8d
shl r8d, 1
shl r11d, 2
add r8d, r9d
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
test r8d, avl_unb_left
jz .exit_ok
jmp .check_heavy
calign
.trav_right:
mov r11d, r8d
and r8d, 1
shr r11d, 1
xor r11d, 1
and r8d, r11d
shl r8d, 2
add r8d, r11d
and dword [rax+_avlofs_flags], 0xffff - avl_unb_mask
or dword [rax+_avlofs_flags], r8d
mov r9d, r8d
and r9d, avl_unb_left + avl_unbalanced
xor r9d, avl_unbalanced
test r9d, r9d
jnz .exit_ok
calign
.check_heavy:
test dword [rax+_avlofs_flags], avl_unb_heavy
jnz .node_is_heavy
cmp rax, [rdi+_avlofs_parent]
je .exit_ok
jmp .check_balance
calign
.node_is_heavy:
mov rsi, rax
mov edx, r9d
call _map_rebalance
mov eax, 1 ; return true
epilog
calign
.exit_ok:
mov eax, 1
epilog
calign
.no_root:
mov [rdi+_avlofs_parent], rax
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
mov qword [rax+_avlofs_parent], 0
mov qword [rax+_avlofs_next], 0
mov qword [rax+_avlofs_prev], 0
mov eax, 1
epilog
calign
.node_is_equal:
mov [rax+_avlofs_parent], r8
mov rdx, [r8+_avlofs_trunk]
mov [rax+_avlofs_trunk], rdx
mov [r8+_avlofs_trunk], rax
test rdx, rdx
jz .noprevioustrunk
mov [rdx+_avlofs_parent], rax
; list linkage next
test dword [rdi+_avlofs_flags], 1
jnz .trunklink_insert_order
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
test rdx, rdx
jz .trunklinkright_setlast
mov [rdx+_avlofs_prev], rax
epilog
calign
.trunklinkright_setlast:
mov [rdi+_avlofs_prev], rax
epilog
calign
.noprevioustrunk:
test dword [rdi+_avlofs_flags], 1
jnz .trunklink_insert_order
mov [rax+_avlofs_prev], r8
mov rdx, [r8+_avlofs_next]
mov [rax+_avlofs_next], rdx
mov [r8+_avlofs_next], rax
test rdx, rdx
jz .trunklinkright_setlast
mov [rdx+_avlofs_prev], rax
epilog
calign
.trunklink_insert_order:
mov qword [rax+_avlofs_next], 0
mov rdx, [rdi+_avlofs_prev]
mov [rax+_avlofs_prev], rdx
test rdx, rdx
jz .trunklinkleft_set_first
mov [rdx+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
epilog
calign
.trunklinkleft_set_first:
mov [rdi+_avlofs_next], rax
mov [rdi+_avlofs_prev], rax
epilog
end if
if used intmap$erase | defined include_everything
falign
intmap$erase:
prolog intmap$erase
call _intmap_locate_node
test r9d, avl_status_found
jz .not_found
mov r11, [r8+_avlofs_parent]
mov r9, [r8+_avlofs_left]
mov rdx, [r8+_avlofs_right]
test rdx, rdx
jz .case_one
mov rax, [rdx+_avlofs_left]
test rax, rax
jz .case_two
jmp .case_three
calign
.case_one:
test r11, r11
jz .case_one_check_empty
test r9, r9
jz .case_one_no_c
mov [r9+_avlofs_parent], r11
calign
.case_one_no_c:
sub ecx, 1
bt r10d, ecx
jnc .case_one_relink_right
mov [r11+_avlofs_left], r9
mov rsi, r11
push r8
call _map_left_lighter
pop r8
jmp .relinked
calign
.case_one_relink_right:
mov [r11+_avlofs_right], r9
mov rsi, r11
push r8
call _map_right_lighter
pop r8
jmp .relinked
calign
.case_one_check_empty:
test r9, r9
jnz .case_one_new_root
mov qword [rdi+_avlofs_parent], 0
jmp .relinked
calign
.case_one_new_root:
mov qword [r9+_avlofs_parent], 0
mov [rdi+_avlofs_parent], r9
jmp .relinked
calign
.case_two:
mov [rdx+_avlofs_left], r9
test r9, r9
jz .case_two_no_c
mov [r9+_avlofs_parent], rdx
calign
.case_two_no_c:
test r11, r11
jz .case_two_new_root
mov [rdx+_avlofs_parent], r11
sub ecx, 1
bt r10d, ecx
jnc .case_two_relink_right
mov [r11+_avlofs_left], rdx
jmp .case_two_rebalance
calign
.case_two_relink_right:
mov [r11+_avlofs_right], rdx
calign
.case_two_rebalance:
push r9
mov r9d, dword [r8+_avlofs_flags]
and r9d, avl_all
and dword [rdx+_avlofs_flags], 0xffff - avl_all
or dword [rdx+_avlofs_flags], r9d
pop r9
mov r11, rdx
mov rsi, r11
push r8
call _map_right_lighter
pop r8
jmp .relinked
calign
.case_two_new_root:
mov qword [rdx+_avlofs_parent], 0
mov [rdi+_avlofs_parent], rdx
jmp .case_two_rebalance
calign
.case_three:
push r8
mov rsi, r8
call _map_successor
mov r9, [rax+_avlofs_right]
mov r8, [rax+_avlofs_parent]
mov [r8+_avlofs_left], r9
test r9, r9
jnz .case_three_succ_has_right
calign
.case_three_succ_no_right:
mov rsi, r8
push rax
call _map_left_lighter
pop rax
pop r8
mov r9, [r8+_avlofs_left]
mov rdx, [r8+_avlofs_right]
mov [rax+_avlofs_left], r9
mov r11, [r8+_avlofs_parent]
test r9, r9
jz .case_three_succ_no_right_no_c
mov [r9+_avlofs_parent], rax
calign
.case_three_succ_no_right_no_c:
mov [rdx+_avlofs_parent], rax
mov [rax+_avlofs_right], rdx
push r9
mov r9d, dword [r8+_avlofs_flags]
and r9d, avl_all
and dword [rax+_avlofs_flags], 0xffff - avl_all
or dword [rax+_avlofs_flags], r9d
pop r9
mov [rax+_avlofs_parent], r11
test r11, r11
jz .case_three_was_root
cmp r8, [r11+_avlofs_right]
je .case_three_relink_right
mov [r11+_avlofs_left], rax
jmp .relinked
calign
.case_three_relink_right:
mov [r11+_avlofs_right], rax
jmp .relinked
calign
.relinked:
xor eax, eax
mov r11, [r8+_avlofs_prev]
mov rdx, [r8+_avlofs_next]
test r11, r11
jz .relinked_loop_set_first
mov [r11+_avlofs_next], rdx
jmp .relinked_loop_otherside
calign
.relinked_loop:
mov r11, [r8+_avlofs_prev]
mov rdx, [r8+_avlofs_next]
test r11, r11
jz .relinked_loop_set_first
mov [r11+_avlofs_next], rdx
jmp .relinked_loop_otherside
calign
.relinked_loop_set_first:
mov [rdi+_avlofs_next], rdx
mov r11, [r8+_avlofs_next]
mov rdx, [r8+_avlofs_prev]
test r11, r11
jz .relinked_loop_set_last
mov [r11+_avlofs_prev], rdx
jmp .relinked_loop_dec
calign
.relinked_loop_otherside:
mov r11, [r8+_avlofs_next]
mov rdx, [r8+_avlofs_prev]
test r11, r11
jz .relinked_loop_set_last
mov [r11+_avlofs_prev], rdx
jmp .relinked_loop_dec
calign
.relinked_loop_set_last:
mov [rdi+_avlofs_prev], rdx
sub qword [rdi+_avlofs_right], 1
mov r11, [r8+_avlofs_trunk]
push rdi rax r11
mov rdi, r8
call heap$free
pop r11 rax rdi
add eax, 1
mov r8, r11
test r8, r8
jnz .relinked_loop
epilog
calign
.relinked_loop_dec:
sub qword [rdi+_avlofs_right], 1
mov r11, [r8+_avlofs_trunk]
push rdi rax r11
mov rdi, r8
call heap$free
pop r11 rax rdi
add eax, 1
mov r8, r11
test r8, r8
jnz .relinked_loop
epilog
calign
.case_three_succ_has_right:
mov [r9+_avlofs_parent], r8
jmp .case_three_succ_no_right
calign
.case_three_was_root:
mov qword [rax+_avlofs_parent], 0
mov [rdi+_avlofs_parent], rax
jmp .relinked
calign
.not_found:
xor eax, eax ; no nodes deleted
epilog
end if
if used unsignedmap$erase | defined include_everything
falign
unsignedmap$erase:
prolog unsignedmap$erase
call _unsignedmap_locate_node
test r9d, avl_status_found
jz .not_found
mov r11, [r8+_avlofs_parent]
mov r9, [r8+_avlofs_left]
mov rdx, [r8+_avlofs_right]
test rdx, rdx
jz .case_one
mov rax, [rdx+_avlofs_left]
test rax, rax
jz .case_two
jmp .case_three
calign
.case_one:
test r11, r11
jz .case_one_check_empty
test r9, r9
jz .case_one_no_c
mov [r9+_avlofs_parent], r11
calign
.case_one_no_c:
sub ecx, 1
bt r10d, ecx
jnc .case_one_relink_right
mov [r11+_avlofs_left], r9
mov rsi, r11
push r8
call _map_left_lighter
pop r8
jmp .relinked
calign
.case_one_relink_right:
mov [r11+_avlofs_right], r9
mov rsi, r11
push r8
call _map_right_lighter
pop r8
jmp .relinked
calign
.case_one_check_empty:
test r9, r9
jnz .case_one_new_root
mov qword [rdi+_avlofs_parent], 0
jmp .relinked
calign
.case_one_new_root:
mov qword [r9+_avlofs_parent], 0
mov [rdi+_avlofs_parent], r9
jmp .relinked
calign
.case_two:
mov [rdx+_avlofs_left], r9
test r9, r9
jz .case_two_no_c
mov [r9+_avlofs_parent], rdx
calign
.case_two_no_c:
test r11, r11
jz .case_two_new_root
mov [rdx+_avlofs_parent], r11
sub ecx, 1
bt r10d, ecx
jnc .case_two_relink_right
mov [r11+_avlofs_left], rdx
jmp .case_two_rebalance
calign
.case_two_relink_right:
mov [r11+_avlofs_right], rdx
calign
.case_two_rebalance:
push r9
mov r9d, dword [r8+_avlofs_flags]
and r9d, avl_all
and dword [rdx+_avlofs_flags], 0xffff - avl_all
or dword [rdx+_avlofs_flags], r9d
pop r9
mov r11, rdx
mov rsi, r11
push r8
call _map_right_lighter
pop r8
jmp .relinked
calign
.case_two_new_root:
mov qword [rdx+_avlofs_parent], 0
mov [rdi+_avlofs_parent], rdx
jmp .case_two_rebalance
calign
.case_three:
push r8
mov rsi, r8
call _map_successor
mov r9, [rax+_avlofs_right]
mov r8, [rax+_avlofs_parent]
mov [r8+_avlofs_left], r9
test r9, r9
jnz .case_three_succ_has_right
calign
.case_three_succ_no_right:
mov rsi, r8
push rax
call _map_left_lighter
pop rax
pop r8
mov r9, [r8+_avlofs_left]
mov rdx, [r8+_avlofs_right]
mov [rax+_avlofs_left], r9
mov r11, [r8+_avlofs_parent]
test r9, r9
jz .case_three_succ_no_right_no_c
mov [r9+_avlofs_parent], rax
calign
.case_three_succ_no_right_no_c:
mov [rdx+_avlofs_parent], rax
mov [rax+_avlofs_right], rdx
push r9
mov r9d, dword [r8+_avlofs_flags]
and r9d, avl_all
and dword [rax+_avlofs_flags], 0xffff - avl_all
or dword [rax+_avlofs_flags], r9d
pop r9
mov [rax+_avlofs_parent], r11
test r11, r11
jz .case_three_was_root
cmp r8, [r11+_avlofs_right]
je .case_three_relink_right
mov [r11+_avlofs_left], rax
jmp .relinked
calign
.case_three_relink_right:
mov [r11+_avlofs_right], rax
jmp .relinked
calign
.relinked:
xor eax, eax
mov r11, [r8+_avlofs_prev]
mov rdx, [r8+_avlofs_next]
test r11, r11
jz .relinked_loop_set_first
mov [r11+_avlofs_next], rdx
jmp .relinked_loop_otherside
calign
.relinked_loop:
mov r11, [r8+_avlofs_prev]
mov rdx, [r8+_avlofs_next]
test r11, r11
jz .relinked_loop_set_first
mov [r11+_avlofs_next], rdx
jmp .relinked_loop_otherside
calign
.relinked_loop_set_first:
mov [rdi+_avlofs_next], rdx
mov r11, [r8+_avlofs_next]
mov rdx, [r8+_avlofs_prev]
test r11, r11
jz .relinked_loop_set_last
mov [r11+_avlofs_prev], rdx
jmp .relinked_loop_dec
calign
.relinked_loop_otherside:
mov r11, [r8+_avlofs_next]
mov rdx, [r8+_avlofs_prev]
test r11, r11
jz .relinked_loop_set_last
mov [r11+_avlofs_prev], rdx
jmp .relinked_loop_dec
calign
.relinked_loop_set_last:
mov [rdi+_avlofs_prev], rdx
sub qword [rdi+_avlofs_right], 1
mov r11, [r8+_avlofs_trunk]
push rdi rax r11
mov rdi, r8
call heap$free
pop r11 rax rdi
add eax, 1
mov r8, r11
test r8, r8
jnz .relinked_loop
epilog
calign
.relinked_loop_dec:
sub qword [rdi+_avlofs_right], 1
mov r11, [r8+_avlofs_trunk]
push rdi rax r11
mov rdi, r8
call heap$free
pop r11 rax rdi
add eax, 1
mov r8, r11
test r8, r8
jnz .relinked_loop
epilog
calign
.case_three_succ_has_right:
mov [r9+_avlofs_parent], r8
jmp .case_three_succ_no_right
calign
.case_three_was_root:
mov qword [rax+_avlofs_parent], 0
mov [rdi+_avlofs_parent], rax
jmp .relinked
calign
.not_found:
xor eax, eax ; no nodes deleted
epilog
end if
if used unsignedmap$erase_specific | defined include_everything
; different from the above in that we pay attention to its value object and leave the rest (if any)
; of the trunk alone (will delete all matching values)
falign
unsignedmap$erase_specific:
prolog unsignedmap$erase_specific
push rdx rsi rdi
call _unsignedmap_locate_node_specific
test r9d, avl_status_found
jz .alldone
call unsignedmap$erase_specific_node
calign
.top:
mov rdi, [rsp]
mov rsi, [rsp+8]
mov rdx, [rsp+16]
call _unsignedmap_locate_node_specific
test r9d, avl_status_found
jz .alldone
call unsignedmap$erase_specific_node
jmp .top
calign
.alldone:
add rsp, 24
epilog
end if
if used unsignedmap$erase_specific_node | defined include_everything
; not meant to be called publically, called from above public function
falign
unsignedmap$erase_specific_node:
prolog unsignedmap$erase_specific_node
cmp qword [r8+_avlofs_trunk], 0
jne .has_trunk
mov r11, [r8+_avlofs_parent]
mov r9, [r8+_avlofs_left]
mov rdx, [r8+_avlofs_right]
test rdx, rdx
jz .case_one
mov rax, [rdx+_avlofs_left]
test rax, rax
jz .case_two
jmp .case_three
calign
.case_one:
test r11, r11
jz .case_one_check_empty
test r9, r9
jz .case_one_no_c
mov [r9+_avlofs_parent], r11
calign
.case_one_no_c:
sub ecx, 1
bt r10d, ecx
jnc .case_one_relink_right
mov [r11+_avlofs_left], r9
mov rsi, r11
push r8
call _map_left_lighter
pop r8
jmp .relinked
calign
.case_one_relink_right:
mov [r11+_avlofs_right], r9
mov rsi, r11
push r8
call _map_right_lighter
pop r8
jmp .relinked
calign
.case_one_check_empty:
test r9, r9
jnz .case_one_new_root
mov qword [rdi+_avlofs_parent], 0
jmp .relinked
calign
.case_one_new_root:
mov qword [r9+_avlofs_parent], 0
mov [rdi+_avlofs_parent], r9
jmp .relinked
calign
.case_two:
mov [rdx+_avlofs_left], r9
test r9, r9
jz .case_two_no_c
mov [r9+_avlofs_parent], rdx
calign
.case_two_no_c:
test r11, r11
jz .case_two_new_root
mov [rdx+_avlofs_parent], r11
sub ecx, 1
bt r10d, ecx
jnc .case_two_relink_right
mov [r11+_avlofs_left], rdx
jmp .case_two_rebalance
calign
.case_two_relink_right:
mov [r11+_avlofs_right], rdx
calign
.case_two_rebalance:
push r9
mov r9d, dword [r8+_avlofs_flags]
and r9d, avl_all
and dword [rdx+_avlofs_flags], 0xffff - avl_all
or dword [rdx+_avlofs_flags], r9d
pop r9
mov r11, rdx
mov rsi, r11
push r8
call _map_right_lighter
pop r8
jmp .relinked
calign
.case_two_new_root:
mov qword [rdx+_avlofs_parent], 0
mov [rdi+_avlofs_parent], rdx
jmp .case_two_rebalance
calign
.case_three:
push r8
mov rsi, r8
call _map_successor
mov r9, [rax+_avlofs_right]
mov r8, [rax+_avlofs_parent]
mov [r8+_avlofs_left], r9
test r9, r9
jnz .case_three_succ_has_right
calign
.case_three_succ_no_right:
mov rsi, r8
push rax
call _map_left_lighter
pop rax
pop r8
mov r9, [r8+_avlofs_left]
mov rdx, [r8+_avlofs_right]
mov [rax+_avlofs_left], r9
mov r11, [r8+_avlofs_parent]
test r9, r9
jz .case_three_succ_no_right_no_c
mov [r9+_avlofs_parent], rax
calign
.case_three_succ_no_right_no_c:
mov [rdx+_avlofs_parent], rax
mov [rax+_avlofs_right], rdx
push r9
mov r9d, dword [r8+_avlofs_flags]
and r9d, avl_all
and dword [rax+_avlofs_flags], 0xffff - avl_all
or dword [rax+_avlofs_flags], r9d
pop r9
mov [rax+_avlofs_parent], r11
test r11, r11
jz .case_three_was_root
cmp r8, [r11+_avlofs_right]
je .case_three_relink_right
mov [r11+_avlofs_left], rax
jmp .relinked
calign
.case_three_relink_right:
mov [r11+_avlofs_right], rax
jmp .relinked
calign
.relinked:
xor eax, eax
mov r11, [r8+_avlofs_prev]
mov rdx, [r8+_avlofs_next]
test r11, r11
jz .relinked_loop_set_first
mov [r11+_avlofs_next], rdx
jmp .relinked_loop_otherside
calign
.relinked_loop:
mov r11, [r8+_avlofs_prev]
mov rdx, [r8+_avlofs_next]
test r11, r11
jz .relinked_loop_set_first
mov [r11+_avlofs_next], rdx
jmp .relinked_loop_otherside
calign
.relinked_loop_set_first:
mov [rdi+_avlofs_next], rdx
mov r11, [r8+_avlofs_next]
mov rdx, [r8+_avlofs_prev]
test r11, r11
jz .relinked_loop_set_last
mov [r11+_avlofs_prev], rdx
jmp .relinked_loop_dec
calign
.relinked_loop_otherside:
mov r11, [r8+_avlofs_next]
mov rdx, [r8+_avlofs_prev]
test r11, r11
jz .relinked_loop_set_last
mov [r11+_avlofs_prev], rdx
jmp .relinked_loop_dec
calign
.relinked_loop_set_last:
mov [rdi+_avlofs_prev], rdx
sub qword [rdi+_avlofs_right], 1
mov r11, [r8+_avlofs_trunk]
push rdi rax r11
mov rdi, r8
call heap$free
pop r11 rax rdi
add eax, 1
mov r8, r11
test r8, r8
jnz .relinked_loop
epilog
calign
.relinked_loop_dec:
sub qword [rdi+_avlofs_right], 1
mov r11, [r8+_avlofs_trunk]
push rdi rax r11
mov rdi, r8
call heap$free
pop r11 rax rdi
add eax, 1
mov r8, r11
test r8, r8
jnz .relinked_loop
epilog
calign
.case_three_succ_has_right:
mov [r9+_avlofs_parent], r8
jmp .case_three_succ_no_right
calign
.case_three_was_root:
mov qword [rax+_avlofs_parent], 0
mov [rdi+_avlofs_parent], rax
jmp .relinked
calign
.not_found:
xor eax, eax ; no nodes deleted
epilog
calign
.has_trunk:
mov rax, r8
cmp rdx, r8
je .has_trunk_foundit
calign
.again:
mov rax, [rax+_avlofs_trunk]
test rax, rax
jz .not_found
cmp rdx, rax
jne .again
calign
.has_trunk_foundit:
mov r11, [rax+_avlofs_prev]
mov rdx, [rax+_avlofs_next]
test r11, r11
jz .set_first
mov [r11+_avlofs_next], rdx
jmp .otherside
calign
.set_first:
mov [rdi+_avlofs_next], rdx
calign
.otherside:
test rdx, rdx
jz .set_last
mov [rdx+_avlofs_prev], r11
jmp .has_trunk_keep_going
calign
.set_last:
mov [rdi+_avlofs_prev], r11
calign
.has_trunk_keep_going:
sub qword [rdi+_avlofs_right], 1
cmp rax, r8
je .top_of_trunk
; else, we are not the top of the trunk, and we have a parent
mov r11, [rax+_avlofs_parent]
mov rdx, [rax+_avlofs_trunk]
mov [r11+_avlofs_trunk], rdx
test rdx, rdx
jz .not_top_no_new_parent
mov [rdx+_avlofs_parent], r11
calign
.not_top_no_new_parent:
mov rdi, rax
call heap$free
mov eax, 1
epilog
calign
.top_of_trunk:
mov rdx, [rax+_avlofs_trunk]
cmp rax, [rdi+_avlofs_parent]
jne .top_of_trunk_not_root
mov [rdi+_avlofs_parent], rdx
calign
.top_of_trunk_not_root:
mov r11, [rax+_avlofs_parent]
mov [rdx+_avlofs_parent], r11
test r11, r11
jz .top_of_trunk_no_parent
cmp rax, [r11+_avlofs_left]
jne .top_of_trunk_parent_not_left
mov [r11+_avlofs_left], rdx
jmp .top_of_trunk_no_parent
calign
.top_of_trunk_parent_not_left:
cmp rax, [r11+_avlofs_right]
jne .top_of_trunk_no_parent
mov [r11+_avlofs_right], rdx
calign
.top_of_trunk_no_parent:
mov r9, [rax+_avlofs_left]
mov [rdx+_avlofs_left], r9
test r9, r9
jz .top_of_trunk_noleft
mov [r9+_avlofs_parent], rdx
calign
.top_of_trunk_noleft:
mov r9, [rax+_avlofs_right]
mov [rdx+_avlofs_right], r9
test r9, r9
jz .top_of_trunk_noright
mov [r9+_avlofs_parent], rdx
calign
.top_of_trunk_noright:
mov r9d, dword [rax+_avlofs_flags]
mov dword [rdx+_avlofs_flags], r9d
mov rdi, rax
call heap$free
mov eax, 1
epilog
end if
if used doublemap$erase | defined include_everything
falign
doublemap$erase:
prolog doublemap$erase
call _doublemap_locate_node
test r9d, avl_status_found
jz .not_found
mov r11, [r8+_avlofs_parent]
mov r9, [r8+_avlofs_left]
mov rdx, [r8+_avlofs_right]
test rdx, rdx
jz .case_one
mov rax, [rdx+_avlofs_left]
test rax, rax
jz .case_two
jmp .case_three
calign
.case_one:
test r11, r11
jz .case_one_check_empty
test r9, r9
jz .case_one_no_c
mov [r9+_avlofs_parent], r11
calign
.case_one_no_c:
sub ecx, 1
bt r10d, ecx
jnc .case_one_relink_right
mov [r11+_avlofs_left], r9
mov rsi, r11
push r8
call _map_left_lighter
pop r8
jmp .relinked
calign
.case_one_relink_right:
mov [r11+_avlofs_right], r9
mov rsi, r11
push r8
call _map_right_lighter
pop r8
jmp .relinked
calign
.case_one_check_empty:
test r9, r9
jnz .case_one_new_root
mov qword [rdi+_avlofs_parent], 0
jmp .relinked
calign
.case_one_new_root:
mov qword [r9+_avlofs_parent], 0
mov [rdi+_avlofs_parent], r9
jmp .relinked
calign
.case_two:
mov [rdx+_avlofs_left], r9
test r9, r9
jz .case_two_no_c
mov [r9+_avlofs_parent], rdx
calign
.case_two_no_c:
test r11, r11
jz .case_two_new_root
mov [rdx+_avlofs_parent], r11
sub ecx, 1
bt r10d, ecx
jnc .case_two_relink_right
mov [r11+_avlofs_left], rdx
jmp .case_two_rebalance
calign
.case_two_relink_right:
mov [r11+_avlofs_right], rdx
calign
.case_two_rebalance:
push r9
mov r9d, dword [r8+_avlofs_flags]
and r9d, avl_all
and dword [rdx+_avlofs_flags], 0xffff - avl_all
or dword [rdx+_avlofs_flags], r9d
pop r9
mov r11, rdx
mov rsi, r11
push r8
call _map_right_lighter
pop r8
jmp .relinked
calign
.case_two_new_root:
mov qword [rdx+_avlofs_parent], 0
mov [rdi+_avlofs_parent], rdx
jmp .case_two_rebalance
calign
.case_three:
push r8
mov rsi, r8
call _map_successor
mov r9, [rax+_avlofs_right]
mov r8, [rax+_avlofs_parent]
mov [r8+_avlofs_left], r9
test r9, r9
jnz .case_three_succ_has_right
calign
.case_three_succ_no_right:
mov rsi, r8
push rax
call _map_left_lighter
pop rax
pop r8
mov r9, [r8+_avlofs_left]
mov rdx, [r8+_avlofs_right]
mov [rax+_avlofs_left], r9
mov r11, [r8+_avlofs_parent]
test r9, r9
jz .case_three_succ_no_right_no_c
mov [r9+_avlofs_parent], rax
calign
.case_three_succ_no_right_no_c:
mov [rdx+_avlofs_parent], rax
mov [rax+_avlofs_right], rdx
push r9
mov r9d, dword [r8+_avlofs_flags]
and r9d, avl_all
and dword [rax+_avlofs_flags], 0xffff - avl_all
or dword [rax+_avlofs_flags], r9d
pop r9
mov [rax+_avlofs_parent], r11
test r11, r11
jz .case_three_was_root
cmp r8, [r11+_avlofs_right]
je .case_three_relink_right
mov [r11+_avlofs_left], rax
jmp .relinked
calign
.case_three_relink_right:
mov [r11+_avlofs_right], rax
jmp .relinked
calign
.relinked:
xor eax, eax
mov r11, [r8+_avlofs_prev]
mov rdx, [r8+_avlofs_next]
test r11, r11
jz .relinked_loop_set_first
mov [r11+_avlofs_next], rdx
jmp .relinked_loop_otherside
calign
.relinked_loop:
mov r11, [r8+_avlofs_prev]
mov rdx, [r8+_avlofs_next]
test r11, r11
jz .relinked_loop_set_first
mov [r11+_avlofs_next], rdx
jmp .relinked_loop_otherside
calign
.relinked_loop_set_first:
mov [rdi+_avlofs_next], rdx
mov r11, [r8+_avlofs_next]
mov rdx, [r8+_avlofs_prev]
test r11, r11
jz .relinked_loop_set_last
mov [r11+_avlofs_prev], rdx
jmp .relinked_loop_dec
calign
.relinked_loop_otherside:
mov r11, [r8+_avlofs_next]
mov rdx, [r8+_avlofs_prev]
test r11, r11
jz .relinked_loop_set_last
mov [r11+_avlofs_prev], rdx
jmp .relinked_loop_dec
calign
.relinked_loop_set_last:
mov [rdi+_avlofs_prev], rdx
sub qword [rdi+_avlofs_right], 1
mov r11, [r8+_avlofs_trunk]
push rdi rax r11
mov rdi, r8
call heap$free
pop r11 rax rdi
add eax, 1
mov r8, r11
test r8, r8
jnz .relinked_loop
epilog
calign
.relinked_loop_dec:
sub qword [rdi+_avlofs_right], 1
mov r11, [r8+_avlofs_trunk]
push rdi rax r11
mov rdi, r8
call heap$free
pop r11 rax rdi
add eax, 1
mov r8, r11
test r8, r8
jnz .relinked_loop
epilog
calign
.case_three_succ_has_right:
mov [r9+_avlofs_parent], r8
jmp .case_three_succ_no_right
calign
.case_three_was_root:
mov qword [rax+_avlofs_parent], 0
mov [rdi+_avlofs_parent], rax
jmp .relinked
calign
.not_found:
xor eax, eax ; no nodes deleted
epilog
end if
if used stringmap$erase | defined include_everything
; NOTE: caution is advised! special handling is required to deal with the fact that
; we do not heap$free either the key or the value (that is up to the caller)
; returns count of nodes removed (0 == not found) in eax, rdx == topmost node key, r8 == topmost node value
falign
stringmap$erase:
prolog stringmap$erase
call _stringmap_locate_node
test r9d, avl_status_found
jz .not_found
push qword [r8+_avlofs_key]
push qword [r8+_avlofs_value]
mov r11, [r8+_avlofs_parent]
mov r9, [r8+_avlofs_left]
mov rdx, [r8+_avlofs_right]
test rdx, rdx
jz .case_one
mov rax, [rdx+_avlofs_left]
test rax, rax
jz .case_two
jmp .case_three
calign
.case_one:
test r11, r11
jz .case_one_check_empty
test r9, r9
jz .case_one_no_c
mov [r9+_avlofs_parent], r11
calign
.case_one_no_c:
sub ecx, 1
bt r10d, ecx
jnc .case_one_relink_right
mov [r11+_avlofs_left], r9
mov rsi, r11
push r8
call _map_left_lighter
pop r8
jmp .relinked
calign
.case_one_relink_right:
mov [r11+_avlofs_right], r9
mov rsi, r11
push r8
call _map_right_lighter
pop r8
jmp .relinked
calign
.case_one_check_empty:
test r9, r9
jnz .case_one_new_root
mov qword [rdi+_avlofs_parent], 0
jmp .relinked
calign
.case_one_new_root:
mov qword [r9+_avlofs_parent], 0
mov [rdi+_avlofs_parent], r9
jmp .relinked
calign
.case_two:
mov [rdx+_avlofs_left], r9
test r9, r9
jz .case_two_no_c
mov [r9+_avlofs_parent], rdx
calign
.case_two_no_c:
test r11, r11
jz .case_two_new_root
mov [rdx+_avlofs_parent], r11
sub ecx, 1
bt r10d, ecx
jnc .case_two_relink_right
mov [r11+_avlofs_left], rdx
jmp .case_two_rebalance
calign
.case_two_relink_right:
mov [r11+_avlofs_right], rdx
calign
.case_two_rebalance:
push r9
mov r9d, dword [r8+_avlofs_flags]
and r9d, avl_all
and dword [rdx+_avlofs_flags], 0xffff - avl_all
or dword [rdx+_avlofs_flags], r9d
pop r9
mov r11, rdx
mov rsi, r11
push r8
call _map_right_lighter
pop r8
jmp .relinked
calign
.case_two_new_root:
mov qword [rdx+_avlofs_parent], 0
mov [rdi+_avlofs_parent], rdx
jmp .case_two_rebalance
calign
.case_three:
push r8
mov rsi, r8
call _map_successor
mov r9, [rax+_avlofs_right]
mov r8, [rax+_avlofs_parent]
mov [r8+_avlofs_left], r9
test r9, r9
jnz .case_three_succ_has_right
calign
.case_three_succ_no_right:
mov rsi, r8
push rax
call _map_left_lighter
pop rax
pop r8
mov r9, [r8+_avlofs_left]
mov rdx, [r8+_avlofs_right]
mov [rax+_avlofs_left], r9
mov r11, [r8+_avlofs_parent]
test r9, r9
jz .case_three_succ_no_right_no_c
mov [r9+_avlofs_parent], rax
calign
.case_three_succ_no_right_no_c:
mov [rdx+_avlofs_parent], rax
mov [rax+_avlofs_right], rdx
push r9
mov r9d, dword [r8+_avlofs_flags]
and r9d, avl_all
and dword [rax+_avlofs_flags], 0xffff - avl_all
or dword [rax+_avlofs_flags], r9d
pop r9
mov [rax+_avlofs_parent], r11
test r11, r11
jz .case_three_was_root
cmp r8, [r11+_avlofs_right]
je .case_three_relink_right
mov [r11+_avlofs_left], rax
jmp .relinked
calign
.case_three_relink_right:
mov [r11+_avlofs_right], rax
jmp .relinked
calign
.relinked:
xor eax, eax
mov r11, [r8+_avlofs_prev]
mov rdx, [r8+_avlofs_next]
test r11, r11
jz .relinked_loop_set_first
mov [r11+_avlofs_next], rdx
jmp .relinked_loop_otherside
calign
.relinked_loop:
mov r11, [r8+_avlofs_prev]
mov rdx, [r8+_avlofs_next]
test r11, r11
jz .relinked_loop_set_first
mov [r11+_avlofs_next], rdx
jmp .relinked_loop_otherside
calign
.relinked_loop_set_first:
mov [rdi+_avlofs_next], rdx
mov r11, [r8+_avlofs_next]
mov rdx, [r8+_avlofs_prev]
test r11, r11
jz .relinked_loop_set_last
mov [r11+_avlofs_prev], rdx
jmp .relinked_loop_dec
calign
.relinked_loop_otherside:
mov r11, [r8+_avlofs_next]
mov rdx, [r8+_avlofs_prev]
test r11, r11
jz .relinked_loop_set_last
mov [r11+_avlofs_prev], rdx
jmp .relinked_loop_dec
calign
.relinked_loop_set_last:
mov [rdi+_avlofs_prev], rdx
sub qword [rdi+_avlofs_right], 1
mov r11, [r8+_avlofs_trunk]
push rdi rax r11
mov rdi, r8
call heap$free
pop r11 rax rdi
add eax, 1
mov r8, r11
test r8, r8
jnz .relinked_loop
pop r8 rdx
epilog
calign
.relinked_loop_dec:
sub qword [rdi+_avlofs_right], 1
mov r11, [r8+_avlofs_trunk]
push rdi rax r11
mov rdi, r8
call heap$free
pop r11 rax rdi
add eax, 1
mov r8, r11
test r8, r8
jnz .relinked_loop
pop r8 rdx
epilog
calign
.case_three_succ_has_right:
mov [r9+_avlofs_parent], r8
jmp .case_three_succ_no_right
calign
.case_three_was_root:
mov qword [rax+_avlofs_parent], 0
mov [rdi+_avlofs_parent], rax
jmp .relinked
calign
.not_found:
xor eax, eax ; no nodes deleted
epilog
end if