On 26 March 2014, LCD 47 <[email protected]> wrote:
[...]
> FWIW, I have a preliminary implementation, and I ran a few
> benchmarks. Here are few numbers:
[...]
Patch attached below. The patch adds an optional parameter {mode}
to uniq():
uniq({list} [, {mode} [, {func} [, {dict}]]])
If {mode} is absent, or if it is set to "sorted", uniq() removes
only consecutive dupes; if {mode} is set to "stable", uniq() removes all
dupes without changing the order of the items in {list}.
Sadly, the new syntax can't be backwards compatible while still
remaining useful.
If you're curious about the numbers I mentioned in my previous
message, I also attached a small benchmark script. You need +python to
run it (Python is used only to generate 1 mil. of random numbers).
Several obvious improvements are possible, f.i. better checks for
sys/tree.h, or perhaps re-implementing outside sys/tree.h the few
functions for red-black trees that we're actually using. Given the
reactions so far to all this, I'll leave the pleasure of implementing
those improvements to somebody else.
/lcd
--
--
You received this message from the "vim_dev" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php
---
You received this message because you are subscribed to the Google Groups
"vim_dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
diff -r d96e8fbc3747 runtime/doc/eval.txt
--- a/runtime/doc/eval.txt Tue Mar 25 18:24:23 2014 +0100
+++ b/runtime/doc/eval.txt Wed Mar 26 19:57:07 2014 +0200
@@ -2006,7 +2006,7 @@
type( {name}) Number type of variable {name}
undofile( {name}) String undo file name for {name}
undotree() List undo file tree
-uniq( {list} [, {func} [, {dict}]])
+uniq( {list} [, {mode} [, {func} [, {dict}]]])
List remove adjacent duplicates from a list
values( {dict}) List values in {dict}
virtcol( {expr}) Number screen column of cursor or mark
@@ -5978,7 +5978,7 @@
The number can be used with the |:tab| command.
-tabpagewinnr({tabarg}, [{arg}]) *tabpagewinnr()*
+tabpagewinnr({tabarg}[, {arg}]) *tabpagewinnr()*
Like |winnr()| but for tab page {tabarg}.
{tabarg} specifies the number of tab page to be used.
{arg} is used like with |winnr()|:
@@ -5996,7 +5996,7 @@
for the current buffer. This is the 'tags' option expanded.
-taglist({expr})
*taglist()*
+taglist({expr}) *taglist()*
Returns a list of tags matching the regular expression {expr}.
Each list item is a dictionary with at least the following
entries:
@@ -6178,10 +6178,14 @@
blocks. Each item may again have an "alt"
item.
-uniq({list} [, {func} [, {dict}]]) *uniq()* *E882*
- Remove second and succeeding copies of repeated adjacent
- {list} items in-place. Returns {list}. If you want a list
- to remain unmodified make a copy first: >
+uniq({list} [, {mode} [, {func} [, {dict}]]]) *uniq()* *E882*
+ Eliminate duplicates from {list}. If {mode} is absent, or if
+ it is set to "sorted", remove second and succeeding copies of
+ repeated adjacent {list} items. If {mode} is set to "stable",
+ remove second and succeeding copies of {list} items, regardless
+ of whether they are adjacent or not. The operation is done
+ in-place. If you want the |List| to remain unmodified make a
+ copy first: >
:let newlist = uniq(copy(mylist))
< The default compare function uses the string representation of
each item. For the use of {func} and {dict} see |sort()|.
diff -r d96e8fbc3747 src/config.h.in
--- a/src/config.h.in Tue Mar 25 18:24:23 2014 +0100
+++ b/src/config.h.in Wed Mar 26 19:57:07 2014 +0200
@@ -258,6 +258,7 @@
#undef HAVE_SYS_SYSINFO_H
#undef HAVE_SYS_SYSTEMINFO_H
#undef HAVE_SYS_TIME_H
+#undef HAVE_SYS_TREE_H
#undef HAVE_SYS_TYPES_H
#undef HAVE_SYS_UTSNAME_H
#undef HAVE_TERMCAP_H
diff -r d96e8fbc3747 src/configure.in
--- a/src/configure.in Tue Mar 25 18:24:23 2014 +0100
+++ b/src/configure.in Wed Mar 26 19:57:07 2014 +0200
@@ -2797,7 +2797,8 @@
libc.h sys/statfs.h poll.h sys/poll.h pwd.h \
utime.h sys/param.h libintl.h libgen.h \
util/debug.h util/msg18n.h frame.h sys/acl.h \
- sys/access.h sys/sysinfo.h wchar.h wctype.h)
+ sys/access.h sys/sysinfo.h wchar.h wctype.h \
+ sys/tree.h)
dnl sys/ptem.h depends on sys/stream.h on Solaris
AC_CHECK_HEADERS(sys/ptem.h, [], [],
diff -r d96e8fbc3747 src/eval.c
--- a/src/eval.c Tue Mar 25 18:24:23 2014 +0100
+++ b/src/eval.c Wed Mar 26 19:57:07 2014 +0200
@@ -31,6 +31,12 @@
# include <math.h>
#endif
+#if defined(HAVE_SYS_TREE_H)
+# include <sys/tree.h>
+#else
+# include "sys_tree.h"
+#endif
+
#define DICT_MAXNEST 100 /* maximum nesting of lists and dicts */
#define DO_NOT_FREE_CNT 99999 /* refcount for dict or list that should not
@@ -374,6 +380,19 @@
static dictitem_T vimvars_var; /* variable used for v: */
#define vimvarht vimvardict.dv_hashtab
+/* modes for uniq() */
+#define UNIQ_SORTED 0
+#define UNIQ_STABLE 1
+
+struct rbnode_S {
+ RB_ENTRY(rbnode_S) entry;
+ listitem_T *item;
+};
+
+typedef struct rbnode_S rbnode_T;
+
+RB_HEAD(rbtree_S, rbnode_S);
+
static void prepare_vimvar __ARGS((int idx, typval_T *save_tv));
static void restore_vimvar __ARGS((int idx, typval_T *save_tv));
static int ex_let_vars __ARGS((char_u *arg, typval_T *tv, int copy, int
semicolon, int var_count, char_u *nextchars));
@@ -8151,7 +8170,7 @@
{"type", 1, 1, f_type},
{"undofile", 1, 1, f_undofile},
{"undotree", 0, 0, f_undotree},
- {"uniq", 1, 3, f_uniq},
+ {"uniq", 1, 4, f_uniq},
{"values", 1, 1, f_values},
{"virtcol", 1, 1, f_virtcol},
{"visualmode", 0, 1, f_visualmode},
@@ -17025,7 +17044,7 @@
static char_u *item_compare_func;
static dict_T *item_compare_selfdict;
static int item_compare_func_err;
-static void do_sort_uniq __ARGS((typval_T *argvars, typval_T *rettv, int
sort));
+static int (*item_compare_func_ptr)__ARGS((const void *, const void *));
#define ITEM_COMPARE_FAIL 999
/*
@@ -17099,14 +17118,25 @@
return res;
}
+ static int
+#ifdef __BORLANDC__
+_RTLENTRYF
+#endif
+rbnode_compare(s1, s2)
+ rbnode_T *s1;
+ rbnode_T *s2;
+{
+ return item_compare_func_ptr((void *)&s1->item, (void *)&s2->item);
+}
+RB_GENERATE(rbtree_S, rbnode_S, entry, rbnode_compare);
+
/*
* "sort({list})" function
*/
static void
-do_sort_uniq(argvars, rettv, sort)
- typval_T *argvars;
- typval_T *rettv;
- int sort;
+f_sort(argvars, rettv)
+ typval_T *argvars;
+ typval_T *rettv;
{
list_T *l;
listitem_T *li;
@@ -17115,12 +17145,12 @@
long i;
if (argvars[0].v_type != VAR_LIST)
- EMSG2(_(e_listarg), sort ? "sort()" : "uniq()");
+ EMSG2(_(e_listarg), "sort()");
else
{
l = argvars[0].vval.v_list;
if (l == NULL || tv_check_lock(l->lv_lock,
- (char_u *)(sort ? _("sort() argument") : _("uniq() argument"))))
+ (char_u *)(_("sort() argument"))))
return;
rettv->vval.v_list = l;
rettv->v_type = VAR_LIST;
@@ -17169,70 +17199,193 @@
return;
i = 0;
- if (sort)
- {
- /* sort(): ptrs will be the list to sort */
+ /* ptrs will be the list to sort */
+ for (li = l->lv_first; li != NULL; li = li->li_next)
+ ptrs[i++] = li;
+
+ item_compare_func_err = FALSE;
+ /* test the compare function */
+ if (item_compare_func != NULL
+ && item_compare2((void *)&ptrs[0], (void *)&ptrs[1])
+ == ITEM_COMPARE_FAIL)
+ EMSG(_("E702: Sort compare function failed"));
+ else
+ {
+ /* Sort the array with item pointers. */
+ qsort((void *)ptrs, (size_t)len, sizeof(listitem_T *),
+ item_compare_func == NULL ? item_compare : item_compare2);
+
+ if (!item_compare_func_err)
+ {
+ /* Clear the List and append the items in sorted order. */
+ l->lv_first = l->lv_last = l->lv_idx_item = NULL;
+ l->lv_len = 0;
+ for (i = 0; i < len; ++i)
+ list_append(l, ptrs[i]);
+ }
+ }
+
+ vim_free(ptrs);
+ }
+}
+
+/*
+ * "uniq({list})" function
+ */
+ static void
+f_uniq(argvars, rettv)
+ typval_T *argvars;
+ typval_T *rettv;
+{
+ list_T *l;
+ listitem_T *li;
+ listitem_T **ptrs;
+ char_u *mode_name;
+ long len;
+ long i;
+ int ptrs_count, pool_count;
+ int mode;
+
+ if (argvars[0].v_type != VAR_LIST)
+ EMSG2(_(e_listarg), "uniq()");
+ else
+ {
+ l = argvars[0].vval.v_list;
+ if (l == NULL || tv_check_lock(l->lv_lock,
+ (char_u *)(_("uniq() argument"))))
+ return;
+ rettv->vval.v_list = l;
+ rettv->v_type = VAR_LIST;
+ ++l->lv_refcount;
+
+ len = list_len(l);
+ if (len <= 1)
+ return; /* short list sorts pretty quickly */
+
+ mode = UNIQ_SORTED;
+ item_compare_ic = FALSE;
+ item_compare_func = NULL;
+ item_compare_selfdict = NULL;
+ if (argvars[1].v_type != VAR_UNKNOWN)
+ {
+ /* optional second argument: {mode} */
+ if (argvars[1].v_type == VAR_STRING)
+ {
+ mode_name = get_tv_string(&argvars[1]);
+
+ if (STRCMP(mode_name, "sorted") == 0)
+ mode = UNIQ_SORTED;
+ else if (STRCMP(mode_name, "stable") == 0)
+ mode = UNIQ_STABLE;
+ else
+ {
+ EMSG(_("E116: Invalid arguments for function uniq()"));
+ return;
+ }
+ }
+ else
+ {
+ EMSG(_("E116: Invalid arguments for function uniq()"));
+ return;
+ }
+
+ /* optional third argument: {func} */
+ if (argvars[2].v_type != VAR_UNKNOWN)
+ {
+ if (argvars[2].v_type == VAR_FUNC)
+ item_compare_func = argvars[2].vval.v_string;
+ else
+ {
+ int error = FALSE;
+
+ i = get_tv_number_chk(&argvars[2], &error);
+ if (error)
+ return; /* type error; errmsg already given */
+ if (i == 1)
+ item_compare_ic = TRUE;
+ else
+ item_compare_func = get_tv_string(&argvars[2]);
+ }
+
+ if (argvars[3].v_type != VAR_UNKNOWN)
+ {
+ /* optional fourth argument: {dict} */
+ if (argvars[3].v_type != VAR_DICT)
+ {
+ EMSG(_(e_dictreq));
+ return;
+ }
+ item_compare_selfdict = argvars[3].vval.v_dict;
+ }
+ }
+ }
+
+ /* ptrs will be a stack of items to remove */
+ ptrs = (listitem_T **)alloc((int)((len - 1) * sizeof(listitem_T *)));
+ if (ptrs == NULL)
+ return;
+ ptrs_count = 0;
+
+ item_compare_func_err = FALSE;
+ item_compare_func_ptr = item_compare_func ? item_compare2 :
item_compare;
+ if (mode == UNIQ_STABLE)
+ {
+ struct rbtree_S rbtree;
+ rbnode_T *pool = (rbnode_T *)alloc((int)(len * sizeof(rbnode_T)));
+
+ RB_INIT(&rbtree);
+
+ /* rbtree node wrappers around the items of the list to process */
+ pool_count = 0;
for (li = l->lv_first; li != NULL; li = li->li_next)
- ptrs[i++] = li;
-
- item_compare_func_err = FALSE;
- /* test the compare function */
- if (item_compare_func != NULL
- && item_compare2((void *)&ptrs[0], (void *)&ptrs[1])
- == ITEM_COMPARE_FAIL)
- EMSG(_("E702: Sort compare function failed"));
- else
- {
- /* Sort the array with item pointers. */
- qsort((void *)ptrs, (size_t)len, sizeof(listitem_T *),
- item_compare_func == NULL ? item_compare : item_compare2);
-
- if (!item_compare_func_err)
- {
- /* Clear the List and append the items in sorted order. */
- l->lv_first = l->lv_last = l->lv_idx_item = NULL;
- l->lv_len = 0;
- for (i = 0; i < len; ++i)
- list_append(l, ptrs[i]);
- }
- }
- }
- else
- {
- int (*item_compare_func_ptr)__ARGS((const void *, const void *));
-
- /* f_uniq(): ptrs will be a stack of items to remove */
- item_compare_func_err = FALSE;
- item_compare_func_ptr = item_compare_func
- ? item_compare2 : item_compare;
+ pool[pool_count++].item = li;
+
+ RB_INSERT(rbtree_S, &rbtree, pool);
+ pool_count = 1;
for (li = l->lv_first; li != NULL && li->li_next != NULL;
- li = li->li_next)
+ li =
li->li_next)
+ {
+ if (RB_INSERT(rbtree_S, &rbtree, pool + pool_count++) != NULL)
+ ptrs[ptrs_count++] = li;
+ if (item_compare_func_err)
+ {
+ EMSG(_("E882: Uniq compare function failed"));
+ break;
+ }
+ }
+
+ vim_free(pool);
+ }
+ else
+ {
+ for (li = l->lv_first; li != NULL && li->li_next != NULL;
+ li =
li->li_next)
{
if (item_compare_func_ptr((void *)&li, (void *)&li->li_next)
- == 0)
- ptrs[i++] = li;
+ ==
0)
+ ptrs[ptrs_count++] = li;
if (item_compare_func_err)
{
EMSG(_("E882: Uniq compare function failed"));
break;
}
}
-
- if (!item_compare_func_err)
- {
- while (--i >= 0)
- {
- li = ptrs[i]->li_next;
- ptrs[i]->li_next = li->li_next;
- if (li->li_next != NULL)
- li->li_next->li_prev = ptrs[i];
- else
- l->lv_last = ptrs[i];
- list_fix_watch(l, li);
- listitem_free(li);
- l->lv_len--;
- }
+ }
+
+ if (!item_compare_func_err)
+ {
+ while (--ptrs_count >= 0)
+ {
+ li = ptrs[ptrs_count]->li_next;
+ ptrs[ptrs_count]->li_next = li->li_next;
+ if (li->li_next != NULL)
+ li->li_next->li_prev = ptrs[ptrs_count];
+ else
+ l->lv_last = ptrs[ptrs_count];
+ list_fix_watch(l, li);
+ listitem_free(li);
+ l->lv_len--;
}
}
@@ -17241,28 +17394,6 @@
}
/*
- * "sort({list})" function
- */
- static void
-f_sort(argvars, rettv)
- typval_T *argvars;
- typval_T *rettv;
-{
- do_sort_uniq(argvars, rettv, TRUE);
-}
-
-/*
- * "uniq({list})" function
- */
- static void
-f_uniq(argvars, rettv)
- typval_T *argvars;
- typval_T *rettv;
-{
- do_sort_uniq(argvars, rettv, FALSE);
-}
-
-/*
* "soundfold({word})" function
*/
static void
diff -r d96e8fbc3747 src/sys_tree.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/sys_tree.h Wed Mar 26 19:57:07 2014 +0200
@@ -0,0 +1,748 @@
+/* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */
+/*
+ * Copyright 2002 Niels Provos <[email protected]>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef _SYS_TREE_H_
+#define _SYS_TREE_H_
+
+/*
+ * This file defines data structures for different types of trees:
+ * splay trees and red-black trees.
+ *
+ * A splay tree is a self-organizing data structure. Every operation
+ * on the tree causes a splay to happen. The splay moves the requested
+ * node to the root of the tree and partly rebalances it.
+ *
+ * This has the benefit that request locality causes faster lookups as
+ * the requested nodes move to the top of the tree. On the other hand,
+ * every lookup causes memory writes.
+ *
+ * The Balance Theorem bounds the total access time for m operations
+ * and n inserts on an initially empty tree as O((m + n)lg n). The
+ * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
+ *
+ * A red-black tree is a binary search tree with the node color as an
+ * extra attribute. It fulfills a set of conditions:
+ * - every search path from the root to a leaf consists of the
+ * same number of black nodes,
+ * - each red node (except for the root) has a black parent,
+ * - each leaf node is black.
+ *
+ * Every operation on a red-black tree is bounded as O(lg n).
+ * The maximum height of a red-black tree is 2lg (n+1).
+ */
+
+#define SPLAY_HEAD(name, type) \
+struct name { \
+ struct type *sph_root; /* root of the tree */ \
+}
+
+#define SPLAY_INITIALIZER(root)
\
+ { NULL }
+
+#define SPLAY_INIT(root) do { \
+ (root)->sph_root = NULL; \
+} while (0)
+
+#define SPLAY_ENTRY(type) \
+struct { \
+ struct type *spe_left; /* left element */ \
+ struct type *spe_right; /* right element */ \
+}
+
+#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
+#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
+#define SPLAY_ROOT(head) (head)->sph_root
+#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
+
+/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
+#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
+ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
+ SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
+ (head)->sph_root = tmp; \
+} while (0)
+
+#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
+ SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
+ SPLAY_LEFT(tmp, field) = (head)->sph_root; \
+ (head)->sph_root = tmp; \
+} while (0)
+
+#define SPLAY_LINKLEFT(head, tmp, field) do { \
+ SPLAY_LEFT(tmp, field) = (head)->sph_root; \
+ tmp = (head)->sph_root; \
+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
+} while (0)
+
+#define SPLAY_LINKRIGHT(head, tmp, field) do { \
+ SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
+ tmp = (head)->sph_root; \
+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
+} while (0)
+
+#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
+ SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
+ SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
+ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
+ SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
+} while (0)
+
+/* Generates prototypes and inline functions */
+
+#define SPLAY_PROTOTYPE(name, type, field, cmp)
\
+void name##_SPLAY(struct name *, struct type *); \
+void name##_SPLAY_MINMAX(struct name *, int); \
+struct type *name##_SPLAY_INSERT(struct name *, struct type *);
\
+struct type *name##_SPLAY_REMOVE(struct name *, struct type *);
\
+ \
+/* Finds the node with the same key as elm */ \
+static __inline struct type * \
+name##_SPLAY_FIND(struct name *head, struct type *elm) \
+{ \
+ if (SPLAY_EMPTY(head)) \
+ return(NULL); \
+ name##_SPLAY(head, elm); \
+ if ((cmp)(elm, (head)->sph_root) == 0) \
+ return (head->sph_root); \
+ return (NULL); \
+} \
+ \
+static __inline struct type * \
+name##_SPLAY_NEXT(struct name *head, struct type *elm) \
+{ \
+ name##_SPLAY(head, elm); \
+ if (SPLAY_RIGHT(elm, field) != NULL) { \
+ elm = SPLAY_RIGHT(elm, field); \
+ while (SPLAY_LEFT(elm, field) != NULL) { \
+ elm = SPLAY_LEFT(elm, field); \
+ } \
+ } else \
+ elm = NULL; \
+ return (elm); \
+} \
+ \
+static __inline struct type * \
+name##_SPLAY_MIN_MAX(struct name *head, int val) \
+{ \
+ name##_SPLAY_MINMAX(head, val); \
+ return (SPLAY_ROOT(head)); \
+}
+
+/* Main splay operation.
+ * Moves node close to the key of elm to top
+ */
+#define SPLAY_GENERATE(name, type, field, cmp) \
+struct type * \
+name##_SPLAY_INSERT(struct name *head, struct type *elm) \
+{ \
+ if (SPLAY_EMPTY(head)) { \
+ SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
+ } else { \
+ int __comp; \
+ name##_SPLAY(head, elm); \
+ __comp = (cmp)(elm, (head)->sph_root); \
+ if(__comp < 0) { \
+ SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root,
field);\
+ SPLAY_RIGHT(elm, field) = (head)->sph_root; \
+ SPLAY_LEFT((head)->sph_root, field) = NULL; \
+ } else if (__comp > 0) { \
+ SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root,
field);\
+ SPLAY_LEFT(elm, field) = (head)->sph_root; \
+ SPLAY_RIGHT((head)->sph_root, field) = NULL; \
+ } else \
+ return ((head)->sph_root); \
+ } \
+ (head)->sph_root = (elm); \
+ return (NULL); \
+} \
+ \
+struct type * \
+name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *__tmp; \
+ if (SPLAY_EMPTY(head)) \
+ return (NULL); \
+ name##_SPLAY(head, elm); \
+ if ((cmp)(elm, (head)->sph_root) == 0) { \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root,
field);\
+ } else { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
+ name##_SPLAY(head, elm); \
+ SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
+ } \
+ return (elm); \
+ } \
+ return (NULL); \
+} \
+ \
+void \
+name##_SPLAY(struct name *head, struct type *elm) \
+{ \
+ struct type __node, *__left, *__right, *__tmp; \
+ int __comp; \
+\
+ SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+ __left = __right = &__node; \
+\
+ while ((__comp = (cmp)(elm, (head)->sph_root))) { \
+ if (__comp < 0) { \
+ __tmp = SPLAY_LEFT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if ((cmp)(elm, __tmp) < 0){ \
+ SPLAY_ROTATE_RIGHT(head, __tmp, field); \
+ if (SPLAY_LEFT((head)->sph_root, field) ==
NULL)\
+ break; \
+ } \
+ SPLAY_LINKLEFT(head, __right, field); \
+ } else if (__comp > 0) { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if ((cmp)(elm, __tmp) > 0){ \
+ SPLAY_ROTATE_LEFT(head, __tmp, field); \
+ if (SPLAY_RIGHT((head)->sph_root, field) ==
NULL)\
+ break; \
+ } \
+ SPLAY_LINKRIGHT(head, __left, field); \
+ } \
+ } \
+ SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
+} \
+ \
+/* Splay with either the minimum or the maximum element
\
+ * Used to find minimum or maximum element in tree. \
+ */ \
+void name##_SPLAY_MINMAX(struct name *head, int __comp) \
+{ \
+ struct type __node, *__left, *__right, *__tmp; \
+\
+ SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+ __left = __right = &__node; \
+\
+ while (1) { \
+ if (__comp < 0) { \
+ __tmp = SPLAY_LEFT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if (__comp < 0){ \
+ SPLAY_ROTATE_RIGHT(head, __tmp, field); \
+ if (SPLAY_LEFT((head)->sph_root, field) ==
NULL)\
+ break; \
+ } \
+ SPLAY_LINKLEFT(head, __right, field); \
+ } else if (__comp > 0) { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if (__comp > 0) { \
+ SPLAY_ROTATE_LEFT(head, __tmp, field); \
+ if (SPLAY_RIGHT((head)->sph_root, field) ==
NULL)\
+ break; \
+ } \
+ SPLAY_LINKRIGHT(head, __left, field); \
+ } \
+ } \
+ SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
+}
+
+#define SPLAY_NEGINF -1
+#define SPLAY_INF 1
+
+#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
+#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
+#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
+#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
+#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
+ : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
+#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
+ : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
+
+#define SPLAY_FOREACH(x, name, head) \
+ for ((x) = SPLAY_MIN(name, head); \
+ (x) != NULL; \
+ (x) = SPLAY_NEXT(name, head, x))
+
+/* Macros that define a red-black tree */
+#define RB_HEAD(name, type) \
+struct name { \
+ struct type *rbh_root; /* root of the tree */ \
+}
+
+#define RB_INITIALIZER(root) \
+ { NULL }
+
+#define RB_INIT(root) do { \
+ (root)->rbh_root = NULL; \
+} while (0)
+
+#define RB_BLACK 0
+#define RB_RED 1
+#define RB_ENTRY(type) \
+struct { \
+ struct type *rbe_left; /* left element */ \
+ struct type *rbe_right; /* right element */ \
+ struct type *rbe_parent; /* parent element */ \
+ int rbe_color; /* node color */ \
+}
+
+#define RB_LEFT(elm, field) (elm)->field.rbe_left
+#define RB_RIGHT(elm, field) (elm)->field.rbe_right
+#define RB_PARENT(elm, field) (elm)->field.rbe_parent
+#define RB_COLOR(elm, field) (elm)->field.rbe_color
+#define RB_ROOT(head) (head)->rbh_root
+#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
+
+#define RB_SET(elm, parent, field) do {
\
+ RB_PARENT(elm, field) = parent; \
+ RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
+ RB_COLOR(elm, field) = RB_RED; \
+} while (0)
+
+#define RB_SET_BLACKRED(black, red, field) do {
\
+ RB_COLOR(black, field) = RB_BLACK; \
+ RB_COLOR(red, field) = RB_RED; \
+} while (0)
+
+#ifndef RB_AUGMENT
+#define RB_AUGMENT(x) do {} while (0)
+#endif
+
+#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
+ (tmp) = RB_RIGHT(elm, field); \
+ if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
+ RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
+ } \
+ RB_AUGMENT(elm); \
+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+ } else \
+ (head)->rbh_root = (tmp); \
+ RB_LEFT(tmp, field) = (elm); \
+ RB_PARENT(elm, field) = (tmp); \
+ RB_AUGMENT(tmp); \
+ if ((RB_PARENT(tmp, field))) \
+ RB_AUGMENT(RB_PARENT(tmp, field)); \
+} while (0)
+
+#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
+ (tmp) = RB_LEFT(elm, field); \
+ if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
+ RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
+ } \
+ RB_AUGMENT(elm); \
+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+ } else \
+ (head)->rbh_root = (tmp); \
+ RB_RIGHT(tmp, field) = (elm); \
+ RB_PARENT(elm, field) = (tmp); \
+ RB_AUGMENT(tmp); \
+ if ((RB_PARENT(tmp, field))) \
+ RB_AUGMENT(RB_PARENT(tmp, field)); \
+} while (0)
+
+/* Generates prototypes and inline functions */
+#define RB_PROTOTYPE(name, type, field, cmp)
\
+ RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#define RB_PROTOTYPE_STATIC(name, type, field, cmp)
\
+ RB_PROTOTYPE_INTERNAL(name, type, field, cmp,
__attribute__((__unused__)) static)
+#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
+attr void name##_RB_INSERT_COLOR(struct name *, struct type *);
\
+attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
+attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
+attr struct type *name##_RB_INSERT(struct name *, struct type *); \
+attr struct type *name##_RB_FIND(struct name *, struct type *);
\
+attr struct type *name##_RB_NFIND(struct name *, struct type *); \
+attr struct type *name##_RB_NEXT(struct type *); \
+attr struct type *name##_RB_PREV(struct type *); \
+attr struct type *name##_RB_MINMAX(struct name *, int);
\
+ \
+
+/* Main rb operation.
+ * Moves node close to the key of elm to top
+ */
+#define RB_GENERATE(name, type, field, cmp)
\
+ RB_GENERATE_INTERNAL(name, type, field, cmp,)
+#define RB_GENERATE_STATIC(name, type, field, cmp)
\
+ RB_GENERATE_INTERNAL(name, type, field, cmp,
__attribute__((__unused__)) static)
+#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
+attr void \
+name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
+{ \
+ struct type *parent, *gparent, *tmp; \
+ while ((parent = RB_PARENT(elm, field)) && \
+ RB_COLOR(parent, field) == RB_RED) { \
+ gparent = RB_PARENT(parent, field); \
+ if (parent == RB_LEFT(gparent, field)) { \
+ tmp = RB_RIGHT(gparent, field); \
+ if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_SET_BLACKRED(parent, gparent, field);\
+ elm = gparent; \
+ continue; \
+ } \
+ if (RB_RIGHT(parent, field) == elm) { \
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ RB_SET_BLACKRED(parent, gparent, field); \
+ RB_ROTATE_RIGHT(head, gparent, tmp, field); \
+ } else { \
+ tmp = RB_LEFT(gparent, field); \
+ if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_SET_BLACKRED(parent, gparent, field);\
+ elm = gparent; \
+ continue; \
+ } \
+ if (RB_LEFT(parent, field) == elm) { \
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ RB_SET_BLACKRED(parent, gparent, field); \
+ RB_ROTATE_LEFT(head, gparent, tmp, field); \
+ } \
+ } \
+ RB_COLOR(head->rbh_root, field) = RB_BLACK; \
+} \
+ \
+attr void \
+name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type
*elm) \
+{ \
+ struct type *tmp; \
+ while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
+ elm != RB_ROOT(head)) { \
+ if (RB_LEFT(parent, field) == elm) { \
+ tmp = RB_RIGHT(parent, field); \
+ if (RB_COLOR(tmp, field) == RB_RED) { \
+ RB_SET_BLACKRED(tmp, parent, field); \
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ tmp = RB_RIGHT(parent, field); \
+ } \
+ if ((RB_LEFT(tmp, field) == NULL || \
+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK)
&&\
+ (RB_RIGHT(tmp, field) == NULL || \
+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK))
{\
+ RB_COLOR(tmp, field) = RB_RED; \
+ elm = parent; \
+ parent = RB_PARENT(elm, field); \
+ } else { \
+ if (RB_RIGHT(tmp, field) == NULL || \
+ RB_COLOR(RB_RIGHT(tmp, field), field) ==
RB_BLACK) {\
+ struct type *oleft; \
+ if ((oleft = RB_LEFT(tmp, field)))\
+ RB_COLOR(oleft, field) =
RB_BLACK;\
+ RB_COLOR(tmp, field) = RB_RED; \
+ RB_ROTATE_RIGHT(head, tmp, oleft,
field);\
+ tmp = RB_RIGHT(parent, field); \
+ } \
+ RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+ RB_COLOR(parent, field) = RB_BLACK; \
+ if (RB_RIGHT(tmp, field)) \
+ RB_COLOR(RB_RIGHT(tmp, field), field) =
RB_BLACK;\
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ elm = RB_ROOT(head); \
+ break; \
+ } \
+ } else { \
+ tmp = RB_LEFT(parent, field); \
+ if (RB_COLOR(tmp, field) == RB_RED) { \
+ RB_SET_BLACKRED(tmp, parent, field); \
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ tmp = RB_LEFT(parent, field); \
+ } \
+ if ((RB_LEFT(tmp, field) == NULL || \
+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK)
&&\
+ (RB_RIGHT(tmp, field) == NULL || \
+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK))
{\
+ RB_COLOR(tmp, field) = RB_RED; \
+ elm = parent; \
+ parent = RB_PARENT(elm, field); \
+ } else { \
+ if (RB_LEFT(tmp, field) == NULL || \
+ RB_COLOR(RB_LEFT(tmp, field), field) ==
RB_BLACK) {\
+ struct type *oright; \
+ if ((oright = RB_RIGHT(tmp, field)))\
+ RB_COLOR(oright, field) =
RB_BLACK;\
+ RB_COLOR(tmp, field) = RB_RED; \
+ RB_ROTATE_LEFT(head, tmp, oright,
field);\
+ tmp = RB_LEFT(parent, field); \
+ } \
+ RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+ RB_COLOR(parent, field) = RB_BLACK; \
+ if (RB_LEFT(tmp, field)) \
+ RB_COLOR(RB_LEFT(tmp, field), field) =
RB_BLACK;\
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ elm = RB_ROOT(head); \
+ break; \
+ } \
+ } \
+ } \
+ if (elm) \
+ RB_COLOR(elm, field) = RB_BLACK; \
+} \
+ \
+attr struct type * \
+name##_RB_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *child, *parent, *old = elm; \
+ int color; \
+ if (RB_LEFT(elm, field) == NULL) \
+ child = RB_RIGHT(elm, field); \
+ else if (RB_RIGHT(elm, field) == NULL) \
+ child = RB_LEFT(elm, field); \
+ else { \
+ struct type *left; \
+ elm = RB_RIGHT(elm, field); \
+ while ((left = RB_LEFT(elm, field))) \
+ elm = left; \
+ child = RB_RIGHT(elm, field); \
+ parent = RB_PARENT(elm, field); \
+ color = RB_COLOR(elm, field); \
+ if (child) \
+ RB_PARENT(child, field) = parent; \
+ if (parent) { \
+ if (RB_LEFT(parent, field) == elm) \
+ RB_LEFT(parent, field) = child; \
+ else \
+ RB_RIGHT(parent, field) = child; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = child; \
+ if (RB_PARENT(elm, field) == old) \
+ parent = elm; \
+ (elm)->field = (old)->field; \
+ if (RB_PARENT(old, field)) { \
+ if (RB_LEFT(RB_PARENT(old, field), field) == old)\
+ RB_LEFT(RB_PARENT(old, field), field) = elm;\
+ else \
+ RB_RIGHT(RB_PARENT(old, field), field) = elm;\
+ RB_AUGMENT(RB_PARENT(old, field)); \
+ } else \
+ RB_ROOT(head) = elm; \
+ RB_PARENT(RB_LEFT(old, field), field) = elm; \
+ if (RB_RIGHT(old, field)) \
+ RB_PARENT(RB_RIGHT(old, field), field) = elm; \
+ if (parent) { \
+ left = parent; \
+ do { \
+ RB_AUGMENT(left); \
+ } while ((left = RB_PARENT(left, field))); \
+ } \
+ goto color; \
+ } \
+ parent = RB_PARENT(elm, field); \
+ color = RB_COLOR(elm, field); \
+ if (child) \
+ RB_PARENT(child, field) = parent; \
+ if (parent) { \
+ if (RB_LEFT(parent, field) == elm) \
+ RB_LEFT(parent, field) = child; \
+ else \
+ RB_RIGHT(parent, field) = child; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = child; \
+color: \
+ if (color == RB_BLACK) \
+ name##_RB_REMOVE_COLOR(head, parent, child); \
+ return (old); \
+} \
+ \
+/* Inserts a node into the RB tree */ \
+attr struct type * \
+name##_RB_INSERT(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp; \
+ struct type *parent = NULL; \
+ int comp = 0; \
+ tmp = RB_ROOT(head); \
+ while (tmp) { \
+ parent = tmp; \
+ comp = (cmp)(elm, parent); \
+ if (comp < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ RB_SET(elm, parent, field); \
+ if (parent != NULL) { \
+ if (comp < 0) \
+ RB_LEFT(parent, field) = elm; \
+ else \
+ RB_RIGHT(parent, field) = elm; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = elm; \
+ name##_RB_INSERT_COLOR(head, elm); \
+ return (NULL); \
+} \
+ \
+/* Finds the node with the same key as elm */ \
+attr struct type * \
+name##_RB_FIND(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ return (NULL); \
+} \
+ \
+/* Finds the first node greater than or equal to the search key */ \
+attr struct type * \
+name##_RB_NFIND(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ struct type *res = NULL; \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) { \
+ res = tmp; \
+ tmp = RB_LEFT(tmp, field); \
+ } \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ return (res); \
+} \
+ \
+/* ARGSUSED */ \
+attr struct type * \
+name##_RB_NEXT(struct type *elm) \
+{ \
+ if (RB_RIGHT(elm, field)) { \
+ elm = RB_RIGHT(elm, field); \
+ while (RB_LEFT(elm, field)) \
+ elm = RB_LEFT(elm, field); \
+ } else { \
+ if (RB_PARENT(elm, field) && \
+ (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
+ elm = RB_PARENT(elm, field); \
+ else { \
+ while (RB_PARENT(elm, field) && \
+ (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
+ elm = RB_PARENT(elm, field); \
+ elm = RB_PARENT(elm, field); \
+ } \
+ } \
+ return (elm); \
+} \
+ \
+/* ARGSUSED */ \
+attr struct type * \
+name##_RB_PREV(struct type *elm) \
+{ \
+ if (RB_LEFT(elm, field)) { \
+ elm = RB_LEFT(elm, field); \
+ while (RB_RIGHT(elm, field)) \
+ elm = RB_RIGHT(elm, field); \
+ } else { \
+ if (RB_PARENT(elm, field) && \
+ (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
+ elm = RB_PARENT(elm, field); \
+ else { \
+ while (RB_PARENT(elm, field) && \
+ (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
+ elm = RB_PARENT(elm, field); \
+ elm = RB_PARENT(elm, field); \
+ } \
+ } \
+ return (elm); \
+} \
+ \
+attr struct type * \
+name##_RB_MINMAX(struct name *head, int val) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ struct type *parent = NULL; \
+ while (tmp) { \
+ parent = tmp; \
+ if (val < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else \
+ tmp = RB_RIGHT(tmp, field); \
+ } \
+ return (parent); \
+}
+
+#define RB_NEGINF -1
+#define RB_INF 1
+
+#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
+#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
+#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
+#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
+#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
+#define RB_PREV(name, x, y) name##_RB_PREV(y)
+#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
+#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
+
+#define RB_FOREACH(x, name, head) \
+ for ((x) = RB_MIN(name, head); \
+ (x) != NULL; \
+ (x) = name##_RB_NEXT(x))
+
+#define RB_FOREACH_SAFE(x, name, head, y) \
+ for ((x) = RB_MIN(name, head); \
+ ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \
+ (x) = (y))
+
+#define RB_FOREACH_REVERSE(x, name, head) \
+ for ((x) = RB_MAX(name, head); \
+ (x) != NULL; \
+ (x) = name##_RB_PREV(x))
+
+#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
+ for ((x) = RB_MAX(name, head); \
+ ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \
+ (x) = (y))
+
+#endif /* _SYS_TREE_H_ */
diff -r d96e8fbc3747 src/testdir/test55.in
--- a/src/testdir/test55.in Tue Mar 25 18:24:23 2014 +0100
+++ b/src/testdir/test55.in Wed Mar 26 19:57:07 2014 +0200
@@ -326,6 +326,7 @@
:" reverse(), sort(), uniq()
:let l = ['-0', 'A11', 2, 2, 'xaaa', 4, 'foo', 'foo6', 'foo', [0, 1, 2], 'x8',
[0, 1, 2], 1.5]
:$put =string(uniq(copy(l)))
+:$put =string(uniq(copy(l), 'stable'))
:$put =string(reverse(l))
:$put =string(reverse(reverse(l)))
:$put =string(sort(l))
diff -r d96e8fbc3747 src/testdir/test55.ok
--- a/src/testdir/test55.ok Tue Mar 25 18:24:23 2014 +0100
+++ b/src/testdir/test55.ok Wed Mar 26 19:57:07 2014 +0200
@@ -95,6 +95,7 @@
caught a:000[3]
[1, 2, [3, 9, 5, 6], {'a': 12, '5': 8}]
['-0', 'A11', 2, 'xaaa', 4, 'foo', 'foo6', 'foo', [0, 1, 2], 'x8', [0, 1, 2],
1.5]
+['-0', 'A11', 2, 'xaaa', 4, 'foo', 'foo6', [0, 1, 2], 'x8', 1.5]
[1.5, [0, 1, 2], 'x8', [0, 1, 2], 'foo', 'foo6', 'foo', 4, 'xaaa', 2, 2,
'A11', '-0']
[1.5, [0, 1, 2], 'x8', [0, 1, 2], 'foo', 'foo6', 'foo', 4, 'xaaa', 2, 2,
'A11', '-0']
['-0', 'A11', 'foo', 'foo', 'foo6', 'x8', 'xaaa', 1.5, 2, 2, 4, [0, 1, 2], [0,
1, 2]]
function! Data(size)
let list = []
python << EOL
import vim, random
size = int(vim.eval('a:size'))
vim.bindeval('list').extend([ random.randint(0, int(size * 0.8)) for i in
range(size) ])
EOL
return list
endfunction
function! StableUniq(list)
let seen = {}
let uniques = []
for elem in a:list
if !has_key(seen, elem)
let seen[elem] = 1
call add(uniques, elem)
endif
endfor
return uniques
endfunction
function! Compare(a, b)
return a:a - a:b
endfunction
function! Bench()
let data = Data(1000000)
let tmp = copy(data)
call sort(tmp)
let tmp = copy(data)
call uniq(tmp, 'stable')
let tmp = copy(data)
call StableUniq(tmp)
let tmp = copy(data)
call sort(tmp, 'Compare')
let tmp = copy(data)
call uniq(tmp, 'stable', 'Compare')
endfunction
profile start uniq_benchmarks.log
profile! func Bench
call Bench()
quit
