Author: Armin Rigo <[email protected]>
Branch: vmprof
Changeset: r76332:4c96d8444ca3
Date: 2015-03-11 19:58 +0100
http://bitbucket.org/pypy/pypy/changeset/4c96d8444ca3/
Log: Add a skiplist implementation
diff --git a/rpython/jit/backend/llsupport/src/skiplist.c
b/rpython/jit/backend/llsupport/src/skiplist.c
new file mode 100644
--- /dev/null
+++ b/rpython/jit/backend/llsupport/src/skiplist.c
@@ -0,0 +1,95 @@
+#include <stdlib.h>
+#include <stdint.h>
+
+
+#define SKIPLIST_HEIGHT 8
+
+typedef struct skipnode_s {
+ uintptr_t key;
+ char *data;
+ struct skipnode_s *next[SKIPLIST_HEIGHT]; /* may be smaller */
+} skipnode_t;
+
+static skipnode_t *skiplist_malloc(uintptr_t datasize)
+{
+ char *result;
+ uintptr_t basesize;
+ uintptr_t length = 1;
+ while (length < SKIPLIST_HEIGHT && (rand() & 3) == 0)
+ length++;
+ basesize = sizeof(skipnode_t) -
+ (SKIPLIST_HEIGHT - length) * sizeof(skipnode_t *);
+ result = malloc(basesize + datasize);
+ if (result != NULL) {
+ ((skipnode_t *)result)->data = result + basesize;
+ }
+ return (skipnode_t *)result;
+}
+
+static skipnode_t *skiplist_search(skipnode_t *head, uintptr_t searchkey)
+{
+ /* Returns the skipnode with key closest (but <=) searchkey.
+ Note that if there is no item with key <= searchkey in the list,
+ this will return the head node. */
+ uintptr_t level = SKIPLIST_HEIGHT - 1;
+ while (1) {
+ skipnode_t *next = head->next[level];
+ if (next != NULL && next->key <= searchkey) {
+ head = next;
+ }
+ else {
+ if (level == 0)
+ break;
+ level -= 1;
+ }
+ }
+ return head;
+}
+
+static void skiplist_insert(skipnode_t *head, skipnode_t *new)
+{
+ uintptr_t size0 = sizeof(skipnode_t) -
+ SKIPLIST_HEIGHT * sizeof(skipnode_t *);
+ uintptr_t height_of_new = (new->data - ((char *)new + size0)) /
+ sizeof(skipnode_t *);
+
+ uintptr_t level = SKIPLIST_HEIGHT - 1;
+ uintptr_t searchkey = new->key;
+ while (1) {
+ skipnode_t *next = head->next[level];
+ if (next != NULL && next->key <= searchkey) {
+ head = next;
+ }
+ else {
+ if (level < height_of_new) {
+ new->next[level] = next;
+ head->next[level] = new;
+ if (level == 0)
+ break;
+ }
+ level -= 1;
+ }
+ }
+}
+
+static void skiplist_remove(skipnode_t *head, uintptr_t exact_key)
+{
+ uintptr_t level = SKIPLIST_HEIGHT - 1;
+ while (1) {
+ skipnode_t *next = head->next[level];
+ if (next != NULL && next->key <= exact_key) {
+ if (next->key == exact_key) {
+ head->next[level] = next->next[level];
+ if (level == 0)
+ return; /* successfully removed */
+ level -= 1;
+ }
+ else
+ head = next;
+ }
+ else {
+ assert(level > 0); /* else, 'exact_key' not found! */
+ level -= 1;
+ }
+ }
+}
diff --git a/rpython/jit/backend/llsupport/test/test_skiplist.py
b/rpython/jit/backend/llsupport/test/test_skiplist.py
new file mode 100644
--- /dev/null
+++ b/rpython/jit/backend/llsupport/test/test_skiplist.py
@@ -0,0 +1,85 @@
+import random, os
+import cffi
+
+ffi = cffi.FFI()
+
+ffi.cdef("""
+typedef struct {
+ uintptr_t key;
+ char *data;
+ ...;
+} skipnode_t;
+
+skipnode_t *skiplist_malloc(uintptr_t datasize);
+skipnode_t *skiplist_search(skipnode_t *head, uintptr_t searchkey);
+void skiplist_insert(skipnode_t *head, skipnode_t *new);
+void skiplist_remove(skipnode_t *head, uintptr_t exact_key);
+""")
+
+filename = os.path.join(os.path.dirname(__file__), '..', 'src', 'skiplist.c')
+lib = ffi.verify(open(filename).read())
+
+
+def test_insert_search_remove():
+ my_head = ffi.new("skipnode_t *")
+ assert lib.skiplist_search(my_head, 0) == my_head
+ #
+ keys = random.sample(xrange(2, 10**9), 50000)
+ nodes = {}
+ for key in keys:
+ node = lib.skiplist_malloc(4)
+ node.key = key
+ ffi.cast("int *", node.data)[0] = key
+ lib.skiplist_insert(my_head, node)
+ nodes[key] = node
+ #
+ random.shuffle(keys)
+ for key in keys:
+ node = lib.skiplist_search(my_head, key)
+ assert nodes[key] == node
+ if key + 1 not in nodes:
+ assert node == lib.skiplist_search(my_head, key + 1)
+ #
+ keys.sort()
+ following = {}
+ preceeding = {}
+ for key, next_key in zip(keys[:-1], keys[1:]):
+ following[key] = next_key
+ preceeding[next_key] = key
+ following[0] = keys[0]
+ following[keys[-1]] = 10**9
+ preceeding[keys[0]] = 0
+ #
+ for i in range(100000):
+ random_key = random.randrange(2, 10**9)
+ node = lib.skiplist_search(my_head, random_key)
+ assert node.key <= random_key
+ if node == my_head:
+ assert random_key < following[0]
+ else:
+ assert node == nodes[node.key]
+ assert following[node.key] > random_key
+ #
+ random_keys = list(keys)
+ random.shuffle(random_keys)
+ for i in range(10000):
+ node = nodes.pop(random_keys.pop())
+ prev = preceeding[node.key]
+ next = following[node.key]
+ following[prev] = next
+ preceeding[next] = prev
+ lib.skiplist_remove(my_head, node.key)
+ if prev == 0:
+ assert lib.skiplist_search(my_head, node.key) == my_head
+ else:
+ assert lib.skiplist_search(my_head, node.key) == nodes[prev]
+ #
+ for i in range(100000):
+ random_key = random.randrange(2, 10**9)
+ node = lib.skiplist_search(my_head, random_key)
+ assert node.key <= random_key
+ if node == my_head:
+ assert random_key < following[0]
+ else:
+ assert node == nodes[node.key]
+ assert following[node.key] > random_key
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
