1/**
2 * \file
3 * \brief Header file for skip list.
4 */
5
6/*
7 * Copyright (c) 2011, ETH Zurich.
8 * All rights reserved.
9 *
10 * This file is distributed under the terms in the attached LICENSE file.
11 * If you do not find this file, copies can be found by writing to:
12 * ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group.
13 */
14
15#ifndef SKIPLIST_H_
16#define SKIPLIST_H_
17
18#include <barrelfish/types.h>
19
20struct skip_list {
21    struct skip_node* header;
22    size_t level;
23    size_t entries; // used to sort lists based on #entries for intersect
24};
25
26struct skip_node {
27    char* element;
28    struct skip_node** forward;
29};
30
31errval_t skip_create_list(struct skip_list**);
32void skip_insert(struct skip_list*, char*);
33bool skip_contains(struct skip_list*, char*);
34char* skip_delete(struct skip_list*, char*);
35char* skip_intersect(struct skip_list**, size_t, char*);
36
37void skip_print_list(struct skip_list*);
38
39#endif /* SKIPLIST_H_ */
40