From 6f176096b8f3a2088c01d67a36e4b67750ec179e Mon Sep 17 00:00:00 2001 From: ame Date: Wed, 27 May 2026 06:00:43 -0500 Subject: .table updates, .dup & .equal --- library/lullaby/table.lua | 48 +++++-------- src/lua.c | 16 ----- src/lua.h | 11 ++- src/sort.c | 174 ---------------------------------------------- src/sort.h | 10 --- src/table.c | 98 +++++++++++++++++++++++++- src/table.h | 36 +++++----- tests/units/sort.lua | 22 ++++++ 8 files changed, 163 insertions(+), 252 deletions(-) create mode 100644 tests/units/sort.lua diff --git a/library/lullaby/table.lua b/library/lullaby/table.lua index 51414f7..f0f11ec 100644 --- a/library/lullaby/table.lua +++ b/library/lullaby/table.lua @@ -1,6 +1,6 @@ ---@meta ----to be rewritten +---to be mostly rewritten ---@class lullaby.table local table = {} @@ -15,6 +15,23 @@ local table = {} ---@return string[] function table.split(haystack, search, skip) end +---compares 2 tables recursivley +---@param A any[] +---@param B any[] +---@param depth integer? max depth to search, defaults to -1 +---@return boolean +function table.equal(A, B, depth) end + +---clones table recursivley +---@param table any[] +---@return value[] +function table.dup(table) end + +---gets table len, useful for key,value tables +---@param table any[] +---@return integer +function table.len(table) end + ---greatest, least ---@deprecated ---@param array number[] @@ -40,33 +57,4 @@ function table.bubblesort(array) end ---@param array number[] function table.heapsort(array) end ----least, greatest ----@deprecated ----@param array integer[] -function table.countintsort(array) end - ----dont use this lol ----@deprecated ----greatest, least ----@param array number[] -function table.miraclesort(array) end - ----dont use this lol ----@deprecated ----greatest, least ----@param array number[] -function table.stalinsort(array) end - ----dont use this lol ----@deprecated ----greatest, least ----@param array number[] -function table.slowsort(array) end - ----dont use this lol ----@deprecated ----greatest, least ----@param array number[] -function table.bogosort(array) end - return table diff --git a/src/lua.c b/src/lua.c index 3accdb4..f60fba5 100644 --- a/src/lua.c +++ b/src/lua.c @@ -13,18 +13,6 @@ int luaI_nothing(lua_State* L){ return 0; } -void* __malloc_(size_t N){ - printf("hi"); - malloc_count++; - return (malloc)(N); -} - -void __free_(void* p){ - malloc_count--; - printf("%i\n",malloc_count); - return (free)(p); -} - int luaI_iserror(lua_State* L){ if(lua_gettop(L) < 3) return 0; return lua_type(L, -3) == LUA_TNIL && @@ -172,10 +160,6 @@ int writer(lua_State *L, const void* p, size_t sz, void* ud){ return 0; } -enum table_cache { - CACHE_HIT, CACHE_MISS -}; - enum table_cache table_cache(lua_State* L, char* key, int index){ lua_getfield(L, LUA_REGISTRYINDEX, key); if(lua_type(L, -1) == LUA_TNIL){ diff --git a/src/lua.h b/src/lua.h index 1e45242..da65101 100644 --- a/src/lua.h +++ b/src/lua.h @@ -17,14 +17,17 @@ enum deep_copy_flags { STRIP_GC = (1 << 5), IS_UPVALUE = (1 << 6), }; + +enum table_cache { + CACHE_HIT, CACHE_MISS +}; #endif #ifndef GIT_COMMIT #define GIT_COMMIT "unknown" #endif -void* __malloc_(size_t); -void __free_(void*); +enum table_cache table_cache(lua_State* L, char* key, int index); void luaI_deepcopy(lua_State* src, lua_State* dest, enum deep_copy_flags); void luaI_deepcopy2(lua_State* src, lua_State* dest); @@ -108,6 +111,10 @@ extern int _print_errors; int writer(lua_State*, const void*, size_t, void*); +#if LUA_VERSION_NUM != 501 + #define lua_equal(L, A, B) lua_compare(L, A, B, LUA_OPEQ) +#endif + #if LUA_VERSION_NUM == 504 #define lua_objlen lua_rawlen diff --git a/src/sort.c b/src/sort.c index 4462160..83fd0da 100644 --- a/src/sort.c +++ b/src/sort.c @@ -245,182 +245,8 @@ int l_bubblesort(lua_State* L) { return 1; } -int l_countingsort(lua_State* L) { - luaL_checktype(L, 1, LUA_TTABLE); - size_t len = lua_objlen(L,1); - int* nums = malloc(sizeof * nums * len); - int* out = malloc(sizeof * nums * len); - int max = 0; - for(int i = 0; i <= len-1; i++){ - - lua_pushinteger(L,i+1); - lua_gettable(L,1); - - nums[i] = luaL_checknumber(L, -1); - out[i] = 0; - - if(nums[i]<0) p_fatal("array.countingsort() requires all indices to be >= 0"); - max = max < nums[i] ? nums[i] : max; - - lua_pop(L,1); - } - - int* count = calloc(max + 1, sizeof * count); - - for(size_t i = 0; i < len; i++){ - count[nums[i]]++; - } - - for(size_t i = 1; i <= max; i++){ - count[i] += count[i - 1]; - } - - for(int i = len - 1; i >= 0; i--){ - out[count[nums[i]] - 1] = nums[i]; - count[nums[i]]--; - } - - lua_newtable(L); - for(size_t i = 0; i != len; i++){ - lua_pushnumber(L,i+1); - lua_pushnumber(L,out[i]); - lua_settable(L, -3); - } - - free(count); - free(nums); - free(out); - return 1; -} - int i_sorted(double* arr, size_t len){ for(size_t i = 0; i != len - 1; i++) if(arr[i] > arr[i+1]) return 0; return 1; } - -int l_miraclesort(lua_State* L) { - luaL_checktype(L, 1, LUA_TTABLE); - size_t len = lua_objlen(L,1); - double* nums = malloc(sizeof * nums * len); - for(size_t i = 0; i <= len-1; i++){ - - lua_pushinteger(L,i+1); - lua_gettable(L,1); - - nums[i] = luaL_checknumber(L, -1); - lua_pop(L,1); - } - - for(;!i_sorted(nums,len);); - - lua_newtable(L); - for(size_t i = 0; i != len; i++){ - lua_pushnumber(L,i+1); - lua_pushnumber(L,nums[i]); - lua_settable(L, -3); - } - - free(nums); - return 1; -} - -int l_stalinsort(lua_State* L) { - luaL_checktype(L, 1, LUA_TTABLE); - size_t len = lua_objlen(L,1); - size_t rlen = 0; - double* nums = malloc(sizeof * nums * len); - for(size_t i = 0; i <= len-1; i++){ - - lua_pushinteger(L,i+1); - lua_gettable(L,1); - - double n = luaL_checknumber(L, -1); - if(rlen == 0 || nums[rlen - 1] <= n){ - nums[rlen] = n; - rlen++; - } - - lua_pop(L,1); - } - - - lua_newtable(L); - for(size_t i = 0; i != rlen; i++){ - lua_pushnumber(L,i+1); - lua_pushnumber(L,nums[i]); - lua_settable(L, -3); - } - - free(nums); - return 1; -} - -void i_slowsort(double* arr, int i, int j){ - if(i >= j) return; - - int m = (i + j) /2; - - i_slowsort(arr, i, m); - i_slowsort(arr, m + 1, j); - - if(arr[j] < arr[m]){ - i_swap(arr[j], arr[m]); - } - - i_slowsort(arr, i, j - 1); -} - -int l_slowsort(lua_State* L) { - luaL_checktype(L, 1, LUA_TTABLE); - size_t len = lua_objlen(L,1); - double* nums = malloc(sizeof * nums * len); - for(int i = 0; i <= len-1; i++){ - - lua_pushinteger(L,i+1); - lua_gettable(L,1); - - nums[i] = luaL_checknumber(L, -1); - lua_pop(L,1); - } - - i_slowsort(nums, 0, len - 1); - - lua_newtable(L); - for(size_t i = 0; i != len; i++){ - lua_pushnumber(L,i+1); - lua_pushnumber(L,nums[i]); - lua_settable(L, -3); - } - - free(nums); - return 1; -} - -int l_bogosort(lua_State* L) { - luaL_checktype(L, 1, LUA_TTABLE); - size_t len = lua_objlen(L,1); - double* nums = malloc(sizeof * nums * len); - for(size_t i = 0; i <= len-1; i++){ - - lua_pushinteger(L,i+1); - lua_gettable(L,1); - - nums[i] = luaL_checknumber(L, -1); - lua_pop(L,1); - } - - for(;!i_sorted(nums, len);){ - i_shuffle(nums, len); - } - - lua_newtable(L); - for(size_t i = 0; i != len; i++){ - lua_pushnumber(L,i+1); - lua_pushnumber(L,nums[i]); - lua_settable(L, -3); - } - - free(nums); - return 1; -} diff --git a/src/sort.h b/src/sort.h index e59cd4e..2b2efee 100644 --- a/src/sort.h +++ b/src/sort.h @@ -7,13 +7,3 @@ int l_mergesort(lua_State*); //[double+int] -> arr[N] (greatest -> least) int l_shellsort(lua_State*); //[double+int] -> arr[N] (greatest -> least) int l_bubblesort(lua_State*); //[double+int] -> arr[N] (greatest -> least) int l_heapsort(lua_State*); //[double+int] -> arr[N] (greatest -> least) - -//non-comparison sorts -//good for large arrays filled with small values -int l_countingsort(lua_State*); //[int] (arr[N] >= 0) -> arr[N] (least -> greatest) - -//esoteric sorts -int l_miraclesort(lua_State*); //[double+int] -> arr[-∞<=N<=∞] (greatest -> least) -int l_stalinsort(lua_State*); //[double+int] -> arr[?<=N] (greatest -> least) -int l_slowsort(lua_State*); //[double+int] -> arr[N] (greatest -> least) -int l_bogosort(lua_State*); //[double+int] -> arr[N] (greatest -> least) diff --git a/src/table.c b/src/table.c index bf14892..f5bdd5d 100644 --- a/src/table.c +++ b/src/table.c @@ -3,6 +3,99 @@ #include #include +void value_clone_req(lua_State* L){ + int idx = lua_gettop(L); + + if(lua_type(L, idx) == LUA_TTABLE){ + char* key = calloc(sizeof* key, 50); + sprintf(key, "clone-%p", lua_topointer(L, idx)); + lua_newtable(L); + int nidx = lua_gettop(L); + + if(table_cache(L, key, nidx) == CACHE_HIT){ + free(key); + return; + } + free(key); + + lua_pushnil(L); + for(;lua_next(L, idx);){ + value_clone_req(L); + lua_pushvalue(L, -3); + lua_pushvalue(L, -2); + lua_settable(L, nidx); + lua_pop(L, 2); + } + } else { + lua_pushvalue(L, idx); + } +} + +int l_dup(lua_State* L){ + if(lua_gettop(L) != 1) return 0; + + value_clone_req(L); + lua_pushvalue(L, 2); + return 1; +} + +int req_equal(lua_State* L, int maxdepth, int currentdepth, parray_t* req_table){ + if(maxdepth < currentdepth && maxdepth != -1) + return 1; + + int t1 = lua_gettop(L); + int t2 = lua_gettop(L) - 1; + if(i_len(L, t1) != i_len(L, t2)) + return 0; + lua_pushnil(L); + for(;lua_next(L, t1) != 0;){ //-3 = key, -2 = t1[key], -1 = t2[key] + lua_pushvalue(L, -2); + lua_gettable(L, t2); + + if(lua_type(L, -1) != lua_type(L, -2)) + return 0; + + if(lua_type(L, -1) == LUA_TTABLE){ + const void* p = lua_topointer(L, -2); + char* str = calloc(sizeof* str, 50); + sprintf(str, "%p", p); + if(parray_geti(req_table, str) == -1){ + parray_set(req_table, str, req_table); + if(!req_equal(L, maxdepth, currentdepth + 1, req_table)){ + free(str); + return 0; + } + } + free(str); + } else { + if(!lua_equal(L, -2, -1)) + return 0; + } + + lua_pop(L, 2); + } + return 1; +} + +int l_equal(lua_State* L){ + if(lua_gettop(L) <= 1){ + lua_pushboolean(L, 1); + return 1; + } + + luaL_checktype(L, 1, LUA_TTABLE); + luaL_checktype(L, 2, LUA_TTABLE); + int64_t depth = -1; + if(lua_gettop(L) >= 3) depth = luaL_checknumber(L, 3); + lua_settop(L, 2); + + parray_t* p = parray_init(); + lua_pushboolean(L, req_equal(L, depth, 0, p)); + parray_lclear(p); + + return 1; +} + int l_split(lua_State* L){ size_t str_len = 0; size_t search_len = 0; @@ -59,6 +152,7 @@ uint64_t i_len(lua_State* L, int pos){ } return i; } + int l_len(lua_State* L) { luaL_checktype(L, 1, LUA_TTABLE); lua_pushnumber(L,i_len(L,1)); @@ -84,7 +178,7 @@ int l_reverse(lua_State* L) { return 1; } -int l_greatest(lua_State* L) { +int l_max(lua_State* L) { luaL_checktype(L, 1, LUA_TTABLE); size_t len = lua_objlen(L,1); int touched = 0; @@ -104,7 +198,7 @@ int l_greatest(lua_State* L) { return 1; } -int l_least(lua_State* L) { +int l_min(lua_State* L) { luaL_checktype(L, 1, LUA_TTABLE); size_t len = lua_objlen(L,1); int touched = 0; diff --git a/src/table.h b/src/table.h index 6d872c3..b114cd2 100644 --- a/src/table.h +++ b/src/table.h @@ -9,8 +9,8 @@ uint64_t i_len(lua_State*,int); int l_len(lua_State*); //[double+int] -> i int l_reverse(lua_State*); //[double+int] -> arr[N] -int l_greatest(lua_State*); //[double+int] -> i -int l_least(lua_State*); //[double+int] -> i +int l_max(lua_State*); //[double+int] -> i +int l_min(lua_State*); //[double+int] -> i int l_shuffle(lua_State*); //[double+int] -> arr[N] int l_sum(lua_State*); //[double+int] -> i @@ -21,35 +21,35 @@ int l_to_char_array(lua_State*); int l_unpack(lua_State*); int l_split(lua_State*); +int l_equal(lua_State*); +int l_dup(lua_State*); #define clean_lullaby_table luaI_nothing + +#warning "docs needed here" static const luaL_Reg table_function_list [] = { {"len",l_len}, - {"reverse",l_reverse}, - {"greatest",l_greatest}, - {"least",l_least}, - {"shuffle",l_shuffle}, - {"sum",l_sum}, + {"reverse",l_reverse}, //no docs + {"max",l_max}, //no docs + {"min",l_min}, //no docs + {"shuffle",l_shuffle}, //no docs + {"sum",l_sum}, //no docs {"split",l_split}, - {"to_char_array", l_to_char_array}, + {"to_char_array", l_to_char_array}, //no docs - {"index",l_indexof}, - {"sindex",l_sindexof}, + {"index",l_indexof}, //no docs + {"sindex",l_sindexof}, //no docs + //updates these and the functions {"quicksort",l_quicksort}, {"mergesort",l_mergesort}, {"shellsort",l_shellsort}, {"bubblesort",l_bubblesort}, {"heapsort",l_heapsort}, - {"countingsort",l_countingsort}, - - {"miraclesort",l_miraclesort}, - {"stalinsort",l_stalinsort}, - {"slowsort",l_slowsort}, - {"bogosort",l_bogosort}, - - {"unpack", l_unpack}, + {"unpack", l_unpack}, //no docs + {"equal", l_equal}, + {"dup", l_dup}, {NULL,NULL} }; diff --git a/tests/units/sort.lua b/tests/units/sort.lua new file mode 100644 index 0000000..343f65e --- /dev/null +++ b/tests/units/sort.lua @@ -0,0 +1,22 @@ +local input = {} +local len = 500 +local max = 9999 + +for i=1,len do + table.insert(input, math.random(-max, max)) +end + +local a = llby.table.dup(input) +local b = llby.table.dup(input) +local c = llby.table.dup(input) +local d = llby.table.dup(input) +local e = llby.table.dup(input) + +llby.table.quicksort(a) +llby.table.bubblesort(b) +llby.table.heapsort(c) +llby.table.shellsort(d) +llby.table.mergesort(e) + +return llby.table.equal(a, b) and llby.table.equal(b, c) and + llby.table.equal(c, d) and llby.table.equal(d, e) -- cgit v1.2.3