From ad541c67761b8aa6da1566802c347cac4018d0c2 Mon Sep 17 00:00:00 2001 From: Dirk Engling Date: Mon, 2 Nov 2026 20:50:24 +0100 Subject: Move the build sources into src/ --- src/ot_vector.c | 287 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 287 insertions(+) create mode 100644 src/ot_vector.c (limited to 'src/ot_vector.c') diff --git a/src/ot_vector.c b/src/ot_vector.c new file mode 100644 index 0000000..ab0566c --- /dev/null +++ b/src/ot_vector.c @@ -0,0 +1,287 @@ +/* This software was written by Dirk Engling + It is considered beerware. Prost. Skol. Cheers or whatever. */ + +/* System */ +#include +#include +#include +#include + +/* Opentracker */ +#include "trackerlogic.h" + +static int vector_compare_peer6(const void *peer1, const void *peer2) { return memcmp(peer1, peer2, OT_PEER_COMPARE_SIZE6); } +static int vector_compare_peer4(const void *peer1, const void *peer2) { return memcmp(peer1, peer2, OT_PEER_COMPARE_SIZE4); } + +/* This function gives us a binary search that returns a pointer, even if + no exact match is found. In that case it sets exactmatch 0 and gives + calling functions the chance to insert data +*/ +void *vector_binary_search(const void *const key, const void *base, const size_t member_count, const size_t member_size, size_t compare_size, int *exactmatch) { + size_t interval = member_count; + + while (interval) { + uint8_t *lookat = ((uint8_t *)base) + member_size * (interval / 2); + int cmp = memcmp(lookat, key, compare_size); + if (cmp == 0) { + base = lookat; + break; + } + if (cmp < 0) { + base = lookat + member_size; + interval--; + } + interval /= 2; + } + + *exactmatch = interval; + return (void *)base; +} + +static uint8_t vector_hash_peer(ot_peer const *peer, size_t compare_size, size_t bucket_count) { + unsigned int hash = 5381; + uint8_t *p = (uint8_t *)peer; + while (compare_size--) + hash += (hash << 5) + *(p++); + return hash % bucket_count; +} + +/* This is the generic insert operation for our vector type. + It tries to locate the object at "key" with size "member_size" by comparing its first "compare_size" bytes with + those of objects in vector. Our special "vector_binary_search" function does that and either returns the match or a + pointer to where the object is to be inserted. vector_find_or_insert makes space for the object and copies it, + if it wasn't found in vector. Caller needs to check the passed "exactmatch" variable to see, whether an insert + took place. If resizing the vector failed, NULL is returned, else the pointer to the object in vector. +*/ +void *vector_find_or_insert(ot_vector *vector, void *key, size_t member_size, size_t compare_size, int *exactmatch) { + uint8_t *match = vector_binary_search(key, vector->data, vector->size, member_size, compare_size, exactmatch); + size_t match_offset, bytes_after; + + if (*exactmatch) + return match; + + /* Hold the insertion point as an offset rather than a pointer: it survives + the realloc below, and an empty vector has no data pointer to offset from + in the first place */ + match_offset = vector->size ? (size_t)(match - (uint8_t *)vector->data) : 0; + bytes_after = member_size * vector->size - match_offset; + + if (vector->size + 1 > vector->space) { + size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS; + uint8_t *new_data = realloc(vector->data, new_space * member_size); + + if (!new_data) + return NULL; + + vector->data = new_data; + vector->space = new_space; + } + + match = (uint8_t *)vector->data + match_offset; + memmove(match + member_size, match, bytes_after); + + vector->size++; + return match; +} + +ot_peer *vector_find_or_insert_peer(ot_vector *vector, ot_peer const *peer, size_t peer_size, int *exactmatch) { + ot_peer *match; + const size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size); + size_t match_offset, bytes_after; + + /* If space is zero but size is set, we're dealing with a list of vector->size buckets */ + if (vector->space < vector->size) + vector = ((ot_vector *)vector->data) + vector_hash_peer(peer, compare_size, vector->size); + match = vector_binary_search(peer, vector->data, vector->size, peer_size, compare_size, exactmatch); + + if (*exactmatch) + return match; + + /* Hold the insertion point as an offset rather than a pointer: it survives + the realloc below, and an empty vector has no data pointer to offset from + in the first place. bytes_after is what has to move up by peer_size to + make room for the new peer */ + match_offset = vector->size ? (size_t)(match - (ot_peer *)vector->data) : 0; + bytes_after = vector->size * peer_size - match_offset; + + if (vector->size + 1 > vector->space) { + size_t new_space = vector->space ? OT_VECTOR_GROW_RATIO * vector->space : OT_VECTOR_MIN_MEMBERS; + ot_peer *new_data = realloc(vector->data, new_space * peer_size); + + if (!new_data) + return NULL; + + vector->data = new_data; + vector->space = new_space; + } + + match = (ot_peer *)vector->data + match_offset; + memmove(match + peer_size, match, bytes_after); + + vector->size++; + return match; +} + +/* This is the non-generic delete from vector-operation specialized for peers in pools. + It returns 0 if no peer was found (and thus not removed) + 1 if a non-seeding peer was removed + 2 if a seeding peer was removed +*/ +int vector_remove_peer(ot_vector *vector, ot_peer const *peer, size_t peer_size) { + int exactmatch, was_seeder; + ot_peer *match, *end; + size_t compare_size = OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size); + + if (!vector->size) + return 0; + + /* If space is zero but size is set, we're dealing with a list of vector->size buckets */ + if (vector->space < vector->size) + vector = ((ot_vector *)vector->data) + vector_hash_peer(peer, compare_size, vector->size); + + end = ((ot_peer *)vector->data) + peer_size * vector->size; + match = (ot_peer *)vector_binary_search(peer, vector->data, vector->size, peer_size, compare_size, &exactmatch); + if (!exactmatch) + return 0; + + was_seeder = (OT_PEERFLAG_D(match, peer_size) & PEER_FLAG_SEEDING) ? 2 : 1; + memmove(match, match + peer_size, end - match - peer_size); + + vector->size--; + vector_fixup_peers(vector, peer_size); + return was_seeder; +} + +void vector_remove_torrent(ot_vector *vector, ot_torrent *match) { + ot_torrent *end; + + if (!vector->size) + return; + + end = ((ot_torrent *)vector->data) + vector->size; + + free_peerlist(match->peer_list6); + free_peerlist(match->peer_list4); + + memmove(match, match + 1, sizeof(ot_torrent) * (end - match - 1)); + if ((--vector->size * OT_VECTOR_SHRINK_THRESH < vector->space) && (vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS)) { + vector->space /= OT_VECTOR_SHRINK_RATIO; + vector->data = realloc(vector->data, vector->space * sizeof(ot_torrent)); + } +} + +void vector_clean_list(ot_vector *vector, size_t num_buckets) { + while (num_buckets--) + free(vector[num_buckets].data); + free(vector); + return; +} + +void vector_redistribute_buckets(ot_peerlist *peer_list, size_t peer_size) { + size_t bucket, bucket_size_new, num_buckets_new, num_buckets_old = 1; + ot_vector *bucket_list_new, *bucket_list_old = &peer_list->peers; + int (*sort_func)(const void *, const void *) = peer_size == OT_PEER_SIZE6 ? &vector_compare_peer6 : &vector_compare_peer4; + + if (OT_PEERLIST_HASBUCKETS(peer_list)) { + num_buckets_old = peer_list->peers.size; + bucket_list_old = peer_list->peers.data; + } + + if (peer_list->peer_count < 255) + num_buckets_new = 1; + else if (peer_list->peer_count > 8192) + num_buckets_new = 64; + else if (peer_list->peer_count >= 512 && peer_list->peer_count < 4096) + num_buckets_new = 16; + else if (peer_list->peer_count < 512 && num_buckets_old <= 16) + num_buckets_new = num_buckets_old; + else if (peer_list->peer_count < 512) + num_buckets_new = 1; + else if (peer_list->peer_count < 8192 && num_buckets_old > 1) + num_buckets_new = num_buckets_old; + else + num_buckets_new = 16; + + if (num_buckets_new == num_buckets_old) + return; + + /* Assume near perfect distribution */ + bucket_list_new = calloc(1, num_buckets_new * sizeof(ot_vector)); + if (!bucket_list_new) + return; + + bucket_size_new = OT_VECTOR_MIN_MEMBERS; + while (bucket_size_new * num_buckets_new < peer_list->peer_count) + bucket_size_new *= OT_VECTOR_GROW_RATIO; + + /* preallocate vectors to hold all peers */ + for (bucket = 0; bucket < num_buckets_new; ++bucket) { + bucket_list_new[bucket].space = bucket_size_new; + bucket_list_new[bucket].data = malloc(bucket_size_new * peer_size); + if (!bucket_list_new[bucket].data) { + vector_clean_list(bucket_list_new, num_buckets_new); + return; + } + } + + /* Now sort them into the correct bucket */ + for (bucket = 0; bucket < num_buckets_old; ++bucket) { + ot_peer *peers_old = bucket_list_old[bucket].data; + size_t peer_count_old = bucket_list_old[bucket].size; + while (peer_count_old--) { + ot_vector *bucket_dest = bucket_list_new; + if (num_buckets_new > 1) + bucket_dest += vector_hash_peer(peers_old, OT_PEER_COMPARE_SIZE_FROM_PEER_SIZE(peer_size), num_buckets_new); + if (bucket_dest->size + 1 > bucket_dest->space) { + void *tmp = realloc(bucket_dest->data, peer_size * OT_VECTOR_GROW_RATIO * bucket_dest->space); + if (!tmp) { + vector_clean_list(bucket_list_new, num_buckets_new); + return; + } + bucket_dest->data = tmp; + bucket_dest->space *= OT_VECTOR_GROW_RATIO; + } + memcpy((ot_peer *)bucket_dest->data + peer_size * bucket_dest->size++, peers_old, peer_size); + peers_old += peer_size; + } + } + + /* Now sort each bucket to later allow bsearch */ + for (bucket = 0; bucket < num_buckets_new; ++bucket) + qsort(bucket_list_new[bucket].data, bucket_list_new[bucket].size, peer_size, sort_func); + + /* Everything worked fine. Now link new bucket_list to peer_list */ + if (OT_PEERLIST_HASBUCKETS(peer_list)) + vector_clean_list((ot_vector *)peer_list->peers.data, peer_list->peers.size); + else + free(peer_list->peers.data); + + if (num_buckets_new > 1) { + peer_list->peers.data = bucket_list_new; + peer_list->peers.size = num_buckets_new; + peer_list->peers.space = 0; /* Magic marker for "is list of buckets" */ + } else { + peer_list->peers.data = bucket_list_new->data; + peer_list->peers.size = bucket_list_new->size; + peer_list->peers.space = bucket_list_new->space; + free(bucket_list_new); + } +} + +void vector_fixup_peers(ot_vector *vector, size_t peer_size) { + int need_fix = 0; + + if (!vector->size) { + free(vector->data); + vector->data = NULL; + vector->space = 0; + return; + } + + while ((vector->size * OT_VECTOR_SHRINK_THRESH < vector->space) && (vector->space >= OT_VECTOR_SHRINK_RATIO * OT_VECTOR_MIN_MEMBERS)) { + vector->space /= OT_VECTOR_SHRINK_RATIO; + need_fix++; + } + if (need_fix) + vector->data = realloc(vector->data, vector->space * peer_size); +} -- cgit v1.3