What does this function?

[MadDogMayCry0]

@tezc sc_mapremap ??? What is the better way update memory usage after many attemtps with deliting and adding keys and values? This time i try to use this sheme

sc_map_init_64s(&tmp, 0, 0);
            sc_map_foreach (&map, key, value){
                sc_map_put_64s(&tmp, key, value);
            }
            sc_map_term_64s(&map);
            sc_map_init_64s(&map, 0, 0);
            sc_map_foreach (&tmp, key, value){
                sc_map_put_64s(&map, key, value);
            }
            sc_map_term_64s(&tmp);

but maby exists better way?

[tezc]

@MadDogMayCry0 Underlying array in the hashmap only grows, it does not shrink. So, you want it shrink if many keys are deleted? It's not possible right now but we can add it, probably sc_map_init...() can accept another parameter, something like shrink_factor, then map shrinks automatically according to that parameter. I'll take a look later today.

    bool sc_map_init_##name(struct sc_map_##name *map, uint32_t cap,       \
                uint32_t load_factor);                         \

[MadDogMayCry0]

@tezc where can i get load_factor of current array? Or do i see in a wrong direction? =)

So, you want it shrink if many keys are deleted?

  bool sc_map_init_##name(struct sc_map_##name *map, uint32_t cap,       \
              uint32_t load_factor);                         \

Yea, i want to a litle bit optimising an array after that, to speed up "foreach" :)

[tezc]

@MadDogMayCry0

load_factor determines when to expand the underlying array. If you pass zero to it, it gets the default value which is 75. So, if %75 of the underlying array is used, array doubles its capacity. Map doesn't expose current load factor but this is C, you can access map's variables and just print it like this:

struct sc_map_str map;

sc_map_init_str(&map, 0, 0);

sc_map_put_str(&map, "jack", "chicago");
sc_map_put_str(&map, "jane", "new york");
sc_map_put_str(&map, "janie", "atlanta");

printf("load factor :%f \n", (double) map.size / (double) map.cap);

[tezc]

Yea, i want to a litle bit optimising an array after that, to speed up "foreach" :)

Are you sure this is a bottleneck? You may actually hurt performance by shrinking it. Shrinking takes some time and when you load data back, it needs to expand again, shrinking and expanding might consume more CPU cycles than just iterating on an array sequentially. So, just fyi, most softwares are okay without shrinking. People often want shrinking data structures to save some memory.

[MadDogMayCry0]

Yea, i want to a litle bit optimising an array after that, to speed up "foreach" :)

Are you sure this is a bottleneck?

I try to use it on ESP32 Microcontroller, and it's not the rest to optimizing something. I doing this only when array returns me 0 items inside of it, and app did deleted more as 1000 items before.

 if(sc_map_size_64s(&map) == 0){
            //Refresh tree
            sc_map_term_64s(&map);
            sc_map_init_64s(&map, 0, 0);
        }

[tezc]

Ah okay I see, probably this is important in microcontroller world. I'll take a look later today, we can add auto shrinking without too much change anyway.

[MadDogMayCry0]

@tezc Hello! No any news?

[tezc]

@MadDogMayCry0 Sorry, couldn't finalize this. Looks like auto shrink brings some complexity and some performance overhead. (This hashmap is being used in a very performance sensitive apps). So, I need to take another look, hopefully this weekend.

Meanwhile, I thought maybe we add another function sc_map_shrink_xx(), like sc_map_shrink_64s(). It will shrink the underlying array if possible. So, users are supposed to call this function whenever they want, possibly after each map operation. Implementation is here: https://github.com/tezc/sc/pull/81

So, situation is:

• I'd like to make shrinking automatic if I can find a way to do it without introducing complexity & performance overhead.
• Otherwise, I'll merge shrink() function in that PR. Need to go over it again and add some more tests probably.

Meanwhile, maybe you can try that version in the PR. Is it good enough for your use case? This is the branch: https://github.com/tezc/sc/tree/map-shrink/map

[MadDogMayCry0]

@tezc Hello. UPD. Ohh.. i found the problem.. i have to use const char* ptr to put some values and keys in to hash, but then i have a problem yet :( i put chars from user input like so

char tel[24];
char msg[256];
input_read(tel,msg);
sc_map_put_64s(&map, i,tel);
sc_map_put_64s(&arr, i,msg);
i++;

and after

uint32_t key;
const char *val;  
sc_map_foreach (&arr, key, val) {
    printf("%d %s\r\n",key,val);
}

i have clones from last each input. For example 3 inputs and the last one was "sdjahf lkjsahdflkjhsadlfkjhsalkjd"

0 sdjahf lkjsahdflkjhsadlfkjhsalkjd
1 sdjahf lkjsahdflkjhsadlfkjhsalkjd
2 sdjahf lkjsahdflkjhsadlfkjhsalkjd

when i put input to const char * ptr;

const char * ptr = malloc(strlen(msg)+1);
strcpy(ptr,msg);
sc_map_put_64s(&arr, ii,ptr);

but now i got memory leak. Pls help to lua user :)

Please tell me, how can I understand how many bytes I can put in a hash table, for example, with 100kb of RAM? Now i do counting the string that i put, but always got 3000 records regardless of byte length...

I'm using a function that shows me the out of bounds, but I need to know how much more data i have before left. Thank you.

[MadDogMayCry0]

@tezc UPD. Ohh.. i found the problem.. i have to use const char* ptr to put some values and keys in to hash, but then i have a problem yet :( i put chars from user input like so

char tel[24];
char msg[256];
input_read(tel,msg);
sc_map_put_64s(&map, i,tel);
sc_map_put_64s(&arr, i,msg);
i++;

and after

uint32_t key;
const char *val;  
sc_map_foreach (&arr, key, val) {
    printf("%d %s\r\n",key,val);
}

i have clones from last each input. For example 3 inputs and the last one was "sdjahf lkjsahdflkjhsadlfkjhsalkjd"

0 sdjahf lkjsahdflkjhsadlfkjhsalkjd
1 sdjahf lkjsahdflkjhsadlfkjhsalkjd
2 sdjahf lkjsahdflkjhsadlfkjhsalkjd

when i put input to const char * ptr;

const char * ptr = malloc(strlen(msg)+1);
strcpy(ptr,msg);
sc_map_put_64s(&arr, ii,ptr);

but now i got memory leak. Pls help to lua user :)

[MadDogMayCry0]

UPD. My understanding to C is absolute bad. What i got.

const char **ptr[1024]={0};
char msg[128];
usr_input(msg,128);
ptr[i] = (char*)malloc(strlen(msg)+1);
strcpy(ptr[i],msg);
sc_map_put_64s(&map, i, ptr[i]);

and when i delete the element from SC i can free PTR

value = sc_map_del_64s(&map, i);
free(ptr[i]);

Do i right or is there a right way?

[tezc]

Hi @MadDogMayCry0

Yes, looks like you were using stack allocated values and that was causing problems. Last snippet looks okay. I'd just check two things: 1- When you put a key into the map, if you are overwriting the value, you should free it as well. 2- When you delete a key, if key does not exist, probably you should not call free(ptr[i])

See the if checks below:

const char **ptr[1024]={0};
char msg[128];
usr_input(msg,128);
ptr[i] = (char*)malloc(strlen(msg)+1);
strcpy(ptr[i],msg);
prev_value = sc_map_put_64s(&map, i, ptr[i]);
if (sc_map_found(&map)) {
    free(prev_value);
}

value = sc_map_del_64s(&map, i);
// Free the memory only if key `i` exists.
if (sc_map_found(&map)) {
    free(ptr[i]);
}

I don't know what you are trying to do but maybe you don't need ptr array at all:

char msg[128];
usr_input(msg,128);

char *value = malloc(strlen(msg) + 1);
strcpy(value, msg);

char *prev_value = sc_map_put_64s(&map, i, value);
if (sc_map_found(&map)) {
   // We are overwriting the key, free the value. 
    free(prev_value);
}

// -----------------------------
char *value = sc_map_del_64s(&map, i);
// Free the memory only if key `i` exists.
if (sc_map_found(&map)) {
    free(value);
}

[MadDogMayCry0]

@tezc Thx for answer above, it's works like a charm! Now I have infinite dark power in my hands (offscreen evil laughter). But one more question. I need function that can put values to specific MAP's. I tryed to implement something like this:

void map_put(sc_map_64s *map,int key,char *val){
    char *ptr = (char*)malloc(strlen(val)+1);
    strcpy(ptr,val);
    char * value = (char*)sc_map_put_64s(&map, key, ptr);
    if (sc_map_found(&map)){
        free(value);
    }
}

but i get error

../main/app.c:66:14: error: unknown type name 'sc_map_64s'; did you mean 'sc_map_oom'?
 void map_put(sc_map_64s *map,int key,char *val){
              ^~~~~~~~~~
              sc_map_oom

Pls help :)

[tezc]

void map_put(struct sc_map_64s *map, int key, char *val)
{
    char *ptr = malloc(strlen(val) + 1);
    strcpy(ptr, val);

    char *value = (char *) sc_map_put_64s(map, key, ptr);
    if (sc_map_found(map)) {
        free(value);
    }
}

@MadDogMayCry0 You forgot struct keyword in the function parameter. Try this snippet above.

[MadDogMayCry0]

@tezc Hello! 1 - Pls, how can i break foreach?

sc_map_foreach(&port_list, key, val) {
    break;
}

did'nt works.

2 - it is possable somehow to get first element without to use foreach when key is not determined?

[tezc]

@MadDogMayCry0 Oops, this is a bug :/ I see all our use cases either use return, goto or we iterate all the values so, we didn't realize it.

Options:

1- return statement will work:

const char *getFirstValue() 
{
    const char* key, val;

    sc_map_foreach(&port_list, key, val) {
        return val;
    } 
    return NULL;
}

2- goto will work:

const char *getFirstValue() 
{
    const char* key, val;

    sc_map_foreach(&port_list, key, val) {
        goto found;
    }

found:
    return val;
}

3- I just wrote this fix but couldn't try it thoroughly(not sure if I broke anything else), maybe you can replace sc_map_foreach() with this one and try the fix:

#define sc_map_foreach(map, K, V)                                              \
    for (int64_t __i = -1, __b = 0; !__b && __i < (map)->cap; __i++)       \
        for ((V) = (map)->mem[__i].value, (K) = (map)->mem[__i].key,   \
            __b = 1;                                                   \
             __b && ((__i == -1 && (map)->used) || (K) != 0) ? 1 : (__b = 0); __b = 0)

I'll take a look at this issue whenever I have some spare time. Until then, these workarounds should work. (sc_map_foreach(), sc_map_foreach_key(), sc_map_foreach_value(), all sufffer from this issue and needs to be fixed).

Regarding, random element, it'd actually do same thing with the for each loop, so, if you wrap it similar to above, you can get a random element. Btw, just be sure map is the data structure you want. If you want to just get a random element, you can try a queue or array as well. You can find these data structures in this repo. Just fyi.

[MadDogMayCry0]

@tezc Seems to works good.

#define sc_map_foreach(map, K, V)                                              \
    for (int64_t __i = -1, __b = 0; !__b && __i < (map)->cap; __i++)       \
        for ((V) = (map)->mem[__i].value, (K) = (map)->mem[__i].key,   \
            __b = 1;                                                   \
             __b && ((__i == -1 && (map)->used) || (K) != 0) ? 1 : (__b = 0); __b = 0)

and return too. Thank You!