Changeset View
Changeset View
Standalone View
Standalone View
head/sys/sys/tree.h
Show First 20 Lines • Show All 119 Lines • ▼ Show 20 Lines | |||||
#define SPLAY_PROTOTYPE(name, type, field, cmp) \ | #define SPLAY_PROTOTYPE(name, type, field, cmp) \ | ||||
void name##_SPLAY(struct name *, struct type *); \ | void name##_SPLAY(struct name *, struct type *); \ | ||||
void name##_SPLAY_MINMAX(struct name *, int); \ | void name##_SPLAY_MINMAX(struct name *, int); \ | ||||
struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ | struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ | ||||
struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ | struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ | ||||
\ | \ | ||||
/* Finds the node with the same key as elm */ \ | /* Finds the node with the same key as elm */ \ | ||||
static __inline struct type * \ | static __unused __inline struct type * \ | ||||
name##_SPLAY_FIND(struct name *head, struct type *elm) \ | name##_SPLAY_FIND(struct name *head, struct type *elm) \ | ||||
{ \ | { \ | ||||
if (SPLAY_EMPTY(head)) \ | if (SPLAY_EMPTY(head)) \ | ||||
return(NULL); \ | return(NULL); \ | ||||
name##_SPLAY(head, elm); \ | name##_SPLAY(head, elm); \ | ||||
if ((cmp)(elm, (head)->sph_root) == 0) \ | if ((cmp)(elm, (head)->sph_root) == 0) \ | ||||
return (head->sph_root); \ | return (head->sph_root); \ | ||||
return (NULL); \ | return (NULL); \ | ||||
} \ | } \ | ||||
\ | \ | ||||
static __inline struct type * \ | static __unused __inline struct type * \ | ||||
name##_SPLAY_NEXT(struct name *head, struct type *elm) \ | name##_SPLAY_NEXT(struct name *head, struct type *elm) \ | ||||
{ \ | { \ | ||||
name##_SPLAY(head, elm); \ | name##_SPLAY(head, elm); \ | ||||
if (SPLAY_RIGHT(elm, field) != NULL) { \ | if (SPLAY_RIGHT(elm, field) != NULL) { \ | ||||
elm = SPLAY_RIGHT(elm, field); \ | elm = SPLAY_RIGHT(elm, field); \ | ||||
while (SPLAY_LEFT(elm, field) != NULL) { \ | while (SPLAY_LEFT(elm, field) != NULL) { \ | ||||
elm = SPLAY_LEFT(elm, field); \ | elm = SPLAY_LEFT(elm, field); \ | ||||
} \ | } \ | ||||
} else \ | } else \ | ||||
elm = NULL; \ | elm = NULL; \ | ||||
return (elm); \ | return (elm); \ | ||||
} \ | } \ | ||||
\ | \ | ||||
static __inline struct type * \ | static __unused __inline struct type * \ | ||||
name##_SPLAY_MIN_MAX(struct name *head, int val) \ | name##_SPLAY_MIN_MAX(struct name *head, int val) \ | ||||
{ \ | { \ | ||||
name##_SPLAY_MINMAX(head, val); \ | name##_SPLAY_MINMAX(head, val); \ | ||||
return (SPLAY_ROOT(head)); \ | return (SPLAY_ROOT(head)); \ | ||||
} | } | ||||
/* Main splay operation. | /* Main splay operation. | ||||
* Moves node close to the key of elm to top | * Moves node close to the key of elm to top | ||||
▲ Show 20 Lines • Show All 642 Lines • Show Last 20 Lines |