From 12eeb35015aba138a4e543c28c2ecee58d532440 Mon Sep 17 00:00:00 2001 From: Mistivia Date: Mon, 9 Jun 2025 01:42:18 +0800 Subject: pass by value in basic traits --- src/basic_traits.c | 28 +++++++++++------------ src/basic_traits.h | 6 ++--- src/hash_table.c | 6 ++--- src/hash_table.h | 34 +++++++++++++++++----------- src/pqueue.h | 6 ++--- src/sort.h | 12 +++++----- src/type_alias.h | 3 --- src/vec.h | 12 +++++----- tests/test_htable.c | 15 +++++++------ tests/test_pque.c | 64 ----------------------------------------------------- tests/test_pqueue.c | 8 +++---- tests/test_vec.c | 2 +- 12 files changed, 69 insertions(+), 127 deletions(-) delete mode 100644 tests/test_pque.c diff --git a/src/basic_traits.c b/src/basic_traits.c index e3e6b1b..d46de15 100644 --- a/src/basic_traits.c +++ b/src/basic_traits.c @@ -5,16 +5,16 @@ #include "mmhash.h" #define BASIC_TRAITS_IMPL(T) \ - bool T##_eq(T* lhs, T* rhs) { \ - return *lhs == *rhs; \ + bool T##_eq(T lhs, T rhs) { \ + return lhs == rhs; \ } \ - int T##_cmp(T* lhs, T* rhs) { \ - if (*lhs == *rhs) return 0; \ - if (*lhs < *rhs) return -1; \ + int T##_cmp(T lhs, T rhs) { \ + if (lhs == rhs) return 0; \ + if (lhs < rhs) return -1; \ return 1; \ } \ - uint64_t T##_hash(T* x) { \ - return mmhash(x, sizeof(T), 0); \ + uint64_t T##_hash(T x) { \ + return mmhash(&x, sizeof(T), 0); \ } BASIC_TRAITS_IMPL(Char); @@ -27,17 +27,17 @@ BASIC_TRAITS_IMPL(Double); BASIC_TRAITS_IMPL(Float); BASIC_TRAITS_IMPL(VoidPtr); -bool String_eq(String* lhs, String *rhs) { - return strcmp(*lhs, *rhs) == 0; +bool String_eq(String lhs, String rhs) { + return strcmp(lhs, rhs) == 0; } -int String_cmp(String* lhs, String *rhs) { - return strcmp(*lhs, *rhs); +int String_cmp(String lhs, String rhs) { + return strcmp(lhs, rhs); } -ULong String_hash(String *x) { - size_t len = strlen(*x); - return mmhash(*x, len, 0); +ULong String_hash(String x) { + size_t len = strlen(x); + return mmhash(x, len, 0); } diff --git a/src/basic_traits.h b/src/basic_traits.h index 7c70863..700a49a 100644 --- a/src/basic_traits.h +++ b/src/basic_traits.h @@ -5,9 +5,9 @@ // basic traits #define BASIC_TRAITS_DEF(T) \ - Bool T##_eq(T* lhs, T* rhs); \ - Int T##_cmp(T* lhs, T* rhs); \ - ULong T##_hash(T* x); + Bool T##_eq(T lhs, T rhs); \ + Int T##_cmp(T lhs, T rhs); \ + ULong T##_hash(T x); BASIC_TRAITS_DEF(Int); BASIC_TRAITS_DEF(Bool); diff --git a/src/hash_table.c b/src/hash_table.c index 0e7bd41..c768df8 100644 --- a/src/hash_table.c +++ b/src/hash_table.c @@ -19,7 +19,7 @@ HASH_TABLE_IMPL(VoidPtr, Int); HASH_TABLE_IMPL(VoidPtr, String); -static void rebuild(HashTable *ht, VoidHashFn hash, VoidEqFn eq) { +static void rebuild(HashTable *ht, uint64_t (*hash)(void*), bool (*eq)(void*, void*)) { HashTable newht; init_hash_table(&newht, ht->elemsz, ht->size * 6); void *iter = hash_table_begin(ht); @@ -44,7 +44,7 @@ void init_hash_table(HashTable *ht, int64_t elemsz, int64_t cap) { ht->elemsz = elemsz; } -bool hash_table_insert(HashTable *ht, void *elem, VoidHashFn hash, VoidEqFn eq) { +bool hash_table_insert(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)) { if (ht->taken + 1 > ht->cap / 2) { rebuild(ht, hash, eq); } @@ -76,7 +76,7 @@ void *hash_table_ref(HashTable *ht, int64_t pos) { return ht->buf + pos * ht->elemsz; } -void *hash_table_find(HashTable *ht, void *elem, VoidHashFn hash, VoidEqFn eq) { +void *hash_table_find(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)) { int64_t pos = hash(elem) % ht->cap; while (ht->flagbuf[pos] != HTFL_NUL) { if (ht->flagbuf[pos] == HTFL_VAL diff --git a/src/hash_table.h b/src/hash_table.h index 429142c..ba42628 100644 --- a/src/hash_table.h +++ b/src/hash_table.h @@ -26,30 +26,38 @@ typedef struct hash_table HashTable; HashTable ht; \ } K##2##V##HashTable; \ void K##2##V##HashTable_init(K##2##V##HashTable *self); \ - bool K##2##V##HashTable_insert(K##2##V##HashTable *self, K *key, V *value); \ + bool K##2##V##HashTable_insert(K##2##V##HashTable *self, K key, V value); \ void K##2##V##HashTable_remove(K##2##V##HashTable *ht, K##2##V##HashTableIter iter); \ - V* K##2##V##HashTable_get(K##2##V##HashTable *self, K *key); \ - K##2##V##HashTableIter K##2##V##HashTable_find(K##2##V##HashTable *self, K *key); \ + V* K##2##V##HashTable_get(K##2##V##HashTable *self, K key); \ + K##2##V##HashTableIter K##2##V##HashTable_find(K##2##V##HashTable *self, K key); \ K##2##V##HashTableIter K##2##V##HashTable_begin(K##2##V##HashTable *self); \ K##2##V##HashTableIter K##2##V##HashTable_next(K##2##V##HashTable *self, K##2##V##HashTableIter iter); \ void K##2##V##HashTable_free(K##2##V##HashTable *self); \ K##2##V##HashTable K##2##V##HashTable_move(K##2##V##HashTable *self); \ #define HASH_TABLE_IMPL(K, V) \ + static uint64_t K##2##V##HashTable_hash(void *vk) { \ + K *k = vk; \ + return K##_hash(*k); \ + } \ + static bool K##2##V##HashTable_eq(void *vk1, void *vk2) { \ + K *k1 = vk1, *k2 = vk2; \ + return K##_eq(*k1, *k2); \ + } \ void K##2##V##HashTable_init(K##2##V##HashTable *self) { \ init_hash_table(&self->ht, sizeof(K##2##V##HashTableEntry), 16); \ } \ - bool K##2##V##HashTable_insert(K##2##V##HashTable *self, K *key, V *value) { \ + bool K##2##V##HashTable_insert(K##2##V##HashTable *self, K key, V value) { \ K##2##V##HashTableEntry entry; \ - memcpy(&entry.key, key, sizeof(K)); \ - memcpy(&entry.val, value, sizeof(K)); \ - return hash_table_insert(&self->ht, &entry, (VoidHashFn)K##_hash, (VoidEqFn)K##_eq); \ + entry.key = key; \ + entry.val = value; \ + return hash_table_insert(&self->ht, &entry, K##2##V##HashTable_hash, K##2##V##HashTable_eq); \ } \ - K##2##V##HashTableIter K##2##V##HashTable_find(K##2##V##HashTable *self, K *key) { \ - return hash_table_find(&self->ht, key, (VoidHashFn)K##_hash, (VoidEqFn)K##_eq); \ + K##2##V##HashTableIter K##2##V##HashTable_find(K##2##V##HashTable *self, K key) { \ + return hash_table_find(&self->ht, &key, K##2##V##HashTable_hash, K##2##V##HashTable_eq); \ } \ - V* K##2##V##HashTable_get(K##2##V##HashTable *self, K *key) { \ - K##2##V##HashTableEntry* entry = hash_table_find(&self->ht, key, (VoidHashFn)K##_hash, (VoidEqFn)K##_eq); \ + V* K##2##V##HashTable_get(K##2##V##HashTable *self, K key) { \ + K##2##V##HashTableEntry* entry = hash_table_find(&self->ht, &key, K##2##V##HashTable_hash, K##2##V##HashTable_eq); \ if (entry == NULL) return NULL; \ return &(entry->val); \ } \ @@ -86,9 +94,9 @@ HASH_TABLE_DEF(VoidPtr, Int); HASH_TABLE_DEF(VoidPtr, String); void init_hash_table(HashTable *ht, int64_t elemsz, int64_t cap); -bool hash_table_insert(HashTable *ht, void *elem, VoidHashFn hash, VoidEqFn eq); +bool hash_table_insert(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)); void hash_table_remove(HashTable *ht, void *iter); -void *hash_table_find(HashTable *ht, void *elem, VoidHashFn hash, VoidEqFn eq); +void *hash_table_find(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)); void *hash_table_begin(HashTable *ht); void *hash_table_next(HashTable *ht, void *iter); void destroy_hash_table(HashTable *ht); diff --git a/src/pqueue.h b/src/pqueue.h index d91b9a2..2cf78ec 100644 --- a/src/pqueue.h +++ b/src/pqueue.h @@ -8,7 +8,7 @@ T##Vector vec; \ } T##PQueue; \ void T##PQueue_init(T##PQueue *self); \ - void T##PQueue_push(T##PQueue *self, T *elem); \ + void T##PQueue_push(T##PQueue *self, T elem); \ void T##PQueue_pop(T##PQueue *self); \ T* T##PQueue_top(T##PQueue *self); \ T##PQueue T##PQueue_move(T##PQueue *self); \ @@ -27,12 +27,12 @@ PQUEUE_DEF(VoidPtr); #define PQUEUE_IMPL(T) \ static int T##PQueue_cmp(T##PQueue *self, int a, int b) { \ - return T##_cmp(T##Vector_ref(&self->vec, a), T##Vector_ref(&self->vec, b)); \ + return T##_cmp(*T##Vector_ref(&self->vec, a), *T##Vector_ref(&self->vec, b)); \ } \ void T##PQueue_init(T##PQueue *self) { \ T##Vector_init(&self->vec); \ } \ - void T##PQueue_push(T##PQueue *self, T *elem) { \ + void T##PQueue_push(T##PQueue *self, T elem) { \ T##Vector_push_back(&self->vec, elem); \ int i = self->vec.size - 1; \ while (i > 0 && T##PQueue_cmp(self, i, i / 2) > 0) { \ diff --git a/src/sort.h b/src/sort.h index 64a5b3e..9266093 100644 --- a/src/sort.h +++ b/src/sort.h @@ -13,9 +13,9 @@ void T##_qsort_swap(T* arr, int lhs, int rhs) { \ if (lhs == rhs) return; \ T buf; \ - memcpy(&buf, arr+lhs, sizeof(T)); \ - memcpy(arr+lhs, arr+rhs, sizeof(T)); \ - memcpy(arr+rhs, &buf, sizeof(T)); \ + buf = arr[lhs]; \ + arr[lhs] = arr[rhs]; \ + arr[rhs] = buf; \ } \ void T##_qsort(T* arr, int n) { \ if (n <= 1) return; \ @@ -23,11 +23,11 @@ T##_qsort_swap(arr, 0, pivot); \ int lp = 1, rp = n-1; \ while (lp < rp) { \ - if (T##_cmp(arr+lp, arr) < 0) { \ + if (T##_cmp(arr[lp], arr[0]) < 0) { \ lp++; \ continue; \ } \ - if (T##_cmp(arr+rp, arr) >= 0) { \ + if (T##_cmp(arr[rp], arr[0]) >= 0) { \ rp--; \ continue; \ } \ @@ -35,7 +35,7 @@ lp++; \ rp--; \ } \ - if (T##_cmp(arr + rp, arr) > 0) rp--; \ + if (T##_cmp(arr[rp], arr[0]) > 0) rp--; \ T##_qsort_swap(arr, 0, rp); \ T##_qsort(arr, rp); \ T##_qsort(arr+rp+1, n-rp-1); \ diff --git a/src/type_alias.h b/src/type_alias.h index 7af783a..8f818ed 100644 --- a/src/type_alias.h +++ b/src/type_alias.h @@ -15,8 +15,5 @@ typedef double Double; typedef const char *String; typedef const void *VoidPtr; -typedef uint64_t (*VoidHashFn)(void*); -typedef bool (*VoidEqFn)(void*, void*); -typedef int (*VoidCmpFn)(void*, void*); #endif diff --git a/src/vec.h b/src/vec.h index f2d9712..ba235e1 100644 --- a/src/vec.h +++ b/src/vec.h @@ -13,8 +13,8 @@ } T##Vector; \ \ void T##Vector_init(T##Vector *self); \ - void T##Vector_push_back(T##Vector *self, T *elem); \ - void T##Vector_insert_before(T##Vector *self, int n, T *elem); \ + void T##Vector_push_back(T##Vector *self, T elem); \ + void T##Vector_insert_before(T##Vector *self, int n, T elem); \ void T##Vector_pop(T##Vector *self); \ void T##Vector_remove(T##Vector *self, size_t n); \ size_t T##Vector_len(T##Vector *self); \ @@ -32,15 +32,15 @@ self->size = 0; \ } \ \ - void T##Vector_push_back(T##Vector *self, T *elem) { \ + void T##Vector_push_back(T##Vector *self, T elem) { \ if (self->size + 1 > self->cap) { \ self->buffer = realloc(self->buffer, sizeof(T) * self->cap * 2); \ self->cap *= 2; \ } \ - memmove(self->buffer + self->size, elem, sizeof(T)); \ + self->buffer[self->size] = elem; \ self->size += 1; \ } \ - void T##Vector_insert_before(T##Vector *self, int n, T *elem) { \ + void T##Vector_insert_before(T##Vector *self, int n, T elem) { \ if (n < 0 || n > self->size) { \ return; \ } \ @@ -52,7 +52,7 @@ memmove(self->buffer + n + 1, \ self->buffer + n, \ sizeof(T) * (self->size - n)); \ - memmove(self->buffer + n, elem, sizeof(T)); \ + self->buffer[n] = elem; \ } \ } \ void T##Vector_pop(T##Vector *self) { \ diff --git a/tests/test_htable.c b/tests/test_htable.c index 3608b5c..3dee2d3 100644 --- a/tests/test_htable.c +++ b/tests/test_htable.c @@ -13,16 +13,17 @@ int main() { Int2IntHashTable ht; Int2IntHashTable_init(&ht); for (int i = 0; i < 10000; i++) { - Int2IntHashTable_insert(&ht, &i, &i); + Int2IntHashTable_insert(&ht, i, i*2); assert(ht.ht.size == i + 1); assert(ht.ht.taken == i + 1); assert(ht.ht.cap >= i + 1); } for (int i = 0; i < 10000; i++) { - assert(Int2IntHashTable_get(&ht, &i) != NULL); + assert(Int2IntHashTable_get(&ht, i) != NULL); + assert(*Int2IntHashTable_get(&ht, i) == i * 2); int t = 10000 + i; - assert(Int2IntHashTable_get(&ht, &t) == NULL); + assert(Int2IntHashTable_get(&ht, t) == NULL); } memset(found, 0, sizeof(bool) * 10000); @@ -36,17 +37,17 @@ int main() { } for (int i = 0; i < 5000; i++) { - Int2IntHashTableIter iter = Int2IntHashTable_find(&ht, &i); + Int2IntHashTableIter iter = Int2IntHashTable_find(&ht, i); Int2IntHashTable_remove(&ht, iter); } for (int i = 0; i < 5000; i++) { - assert(Int2IntHashTable_find(&ht, &i) == NULL); + assert(Int2IntHashTable_find(&ht, i) == NULL); int t = 5000 + i; - assert(Int2IntHashTable_find(&ht, &t) != NULL); + assert(Int2IntHashTable_find(&ht, t) != NULL); } for (int i = 0; i < 5000; i++) { - Int2IntHashTable_insert(&ht, &i, &i); + Int2IntHashTable_insert(&ht, i, i); } memset(found, 0, sizeof(bool) * 10000); diff --git a/tests/test_pque.c b/tests/test_pque.c deleted file mode 100644 index 6503174..0000000 --- a/tests/test_pque.c +++ /dev/null @@ -1,64 +0,0 @@ -#include -#include -#include -#include - -#include "pqueue.h" -#include "basic_traits.h" - -typedef Int MinInt; - -int MinInt_cmp(Int *lhs, Int *rhs) { - return -Int_cmp(lhs, rhs); -} - -VECTOR_DEF(MinInt); -VECTOR_IMPL(MinInt); - -PQUEUE_DEF(MinInt); -PQUEUE_IMPL(MinInt); - -int main() { - printf("[TEST] pqueue\n"); - - IntPQueue pq; - IntPQueue_init(&pq); - int elems[10] = {1, 3, 2, 4, 6, 5, 9, 7, 8, 10}; - for (int i = 0; i < 10; i++) { - int e = elems[i]; - IntPQueue_push(&pq, &e); - } - for (int i = 10; i >= 1; i--) { - int *top = IntPQueue_top(&pq); - assert(i == *top); - IntPQueue_pop(&pq); - } - assert(IntPQueue_top(&pq) == NULL); - - - MinIntPQueue minpq; - MinIntPQueue_init(&minpq); - for (int i = 0; i < 10; i++) { - int e = elems[i]; - MinIntPQueue_push(&minpq, &e); - } - for (int i = 1; i <= 10; i++) { - int *top = MinIntPQueue_top(&minpq); - assert(i == *top); - MinIntPQueue_pop(&minpq); - } - assert(MinIntPQueue_top(&minpq) == NULL); - MinIntVector_free(&minpq.vec); - - int elems2[10] = {-10, -8, -7, -9, -5, -6, -4, -2, -3, -1}; - int expected[10] = {-10, -8, -7, -7, -5, -5, -4, -2, -2, -1}; - for (int i = 0; i < 10; i++) { - int e = elems2[i]; - IntPQueue_push(&pq, &e); - int *top = IntPQueue_top(&pq); - assert(*top == expected[i]); - } - IntVector_free(&pq.vec); - printf("[PASS] pqueue\n"); - return 0; -} diff --git a/tests/test_pqueue.c b/tests/test_pqueue.c index 6503174..436a583 100644 --- a/tests/test_pqueue.c +++ b/tests/test_pqueue.c @@ -8,7 +8,7 @@ typedef Int MinInt; -int MinInt_cmp(Int *lhs, Int *rhs) { +int MinInt_cmp(Int lhs, Int rhs) { return -Int_cmp(lhs, rhs); } @@ -26,7 +26,7 @@ int main() { int elems[10] = {1, 3, 2, 4, 6, 5, 9, 7, 8, 10}; for (int i = 0; i < 10; i++) { int e = elems[i]; - IntPQueue_push(&pq, &e); + IntPQueue_push(&pq, e); } for (int i = 10; i >= 1; i--) { int *top = IntPQueue_top(&pq); @@ -40,7 +40,7 @@ int main() { MinIntPQueue_init(&minpq); for (int i = 0; i < 10; i++) { int e = elems[i]; - MinIntPQueue_push(&minpq, &e); + MinIntPQueue_push(&minpq, e); } for (int i = 1; i <= 10; i++) { int *top = MinIntPQueue_top(&minpq); @@ -54,7 +54,7 @@ int main() { int expected[10] = {-10, -8, -7, -7, -5, -5, -4, -2, -2, -1}; for (int i = 0; i < 10; i++) { int e = elems2[i]; - IntPQueue_push(&pq, &e); + IntPQueue_push(&pq, e); int *top = IntPQueue_top(&pq); assert(*top == expected[i]); } diff --git a/tests/test_vec.c b/tests/test_vec.c index 4cbc96f..6abdd78 100644 --- a/tests/test_vec.c +++ b/tests/test_vec.c @@ -11,7 +11,7 @@ int main() { for (int i = 0; i < 1000; i++) { assert(vec.size == i); - IntVector_push_back(&vec, &i); + IntVector_push_back(&vec, i); assert(*(IntVector_end(&vec) - 1) == i); } assert(*IntVector_begin(&vec) == 0); -- cgit v1.0