From 04107408ecd2adf031abb286c4c5b7d5cc0c3c9d Mon Sep 17 00:00:00 2001 From: hgn Date: Thu, 18 Aug 2022 00:59:03 +0100 Subject: [PATCH] stuff --- src/vg/vg_io.h | 16 ++- src/vg/vg_steam_networking.h | 22 +-- src/vg/vg_store.h | 272 ++++++++++++++++++++++++----------- 3 files changed, 220 insertions(+), 90 deletions(-) diff --git a/src/vg/vg_io.h b/src/vg/vg_io.h index 56e6219..2650b3f 100644 --- a/src/vg/vg_io.h +++ b/src/vg/vg_io.h @@ -1,5 +1,15 @@ /* Copyright (C) 2021-2022 Harry Godden (hgn) - All Rights Reserved */ +#ifndef VG_IO_H +#define VG_IO_H + +#include "vg_stdint.h" +#include "vg_platform.h" +#include +#include +#include +#include + #define KNRM "\x1B[0m" #define KRED "\x1B[31m" #define KGRN "\x1B[32m" @@ -25,7 +35,7 @@ static void vg_log_write( FILE *file, const char *prefix, break; } - j = i + vsnprintf( buffer + i, vg_list_size( buffer ) - i -2, fmt, args ); + j = i + vsnprintf( buffer + i, vg_list_size( buffer ) - i -12, fmt, args ); strcpy( buffer + j, KNRM ); fputs( buffer, file ); @@ -95,7 +105,7 @@ static char *vg_disk_load_text( const char *path, i64 *size ) char *buf; i64 fsize; - if( (buf = vg_disk_open_read( path, 1, &fsize )) ) + if( (buf = (char *)vg_disk_open_read( path, 1, &fsize )) ) { buf[ fsize ] = 0x00; *size = fsize +1; @@ -142,3 +152,5 @@ static int vg_asset_write( const char *path, void *data, i64 size ) return 0; } } + +#endif /* VG_IO_H */ diff --git a/src/vg/vg_steam_networking.h b/src/vg/vg_steam_networking.h index 874bc9e..679fe89 100644 --- a/src/vg/vg_steam_networking.h +++ b/src/vg/vg_steam_networking.h @@ -9,7 +9,6 @@ #pragma pack(push,8) #endif -typedef enum ESteamNetworkingConfigScope ESteamNetworkingConfigScope; enum ESteamNetworkingConfigScope { k_ESteamNetworkingConfig_Global = 1, @@ -18,8 +17,8 @@ enum ESteamNetworkingConfigScope k_ESteamNetworkingConfig_Connection = 4, k_ESteamNetworkingConfigScope__Force32Bit = 0x7fffffff }; +typedef enum ESteamNetworkingConfigScope ESteamNetworkingConfigScope; -typedef enum ESteamNetworkingConfigDataType ESteamNetworkingConfigDataType; enum ESteamNetworkingConfigDataType { k_ESteamNetworkingConfig_Int32 = 1, @@ -30,8 +29,8 @@ enum ESteamNetworkingConfigDataType k_ESteamNetworkingConfigDataType__Force32Bit = 0x7fffffff }; +typedef enum ESteamNetworkingConfigDataType ESteamNetworkingConfigDataType; -typedef enum ESteamNetworkingConfigValue ESteamNetworkingConfigValue; enum ESteamNetworkingConfigValue { k_ESteamNetworkingConfig_Invalid = 0, @@ -93,9 +92,9 @@ enum ESteamNetworkingConfigValue k_ESteamNetworkingConfig_DELETED_EnumerateDevVars = 35, k_ESteamNetworkingConfigValue__Force32Bit = 0x7fffffff }; +typedef enum ESteamNetworkingConfigValue ESteamNetworkingConfigValue; -typedef enum ESteamNetworkingConnectionState ESteamNetworkingConnectionState; enum ESteamNetworkingConnectionState { k_ESteamNetworkingConnectionState_None = 0, @@ -109,8 +108,8 @@ enum ESteamNetworkingConnectionState k_ESteamNetworkingConnectionState_Dead = -3, k_ESteamNetworkingConnectionState__Force32Bit = 0x7fffffff }; +typedef enum ESteamNetworkingConnectionState ESteamNetworkingConnectionState; -typedef enum ESteamNetConnectionEnd ESteamNetConnectionEnd; enum ESteamNetConnectionEnd { k_ESteamNetConnectionEnd_Invalid = 0, @@ -152,8 +151,8 @@ enum ESteamNetConnectionEnd k_ESteamNetConnectionEnd_Misc_Max = 5999, k_ESteamNetConnectionEnd__Force32Bit = 0x7fffffff }; +typedef enum ESteamNetConnectionEnd ESteamNetConnectionEnd; -typedef enum ESteamNetworkingIdentityType ESteamNetworkingIdentityType; enum ESteamNetworkingIdentityType { k_ESteamNetworkingIdentityType_Invalid = 0, @@ -164,8 +163,8 @@ enum ESteamNetworkingIdentityType k_ESteamNetworkingIdentityType_UnknownType = 4, k_ESteamNetworkingIdentityType__Force32bit = 0x7fffffff, }; +typedef enum ESteamNetworkingIdentityType ESteamNetworkingIdentityType; -typedef enum ESteamNetworkingAvailability ESteamNetworkingAvailability; enum ESteamNetworkingAvailability { k_ESteamNetworkingAvailability_CannotTry = -102, @@ -179,6 +178,7 @@ enum ESteamNetworkingAvailability k_ESteamNetworkingAvailability_Unknown = 0, k_ESteamNetworkingAvailability__Force32bit = 0x7fffffff, }; +typedef enum ESteamNetworkingAvailability ESteamNetworkingAvailability; /* Handle used to identify a connection to a remote host. */ typedef u32 HSteamNetConnection; @@ -244,7 +244,6 @@ struct SteamNetworkingIdentity * "Fake IPs" are assigned to hosts, to make it easier to interface with * older code that assumed all hosts will have an IPv4 address */ -typedef enum ESteamNetworkingFakeIPType ESteamNetworkingFakeIPType; enum ESteamNetworkingFakeIPType { k_ESteamNetworkingFakeIPType_Invalid, @@ -253,6 +252,7 @@ enum ESteamNetworkingFakeIPType k_ESteamNetworkingFakeIPType_LocalIPv4, k_ESteamNetworkingFakeIPType__Force32Bit = 0x7fffffff }; +typedef enum ESteamNetworkingFakeIPType ESteamNetworkingFakeIPType; /* Set everything to zero. E.g. [::]:0 */ void SteamAPI_SteamNetworkingIPAddr_Clear( SteamNetworkingIPAddr* self ); @@ -594,6 +594,12 @@ int SteamAPI_ISteamNetworkingSockets_GetDetailedConnectionStatus( ISteamNetworkingSockets* self, HSteamNetConnection hConn, char *pszBuf, int cbBuf ); +int SteamAPI_ISteamNetworkingSockets_SetConnectionUserData( + ISteamNetworkingSockets* self, HSteamNetConnection hPeer, i64 nUserData ); + +i64 SteamAPI_ISteamNetworkingSockets_GetConnectionUserData( + ISteamNetworkingSockets* self, HSteamNetConnection hPeer ); + int SteamAPI_ISteamNetworkingSockets_GetListenSocketAddress( ISteamNetworkingSockets* self, HSteamListenSocket hSocket, SteamNetworkingIPAddr *address ); diff --git a/src/vg/vg_store.h b/src/vg/vg_store.h index 0bbec25..075695e 100644 --- a/src/vg/vg_store.h +++ b/src/vg/vg_store.h @@ -1,8 +1,19 @@ #ifndef VG_STORE_H #define VG_STORE_H +#include "vg_stdint.h" +#include "vg_io.h" + +/* + * Anderson tree implementation with extensions: + * parents are kept track of + * duplicates are allowed + * data is never allocated or destroyed here + */ + typedef struct aatree aatree; typedef struct aatree_node aatree_node; +typedef struct aatree_pool_node aatree_pool_node; typedef u32 aatree_ptr; #define AATREE_PTR_NIL 0xffffffff @@ -13,23 +24,67 @@ struct aatree void *base; int (*p_cmp)( void *a, void *b ); - int (*p_cmpv)( void *a, void *v ); }; +#pragma pack(push,1) struct aatree_node { aatree_ptr left, right, parent; u32 level, count; }; +struct aatree_pool_node +{ + aatree_ptr next_free; +}; +#pragma pack(pop) + +/* api + * ===========================================================================*/ + +/* return a pointer to the start of the data referenced by t */ +static void *aatree_get_data( aatree *tree, aatree_ptr t ); + +/* link node x into the tree with root t */ +static aatree_ptr aatree_insert( aatree *tree, aatree_ptr t, aatree_ptr x ); + +/* delete node x from tree, does not free memory */ +static aatree_ptr aatree_del( aatree *tree, aatree_ptr x ); + +/* get pointer to element in tree with index k */ +static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k ); + +/* get pointer to the element above x */ +static aatree_ptr aatree_next( aatree *tree, aatree_ptr x ); + +/* get pointer by value, returns NIL if not found. + * + * if duplicates values are present then the result is undefined, but it will be + * AN node with that value, just maybe not the first lexicographically + */ +static aatree_ptr aatree_find( aatree *tree, aatree_ptr t, void *value ); + +/* implementation + * ===========================================================================*/ + static void *aatree_get_data( aatree *tree, aatree_ptr t ) { - return tree->base + tree->stride*t; + return (u8 *)tree->base + tree->stride*t; +} + +static u8 *aatree_node_base( aatree *tree, aatree_ptr t ) +{ + return (u8 *)tree->base + tree->stride*t + tree->offset; +} + +static aatree_pool_node *aatree_get_pool_node( aatree *tree, aatree_ptr t ) +{ + return (aatree_pool_node *)aatree_node_base( tree, t ); } static aatree_node *aatree_get_node( aatree *tree, aatree_ptr t ) { - return tree->base + tree->stride*t + tree->offset; + return (aatree_node *)aatree_node_base( tree, t ); } static void aatree_recount( aatree *tree, aatree_ptr n ) @@ -67,9 +122,6 @@ static aatree_ptr aatree_skew( aatree *tree, u32 t ) aatree_recount( tree, t ); aatree_recount( tree, l ); - /* B's parent is now T, - * T's parent is now L, - * L's parent is now T's old parent */ plnode->parent = ptnode->parent; ptnode->parent = l; if( ptnode->left != AATREE_PTR_NIL ) @@ -110,9 +162,6 @@ static aatree_ptr aatree_split( aatree *tree, aatree_ptr t ) aatree_recount( tree, t ); aatree_recount( tree, r ); - /* B's parent is now T, - * T's parent is now R, - * R's parent is now T's old parent */ prnode->parent = ptnode->parent; ptnode->parent = r; if( ptnode->right != AATREE_PTR_NIL ) @@ -124,8 +173,6 @@ static aatree_ptr aatree_split( aatree *tree, aatree_ptr t ) return t; } -static int aatree_verify( aatree *tree, aatree_ptr t ); - static aatree_ptr aatree_insert( aatree *tree, aatree_ptr t, aatree_ptr x ) { aatree_node *pxnode = aatree_get_node( tree, x ); @@ -143,7 +190,7 @@ static aatree_ptr aatree_insert( aatree *tree, aatree_ptr t, aatree_ptr x ) aatree_node *ptnode = aatree_get_node( tree, t ); int cmp_result = tree->p_cmp( aatree_get_data( tree, t ), aatree_get_data( tree, x ) ); - + ptnode->count ++; if( cmp_result <= 0 ) @@ -173,25 +220,46 @@ static void aatree_link_down( aatree *tree, aatree_ptr p, aatree_ptr *pl, aatree_get_node( tree, *pl )->parent = p; } -static aatree_ptr aatree_del( aatree *tree, aatree_ptr x ) +static aatree_ptr aatree_copy_links( aatree *tree, aatree_ptr root, + aatree_ptr src, aatree_ptr dst ) { - /* Simulate what we would have created on the tail, - * we work along the tail in order, doing the same as the regular - * implementation. This only works because we have parent pointers. */ + aatree_node *pdst = aatree_get_node( tree, dst ), + *psrc = aatree_get_node( tree, src ); + + pdst->count = psrc->count; + pdst->level = psrc->level; + pdst->parent = psrc->parent; + + aatree_link_down( tree, dst, &pdst->left, psrc->left ); + aatree_link_down( tree, dst, &pdst->right, psrc->right ); + if( pdst->parent != AATREE_PTR_NIL ) + { + aatree_node *parent = aatree_get_node( tree, pdst->parent ); + + if( parent->left == src ) + parent->left = dst; + else if( parent->right == src ) + parent->right = dst; + } + else + return dst; + + return root; +} + +static aatree_ptr aatree_del( aatree *tree, aatree_ptr x ) +{ aatree_ptr it = x, up[32]; int count = 1, dir = 0; - aatree_node *search = aatree_get_node( tree, x ); - while(1) - if( search->parent == AATREE_PTR_NIL ) break; - else - { - search = aatree_get_node( tree, search->parent ); - count ++; - } + /* TODO: maybe be a better way to do this, without counting back up */ + for( aatree_node *s = aatree_get_node( tree, x ); + s->parent != AATREE_PTR_NIL; + count ++ ) + s = aatree_get_node( tree, s->parent ); int top=0; while(1) @@ -266,6 +334,7 @@ static aatree_ptr aatree_del( aatree *tree, aatree_ptr x ) aatree_link_down( tree, prev, &pprev->left, pheir->right ); } + /* Tail */ while( --top >= 0 ) { if( top != 0 ) @@ -276,12 +345,11 @@ static aatree_ptr aatree_del( aatree *tree, aatree_ptr x ) aatree_recount( tree, up[top] ); aatree_node *pntop = aatree_get_node( tree, up[top] ); - if( pntop->left == AATREE_PTR_NIL || pntop->right == AATREE_PTR_NIL ){} - else + + if( !(pntop->left == AATREE_PTR_NIL || pntop->right == AATREE_PTR_NIL) ) { - aatree_node - *pnl = aatree_get_node( tree, pntop->left ), - *pnr = aatree_get_node( tree, pntop->right ); + aatree_node *pnl = aatree_get_node( tree, pntop->left ), + *pnr = aatree_get_node( tree, pntop->right ); if( pnl->level < pntop->level-1 || pnr->level < pntop->level-1 ) { @@ -318,52 +386,15 @@ static aatree_ptr aatree_del( aatree *tree, aatree_ptr x ) aatree_get_node( tree, root )->parent = AATREE_PTR_NIL; } } - + + /* This is our extension to the original non-recursive delete, so no data + * has to be moved */ if( _ptrswap_dst != AATREE_PTR_NIL ) - { - /* Copy everything except data from _src to _dst, relink. - * This is a bit of a messy addon, since the algorithm is originally - * based around moving the actual data(key) around, but we have the - * requirement that data can't move, so everything is done normally but - * the pointers are just swapped afterwards. - */ - - aatree_node *pdst = aatree_get_node( tree, _ptrswap_dst ), - *psrc = aatree_get_node( tree, _ptrswap_src ); - - pdst->count = psrc->count; - pdst->level = psrc->level; - pdst->left = psrc->left; - pdst->right = psrc->right; - pdst->parent = psrc->parent; - - if( pdst->parent != AATREE_PTR_NIL ) - { - aatree_node *parent = aatree_get_node( tree, pdst->parent ); - - if( parent->left == _ptrswap_src ) - parent->left = _ptrswap_dst; - else if( parent->right == _ptrswap_src ) - parent->right = _ptrswap_dst; - } - else - { - root = _ptrswap_dst; - } - - if( pdst->left != AATREE_PTR_NIL ) - aatree_get_node( tree, pdst->left )->parent = _ptrswap_dst; - if( pdst->right != AATREE_PTR_NIL ) - aatree_get_node( tree, pdst->right )->parent = _ptrswap_dst; - } + root = aatree_copy_links( tree, root, _ptrswap_src, _ptrswap_dst ); return root; } -/* - * Accessors - */ - static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k ) { u32 i = 0; @@ -371,7 +402,7 @@ static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k ) while( t != AATREE_PTR_NIL ) { aatree_node *ptnode = aatree_get_node( tree, t ); - + u32 j = i; if( ptnode->left != AATREE_PTR_NIL ) j += aatree_get_node( tree, ptnode->left )->count; @@ -397,11 +428,52 @@ static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k ) return AATREE_PTR_NIL; } -static aatree_ptr aatree_ptrof( aatree *tree, aatree_ptr t, void *value ) +static aatree_ptr aatree_next( aatree *tree, aatree_ptr x ) +{ + /* if can go left, go left then all the way right, + * else go up, if it was right link accept + */ + + aatree_node *pnode = aatree_get_node( tree, x ); + if( pnode->right != AATREE_PTR_NIL ) + { + aatree_ptr next = pnode->right; + + while(1) + { + aatree_node *pnext = aatree_get_node( tree, next ); + + if( pnext->left != AATREE_PTR_NIL ) + next = pnext->left; + else + return next; + } + } + else + { + aatree_ptr next = x; + + while(1) + { + aatree_node *pnode = aatree_get_node( tree, next ); + + if( pnode->parent == AATREE_PTR_NIL ) + return AATREE_PTR_NIL; + + aatree_node *pabove = aatree_get_node( tree, pnode->parent ); + if( pabove->left == next ) + return pnode->parent; + else + next = pnode->parent; + } + } +} + +static aatree_ptr aatree_find( aatree *tree, aatree_ptr t, void *value ) { while( t != AATREE_PTR_NIL ) { - int cmp_result = tree->p_cmpv( aatree_get_data( tree, t ), value ); + int cmp_result = tree->p_cmp( aatree_get_data( tree, t ), value ); if( cmp_result == 0 ) return t; @@ -418,7 +490,6 @@ static aatree_ptr aatree_ptrof( aatree *tree, aatree_ptr t, void *value ) return t; } - /* * Debugging stuff, everything below is scaffholding and will be removed * ============================================================================= @@ -489,10 +560,10 @@ static void aatree_show_r( aatree *tree, aatree_ptr t, int lvl, for( int i=0; iright, lvl+1, p_show ); } @@ -508,10 +579,10 @@ static void aatree_show( aatree *tree, aatree_ptr t, void(*p_show)(void *data)) for( int i=0; ilevel; i++ ) { - printf( " " ); + vg_log( " " ); } p_show( data ); - printf( " (%d) \n", t ); + vg_log( " (%d) \n", t ); aatree_show( tree, ptnode->right, p_show ); } @@ -530,7 +601,7 @@ static void aatree_show_counts( aatree *tree, aatree_ptr t, int lvl, int *ln, aatree_show_counts( tree, ptnode->left, lvl+1, ln, err, p_show, show ); - if( show ) printf( " %03d| ", *ln ); + if( show ) vg_log( "%03d| ", *ln ); *ln = *ln +1; if( show ) @@ -556,11 +627,52 @@ static void aatree_show_counts( aatree *tree, aatree_ptr t, int lvl, int *ln, if( !aatree_verify( tree, t ) ) { if( show ) - printf( "error\n" ); + vg_log( "error\n" ); *err = 1; } aatree_show_counts( tree, ptnode->right, lvl+1, ln, err, p_show, show ); } +/* + * Pool allocator utility which can be placed in a union with regular aa nodes. + */ + +static aatree_ptr aatree_init_pool( aatree *info, u32 item_count ) +{ + for( aatree_ptr i=0; inext_free = AATREE_PTR_NIL; + else + pn->next_free = i+1; + } + + return 0; +} + +static aatree_ptr aatree_pool_alloc( aatree *info, aatree_ptr *head ) +{ + if( *head == AATREE_PTR_NIL ) + { + vg_error( "No nodes free in pool allocator!\n" ); + return AATREE_PTR_NIL; + } + else + { + aatree_ptr gap = *head; + *head = aatree_get_pool_node( info, *head )->next_free; + return gap; + } +} + +static void aatree_pool_free( aatree *info, aatree_ptr node, aatree_ptr *head ) +{ + aatree_pool_node *pn = aatree_get_pool_node( info, node ); + pn->next_free = *head; + *head = node; +} + #endif /* VG_STORE_H */ -- 2.25.1