August 2016 - Wine-commits - list.winehq.org

Henri Verbeet : d3d9: Use wined3d_resource_unmap() in d3d9_vertexbuffer_Unlock().
by Alexandre Julliard 30 Aug '16

30 Aug '16

Module: wine Branch: master Commit: f1e78067217edc2de29dcf7b8261a60377e25561 URL: http://source.winehq.org/git/wine.git/?a=commit;h=f1e78067217edc2de29dcf7b8… Author: Henri Verbeet <hverbeet(a)codeweavers.com> Date: Tue Aug 30 11:48:20 2016 +0200 d3d9: Use wined3d_resource_unmap() in d3d9_vertexbuffer_Unlock(). Signed-off-by: Henri Verbeet <hverbeet(a)codeweavers.com> Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- dlls/d3d9/buffer.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/dlls/d3d9/buffer.c b/dlls/d3d9/buffer.c index 53f2272..de77d5a 100644 --- a/dlls/d3d9/buffer.c +++ b/dlls/d3d9/buffer.c @@ -208,7 +208,7 @@ static HRESULT WINAPI d3d9_vertexbuffer_Unlock(IDirect3DVertexBuffer9 *iface) TRACE("iface %p.\n", iface); wined3d_mutex_lock(); - wined3d_buffer_unmap(buffer->wined3d_buffer); + wined3d_resource_unmap(wined3d_buffer_get_resource(buffer->wined3d_buffer), 0); wined3d_mutex_unlock(); return D3D_OK;

1 0

Henri Verbeet : d3d9: Use wined3d_resource_map() in d3d9_indexbuffer_Lock( ).
by Alexandre Julliard 30 Aug '16

30 Aug '16

Module: wine Branch: master Commit: 4d638863fb111794ee1de241da2489ff9be196de URL: http://source.winehq.org/git/wine.git/?a=commit;h=4d638863fb111794ee1de241d… Author: Henri Verbeet <hverbeet(a)codeweavers.com> Date: Tue Aug 30 11:48:21 2016 +0200 d3d9: Use wined3d_resource_map() in d3d9_indexbuffer_Lock(). Signed-off-by: Henri Verbeet <hverbeet(a)codeweavers.com> Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- dlls/d3d9/buffer.c | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) diff --git a/dlls/d3d9/buffer.c b/dlls/d3d9/buffer.c index de77d5a..d66c31d 100644 --- a/dlls/d3d9/buffer.c +++ b/dlls/d3d9/buffer.c @@ -465,14 +465,20 @@ static HRESULT WINAPI d3d9_indexbuffer_Lock(IDirect3DIndexBuffer9 *iface, UINT offset, UINT size, void **data, DWORD flags) { struct d3d9_indexbuffer *buffer = impl_from_IDirect3DIndexBuffer9(iface); + struct wined3d_map_desc wined3d_map_desc; + struct wined3d_box wined3d_box = {0}; HRESULT hr; TRACE("iface %p, offset %u, size %u, data %p, flags %#x.\n", iface, offset, size, data, flags); + wined3d_box.left = offset; + wined3d_box.right = offset + size; wined3d_mutex_lock(); - hr = wined3d_buffer_map(buffer->wined3d_buffer, offset, size, (BYTE **)data, flags); + hr = wined3d_resource_map(wined3d_buffer_get_resource(buffer->wined3d_buffer), + 0, &wined3d_map_desc, &wined3d_box, flags); wined3d_mutex_unlock(); + *data = wined3d_map_desc.data; return hr; }

1 0

Henri Verbeet : d3d9: Use wined3d_resource_unmap() in d3d9_indexbuffer_Unlock().
by Alexandre Julliard 30 Aug '16

30 Aug '16

Module: wine Branch: master Commit: a6e17d11089d774d19877e1266f47e89baab7d0b URL: http://source.winehq.org/git/wine.git/?a=commit;h=a6e17d11089d774d19877e126… Author: Henri Verbeet <hverbeet(a)codeweavers.com> Date: Tue Aug 30 11:48:22 2016 +0200 d3d9: Use wined3d_resource_unmap() in d3d9_indexbuffer_Unlock(). Signed-off-by: Henri Verbeet <hverbeet(a)codeweavers.com> Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- dlls/d3d9/buffer.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/dlls/d3d9/buffer.c b/dlls/d3d9/buffer.c index d66c31d..dc52d93 100644 --- a/dlls/d3d9/buffer.c +++ b/dlls/d3d9/buffer.c @@ -490,7 +490,7 @@ static HRESULT WINAPI d3d9_indexbuffer_Unlock(IDirect3DIndexBuffer9 *iface) TRACE("iface %p.\n", iface); wined3d_mutex_lock(); - wined3d_buffer_unmap(buffer->wined3d_buffer); + wined3d_resource_unmap(wined3d_buffer_get_resource(buffer->wined3d_buffer), 0); wined3d_mutex_unlock(); return D3D_OK;

1 0

Hugh McMaster : reg/tests: Fix copy/paste error in 'import' tests.
by Alexandre Julliard 30 Aug '16

30 Aug '16

Module: wine Branch: master Commit: 0cea0605cf7cf4cb013d49b9bee2afc2a662add9 URL: http://source.winehq.org/git/wine.git/?a=commit;h=0cea0605cf7cf4cb013d49b9b… Author: Hugh McMaster <hugh.mcmaster(a)outlook.com> Date: Tue Aug 30 11:07:45 2016 +0000 reg/tests: Fix copy/paste error in 'import' tests. Signed-off-by: Hugh McMaster <hugh.mcmaster(a)outlook.com> Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- programs/reg/tests/reg.c | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) diff --git a/programs/reg/tests/reg.c b/programs/reg/tests/reg.c index 1dab72b..715cdbd 100644 --- a/programs/reg/tests/reg.c +++ b/programs/reg/tests/reg.c @@ -928,12 +928,10 @@ static void test_import(void) todo_wine ok(r == REG_EXIT_SUCCESS, "got exit code %d, expected 0\n", r); test_import_wstr("\xef\xbb\xbf REGEDIT4\n", &r); - ok(r == REG_EXIT_FAILURE || broken(r == REG_EXIT_SUCCESS) /* WinXP */, - "got exit code %d, expected 1\n", r); + todo_wine ok(r == REG_EXIT_SUCCESS, "got exit code %d, expected 0\n", r); test_import_wstr("\xef\xbb\xbf\tREGEDIT4\n", &r); - ok(r == REG_EXIT_FAILURE || broken(r == REG_EXIT_SUCCESS) /* WinXP */, - "got exit code %d, expected 1\n", r); + todo_wine ok(r == REG_EXIT_SUCCESS, "got exit code %d, expected 0\n", r); test_import_wstr("\xef\xbb\xbf\nREGEDIT4\n", &r); ok(r == REG_EXIT_FAILURE || broken(r == REG_EXIT_SUCCESS) /* WinXP */,

1 0

Alistair Leslie-Hughes : inetcomm/tests: Add Attachment tests.
by Alexandre Julliard 30 Aug '16

30 Aug '16

Module: wine Branch: master Commit: 002af352fac43d170aad216bf15098b27555539a URL: http://source.winehq.org/git/wine.git/?a=commit;h=002af352fac43d170aad216bf… Author: Alistair Leslie-Hughes <leslie_alistair(a)hotmail.com> Date: Thu Aug 18 11:13:02 2016 +0000 inetcomm/tests: Add Attachment tests. Signed-off-by: Alistair Leslie-Hughes <leslie_alistair(a)hotmail.com> Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- dlls/inetcomm/tests/mimeole.c | 53 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) diff --git a/dlls/inetcomm/tests/mimeole.c b/dlls/inetcomm/tests/mimeole.c index 011c19f..ce1e4af 100644 --- a/dlls/inetcomm/tests/mimeole.c +++ b/dlls/inetcomm/tests/mimeole.c @@ -338,6 +338,59 @@ static void test_CreateMessage(void) hr = IMimeMessage_GetAttachments(msg, &count, &body_list); ok(hr == S_OK, "ret %08x\n", hr); ok(count == 2, "got %d\n", count); + if(count == 2) + { + ENCODINGTYPE encoding; + IMimeBody *attachment; + PROPVARIANT prop; + + PropVariantInit(&prop); + + hr = IMimeMessage_BindToObject(msg, body_list[0], &IID_IMimeBody, (void**)&attachment); + ok(hr == S_OK, "ret %08x\n", hr); + + hr = IMimeBody_IsContentType(attachment, "multipart", NULL); + ok(hr == S_FALSE, "ret %08x\n", hr); + + hr = IMimeBody_GetCurrentEncoding(attachment, &encoding); + ok(hr == S_OK, "ret %08x\n", hr); + todo_wine ok(encoding == IET_8BIT, "ret %d\n", encoding); + + prop.vt = VT_LPSTR; + hr = IMimeBody_GetProp(attachment, "Content-Transfer-Encoding", 0, &prop); + ok(hr == S_OK, "ret %08x\n", hr); + + ok(prop.vt == VT_LPSTR, "type %d\n", prop.vt); + ok(!strcmp(prop.u.pszVal, "8bit"), "got %s\n", prop.u.pszVal); + PropVariantClear(&prop); + + hr = IMimeBody_IsType(attachment, IBT_ATTACHMENT); + todo_wine ok(hr == S_FALSE, "ret %08x\n", hr); + + IMimeBody_Release(attachment); + + hr = IMimeMessage_BindToObject(msg, body_list[1], &IID_IMimeBody, (void**)&attachment); + ok(hr == S_OK, "ret %08x\n", hr); + + hr = IMimeBody_IsContentType(attachment, "multipart", NULL); + ok(hr == S_FALSE, "ret %08x\n", hr); + + hr = IMimeBody_GetCurrentEncoding(attachment, &encoding); + ok(hr == S_OK, "ret %08x\n", hr); + todo_wine ok(encoding == IET_7BIT, "ret %d\n", encoding); + + prop.vt = VT_LPSTR; + hr = IMimeBody_GetProp(attachment, "Content-Transfer-Encoding", 0, &prop); + ok(hr == S_OK, "ret %08x\n", hr); + ok(prop.vt == VT_LPSTR, "type %d\n", prop.vt); + ok(!strcmp(prop.u.pszVal, "7bit"), "got %s\n", prop.u.pszVal); + PropVariantClear(&prop); + + hr = IMimeBody_IsType(attachment, IBT_ATTACHMENT); + ok(hr == S_OK, "ret %08x\n", hr); + + IMimeBody_Release(attachment); + } CoTaskMemFree(body_list); hr = IMimeBody_GetCharset(body, &hcs);

1 0

Jacek Caban : rpcrt4/tests: Don't load GetUserNameEx dynamically.
by Alexandre Julliard 30 Aug '16

30 Aug '16

Module: wine Branch: master Commit: ffe01b33f1a266aef2ec75e46d23a316750b8211 URL: http://source.winehq.org/git/wine.git/?a=commit;h=ffe01b33f1a266aef2ec75e46… Author: Jacek Caban <jacek(a)codeweavers.com> Date: Mon Aug 29 17:30:10 2016 +0200 rpcrt4/tests: Don't load GetUserNameEx dynamically. Signed-off-by: Jacek Caban <jacek(a)codeweavers.com> Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- dlls/rpcrt4/tests/Makefile.in | 2 +- dlls/rpcrt4/tests/rpc.c | 11 ++--------- dlls/rpcrt4/tests/server.c | 29 ++++++++--------------------- 3 files changed, 11 insertions(+), 31 deletions(-) diff --git a/dlls/rpcrt4/tests/Makefile.in b/dlls/rpcrt4/tests/Makefile.in index 5df97c4..5229d07 100644 --- a/dlls/rpcrt4/tests/Makefile.in +++ b/dlls/rpcrt4/tests/Makefile.in @@ -1,5 +1,5 @@ TESTDLL = rpcrt4.dll -IMPORTS = ole32 rpcrt4 advapi32 +IMPORTS = ole32 rpcrt4 secur32 advapi32 EXTRAIDLFLAGS = --prefix-server=s_ C_SRCS = \ diff --git a/dlls/rpcrt4/tests/rpc.c b/dlls/rpcrt4/tests/rpc.c index 81b598c..d260827 100644 --- a/dlls/rpcrt4/tests/rpc.c +++ b/dlls/rpcrt4/tests/rpc.c @@ -862,19 +862,12 @@ static void test_RpcServerInqDefaultPrincName(void) { RPC_STATUS ret; RPC_CSTR principal, saved_principal; - BOOLEAN (WINAPI *pGetUserNameExA)(EXTENDED_NAME_FORMAT,LPSTR,PULONG); char *username; ULONG len = 0; - pGetUserNameExA = (void *)GetProcAddress( LoadLibraryA("secur32.dll"), "GetUserNameExA" ); - if (!pGetUserNameExA) - { - win_skip( "GetUserNameExA not exported\n" ); - return; - } - pGetUserNameExA( NameSamCompatible, NULL, &len ); + GetUserNameExA( NameSamCompatible, NULL, &len ); username = HeapAlloc( GetProcessHeap(), 0, len ); - pGetUserNameExA( NameSamCompatible, username, &len ); + GetUserNameExA( NameSamCompatible, username, &len ); ret = RpcServerInqDefaultPrincNameA( 0, NULL ); ok( ret == RPC_S_UNKNOWN_AUTHN_SERVICE, "got %u\n", ret ); diff --git a/dlls/rpcrt4/tests/server.c b/dlls/rpcrt4/tests/server.c index 2653f7a..6901f6b 100644 --- a/dlls/rpcrt4/tests/server.c +++ b/dlls/rpcrt4/tests/server.c @@ -44,7 +44,6 @@ static void (WINAPI *pNDRSContextMarshall2)(RPC_BINDING_HANDLE, NDR_SCONTEXT, vo static NDR_SCONTEXT (WINAPI *pNDRSContextUnmarshall2)(RPC_BINDING_HANDLE, void*, ULONG, void*, ULONG); static RPC_STATUS (WINAPI *pRpcServerRegisterIfEx)(RPC_IF_HANDLE,UUID*, RPC_MGR_EPV*, unsigned int, unsigned int,RPC_IF_CALLBACK_FN*); -static BOOLEAN (WINAPI *pGetUserNameExA)(EXTENDED_NAME_FORMAT, LPSTR, PULONG); static RPC_STATUS (WINAPI *pRpcBindingSetAuthInfoExA)(RPC_BINDING_HANDLE, RPC_CSTR, ULONG, ULONG, RPC_AUTH_IDENTITY_HANDLE, ULONG, RPC_SECURITY_QOS *); static RPC_STATUS (WINAPI *pRpcServerRegisterAuthInfoA)(RPC_CSTR, ULONG, RPC_AUTH_KEY_RETRIEVAL_FN, LPVOID); @@ -60,14 +59,12 @@ static const WCHAR worldW[] = { 'W','o','r','l','d','!',0 }; static void InitFunctionPointers(void) { HMODULE hrpcrt4 = GetModuleHandleA("rpcrt4.dll"); - HMODULE hsecur32 = LoadLibraryA("secur32.dll"); pNDRSContextMarshall2 = (void *)GetProcAddress(hrpcrt4, "NDRSContextMarshall2"); pNDRSContextUnmarshall2 = (void *)GetProcAddress(hrpcrt4, "NDRSContextUnmarshall2"); pRpcServerRegisterIfEx = (void *)GetProcAddress(hrpcrt4, "RpcServerRegisterIfEx"); pRpcBindingSetAuthInfoExA = (void *)GetProcAddress(hrpcrt4, "RpcBindingSetAuthInfoExA"); pRpcServerRegisterAuthInfoA = (void *)GetProcAddress(hrpcrt4, "RpcServerRegisterAuthInfoA"); - pGetUserNameExA = (void *)GetProcAddress(hsecur32, "GetUserNameExA"); if (!pNDRSContextMarshall2) old_windows_version = TRUE; } @@ -1500,7 +1497,7 @@ void __cdecl s_authinfo_test(unsigned int protseq, int secure) todo_wine ok(principal != NULL, "NULL principal\n"); } - if (protseq == RPC_PROTSEQ_LRPC && principal && pGetUserNameExA) + if (protseq == RPC_PROTSEQ_LRPC && principal) { int len; char *spn; @@ -1548,9 +1545,6 @@ set_auth_info(RPC_BINDING_HANDLE handle) RPC_STATUS status; RPC_SECURITY_QOS qos; - if (!pGetUserNameExA) - return; - qos.Version = 1; qos.Capabilities = RPC_C_QOS_CAPABILITIES_MUTUAL_AUTH; qos.IdentityTracking = RPC_C_QOS_IDENTITY_STATIC; @@ -1709,11 +1703,9 @@ server(void) if (ncalrpc_status == RPC_S_OK) { run_client("ncalrpc_basic"); - if (pGetUserNameExA) - { - /* we don't need to register RPC_C_AUTHN_WINNT for ncalrpc */ - run_client("ncalrpc_secure"); - } + + /* we don't need to register RPC_C_AUTHN_WINNT for ncalrpc */ + run_client("ncalrpc_secure"); } else skip("lrpc tests skipped due to earlier failure\n"); @@ -1742,20 +1734,15 @@ server(void) START_TEST(server) { + ULONG size = 0; int argc; char **argv; InitFunctionPointers(); - if (pGetUserNameExA) - { - ULONG size = 0; - ok(!pGetUserNameExA(NameSamCompatible, NULL, &size), "GetUserNameExA\n"); - domain_and_user = HeapAlloc(GetProcessHeap(), 0, size); - ok(pGetUserNameExA(NameSamCompatible, domain_and_user, &size), "GetUserNameExA\n"); - } - else - win_skip("GetUserNameExA is needed for some authentication tests\n"); + ok(!GetUserNameExA(NameSamCompatible, NULL, &size), "GetUserNameExA\n"); + domain_and_user = HeapAlloc(GetProcessHeap(), 0, size); + ok(GetUserNameExA(NameSamCompatible, domain_and_user, &size), "GetUserNameExA\n"); argc = winetest_get_mainargs(&argv); progname = argv[0];

1 0

Jacek Caban : winex11.drv: Added ThreadDetach entry point and use it instead of DllMain.
by Alexandre Julliard 30 Aug '16

30 Aug '16

Module: wine Branch: master Commit: af9f722361800c17875964007b4f5f276db5cd4c URL: http://source.winehq.org/git/wine.git/?a=commit;h=af9f722361800c17875964007… Author: Jacek Caban <jacek(a)codeweavers.com> Date: Mon Aug 29 19:58:20 2016 +0200 winex11.drv: Added ThreadDetach entry point and use it instead of DllMain. Signed-off-by: Jacek Caban <jacek(a)codeweavers.com> Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- dlls/winex11.drv/winex11.drv.spec | 1 + dlls/winex11.drv/x11drv_main.c | 8 +++----- 2 files changed, 4 insertions(+), 5 deletions(-) diff --git a/dlls/winex11.drv/winex11.drv.spec b/dlls/winex11.drv/winex11.drv.spec index 7cdce52..ceb0f56 100644 --- a/dlls/winex11.drv/winex11.drv.spec +++ b/dlls/winex11.drv/winex11.drv.spec @@ -53,6 +53,7 @@ @ cdecl WindowPosChanging(long long long ptr ptr ptr ptr) X11DRV_WindowPosChanging @ cdecl WindowPosChanged(long long long ptr ptr ptr ptr ptr) X11DRV_WindowPosChanged @ cdecl SystemParametersInfo(long long ptr long) X11DRV_SystemParametersInfo +@ cdecl ThreadDetach() X11DRV_ThreadDetach # WinTab32 @ cdecl AttachEventQueueToTablet(long) X11DRV_AttachEventQueueToTablet diff --git a/dlls/winex11.drv/x11drv_main.c b/dlls/winex11.drv/x11drv_main.c index d4f5c84..c2e0969 100644 --- a/dlls/winex11.drv/x11drv_main.c +++ b/dlls/winex11.drv/x11drv_main.c @@ -597,9 +597,9 @@ static BOOL process_attach(void) /*********************************************************************** - * X11DRV thread termination routine + * ThreadDetach (X11DRV.@) */ -static void thread_detach(void) +void CDECL X11DRV_ThreadDetach(void) { struct x11drv_thread_data *data = TlsGetValue( thread_data_tls_index ); @@ -690,12 +690,10 @@ BOOL WINAPI DllMain( HINSTANCE hinst, DWORD reason, LPVOID reserved ) switch(reason) { case DLL_PROCESS_ATTACH: + DisableThreadLibraryCalls( hinst ); x11drv_module = hinst; ret = process_attach(); break; - case DLL_THREAD_DETACH: - thread_detach(); - break; } return ret; }

1 0

Jacek Caban : rbtree.h: Store parent entry pointer in each entry.
by Alexandre Julliard 30 Aug '16

30 Aug '16

Module: wine Branch: master Commit: 256f55e75bc5191cfdafd9d04c6f72194dd4a145 URL: http://source.winehq.org/git/wine.git/?a=commit;h=256f55e75bc5191cfdafd9d04… Author: Jacek Caban <jacek(a)codeweavers.com> Date: Mon Aug 15 21:53:13 2016 +0200 rbtree.h: Store parent entry pointer in each entry. Signed-off-by: Jacek Caban <jacek(a)codeweavers.com> Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- include/wine/rbtree.h | 79 ++++++++++++++++++++++++++++++++------------------- 1 file changed, 50 insertions(+), 29 deletions(-) diff --git a/include/wine/rbtree.h b/include/wine/rbtree.h index 13452d9..11f42f7 100644 --- a/include/wine/rbtree.h +++ b/include/wine/rbtree.h @@ -27,6 +27,7 @@ struct wine_rb_entry { + struct wine_rb_entry *parent; struct wine_rb_entry *left; struct wine_rb_entry *right; unsigned int flags; @@ -95,30 +96,46 @@ static inline int wine_rb_is_red(struct wine_rb_entry *entry) return entry && (entry->flags & WINE_RB_FLAG_RED); } -static inline void wine_rb_rotate_left(struct wine_rb_entry **entry) +static inline void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e) { - struct wine_rb_entry *e = *entry; struct wine_rb_entry *right = e->right; + if (!e->parent) + tree->root = right; + else if (e->parent->left == e) + e->parent->left = right; + else + e->parent->right = right; + e->right = right->left; + if (e->right) e->right->parent = e; right->left = e; + right->parent = e->parent; + e->parent = right; right->flags &= ~WINE_RB_FLAG_RED; right->flags |= e->flags & WINE_RB_FLAG_RED; e->flags |= WINE_RB_FLAG_RED; - *entry = right; } -static inline void wine_rb_rotate_right(struct wine_rb_entry **entry) +static inline void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e) { - struct wine_rb_entry *e = *entry; struct wine_rb_entry *left = e->left; + if (!e->parent) + tree->root = left; + else if (e->parent->left == e) + e->parent->left = left; + else + e->parent->right = left; + e->left = left->right; + if (e->left) e->left->parent = e; left->right = e; + left->parent = e->parent; + e->parent = left; left->flags &= ~WINE_RB_FLAG_RED; left->flags |= e->flags & WINE_RB_FLAG_RED; e->flags |= WINE_RB_FLAG_RED; - *entry = left; } static inline void wine_rb_flip_color(struct wine_rb_entry *entry) @@ -128,7 +145,7 @@ static inline void wine_rb_flip_color(struct wine_rb_entry *entry) entry->right->flags ^= WINE_RB_FLAG_RED; } -static inline void wine_rb_fixup(struct wine_rb_stack *stack) +static inline void wine_rb_fixup(struct wine_rb_tree *tree, struct wine_rb_stack *stack) { while (stack->count) { @@ -140,30 +157,30 @@ static inline void wine_rb_fixup(struct wine_rb_stack *stack) return; } - if (wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->left)) wine_rb_rotate_left(entry); - if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->left->left)) wine_rb_rotate_right(entry); + if (wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->left)) wine_rb_rotate_left(tree, *entry); + if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->left->left)) wine_rb_rotate_right(tree, *entry); if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->right)) wine_rb_flip_color(*entry); --stack->count; } } -static inline void wine_rb_move_red_left(struct wine_rb_entry **entry) +static inline void wine_rb_move_red_left(struct wine_rb_tree *tree, struct wine_rb_entry **entry) { wine_rb_flip_color(*entry); if (wine_rb_is_red((*entry)->right->left)) { - wine_rb_rotate_right(&(*entry)->right); - wine_rb_rotate_left(entry); + wine_rb_rotate_right(tree, (*entry)->right); + wine_rb_rotate_left(tree, *entry); wine_rb_flip_color(*entry); } } -static inline void wine_rb_move_red_right(struct wine_rb_entry **entry) +static inline void wine_rb_move_red_right(struct wine_rb_tree *tree, struct wine_rb_entry **entry) { wine_rb_flip_color(*entry); if (wine_rb_is_red((*entry)->left->left)) { - wine_rb_rotate_right(entry); + wine_rb_rotate_right(tree, *entry); wine_rb_flip_color(*entry); } } @@ -247,25 +264,26 @@ static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry) { - struct wine_rb_entry **parent = &tree->root; + struct wine_rb_entry **iter = &tree->root, *parent = tree->root; size_t black_height = 1; - while (*parent) + while (*iter) { int c; - if (!wine_rb_is_red(*parent)) ++black_height; + if (!wine_rb_is_red(*iter)) ++black_height; - wine_rb_stack_push(&tree->stack, parent); + wine_rb_stack_push(&tree->stack, iter); - c = tree->functions->compare(key, *parent); + parent = *iter; + c = tree->functions->compare(key, parent); if (!c) { wine_rb_stack_clear(&tree->stack); return -1; } - else if (c < 0) parent = &(*parent)->left; - else parent = &(*parent)->right; + else if (c < 0) iter = &parent->left; + else iter = &parent->right; } /* After insertion, the path length to any node should be <= (black_height + 1) * 2. */ @@ -276,11 +294,12 @@ static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct } entry->flags = WINE_RB_FLAG_RED; + entry->parent = parent; entry->left = NULL; entry->right = NULL; - *parent = entry; + *iter = entry; - wine_rb_fixup(&tree->stack); + wine_rb_fixup(tree, &tree->stack); tree->root->flags &= ~WINE_RB_FLAG_RED; return 0; @@ -295,19 +314,19 @@ static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key) if (tree->functions->compare(key, *entry) < 0) { wine_rb_stack_push(&tree->stack, entry); - if (!wine_rb_is_red((*entry)->left) && !wine_rb_is_red((*entry)->left->left)) wine_rb_move_red_left(entry); + if (!wine_rb_is_red((*entry)->left) && !wine_rb_is_red((*entry)->left->left)) wine_rb_move_red_left(tree, entry); entry = &(*entry)->left; } else { - if (wine_rb_is_red((*entry)->left)) wine_rb_rotate_right(entry); + if (wine_rb_is_red((*entry)->left)) wine_rb_rotate_right(tree, *entry); if (!tree->functions->compare(key, *entry) && !(*entry)->right) { *entry = NULL; break; } if (!wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->right->left)) - wine_rb_move_red_right(entry); + wine_rb_move_red_right(tree, entry); if (!tree->functions->compare(key, *entry)) { struct wine_rb_entry **e = &(*entry)->right; @@ -320,14 +339,16 @@ static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key) while ((*e)->left) { wine_rb_stack_push(&tree->stack, e); - if (!wine_rb_is_red((*e)->left) && !wine_rb_is_red((*e)->left->left)) wine_rb_move_red_left(e); + if (!wine_rb_is_red((*e)->left) && !wine_rb_is_red((*e)->left->left)) wine_rb_move_red_left(tree, e); e = &(*e)->left; } *e = NULL; - wine_rb_fixup(&tree->stack); + wine_rb_fixup(tree, &tree->stack); *m = **entry; *entry = m; + if (m->right) m->right->parent = m; + if (m->left) m->left->parent = m; break; } @@ -339,7 +360,7 @@ static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key) } } - wine_rb_fixup(&tree->stack); + wine_rb_fixup(tree, &tree->stack); if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED; }

1 0

Jacek Caban : rbtree.h: Use parent pointer instead of stack in wine_rb_postorder.
by Alexandre Julliard 30 Aug '16

30 Aug '16

Module: wine Branch: master Commit: 20740d849e443bc47d1850791897394a12ff779a URL: http://source.winehq.org/git/wine.git/?a=commit;h=20740d849e443bc47d1850791… Author: Jacek Caban <jacek(a)codeweavers.com> Date: Mon Aug 15 21:53:26 2016 +0200 rbtree.h: Use parent pointer instead of stack in wine_rb_postorder. Signed-off-by: Jacek Caban <jacek(a)codeweavers.com> Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- include/wine/rbtree.h | 49 +++++++++++++++++++++---------------------------- 1 file changed, 21 insertions(+), 28 deletions(-) diff --git a/include/wine/rbtree.h b/include/wine/rbtree.h index 11f42f7..2d364e3 100644 --- a/include/wine/rbtree.h +++ b/include/wine/rbtree.h @@ -59,8 +59,6 @@ typedef void (wine_rb_traverse_func_t)(struct wine_rb_entry *entry, void *contex #define WINE_RB_FLAG_RED 0x1 #define WINE_RB_FLAG_STOP 0x2 -#define WINE_RB_FLAG_TRAVERSED_LEFT 0x4 -#define WINE_RB_FLAG_TRAVERSED_RIGHT 0x8 static inline void wine_rb_stack_clear(struct wine_rb_stack *stack) { @@ -185,37 +183,32 @@ static inline void wine_rb_move_red_right(struct wine_rb_tree *tree, struct wine } } -static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context) +static inline struct wine_rb_entry *wine_rb_postorder_head(struct wine_rb_entry *iter) { - struct wine_rb_entry **entry; - - if (!tree->root) return; + if (!iter) return NULL; - for (entry = &tree->root;;) - { - struct wine_rb_entry *e = *entry; - - if (e->left && !(e->flags & WINE_RB_FLAG_TRAVERSED_LEFT)) - { - wine_rb_stack_push(&tree->stack, entry); - e->flags |= WINE_RB_FLAG_TRAVERSED_LEFT; - entry = &e->left; - continue; - } + for (;;) { + while (iter->left) iter = iter->left; + if (!iter->right) return iter; + iter = iter->right; + } +} - if (e->right && !(e->flags & WINE_RB_FLAG_TRAVERSED_RIGHT)) - { - wine_rb_stack_push(&tree->stack, entry); - e->flags |= WINE_RB_FLAG_TRAVERSED_RIGHT; - entry = &e->right; - continue; - } +static inline struct wine_rb_entry *wine_rb_postorder_next(struct wine_rb_entry *iter) +{ + if (!iter->parent) return NULL; + if (iter == iter->parent->right || !iter->parent->right) return iter->parent; + return wine_rb_postorder_head(iter->parent->right); +} - e->flags &= ~(WINE_RB_FLAG_TRAVERSED_LEFT | WINE_RB_FLAG_TRAVERSED_RIGHT); - callback(e, context); +static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context) +{ + struct wine_rb_entry *iter, *next; - if (!tree->stack.count) break; - entry = tree->stack.entries[--tree->stack.count]; + for (iter = wine_rb_postorder_head(tree->root); iter; iter = next) + { + next = wine_rb_postorder_next(iter); + callback(iter, context); } }

1 0

Jacek Caban : rbtree.h: Rewrite wine_rb_remove to use parent pointers instead of stack.
by Alexandre Julliard 30 Aug '16

30 Aug '16

Module: wine Branch: master Commit: f9dc4832ed64a1948341e14e945b77454c603019 URL: http://source.winehq.org/git/wine.git/?a=commit;h=f9dc4832ed64a1948341e14e9… Author: Jacek Caban <jacek(a)codeweavers.com> Date: Mon Aug 15 21:53:53 2016 +0200 rbtree.h: Rewrite wine_rb_remove to use parent pointers instead of stack. Signed-off-by: Jacek Caban <jacek(a)codeweavers.com> Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- include/wine/rbtree.h | 179 ++++++++++++++++++++++++++++++-------------------- 1 file changed, 108 insertions(+), 71 deletions(-) diff --git a/include/wine/rbtree.h b/include/wine/rbtree.h index 2d364e3..a549a87 100644 --- a/include/wine/rbtree.h +++ b/include/wine/rbtree.h @@ -94,7 +94,7 @@ static inline int wine_rb_is_red(struct wine_rb_entry *entry) return entry && (entry->flags & WINE_RB_FLAG_RED); } -static inline void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e) +static inline void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e, int change_color) { struct wine_rb_entry *right = e->right; @@ -110,12 +110,15 @@ static inline void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb right->left = e; right->parent = e->parent; e->parent = right; - right->flags &= ~WINE_RB_FLAG_RED; - right->flags |= e->flags & WINE_RB_FLAG_RED; - e->flags |= WINE_RB_FLAG_RED; + if (change_color) + { + right->flags &= ~WINE_RB_FLAG_RED; + right->flags |= e->flags & WINE_RB_FLAG_RED; + e->flags |= WINE_RB_FLAG_RED; + } } -static inline void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e) +static inline void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e, int change_color) { struct wine_rb_entry *left = e->left; @@ -131,9 +134,12 @@ static inline void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_r left->right = e; left->parent = e->parent; e->parent = left; - left->flags &= ~WINE_RB_FLAG_RED; - left->flags |= e->flags & WINE_RB_FLAG_RED; - e->flags |= WINE_RB_FLAG_RED; + if (change_color) + { + left->flags &= ~WINE_RB_FLAG_RED; + left->flags |= e->flags & WINE_RB_FLAG_RED; + e->flags |= WINE_RB_FLAG_RED; + } } static inline void wine_rb_flip_color(struct wine_rb_entry *entry) @@ -155,34 +161,13 @@ static inline void wine_rb_fixup(struct wine_rb_tree *tree, struct wine_rb_stack return; } - if (wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->left)) wine_rb_rotate_left(tree, *entry); - if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->left->left)) wine_rb_rotate_right(tree, *entry); + if (wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->left)) wine_rb_rotate_left(tree, *entry, 1); + if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->left->left)) wine_rb_rotate_right(tree, *entry, 1); if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->right)) wine_rb_flip_color(*entry); --stack->count; } } -static inline void wine_rb_move_red_left(struct wine_rb_tree *tree, struct wine_rb_entry **entry) -{ - wine_rb_flip_color(*entry); - if (wine_rb_is_red((*entry)->right->left)) - { - wine_rb_rotate_right(tree, (*entry)->right); - wine_rb_rotate_left(tree, *entry); - wine_rb_flip_color(*entry); - } -} - -static inline void wine_rb_move_red_right(struct wine_rb_tree *tree, struct wine_rb_entry **entry) -{ - wine_rb_flip_color(*entry); - if (wine_rb_is_red((*entry)->left->left)) - { - wine_rb_rotate_right(tree, *entry); - wine_rb_flip_color(*entry); - } -} - static inline struct wine_rb_entry *wine_rb_postorder_head(struct wine_rb_entry *iter) { if (!iter) return NULL; @@ -300,60 +285,112 @@ static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key) { - struct wine_rb_entry **entry = &tree->root; + struct wine_rb_entry *entry, *iter, *child, *parent, *w; + int need_fixup; + + if (!(entry = wine_rb_get(tree, key))) return; + + if (entry->right && entry->left) + for(iter = entry->right; iter->left; iter = iter->left); + else + iter = entry; + + child = iter->left ? iter->left : iter->right; + + if (!iter->parent) + tree->root = child; + else if (iter == iter->parent->left) + iter->parent->left = child; + else + iter->parent->right = child; + + if (child) child->parent = iter->parent; + parent = iter->parent; - while (*entry) + need_fixup = !wine_rb_is_red(iter); + + if (entry != iter) { - if (tree->functions->compare(key, *entry) < 0) - { - wine_rb_stack_push(&tree->stack, entry); - if (!wine_rb_is_red((*entry)->left) && !wine_rb_is_red((*entry)->left->left)) wine_rb_move_red_left(tree, entry); - entry = &(*entry)->left; - } + *iter = *entry; + if (!iter->parent) + tree->root = iter; + else if (entry == iter->parent->left) + iter->parent->left = iter; else - { - if (wine_rb_is_red((*entry)->left)) wine_rb_rotate_right(tree, *entry); - if (!tree->functions->compare(key, *entry) && !(*entry)->right) - { - *entry = NULL; - break; - } - if (!wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->right->left)) - wine_rb_move_red_right(tree, entry); - if (!tree->functions->compare(key, *entry)) - { - struct wine_rb_entry **e = &(*entry)->right; - struct wine_rb_entry *m = *e; - while (m->left) m = m->left; + iter->parent->right = iter; - wine_rb_stack_push(&tree->stack, entry); - (*entry)->flags |= WINE_RB_FLAG_STOP; + if (iter->right) iter->right->parent = iter; + if (iter->left) iter->left->parent = iter; + if (parent == entry) parent = iter; + } - while ((*e)->left) + if (need_fixup) + { + while (parent && !wine_rb_is_red(child)) + { + if (child == parent->left) + { + w = parent->right; + if (wine_rb_is_red(w)) { - wine_rb_stack_push(&tree->stack, e); - if (!wine_rb_is_red((*e)->left) && !wine_rb_is_red((*e)->left->left)) wine_rb_move_red_left(tree, e); - e = &(*e)->left; + w->flags &= ~WINE_RB_FLAG_RED; + parent->flags |= WINE_RB_FLAG_RED; + wine_rb_rotate_left(tree, parent, 0); + w = parent->right; + } + if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right)) + { + if (!wine_rb_is_red(w->right)) + { + w->left->flags &= ~WINE_RB_FLAG_RED; + w->flags |= WINE_RB_FLAG_RED; + wine_rb_rotate_right(tree, w, 0); + w = parent->right; + } + w->flags = (w->flags & ~WINE_RB_FLAG_RED) | (parent->flags & WINE_RB_FLAG_RED); + parent->flags &= ~WINE_RB_FLAG_RED; + if (w->right) + w->right->flags &= ~WINE_RB_FLAG_RED; + wine_rb_rotate_left(tree, parent, 0); + child = NULL; + break; } - *e = NULL; - wine_rb_fixup(tree, &tree->stack); - - *m = **entry; - *entry = m; - if (m->right) m->right->parent = m; - if (m->left) m->left->parent = m; - - break; } else { - wine_rb_stack_push(&tree->stack, entry); - entry = &(*entry)->right; + w = parent->left; + if (wine_rb_is_red(w)) + { + w->flags &= ~WINE_RB_FLAG_RED; + parent->flags |= WINE_RB_FLAG_RED; + wine_rb_rotate_right(tree, parent, 0); + w = parent->left; + } + if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right)) + { + if (!wine_rb_is_red(w->left)) + { + w->right->flags &= ~WINE_RB_FLAG_RED; + w->flags |= WINE_RB_FLAG_RED; + wine_rb_rotate_left(tree, w, 0); + w = parent->left; + } + w->flags = (w->flags & ~WINE_RB_FLAG_RED) | (parent->flags & WINE_RB_FLAG_RED); + parent->flags &= ~WINE_RB_FLAG_RED; + if (w->left) + w->left->flags &= ~WINE_RB_FLAG_RED; + wine_rb_rotate_right(tree, parent, 0); + child = NULL; + break; + } } + w->flags |= WINE_RB_FLAG_RED; + child = parent; + parent = child->parent; } + if (child) child->flags &= ~WINE_RB_FLAG_RED; } - wine_rb_fixup(tree, &tree->stack); if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED; }

1 0