Skip to content

Commit

Permalink
[memory][fs-memory] Remove copyings
Browse files Browse the repository at this point in the history
  • Loading branch information
@NikitaZotov
NikitaZotov committed Apr 15, 2023
1 parent ffaba7c commit 888d000
Show file tree
Hide file tree
Showing 21 changed files with 458 additions and 545 deletions.
51 changes: 29 additions & 22 deletions sc-memory/sc-core/sc-store/sc-container/sc-dictionary/sc_dictionary.c
View file
Original file line number Diff line number Diff line change
Expand Up @@ -18,7 +18,7 @@
sc_bool sc_dictionary_initialize(
sc_dictionary ** dictionary,
sc_uint8 children_size,
void (*char_to_int)(sc_char, sc_uint8 *, sc_uint8 *))
void (*char_to_int)(sc_char, sc_uint8 *, const sc_uint8 *))
{
if (*dictionary != null_ptr)
return SC_FALSE;
Expand Down Expand Up @@ -75,9 +75,9 @@ void sc_dictionary_node_destroy(sc_dictionary_node * node, void ** args)
}

inline sc_dictionary_node * _sc_dictionary_get_next_node(
sc_dictionary * dictionary,
sc_dictionary_node * node,
sc_char ch)
const sc_dictionary * dictionary,
const sc_dictionary_node * node,
const sc_char ch)
{
sc_uint8 num;
dictionary->char_to_int(ch, &num, &node->mask);
Expand Down Expand Up @@ -183,21 +183,22 @@ sc_dictionary_node * sc_dictionary_remove_from_node(
sc_dictionary * dictionary,
sc_dictionary_node * node,
const sc_char * sc_string,
const sc_uint32 sc_string_size,
sc_uint32 i)
{
// check prefixes matching
sc_uint32 string_size = strlen(sc_string);
sc_uint32 string_size = sc_string_size;

if (i < string_size)
{
sc_uint8 num = 0;
dictionary->char_to_int(sc_string[i], &num, &node->mask);
sc_dictionary_node * next = node->next[num];
if (SC_DICTIONARY_NODE_IS_VALID(node->next[num]) &&
(sc_str_has_prefix(sc_string + i, next->offset) || strcmp(sc_string + i, next->offset) == 0))
(sc_str_has_prefix(sc_string + i, next->offset) || sc_str_cmp(sc_string + i, next->offset)))
{
sc_dictionary_node * removable =
sc_dictionary_remove_from_node(dictionary, next, sc_string, i + next->offset_size);
sc_dictionary_remove_from_node(dictionary, next, sc_string, sc_string_size, i + next->offset_size);

if (SC_DICTIONARY_NODE_IS_VALID(next))
return removable;
Expand All @@ -206,7 +207,7 @@ sc_dictionary_node * sc_dictionary_remove_from_node(

// check suffixes matching
if (i == string_size &&
(node->offset == null_ptr || strcmp(node->offset, sc_string + (string_size - node->offset_size)) == 0))
(node->offset == null_ptr || sc_str_cmp(node->offset, sc_string + (string_size - node->offset_size))))
{
return node;
}
Expand All @@ -217,10 +218,12 @@ sc_dictionary_node * sc_dictionary_remove_from_node(
sc_bool sc_dictionary_remove(
sc_dictionary * dictionary,
const sc_char * sc_string,
const sc_uint32 sc_string_size,
void * data,
sc_bool (*predicate)(void * data, void * other))
{
sc_dictionary_node * node = sc_dictionary_remove_from_node(dictionary, dictionary->root, sc_string, 0);
sc_dictionary_node * node =
sc_dictionary_remove_from_node(dictionary, dictionary->root, sc_string, sc_string_size, 0);

sc_bool result = node != null_ptr;
if (result == SC_TRUE)
Expand All @@ -231,14 +234,15 @@ sc_bool sc_dictionary_remove(
return result;
}

sc_dictionary_node * sc_dictionary_get_last_node_from_node(
sc_dictionary * dictionary,
sc_dictionary_node * node,
const sc_char * sc_string)
const sc_dictionary_node * sc_dictionary_get_last_node_from_node(
const sc_dictionary * dictionary,
const sc_dictionary_node * node,
const sc_char * sc_string,
const sc_uint32 sc_string_size)
{
// check prefixes matching
sc_uint32 i = 0;
sc_uint32 string_size = strlen(sc_string);
sc_uint32 string_size = sc_string_size;
while (i < string_size)
{
sc_dictionary_node * next = _sc_dictionary_get_next_node(dictionary, node, sc_string[i]);
Expand All @@ -262,29 +266,32 @@ sc_dictionary_node * sc_dictionary_get_last_node_from_node(
return null_ptr;
}

sc_bool sc_dictionary_is_in(sc_dictionary * dictionary, const sc_char * sc_string)
sc_bool sc_dictionary_is_in(const sc_dictionary * dictionary, const sc_char * sc_string, const sc_uint32 sc_string_size)
{
sc_dictionary_node * last = sc_dictionary_get_last_node_from_node(dictionary, dictionary->root, sc_string);
const sc_dictionary_node * last =
sc_dictionary_get_last_node_from_node(dictionary, dictionary->root, sc_string, sc_string_size);

return SC_DICTIONARY_NODE_IS_VALID(last) && last->data_list != null_ptr && last->data_list->size != 0;
}

void * sc_dictionary_get_first_data_from_node(
sc_dictionary * dictionary,
sc_dictionary_node * node,
const sc_char * sc_string)
const sc_dictionary * dictionary,
const sc_dictionary_node * node,
const sc_char * sc_string,
const sc_uint32 sc_string_size)
{
sc_dictionary_node * last = sc_dictionary_get_last_node_from_node(dictionary, node, sc_string);
const sc_dictionary_node * last = sc_dictionary_get_last_node_from_node(dictionary, node, sc_string, sc_string_size);

if (SC_DICTIONARY_NODE_IS_VALID(last) && last->data_list != null_ptr && last->data_list->begin != null_ptr)
return last->data_list->begin->data;

return null_ptr;
}

sc_list * sc_dictionary_get(sc_dictionary * dictionary, const sc_char * sc_string)
sc_list * sc_dictionary_get(const sc_dictionary * dictionary, const sc_char * sc_string, const sc_uint32 sc_string_size)
{
sc_dictionary_node * last = sc_dictionary_get_last_node_from_node(dictionary, dictionary->root, sc_string);
const sc_dictionary_node * last =
sc_dictionary_get_last_node_from_node(dictionary, dictionary->root, sc_string, sc_string_size);

if (SC_DICTIONARY_NODE_IS_VALID(last))
return last->data_list;
Expand Down
20 changes: 13 additions & 7 deletions sc-memory/sc-core/sc-store/sc-container/sc-dictionary/sc_dictionary.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -38,7 +38,7 @@ typedef struct _sc_dictionary
{
sc_dictionary_node * root; // sc-dictionary tree root node
sc_uint8 size; // default sc-dictionary node children size
void (*char_to_int)(sc_char, sc_uint8 *, sc_uint8 *);
void (*char_to_int)(sc_char, sc_uint8 *, const sc_uint8 *);
} sc_dictionary;

/*! Initializes sc-dictionary
Expand All @@ -50,7 +50,7 @@ typedef struct _sc_dictionary
sc_bool sc_dictionary_initialize(
sc_dictionary ** dictionary,
sc_uint8 children_size,
void (*char_to_int)(sc_char, sc_uint8 *, sc_uint8 *));
void (*char_to_int)(sc_char, sc_uint8 *, const sc_uint8 *));

/*! Destroys a sc-dictionary
* @param dictionary A sc-dictionary pointer to destroy
Expand Down Expand Up @@ -82,6 +82,7 @@ sc_dictionary_node * sc_dictionary_append(
/*! Removes data from a sc-dictionary by a common key, if such exists.
* @param sc_dictionary A sc-dictionary where common prefix may be started
* @param sc_string A key string
* @param sc_string A key string size
* @param data A pointer to removable data
* @param predicate A predicate function to delete data by it
* @returns Returns If data was removed then function returns SC_TRUE; otherwise return SC_FALSE.
Expand All @@ -90,34 +91,39 @@ sc_dictionary_node * sc_dictionary_append(
sc_bool sc_dictionary_remove(
sc_dictionary * dictionary,
const sc_char * sc_string,
sc_uint32 sc_string_size,
void * data,
sc_bool (*predicate)(void * data, void * other));

/*! Checks, if a string is in a sc-dictionary by a common prefix with another string started in sc-dictionary
* node, if such exists.
* @param dictionary A sc-dictionary pointer
* @param sc_string A verifiable string
* @param sc_string_size A verifiable string size
* @returns Returns SC_TRUE, if string starts in sc-dictionary node; otherwise return SC_FALSE.
*/
sc_bool sc_dictionary_is_in(sc_dictionary * dictionary, const sc_char * sc_string);
sc_bool sc_dictionary_is_in(const sc_dictionary * dictionary, const sc_char * sc_string, sc_uint32 sc_string_size);

/*! Gets first data from a terminal sc-dictionary node where string ends.
* @param dictionary A sc-dictionary pointer
* @param node A sc-dictionary node where common prefix may be started
* @param sc_string A string to retrieve data by it
* @param sc_string_size A string size
* @returns Returns Data from a sc-dictionary node where string ends
*/
void * sc_dictionary_get_first_data_from_node(
sc_dictionary * dictionary,
sc_dictionary_node * node,
const sc_char * sc_string);
const sc_dictionary * dictionary,
const sc_dictionary_node * node,
const sc_char * sc_string,
sc_uint32 sc_string_size);

/*! Gets datas from a terminal sc-dictionary node where string ends.
* @param dictionary A sc-dictionary pointer
* @param sc_string A string to retrieve datas by it
* @param sc_string_size A string size
* @returns Returns Datas from a sc-dictionary node where string ends
*/
sc_list * sc_dictionary_get(sc_dictionary * dictionary, const sc_char * sc_string);
sc_list * sc_dictionary_get(const sc_dictionary * dictionary, const sc_char * sc_string, sc_uint32 sc_string_size);

/*! Visits all sc-dictionary nodes and calls procedure with it and its data. A method completes down iterating visiting.
* @param dictionary A sc-dictionary pointer
Expand Down
22 changes: 12 additions & 10 deletions sc-memory/sc-core/sc-store/sc-container/sc-dictionary/sc_dictionary_private.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -12,11 +12,10 @@

sc_dictionary_node * _sc_dictionary_node_initialize(sc_uint8 children_size);

sc_dictionary_node * _sc_dictionary_get_next_node(sc_dictionary * dictionary, sc_dictionary_node * node, sc_char ch);

sc_addr * sc_list_to_addr_array(sc_list * list);

sc_addr_hash * sc_list_to_hashes_array(sc_list * list);
sc_dictionary_node * _sc_dictionary_get_next_node(
const sc_dictionary * dictionary,
const sc_dictionary_node * node,
sc_char ch);

/*! Appends a string to a sc-dictionary by a common prefix with another string started in sc-dictionary node, if such
* exists.
Expand All @@ -35,26 +34,29 @@ sc_dictionary_node * sc_dictionary_append_to_node(
* @param dictionary A sc-dictionary pointer
* @param node A sc-dictionary node where common prefix may be started
* @param sc_string A removable string
* @param size Removable string size
* @param sc_string_size Removable string size
* @returns Returns A sc-dictionary node where removable string or its prefix starts
* @note If string isn't in sc-dictionary then null_pointer will be returned
*/
sc_dictionary_node * sc_dictionary_remove_from_node(
sc_dictionary * dictionary,
sc_dictionary_node * node,
const sc_char * sc_string,
sc_uint32 sc_string_size,
sc_uint32 index);

/*! Gets a terminal sc-dictionary node where string ends.
* @param dictionary A sc-dictionary pointer
* @param node A sc-dictionary node where common prefix may be started
* @param sc_string A string to retrieve data by it
* @param sc_string_size A string size
* @returns Returns A sc-dictionary node where string ends
*/
sc_dictionary_node * sc_dictionary_get_last_node_from_node(
sc_dictionary * dictionary,
sc_dictionary_node * node,
const sc_char * sc_string);
const sc_dictionary_node * sc_dictionary_get_last_node_from_node(
const sc_dictionary * dictionary,
const sc_dictionary_node * node,
const sc_char * sc_string,
sc_uint32 sc_string_size);

/*! Visits all sc-dictionary nodes starting with specified node and calls procedure with it and its data. A method
* completes down iterating visiting.
Expand Down
17 changes: 17 additions & 0 deletions sc-memory/sc-core/sc-store/sc-container/sc-string/sc_string.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -10,6 +10,8 @@
#include "../../sc-base/sc_allocator.h"
#include "../../sc_types.h"

#define sc_string_empty(string) ({ sc_string = sc_mem_new(sc_char, 1); })

#define sc_str_cpy(copy, string, size) \
({ \
copy = sc_mem_new(sc_char, size + 1); \
Expand All @@ -18,4 +20,19 @@

#define sc_str_has_prefix(str, prefix) g_str_has_prefix(str, prefix)

#define sc_str_len(string) strlen(string)

#define sc_int_to_str_int(number, string) \
sc_uint32 length = (number == 0) ? 1 : snprintf(null_ptr, 0, "%llu", number); \
string = sc_mem_new(sc_char, length + 1); \
gcvt(number, length, string)

#define sc_str_find(str, substring) strstr(str, substring) != null_ptr

#define sc_str_find_position(str, substring) (sc_uint64)(strstr(str, substring) - str + 1)

#define sc_str_find_get(str, substring) strstr(str, substring)

#define sc_str_cmp(str, other) strcmp(str, other) == 0

#endif
Loading

0 comments on commit 888d000

Please sign in to comment.