+
Skip to content

Serialization #9

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 5 commits into from
Apr 30, 2020
Merged

Serialization #9

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
5 commits
Select commit Hold shift + click to select a range
c1ee5fa
fix queue serialization issue
randy3k Apr 29, 2020
b3c37f6
more serialization tests
randy3k Apr 29, 2020
ddbc93f
fix serialzation of deque by using external pointers
randy3k Apr 30, 2020
0a6655a
add codecov.yml
randy3k Apr 30, 2020
221cb01
add serialization test for ordered_dict
randy3k Apr 30, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions .Rbuildignore
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,3 +12,4 @@ vignettes
.*\.o
^.github$
^.covrignore$
^codecov.yml$
7 changes: 3 additions & 4 deletions R/deque.R
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -59,8 +59,8 @@ deque <- function(items = NULL) {
.Call(C_deque_popleft, self)
}
peek <- function() {
if (is.null(last)) stop("deque is empty")
.Call(C_pairlist_car, last)[[2]]
if (is.null(q)) stop("deque is empty")
.Call(C_deque_peek, self)
}
peekleft <- function() {
if (is.null(q)) stop("deque is empty")
Expand All @@ -85,8 +85,7 @@ deque <- function(items = NULL) {
invisible(self)
}
clear <- function() {
q <<- NULL
last <<- NULL
.Call(C_deque_clear, self)
invisible(self)
}
remove <- function(item) {
Expand Down
3 changes: 1 addition & 2 deletions R/queue.R
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -50,8 +50,7 @@ queue <- function(items = NULL) {
.Call(C_pairlist_car, q)
}
clear <- function() {
q <<- NULL
last <<- NULL
.Call(C_queue_clear, self)
invisible(self)
}
size <- function() length(q)
Expand Down
1 change: 1 addition & 0 deletions codecov.yml
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
comment: false
4 changes: 4 additions & 0 deletions src/collections.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -5,6 +5,7 @@
#include "deque.h"
#include "dict.h"
#include "priority_queue.h"
#include "utils.h"


SEXP missing_arg() {
Expand All @@ -14,6 +15,7 @@ SEXP missing_arg() {
static const R_CallMethodDef CallEntries[] = {
{"queue_push", (DL_FUNC) &queue_push, 2},
{"queue_pop", (DL_FUNC) &queue_pop, 1},
{"queue_clear", (DL_FUNC) &queue_clear, 1},
{"stack_push", (DL_FUNC) &stack_push, 2},
{"stack_pop", (DL_FUNC) &stack_pop, 1},
{"pairlist_car", (DL_FUNC) &pairlist_car, 1},
Expand All @@ -22,7 +24,9 @@ static const R_CallMethodDef CallEntries[] = {
{"deque_pushleft", (DL_FUNC) &deque_pushleft, 2},
{"deque_pop", (DL_FUNC) &deque_pop, 1},
{"deque_popleft", (DL_FUNC) &deque_popleft, 1},
{"deque_peek", (DL_FUNC) &deque_peek, 1},
{"deque_remove", (DL_FUNC) &deque_remove, 2},
{"deque_clear", (DL_FUNC) &deque_clear, 1},
{"dict_get", (DL_FUNC) &dict_get, 3},
{"dict_set", (DL_FUNC) &dict_set, 3},
{"dict_remove", (DL_FUNC) &dict_remove, 2},
Expand Down
137 changes: 98 additions & 39 deletions src/deque.c
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,77 +1,101 @@
#include "deque.h"
#include "utils.h"

// return the current item of a pairlist
SEXP pairlist_car(SEXP x) {
if (!Rf_isList(x))
Rf_error("x must be a pairlist");
return CAR(x);
}
#if !defined(static_inline)
#if defined(_MSC_VER) || defined(__GNUC__)
#define static_inline static __inline
#else
#define static_inline static
#endif
#endif


// return the next item of a pairlist
SEXP pairlist_cdr(SEXP x) {
if (!Rf_isList(x))
Rf_error("x must be a pairlist");
return CDR(x);
static_inline SEXP get_last_cons(SEXP q, SEXP last_ptr) {
SEXP last = PROTECT(R_ExternalPtrAddr(last_ptr));
SEXP nextq;
if (last == NULL) {
nextq = CDR(q);
while (!Rf_isNull(nextq)) {
R_SetExternalPtrAddr(VECTOR_ELT(CAR(nextq), 0), q);
q = nextq;
nextq = CDR(q);
}
R_SetExternalPtrAddr(last_ptr, q);
last = q;
}
UNPROTECT(1);
return last;
}


SEXP deque_push(SEXP self, SEXP value) {
PROTECT(value);
SEXP q = PROTECT(get_sexp_value(self, "q"));
SEXP last;
SEXP v;
SEXP last_ptr = PROTECT(get_sexp_value(self, "last"));
SEXP x = PROTECT(Rf_allocVector(VECSXP ,2));
SEXP last = PROTECT(get_last_cons(q, last_ptr));
SEXP v;
if (q == R_NilValue) {
SET_VECTOR_ELT(x, 0, R_NilValue);
SET_VECTOR_ELT(x, 1, value);
v = PROTECT(Rf_cons(x, R_NilValue));
set_sexp_value(self, "q", v);
set_sexp_value(self, "last", v);
R_SetExternalPtrAddr(last_ptr, v);
UNPROTECT(1);
} else {
last = get_sexp_value(self, "last");
SET_VECTOR_ELT(x, 0, last);
SET_VECTOR_ELT(x, 0, PROTECT(R_MakeExternalPtr(last, R_NilValue, R_NilValue)));
SET_VECTOR_ELT(x, 1, value);
v = PROTECT(Rf_cons(x, R_NilValue));
SETCDR(last, v);
set_sexp_value(self, "last", v);
R_SetExternalPtrAddr(last_ptr, v);
UNPROTECT(2);
}
UNPROTECT(3);
UNPROTECT(5);
return value;
}


SEXP deque_pushleft(SEXP self, SEXP value) {
PROTECT(value);
SEXP q = PROTECT(get_sexp_value(self, "q"));
SEXP v;
SEXP last_ptr = PROTECT(get_sexp_value(self, "last"));
SEXP x = PROTECT(Rf_allocVector(VECSXP ,2));
SEXP v;
if (q == R_NilValue) {
SET_VECTOR_ELT(x, 0, R_NilValue);
SET_VECTOR_ELT(x, 1, value);
v = PROTECT(Rf_cons(x, R_NilValue));
set_sexp_value(self, "q", v);
set_sexp_value(self, "last", v);
R_SetExternalPtrAddr(last_ptr, v);
UNPROTECT(1);
} else {
SET_VECTOR_ELT(x, 0, R_NilValue);
SET_VECTOR_ELT(x, 1, value);
v = PROTECT(Rf_cons(x, q));
SET_VECTOR_ELT(CAR(q), 0, v);
SET_VECTOR_ELT(CAR(q), 0, PROTECT(R_MakeExternalPtr(v, R_NilValue, R_NilValue)));
set_sexp_value(self, "q", v);
UNPROTECT(2);
}
UNPROTECT(3);
UNPROTECT(4);
return value;
}


SEXP deque_pop(SEXP self) {
SEXP last = PROTECT(get_sexp_value(self, "last"));
if (last == R_NilValue) Rf_error("deque is empty");
SEXP prev = VECTOR_ELT(CAR(last), 0);
if (prev == R_NilValue) {
SEXP q = PROTECT(get_sexp_value(self, "q"));
if (q == R_NilValue) Rf_error("deque is empty");
SEXP last_ptr = PROTECT(get_sexp_value(self, "last"));
SEXP last = PROTECT(get_last_cons(q, last_ptr));
SEXP prev_ptr = VECTOR_ELT(CAR(last), 0);
if (prev_ptr == R_NilValue) {
set_sexp_value(self, "q", R_NilValue);
R_SetExternalPtrAddr(last_ptr, NULL);
} else {
SEXP prev = R_ExternalPtrAddr(prev_ptr);
R_SetExternalPtrAddr(last_ptr, prev);
SETCDR(prev, R_NilValue);
}
set_sexp_value(self, "last", prev);
UNPROTECT(1);
UNPROTECT(3);
return VECTOR_ELT(CAR(last), 1);
}

Expand All @@ -80,40 +104,75 @@ SEXP deque_popleft(SEXP self) {
if (q == R_NilValue) Rf_error("deque is empty");
SEXP nextq = CDR(q);
if (nextq == R_NilValue) {
set_sexp_value(self, "last", R_NilValue);
set_sexp_value(self, "q", nextq);
SEXP last_ptr = PROTECT(get_sexp_value(self, "last"));
R_SetExternalPtrAddr(last_ptr, NULL);
UNPROTECT(1);
} else {
set_sexp_value(self, "q", nextq);
SET_VECTOR_ELT(CAR(nextq), 0, R_NilValue);
}
set_sexp_value(self, "q", nextq);
UNPROTECT(1);
return VECTOR_ELT(CAR(q), 1);
}


SEXP deque_peek(SEXP self) {
SEXP last_ptr = PROTECT(get_sexp_value(self, "last"));
SEXP q = PROTECT(get_sexp_value(self, "q"));
if (Rf_isNull(q)) {
Rf_error("deque is empty");
}
SEXP last = PROTECT(get_last_cons(q, last_ptr));
SEXP value = VECTOR_ELT(CAR(last), 1);
UNPROTECT(3);
return value;
}


SEXP deque_remove(SEXP self, SEXP value) {
SEXP q = get_sexp_value(self, "q");
SEXP v, nextq, prev;
SEXP q = PROTECT(get_sexp_value(self, "q"));
SEXP last_ptr = PROTECT(get_sexp_value(self, "last"));
// make sure the pointers are resolved after serialization/unserialization
get_last_cons(q, last_ptr);
SEXP v, nextq, prev_ptr;
while (q != R_NilValue) {
v = CAR(q);
nextq = CDR(q);
if (R_compute_identical(VECTOR_ELT(v, 1), value, 16)) {
prev = VECTOR_ELT(v, 0);
if (nextq == R_NilValue && prev == R_NilValue) {
prev_ptr = VECTOR_ELT(v, 0);
if (nextq == R_NilValue && prev_ptr == R_NilValue) {
set_sexp_value(self, "q", R_NilValue);
set_sexp_value(self, "last", R_NilValue);
R_SetExternalPtrAddr(last_ptr, NULL);
} else if (nextq == R_NilValue) {
// last item
SEXP prev = R_ExternalPtrAddr(prev_ptr);
SETCDR(prev, R_NilValue);
set_sexp_value(self, "last", prev);
} else if (prev == R_NilValue) {
set_sexp_value(self, "q", nextq);
R_SetExternalPtrAddr(last_ptr, prev);
} else if (prev_ptr == R_NilValue) {
// first item
SET_VECTOR_ELT(CAR(nextq), 0, R_NilValue);
set_sexp_value(self, "q", nextq);
} else {
SEXP prev = R_ExternalPtrAddr(prev_ptr);
SETCDR(prev, nextq);
SET_VECTOR_ELT(CAR(nextq), 0, prev);
SET_VECTOR_ELT(CAR(nextq), 0, prev_ptr);
}
UNPROTECT(2);
return R_NilValue;
}
q = nextq;
}
UNPROTECT(2);
Rf_error("value not found");
return R_NilValue;
}


SEXP deque_clear(SEXP self) {
set_sexp_value(self, "q", R_NilValue);
SEXP last = PROTECT(R_MakeExternalPtr(NULL, R_NilValue, R_NilValue));
set_sexp_value(self, "last", last);
UNPROTECT(1);
return R_NilValue;
}
8 changes: 4 additions & 4 deletions src/deque.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4,10 +4,6 @@
#include <R.h>
#include <Rinternals.h>

SEXP pairlist_car(SEXP x);

SEXP pairlist_cdr(SEXP x);

SEXP deque_push(SEXP self, SEXP value);

SEXP deque_pushleft(SEXP self, SEXP value);
Expand All @@ -16,6 +12,10 @@ SEXP deque_pop(SEXP self);

SEXP deque_popleft(SEXP self);

SEXP deque_peek(SEXP self);

SEXP deque_remove(SEXP self, SEXP value);

SEXP deque_clear(SEXP self);

#endif
42 changes: 36 additions & 6 deletions src/queue.c
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,24 +1,45 @@
#include "queue.h"
#include "utils.h"

#if !defined(static_inline)
#if defined(_MSC_VER) || defined(__GNUC__)
#define static_inline static __inline
#else
#define static_inline static
#endif
#endif


static_inline SEXP get_last_cons(SEXP q, SEXP last_ptr) {
SEXP last = PROTECT(R_ExternalPtrAddr(last_ptr));
if (last == NULL) {
last = pairlist_last(q);
R_SetExternalPtrAddr(last_ptr, last);
}
UNPROTECT(1);
return last;
}


SEXP queue_push(SEXP self, SEXP value) {
PROTECT(value);
SEXP q = get_sexp_value(self, "q");
SEXP q = PROTECT(get_sexp_value(self, "q"));
SEXP last_ptr = PROTECT(get_sexp_value(self, "last"));
SEXP last;
SEXP v;
if (q == R_NilValue) {
v = PROTECT(Rf_cons(value, R_NilValue));
set_sexp_value(self, "q", v);
set_sexp_value(self, "last", v);
R_SetExternalPtrAddr(last_ptr, v);
UNPROTECT(1);
} else {
last = PROTECT(get_sexp_value(self, "last"));
last = PROTECT(get_last_cons(q, last_ptr));
v = PROTECT(Rf_cons(value, R_NilValue));
SETCDR(last, v);
set_sexp_value(self, "last", v);
UNPROTECT(1); // last
R_SetExternalPtrAddr(last_ptr, v);
UNPROTECT(2);
}
UNPROTECT(2);
UNPROTECT(3);
return value;
}

Expand All @@ -29,3 +50,12 @@ SEXP queue_pop(SEXP self) {
UNPROTECT(1);
return CAR(q);
}


SEXP queue_clear(SEXP self) {
set_sexp_value(self, "q", R_NilValue);
SEXP last = PROTECT(R_MakeExternalPtr(NULL, R_NilValue, R_NilValue));
set_sexp_value(self, "last", last);
UNPROTECT(1);
return R_NilValue;
}
2 changes: 2 additions & 0 deletions src/queue.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -8,4 +8,6 @@ SEXP queue_push(SEXP self, SEXP value);

SEXP queue_pop(SEXP self);

SEXP queue_clear(SEXP self);

#endif
Loading
点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载