/*
* Red-black search tree support
*
* Copyright 2009 Henri Verbeet
* Copyright 2009 Andrew Riedi
*
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library 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
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
*/
/*
* Oracle LGPL Disclaimer: For the avoidance of doubt, except that if any license choice
* other than GPL or LGPL is available it will apply instead, Oracle elects to use only
* the Lesser General Public License version 2.1 (LGPLv2) at this time for any software where
* a choice of LGPL license versions is made available with the language indicating
* that LGPLv2 or any later version may be used, or where a choice of which version
* of the LGPL is applied is otherwise unspecified.
*/
#ifndef __WINE_WINE_RBTREE_H
#define __WINE_WINE_RBTREE_H
struct wine_rb_entry
{
unsigned int flags;
};
struct wine_rb_stack
{
};
struct wine_rb_functions
{
};
struct wine_rb_tree
{
};
{
}
{
}
{
{
if (!new_entries) return -1;
}
return 0;
}
{
}
{
struct wine_rb_entry *e = *entry;
e->flags |= WINE_RB_FLAG_RED;
}
{
struct wine_rb_entry *e = *entry;
e->flags |= WINE_RB_FLAG_RED;
}
{
}
{
{
{
return;
}
if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->left->left)) wine_rb_rotate_right(entry);
}
}
{
{
}
}
{
{
}
}
static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
{
{
struct wine_rb_entry *e = *entry;
{
e->flags |= WINE_RB_FLAG_TRAVERSED_LEFT;
continue;
}
{
continue;
}
}
}
static inline int wine_rb_init(struct wine_rb_tree *tree, const struct wine_rb_functions *functions)
{
return 0;
}
static inline void wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
{
}
static inline void wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
{
/* Note that we use postorder here because the callback will likely free the entry. */
}
{
while (entry)
{
if (!c) return entry;
}
return NULL;
}
static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
{
while (*parent)
{
int c;
if (!c)
{
return -1;
}
}
/* After insertion, the path length to any node should be <= (black_height + 1) * 2. */
{
return -1;
}
return 0;
}
{
while (*entry)
{
{
if (!wine_rb_is_red((*entry)->left) && !wine_rb_is_red((*entry)->left->left)) wine_rb_move_red_left(entry);
}
else
{
{
break;
}
{
struct wine_rb_entry *m = *e;
while ((*e)->left)
{
e = &(*e)->left;
}
*e = NULL;
*m = **entry;
*entry = m;
break;
}
else
{
}
}
}
}
#endif /* __WINE_WINE_RBTREE_H */