Add sk_FOO_delete_if.
Change-Id: I9abfef8d3d4d3ce0dabe29a5dc391fd4e0200d7f
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/56030
Reviewed-by: Bob Beck <bbe@google.com>
Commit-Queue: Bob Beck <bbe@google.com>
diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c
index fe1b513..2dbb842 100644
--- a/crypto/stack/stack.c
+++ b/crypto/stack/stack.c
@@ -212,7 +212,7 @@
if (where != sk->num - 1) {
OPENSSL_memmove(&sk->data[where], &sk->data[where + 1],
- sizeof(void *) * (sk->num - where - 1));
+ sizeof(void *) * (sk->num - where - 1));
}
sk->num--;
@@ -233,6 +233,22 @@
return NULL;
}
+void sk_delete_if(_STACK *sk, OPENSSL_sk_call_delete_if_func call_func,
+ OPENSSL_sk_delete_if_func func, void *data) {
+ if (sk == NULL) {
+ return;
+ }
+
+ size_t new_num = 0;
+ for (size_t i = 0; i < sk->num; i++) {
+ if (!call_func(func, sk->data[i], data)) {
+ sk->data[new_num] = sk->data[i];
+ new_num++;
+ }
+ }
+ sk->num = new_num;
+}
+
int sk_find(const _STACK *sk, size_t *out_index, const void *p,
OPENSSL_sk_call_cmp_func call_cmp_func) {
if (sk == NULL) {
diff --git a/crypto/stack/stack_test.cc b/crypto/stack/stack_test.cc
index 7be84ed..9a7832c 100644
--- a/crypto/stack/stack_test.cc
+++ b/crypto/stack/stack_test.cc
@@ -290,6 +290,7 @@
// Removing elements does not affect sortedness.
TEST_INT_free(sk_TEST_INT_delete(sk.get(), 0));
EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
+ EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
// Changing the comparison function invalidates sortedness.
sk_TEST_INT_set_cmp_func(sk.get(), compare_reverse);
@@ -392,3 +393,44 @@
}
}
}
+
+TEST(StackTest, DeleteIf) {
+ bssl::UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new(compare));
+ for (int v : {1, 9, 2, 8, 3, 7, 4, 6, 5}) {
+ auto obj = TEST_INT_new(v);
+ ASSERT_TRUE(obj);
+ ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(obj)));
+ }
+
+ auto keep_only_multiples = [](TEST_INT *x, void *data) {
+ auto d = static_cast<const int *>(data);
+ if (*x % *d == 0) {
+ return 0;
+ }
+ TEST_INT_free(x);
+ return 1;
+ };
+
+ int d = 2;
+ sk_TEST_INT_delete_if(sk.get(), keep_only_multiples, &d);
+ ExpectStackEquals(sk.get(), {2, 8, 4, 6});
+
+ EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
+ sk_TEST_INT_sort(sk.get());
+ ExpectStackEquals(sk.get(), {2, 4, 6, 8});
+ EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
+
+ // Keep only multiples of four.
+ d = 4;
+ sk_TEST_INT_delete_if(sk.get(), keep_only_multiples, &d);
+ ExpectStackEquals(sk.get(), {4, 8});
+
+ // Removing elements preserves the sorted bit.
+ EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
+
+ // Delete everything.
+ d = 16;
+ sk_TEST_INT_delete_if(sk.get(), keep_only_multiples, &d);
+ ExpectStackEquals(sk.get(), {});
+ EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
+}
diff --git a/include/openssl/stack.h b/include/openssl/stack.h
index 11761dc..cf03002 100644
--- a/include/openssl/stack.h
+++ b/include/openssl/stack.h
@@ -178,6 +178,17 @@
// otherwise it returns NULL.
SAMPLE *sk_SAMPLE_delete_ptr(STACK_OF(SAMPLE) *sk, const SAMPLE *p);
+// sk_SAMPLE_delete_if_func is the callback function for |sk_SAMPLE_delete_if|.
+// It should return one to remove |p| and zero to keep it.
+typedef int (*sk_SAMPLE_delete_if_func)(SAMPLE *p, void *data);
+
+// sk_SAMPLE_delete_if calls |func| with each element of |sk| and removes the
+// entries where |func| returned one. This function does not free or return
+// removed pointers so, if |sk| owns its contents, |func| should release the
+// pointers prior to returning one.
+void sk_SAMPLE_delete_if(STACK_OF(SAMPLE) *sk, sk_SAMPLE_delete_if_func func,
+ void *data);
+
// sk_SAMPLE_find find the first value in |sk| equal to |p|. |sk|'s comparison
// function determines equality, or pointer equality if |sk| has no comparison
// function.
@@ -260,6 +271,10 @@
// in OpenSSL 1.1.1, so hopefully we can fix this compatibly.
typedef int (*OPENSSL_sk_cmp_func)(const void **a, const void **b);
+// OPENSSL_sk_delete_if_func is the generic version of
+// |sk_SAMPLE_delete_if_func|.
+typedef int (*OPENSSL_sk_delete_if_func)(void *obj, void *data);
+
// The following function types call the above type-erased signatures with the
// true types.
typedef void (*OPENSSL_sk_call_free_func)(OPENSSL_sk_free_func, void *);
@@ -267,6 +282,8 @@
typedef int (*OPENSSL_sk_call_cmp_func)(OPENSSL_sk_cmp_func,
const void *const *,
const void *const *);
+typedef int (*OPENSSL_sk_call_delete_if_func)(OPENSSL_sk_delete_if_func, void *,
+ void *);
// stack_st contains an array of pointers. It is not designed to be used
// directly, rather the wrapper macros should be used.
@@ -300,6 +317,9 @@
OPENSSL_EXPORT size_t sk_insert(_STACK *sk, void *p, size_t where);
OPENSSL_EXPORT void *sk_delete(_STACK *sk, size_t where);
OPENSSL_EXPORT void *sk_delete_ptr(_STACK *sk, const void *p);
+OPENSSL_EXPORT void sk_delete_if(_STACK *sk,
+ OPENSSL_sk_call_delete_if_func call_func,
+ OPENSSL_sk_delete_if_func func, void *data);
OPENSSL_EXPORT int sk_find(const _STACK *sk, size_t *out_index, const void *p,
OPENSSL_sk_call_cmp_func call_cmp_func);
OPENSSL_EXPORT void *sk_shift(_STACK *sk);
@@ -366,7 +386,8 @@
\
typedef void (*sk_##name##_free_func)(ptrtype); \
typedef ptrtype (*sk_##name##_copy_func)(ptrtype); \
- typedef int (*sk_##name##_cmp_func)(constptrtype *a, constptrtype *b); \
+ typedef int (*sk_##name##_cmp_func)(constptrtype *, constptrtype *); \
+ typedef int (*sk_##name##_delete_if_func)(ptrtype, void *); \
\
OPENSSL_INLINE void sk_##name##_call_free_func( \
OPENSSL_sk_free_func free_func, void *ptr) { \
@@ -389,6 +410,11 @@
return ((sk_##name##_cmp_func)cmp_func)(&a_ptr, &b_ptr); \
} \
\
+ OPENSSL_INLINE int sk_##name##_call_delete_if_func( \
+ OPENSSL_sk_delete_if_func func, void *obj, void *data) { \
+ return ((sk_##name##_delete_if_func)func)((ptrtype)obj, data); \
+ } \
+ \
OPENSSL_INLINE STACK_OF(name) *sk_##name##_new(sk_##name##_cmp_func comp) { \
return (STACK_OF(name) *)sk_new((OPENSSL_sk_cmp_func)comp); \
} \
@@ -440,6 +466,12 @@
return (ptrtype)sk_delete_ptr((_STACK *)sk, (const void *)p); \
} \
\
+ OPENSSL_INLINE void sk_##name##_delete_if( \
+ STACK_OF(name) *sk, sk_##name##_delete_if_func func, void *data) { \
+ sk_delete_if((_STACK *)sk, sk_##name##_call_delete_if_func, \
+ (OPENSSL_sk_delete_if_func)func, data); \
+ } \
+ \
OPENSSL_INLINE int sk_##name##_find(const STACK_OF(name) *sk, \
size_t *out_index, constptrtype p) { \
return sk_find((const _STACK *)sk, out_index, (const void *)p, \
