123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300 |
- /*!
- Temelia - Skip-list implementation source file.
- Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
- @author Dascalu Laurentiu
- This program is free software; you can redistribute it and
- modify it under the terms of the GNU General Public License
- as published by the Free Software Foundation; either version 3
- of the License, or (at your option) any later version.
- This program 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 General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
- #include "include/skip_list.h"
- #include "include/common.h"
- #include <stdlib.h>
- struct _skip_list_t
- {
- /*! key reference */
- void *key;
- /*! node's level */
- int level;
- /*! array of pointers to neighbors */
- struct _skip_list_t **next;
- };
- static INLINE int _calculate_level(int max_level);
- skip_list_t skip_list_new(int max_level)
- {
- int i;
- skip_list_t skip_list;
- _ASSERT(max_level, <=, 0, INVALID_INPUT, NULL);
- /*
- * The first node in a skip list is used as sentinel; it doesn't store any key.
- */
- skip_list = (struct _skip_list_t *) _new(sizeof(struct _skip_list_t));
- _ASSERT(skip_list, ==, NULL, NULL_POINTER, NULL);
- skip_list->key = NULL;
- skip_list->level = max_level;
- skip_list->next = (struct _skip_list_t **) _new(max_level
- * sizeof(struct _skip_list_t *));
- if (skip_list->next == NULL)
- {
- _delete(skip_list);
- temelia_errno = NULL_POINTER;
- return NULL;
- }
- for (i = 0; i < max_level; i++)
- skip_list->next[i] = NULL;
- return skip_list;
- }
- void skip_list_node_delete(skip_list_t skip_list)
- {
- int i;
- _ASSERT(skip_list, ==, NULL, NULL_POINTER,);
- for (i = 0; i < skip_list->level; i++)
- skip_list->next[i] = NULL;
- skip_list->level = 0;
- skip_list->key = NULL;
- _delete(skip_list->next);
- _delete(skip_list);
- }
- void *skip_list_node_get_key(skip_list_t skip_list)
- {
- _ASSERT(skip_list, ==, NULL, NULL_POINTER, NULL);
- return skip_list->key;
- }
- void skip_list_node_set_key(skip_list_t skip_list, void *key)
- {
- _ASSERT(skip_list, ==, NULL, NULL_POINTER,);
- skip_list->key = key;
- }
- int skip_list_node_get_level(skip_list_t skip_list)
- {
- _ASSERT(skip_list, ==, NULL, NULL_POINTER, -1);
- return skip_list->level;
- }
- void *skip_list_node_get_next(skip_list_t skip_list)
- {
- _ASSERT(skip_list, ==, NULL, NULL_POINTER, NULL);
- return skip_list->next;
- }
- void *skip_list_node_get_next_level(skip_list_t skip_list, int level)
- {
- _ASSERT(skip_list, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(level, <, 0, INVALID_INPUT, NULL);
- _ASSERT(level, >=, skip_list->level, INVALID_INPUT, NULL);
- return skip_list->next[level];
- }
- void skip_list_delete(skip_list_t skip_list)
- {
- skip_list_t it, prev;
- _ASSERT(skip_list, ==, NULL, NULL_POINTER,);
- it = skip_list;
- while (it)
- {
- prev = it;
- it = it->next[0];
- skip_list_node_delete(prev);
- }
- }
- skip_list_t skip_list_insert(skip_list_t skip_list, void *key, int compare(
- void *x, void *y, void *context), void *context)
- {
- skip_list_t *prevs, add, it;
- int level, i;
- _ASSERT(skip_list, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
- prevs = (skip_list_t *) _new(skip_list->level * sizeof(skip_list_t));
- it = skip_list;
- for (level = skip_list->level - 1; level >= 0; level--)
- {
- while (it->next[level] != NULL && compare(it->next[level]->key, key,
- context) < 0)
- it = it->next[level];
- prevs[level] = it;
- }
- // Key already exists.
- if (it->next[0] && !compare(it->next[0]->key, key, context))
- {
- _delete(prevs);
- /*
- * FIXME: return NULL if key already exists in skip-list ?
- * Or return the node containing that key ?
- */
- return NULL;
- //return it->next[0];
- }
- level = _calculate_level(skip_list->level);
- add = skip_list_new(level);
- _ASSERT(add, ==, NULL, NULL_POINTER, NULL);
- add->key = key;
- for (i = 0; i < level; i++)
- {
- add->next[i] = prevs[i]->next[i];
- prevs[i]->next[i] = add;
- }
- _delete(prevs);
- return add;
- }
- skip_list_t skip_list_search(skip_list_t skip_list, void *key, int compare(
- void *x, void *y, void *context), void *context)
- {
- skip_list_t *prevs;
- skip_list_t it;
- int level;
- _ASSERT(skip_list, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
- prevs = (skip_list_t *) _new(skip_list->level * sizeof(skip_list_t));
- it = skip_list;
- for (level = skip_list->level - 1; level >= 0; level--)
- {
- while (it->next[level] != NULL && compare(it->next[level]->key, key,
- context) < 0)
- it = it->next[level];
- prevs[level] = it;
- }
- // return NULL if key isn't found.
- if (it->next[0] == NULL || compare(it->next[0]->key, key, context))
- {
- _delete(prevs);
- return NULL;
- }
- _delete(prevs);
- return it->next[0];
- }
- int skip_list_remove(skip_list_t skip_list, void *key, int compare(void *x,
- void *y, void *context), void *context)
- {
- skip_list_t *prevs;
- skip_list_t it;
- int level, i;
- _ASSERT(skip_list, ==, NULL, NULL_POINTER, -1);
- _ASSERT(compare, ==, NULL, NULL_POINTER, -1);
- prevs = (skip_list_t *) _new(skip_list->level * sizeof(skip_list_t));
- it = skip_list;
- for (level = skip_list->level - 1; level >= 0; level--)
- {
- while (it->next[level] != NULL && compare(it->next[level]->key, key,
- context) < 0)
- it = it->next[level];
- prevs[level] = it;
- }
- // return NULL if key isn't found.
- if (it->next[0] == NULL || compare(it->next[0]->key, key, context))
- {
- _delete(prevs);
- return 0;
- }
- it = it->next[0];
- for (i = 0; i < it->level; i++)
- prevs[i]->next[i] = it->next[i];
- _delete(prevs);
- skip_list_node_delete(it);
- return 1;
- }
- void skip_list_iterate(skip_list_t skip_list_, void key_handler(void *x,
- void *context), void *context)
- {
- skip_list_t it;
- _ASSERT(skip_list_, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- for (it = skip_list_->next[0]; it != NULL; key_handler(it->key, context), it
- = it->next[0])
- ;
- }
- void skip_list_iterate_level(skip_list_t skip_list_, int level,
- void key_handler(void *x, void *context), void *context)
- {
- skip_list_t it;
- _ASSERT(skip_list_, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- _ASSERT(level, <, 0, INVALID_INPUT,);
- _ASSERT(level, >=, skip_list_->level, INVALID_INPUT,);
- it = skip_list_->next[level];
- while (it)
- {
- key_handler(it->key, context);
- it = it->next[level];
- }
- }
- static INLINE int _calculate_level(int max_level)
- {
- int level = 1;
- while (_rand() % 2)
- ++level;
- return level;
- }
|