wine-commits August 2016

2 participants
777 discussions

Henri Verbeet : d3d9: Use wined3d_resource_unmap() in d3d9_vertexbuffer_Unlock().

by Alexandre Julliard

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;

7 years, 8 months

Henri Verbeet : d3d9: Use wined3d_resource_map() in d3d9_vertexbuffer_Lock ().

by Alexandre Julliard

Module: wine Branch: master Commit: a0400a686c148a92dd2191cd619a05686c0cfceb URL: http://source.winehq.org/git/wine.git/?a=commit;h=a0400a686c148a92dd2191cd6… Author: Henri Verbeet <hverbeet(a)codeweavers.com> Date: Tue Aug 30 11:48:19 2016 +0200 d3d9: Use wined3d_resource_map() in d3d9_vertexbuffer_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 469b345..53f2272 100644 --- a/dlls/d3d9/buffer.c +++ b/dlls/d3d9/buffer.c @@ -183,14 +183,20 @@ static HRESULT WINAPI d3d9_vertexbuffer_Lock(IDirect3DVertexBuffer9 *iface, UINT void **data, DWORD flags) { struct d3d9_vertexbuffer *buffer = impl_from_IDirect3DVertexBuffer9(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; }

7 years, 8 months

Alexandre Julliard : server: Avoid some compiler warnings when EWOULDBLOCK == EAGAIN.

by Alexandre Julliard

Module: wine Branch: master Commit: 438dae524d9410f571f7fe5cc335fb74fec8d2bb URL: http://source.winehq.org/git/wine.git/?a=commit;h=438dae524d9410f571f7fe5cc… Author: Alexandre Julliard <julliard(a)winehq.org> Date: Tue Aug 30 19:08:23 2016 +0900 server: Avoid some compiler warnings when EWOULDBLOCK == EAGAIN. Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- server/request.c | 6 +++--- server/sock.c | 4 ++-- 2 files changed, 5 insertions(+), 5 deletions(-) diff --git a/server/request.c b/server/request.c index 597bf88..b937e6f 100644 --- a/server/request.c +++ b/server/request.c @@ -241,7 +241,7 @@ void write_reply( struct thread *thread ) } if (errno == EPIPE) kill_thread( thread, 0 ); /* normal death */ - else if (errno != EWOULDBLOCK && errno != EAGAIN) + else if (errno != EWOULDBLOCK && (EWOULDBLOCK == EAGAIN || errno != EAGAIN)) fatal_protocol_error( thread, "reply write: %s\n", strerror( errno )); } @@ -368,7 +368,7 @@ error: kill_thread( thread, 0 ); else if (ret > 0) fatal_protocol_error( thread, "partial read %d\n", ret ); - else if (errno != EWOULDBLOCK && errno != EAGAIN) + else if (errno != EWOULDBLOCK && (EWOULDBLOCK == EAGAIN || errno != EAGAIN)) fatal_protocol_error( thread, "read: %s\n", strerror( errno )); } @@ -449,7 +449,7 @@ int receive_fd( struct process *process ) } else { - if (errno != EWOULDBLOCK && errno != EAGAIN) + if (errno != EWOULDBLOCK && (EWOULDBLOCK == EAGAIN || errno != EAGAIN)) { fprintf( stderr, "Protocol error: process %04x: ", process->id ); perror( "recvmsg" ); diff --git a/server/sock.c b/server/sock.c index dc10d2a..89049e0 100644 --- a/server/sock.c +++ b/server/sock.c @@ -1075,8 +1075,8 @@ static void ifchange_poll_event( struct fd *fd, int event ) r = recv( get_unix_fd(fd), buffer, sizeof(buffer), MSG_DONTWAIT ); if (r < 0) { - if (errno == EWOULDBLOCK || errno == EAGAIN) - return; /* retry when poll() says the socket is ready */ + if (errno == EWOULDBLOCK || (EWOULDBLOCK != EAGAIN && errno == EAGAIN)) + return; /* retry when poll() says the socket is ready */ status = sock_get_ntstatus( errno ); } else if (r > 0)

7 years, 8 months

Alexandre Julliard : server: Add a helper function to validate a window handle.

by Alexandre Julliard

Module: wine Branch: master Commit: 70dd64cf9799c0dd5cae867250c8f7fb7a360ace URL: http://source.winehq.org/git/wine.git/?a=commit;h=70dd64cf9799c0dd5cae86725… Author: Alexandre Julliard <julliard(a)winehq.org> Date: Tue Aug 30 18:08:36 2016 +0900 server: Add a helper function to validate a window handle. Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- server/clipboard.c | 42 +++++++++--------------------------------- server/queue.c | 6 ++---- server/user.h | 8 ++++++++ 3 files changed, 19 insertions(+), 37 deletions(-) diff --git a/server/clipboard.c b/server/clipboard.c index f640b50..a9bbaec 100644 --- a/server/clipboard.c +++ b/server/clipboard.c @@ -258,15 +258,11 @@ static int get_seqno( struct clipboard *clipboard ) DECL_HANDLER(open_clipboard) { struct clipboard *clipboard = get_process_clipboard(); - user_handle_t win = req->window; + user_handle_t win = 0; if (!clipboard) return; + if (req->window && !(win = get_valid_window_handle( req->window ))) return; - if (win && !get_user_object_handle( &win, USER_WINDOW )) - { - set_win32_error( ERROR_INVALID_WINDOW_HANDLE ); - return; - } if (clipboard->open_thread && clipboard->open_win != win) { set_error( STATUS_INVALID_LOCK_SEQUENCE ); @@ -363,21 +359,11 @@ DECL_HANDLER(get_clipboard_info) DECL_HANDLER(set_clipboard_viewer) { struct clipboard *clipboard = get_process_clipboard(); - user_handle_t viewer = req->viewer; - user_handle_t previous = req->previous; + user_handle_t viewer = 0, previous = 0; if (!clipboard) return; - - if (viewer && !get_user_object_handle( &viewer, USER_WINDOW )) - { - set_win32_error( ERROR_INVALID_WINDOW_HANDLE ); - return; - } - if (previous && !get_user_object_handle( &previous, USER_WINDOW )) - { - set_win32_error( ERROR_INVALID_WINDOW_HANDLE ); - return; - } + if (req->viewer && !(viewer = get_valid_window_handle( req->viewer ))) return; + if (req->previous && !(previous = get_valid_window_handle( req->previous ))) return; reply->old_viewer = clipboard->viewer; reply->owner = clipboard->owner_win; @@ -393,15 +379,10 @@ DECL_HANDLER(set_clipboard_viewer) DECL_HANDLER(add_clipboard_listener) { struct clipboard *clipboard = get_process_clipboard(); - user_handle_t win = req->window; + user_handle_t win; if (!clipboard) return; - - if (!get_user_object_handle( &win, USER_WINDOW )) - { - set_win32_error( ERROR_INVALID_WINDOW_HANDLE ); - return; - } + if (!(win = get_valid_window_handle( req->window ))) return; add_listener( clipboard, win ); } @@ -411,15 +392,10 @@ DECL_HANDLER(add_clipboard_listener) DECL_HANDLER(remove_clipboard_listener) { struct clipboard *clipboard = get_process_clipboard(); - user_handle_t win = req->window; + user_handle_t win; if (!clipboard) return; - - if (!get_user_object_handle( &win, USER_WINDOW )) - { - set_win32_error( ERROR_INVALID_WINDOW_HANDLE ); - return; - } + if (!(win = get_valid_window_handle( req->window ))) return; if (!remove_listener( clipboard, win )) set_error( STATUS_INVALID_PARAMETER ); } diff --git a/server/queue.c b/server/queue.c index 387c652..c479b38 100644 --- a/server/queue.c +++ b/server/queue.c @@ -2685,10 +2685,9 @@ DECL_HANDLER(register_hotkey) if (win_handle) { - if (!get_user_object_handle( &win_handle, USER_WINDOW )) + if (!(win_handle = get_valid_window_handle( win_handle ))) { release_object( desktop ); - set_win32_error( ERROR_INVALID_WINDOW_HANDLE ); return; } @@ -2754,10 +2753,9 @@ DECL_HANDLER(unregister_hotkey) if (win_handle) { - if (!get_user_object_handle( &win_handle, USER_WINDOW )) + if (!(win_handle = get_valid_window_handle( win_handle ))) { release_object( desktop ); - set_win32_error( ERROR_INVALID_WINDOW_HANDLE ); return; } diff --git a/server/user.h b/server/user.h index ad62b7d..e7eecd4 100644 --- a/server/user.h +++ b/server/user.h @@ -207,4 +207,12 @@ static inline int intersect_rect( rectangle_t *dst, const rectangle_t *src1, con return (dst->left < dst->right && dst->top < dst->bottom); } +/* validate a window handle and return the full handle */ +static inline user_handle_t get_valid_window_handle( user_handle_t win ) +{ + if (get_user_object_handle( &win, USER_WINDOW )) return win; + set_win32_error( ERROR_INVALID_WINDOW_HANDLE ); + return 0; +} + #endif /* __WINE_SERVER_USER_H */

7 years, 8 months

Alexandre Julliard : server: Notify all listeners when the contents of the clipboard have changed.

by Alexandre Julliard

Module: wine Branch: master Commit: c6f12bd9ccd048e27d145371537111935b230242 URL: http://source.winehq.org/git/wine.git/?a=commit;h=c6f12bd9ccd048e27d1453715… Author: Alexandre Julliard <julliard(a)winehq.org> Date: Tue Aug 30 16:33:04 2016 +0900 server: Notify all listeners when the contents of the clipboard have changed. Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- dlls/user32/clipboard.c | 2 +- dlls/user32/tests/clipboard.c | 207 +++++++++++++++++++++++++++++++++++++----- server/clipboard.c | 46 +++++++--- server/queue.c | 27 ++++++ server/user.h | 2 + 5 files changed, 245 insertions(+), 39 deletions(-) Diff: http://source.winehq.org/git/wine.git/?a=commitdiff;h=c6f12bd9ccd048e27d145…

7 years, 8 months

Alexandre Julliard : user32: Fix InSendMessage return value.

by Alexandre Julliard

Module: wine Branch: master Commit: 7594afeb6cf30228e551155a4b4ac636950cd942 URL: http://source.winehq.org/git/wine.git/?a=commit;h=7594afeb6cf30228e551155a4… Author: Alexandre Julliard <julliard(a)winehq.org> Date: Tue Aug 30 14:38:15 2016 +0900 user32: Fix InSendMessage return value. Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- dlls/user32/message.c | 2 +- dlls/user32/tests/msg.c | 93 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 94 insertions(+), 1 deletion(-) diff --git a/dlls/user32/message.c b/dlls/user32/message.c index bc6b661..9bfb453 100644 --- a/dlls/user32/message.c +++ b/dlls/user32/message.c @@ -3612,7 +3612,7 @@ BOOL WINAPI ReplyMessage( LRESULT result ) */ BOOL WINAPI InSendMessage(void) { - return (InSendMessageEx(NULL) & (ISMEX_SEND|ISMEX_REPLIED)) == ISMEX_SEND; + return (InSendMessageEx( NULL ) & (ISMEX_SEND | ISMEX_NOTIFY | ISMEX_CALLBACK)) != 0; } diff --git a/dlls/user32/tests/msg.c b/dlls/user32/tests/msg.c index 9dc1120..ebd1c45 100644 --- a/dlls/user32/tests/msg.c +++ b/dlls/user32/tests/msg.c @@ -15822,6 +15822,98 @@ todo_wine_if (thread_n == 2) flush_sequence(); } +static LRESULT CALLBACK insendmessage_wnd_proc( HWND hwnd, UINT msg, WPARAM wp, LPARAM lp ) +{ + DWORD flags = InSendMessageEx( NULL ); + BOOL ret; + + switch (msg) + { + case WM_USER: + ok( flags == ISMEX_SEND, "wrong flags %x\n", flags ); + ok( InSendMessage(), "InSendMessage returned false\n" ); + ret = ReplyMessage( msg ); + ok( ret, "ReplyMessage failed err %u\n", GetLastError() ); + flags = InSendMessageEx( NULL ); + ok( flags == (ISMEX_SEND | ISMEX_REPLIED), "wrong flags %x\n", flags ); + ok( InSendMessage(), "InSendMessage returned false\n" ); + break; + case WM_USER + 1: + ok( flags == ISMEX_NOTIFY, "wrong flags %x\n", flags ); + ok( InSendMessage(), "InSendMessage returned false\n" ); + ret = ReplyMessage( msg ); + ok( ret, "ReplyMessage failed err %u\n", GetLastError() ); + flags = InSendMessageEx( NULL ); + ok( flags == ISMEX_NOTIFY, "wrong flags %x\n", flags ); + ok( InSendMessage(), "InSendMessage returned false\n" ); + break; + case WM_USER + 2: + ok( flags == ISMEX_CALLBACK, "wrong flags %x\n", flags ); + ok( InSendMessage(), "InSendMessage returned false\n" ); + ret = ReplyMessage( msg ); + ok( ret, "ReplyMessage failed err %u\n", GetLastError() ); + flags = InSendMessageEx( NULL ); + ok( flags == (ISMEX_CALLBACK | ISMEX_REPLIED) || flags == ISMEX_SEND, "wrong flags %x\n", flags ); + ok( InSendMessage(), "InSendMessage returned false\n" ); + break; + case WM_USER + 3: + ok( flags == ISMEX_NOSEND, "wrong flags %x\n", flags ); + ok( !InSendMessage(), "InSendMessage returned true\n" ); + ret = ReplyMessage( msg ); + ok( !ret, "ReplyMessage succeeded\n" ); + break; + } + + return DefWindowProcA( hwnd, msg, wp, lp ); +} + +static void CALLBACK msg_callback( HWND hwnd, UINT msg, ULONG_PTR arg, LRESULT result ) +{ + ok( msg == WM_USER + 2, "wrong msg %x\n", msg ); + ok( result == WM_USER + 2, "wrong result %lx\n", result ); +} + +static DWORD WINAPI send_message_thread( void *arg ) +{ + HWND win = arg; + + SendMessageA( win, WM_USER, 0, 0 ); + SendNotifyMessageA( win, WM_USER + 1, 0, 0 ); + SendMessageCallbackA( win, WM_USER + 2, 0, 0, msg_callback, 0 ); + PostMessageA( win, WM_USER + 3, 0, 0 ); + PostMessageA( win, WM_QUIT, 0, 0 ); + return 0; +} + +static void test_InSendMessage(void) +{ + WNDCLASSA cls; + HWND win; + MSG msg; + HANDLE thread; + DWORD tid; + + memset(&cls, 0, sizeof(cls)); + cls.lpfnWndProc = insendmessage_wnd_proc; + cls.hInstance = GetModuleHandleA(NULL); + cls.lpszClassName = "InSendMessage_test"; + RegisterClassA(&cls); + + win = CreateWindowA( "InSendMessage_test", NULL, 0, 0, 0, 0, 0, NULL, 0, NULL, 0 ); + ok( win != NULL, "CreateWindow failed: %d\n", GetLastError() ); + + thread = CreateThread( NULL, 0, send_message_thread, win, 0, &tid ); + ok( thread != NULL, "CreateThread failed: %d\n", GetLastError() ); + + while (GetMessageA(&msg, NULL, 0, 0)) DispatchMessageA( &msg ); + + ok( WaitForSingleObject( thread, 30000 ) == WAIT_OBJECT_0, "WaitForSingleObject failed\n" ); + CloseHandle( thread ); + + DestroyWindow( win ); + UnregisterClassA( "InSendMessage_test", GetModuleHandleA(NULL) ); +} + static const struct message DoubleSetCaptureSeq[] = { { WM_CAPTURECHANGED, sent }, @@ -15930,6 +16022,7 @@ START_TEST(msg) test_SendMessage_other_thread(1); test_SendMessage_other_thread(2); + test_InSendMessage(); test_SetFocus(); test_SetParent(); test_PostMessage();

7 years, 8 months

Jacek Caban : rbtree.h: Get rid of no longer needed wine_rb_stack.

by Alexandre Julliard

Module: wine Branch: master Commit: 69f571dbebeae3ade039e659165855ddcfc74ded URL: http://source.winehq.org/git/wine.git/?a=commit;h=69f571dbebeae3ade039e6591… Author: Jacek Caban <jacek(a)codeweavers.com> Date: Mon Aug 15 21:54:20 2016 +0200 rbtree.h: Get rid of no longer needed wine_rb_stack. Signed-off-by: Jacek Caban <jacek(a)codeweavers.com> Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- include/wine/rbtree.h | 45 +-------------------------------------------- 1 file changed, 1 insertion(+), 44 deletions(-) diff --git a/include/wine/rbtree.h b/include/wine/rbtree.h index 361766c..f13592e 100644 --- a/include/wine/rbtree.h +++ b/include/wine/rbtree.h @@ -3,6 +3,7 @@ * * Copyright 2009 Henri Verbeet * Copyright 2009 Andrew Riedi + * Copyright 2016 Jacek Caban for CodeWeavers * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -33,13 +34,6 @@ struct wine_rb_entry unsigned int flags; }; -struct wine_rb_stack -{ - struct wine_rb_entry ***entries; - size_t count; - size_t size; -}; - struct wine_rb_functions { void *(*alloc)(size_t size); @@ -52,42 +46,11 @@ struct wine_rb_tree { const struct wine_rb_functions *functions; struct wine_rb_entry *root; - struct wine_rb_stack stack; }; typedef void (wine_rb_traverse_func_t)(struct wine_rb_entry *entry, void *context); #define WINE_RB_FLAG_RED 0x1 -#define WINE_RB_FLAG_STOP 0x2 - -static inline void wine_rb_stack_clear(struct wine_rb_stack *stack) -{ - stack->count = 0; -} - -static inline void wine_rb_stack_push(struct wine_rb_stack *stack, struct wine_rb_entry **entry) -{ - stack->entries[stack->count++] = entry; -} - -static inline int wine_rb_ensure_stack_size(struct wine_rb_tree *tree, size_t size) -{ - struct wine_rb_stack *stack = &tree->stack; - - if (size > stack->size) - { - size_t new_size = stack->size << 1; - struct wine_rb_entry ***new_entries = tree->functions->realloc(stack->entries, - new_size * sizeof(*stack->entries)); - - if (!new_entries) return -1; - - stack->entries = new_entries; - stack->size = new_size; - } - - return 0; -} static inline int wine_rb_is_red(struct wine_rb_entry *entry) { @@ -171,11 +134,6 @@ static inline int wine_rb_init(struct wine_rb_tree *tree, const struct wine_rb_f tree->functions = functions; tree->root = NULL; - tree->stack.entries = functions->alloc(16 * sizeof(*tree->stack.entries)); - if (!tree->stack.entries) return -1; - tree->stack.size = 16; - tree->stack.count = 0; - return 0; } @@ -194,7 +152,6 @@ static inline void wine_rb_clear(struct wine_rb_tree *tree, wine_rb_traverse_fun static inline void wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context) { wine_rb_clear(tree, callback, context); - tree->functions->free(tree->stack.entries); } static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key)

7 years, 8 months

Jacek Caban : rbtree.h: Rewrite wine_rb_put to use parent pointers instead of stack.

by Alexandre Julliard

Module: wine Branch: master Commit: e3a19d3b2f512fa9aa8e27c708408dc8fc39af36 URL: http://source.winehq.org/git/wine.git/?a=commit;h=e3a19d3b2f512fa9aa8e27c70… Author: Jacek Caban <jacek(a)codeweavers.com> Date: Mon Aug 15 21:54:08 2016 +0200 rbtree.h: Rewrite wine_rb_put 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 | 108 ++++++++++++++++++++++++-------------------------- 1 file changed, 51 insertions(+), 57 deletions(-) diff --git a/include/wine/rbtree.h b/include/wine/rbtree.h index a549a87..361766c 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, int change_color) +static inline void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e) { struct wine_rb_entry *right = e->right; @@ -110,15 +110,9 @@ 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; - 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, int change_color) +static inline void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e) { struct wine_rb_entry *left = e->left; @@ -134,12 +128,6 @@ 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; - 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) @@ -149,25 +137,6 @@ 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_tree *tree, struct wine_rb_stack *stack) -{ - while (stack->count) - { - struct wine_rb_entry **entry = stack->entries[stack->count - 1]; - - if ((*entry)->flags & WINE_RB_FLAG_STOP) - { - (*entry)->flags &= ~WINE_RB_FLAG_STOP; - return; - } - - 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 struct wine_rb_entry *wine_rb_postorder_head(struct wine_rb_entry *iter) { if (!iter) return NULL; @@ -243,41 +212,66 @@ 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 **iter = &tree->root, *parent = tree->root; - size_t black_height = 1; while (*iter) { int c; - if (!wine_rb_is_red(*iter)) ++black_height; - - wine_rb_stack_push(&tree->stack, iter); - parent = *iter; c = tree->functions->compare(key, parent); - if (!c) - { - wine_rb_stack_clear(&tree->stack); - return -1; - } + if (!c) return -1; 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. */ - if (wine_rb_ensure_stack_size(tree, black_height << 1) == -1) - { - wine_rb_stack_clear(&tree->stack); - return -1; - } - entry->flags = WINE_RB_FLAG_RED; entry->parent = parent; entry->left = NULL; entry->right = NULL; *iter = entry; - wine_rb_fixup(tree, &tree->stack); + while (wine_rb_is_red(entry->parent)) + { + if (entry->parent == entry->parent->parent->left) + { + if (wine_rb_is_red(entry->parent->parent->right)) + { + wine_rb_flip_color(entry->parent->parent); + entry = entry->parent->parent; + } + else + { + if (entry == entry->parent->right) + { + entry = entry->parent; + wine_rb_rotate_left(tree, entry); + } + entry->parent->flags &= ~WINE_RB_FLAG_RED; + entry->parent->parent->flags |= WINE_RB_FLAG_RED; + wine_rb_rotate_right(tree, entry->parent->parent); + } + } + else + { + if (wine_rb_is_red(entry->parent->parent->left)) + { + wine_rb_flip_color(entry->parent->parent); + entry = entry->parent->parent; + } + else + { + if (entry == entry->parent->left) + { + entry = entry->parent; + wine_rb_rotate_right(tree, entry); + } + entry->parent->flags &= ~WINE_RB_FLAG_RED; + entry->parent->parent->flags |= WINE_RB_FLAG_RED; + wine_rb_rotate_left(tree, entry->parent->parent); + } + } + } + tree->root->flags &= ~WINE_RB_FLAG_RED; return 0; @@ -335,7 +329,7 @@ static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key) { w->flags &= ~WINE_RB_FLAG_RED; parent->flags |= WINE_RB_FLAG_RED; - wine_rb_rotate_left(tree, parent, 0); + wine_rb_rotate_left(tree, parent); w = parent->right; } if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right)) @@ -344,14 +338,14 @@ static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key) { w->left->flags &= ~WINE_RB_FLAG_RED; w->flags |= WINE_RB_FLAG_RED; - wine_rb_rotate_right(tree, w, 0); + wine_rb_rotate_right(tree, w); 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); + wine_rb_rotate_left(tree, parent); child = NULL; break; } @@ -363,7 +357,7 @@ static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key) { w->flags &= ~WINE_RB_FLAG_RED; parent->flags |= WINE_RB_FLAG_RED; - wine_rb_rotate_right(tree, parent, 0); + wine_rb_rotate_right(tree, parent); w = parent->left; } if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right)) @@ -372,14 +366,14 @@ static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key) { w->right->flags &= ~WINE_RB_FLAG_RED; w->flags |= WINE_RB_FLAG_RED; - wine_rb_rotate_left(tree, w, 0); + wine_rb_rotate_left(tree, w); 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); + wine_rb_rotate_right(tree, parent); child = NULL; break; }

7 years, 8 months

Jacek Caban : rbtree.h: Rewrite wine_rb_remove to use parent pointers instead of stack.

by Alexandre Julliard

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; }

7 years, 8 months

Jacek Caban : rbtree.h: Use parent pointer instead of stack in wine_rb_postorder.

by Alexandre Julliard

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); } }

7 years, 8 months

← Newer
1
2
3
4
5
6
7
...
78
Older →

Jump to page:

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

wine-commits August 2016