Rax currently expects values to be valid pointers. This requirement stems from raxNotFound being a pointer to a value NOT part of the rax values.
Using long long values (cast as pointer) creates an overlap risk: maybe one of the functionally useful long long value precisely is the value of raxNotFound.
Proposal: remove this requirement by 1) making raxNotFound a member of struct rax 2) in raxNew, initialize it same as today to (void)"rax-not-found-pointer" 3) add raxNewWithNotFound(raxNotFound) where users can specify their own value (maybe (void)0, (void*)-1, etc, depending on needs).
Is that something that would be considered?
Comment From: QuChen88
According to the current rax documentation, the proper way to check for the not-found condition is as follows:
The lookup function is the following:
void *raxFind(rax *rax, unsigned char *s, size_t len);
This function returns the special value raxNotFound if the key you are trying to access is not there, so an example usage is the following:
void *data = raxFind(rax,mykey,mykey_len);
if (data == raxNotFound) return;
printf("Key value is %p\n", data);
See https://github.com/antirez/rax
Comment From: zuiderkwast
@knggk are you using rax in another project outside of Redis?
If there is some real benefit in storing long long as a rax value in Redis, maybe it can be considered, but probably not if it's only for usage outside of Redis. That's my guess.
Comment From: knggk
Thanks for looking at this @zuiderkwast . I do use it within Redis for closed-source functionality. Obviously you could argue that this proposed rax extension be kept closed as well. Was curious if this was ever considered from OSS perspective?
As @QuChen88 pointed out the doc is not super clear that there's this underlying assumption on values being valid pointers. Is it worth adding it in?
Comment From: zuiderkwast
Ok, thx for explaining. I think adding complexity which is not used by the project itself is questionable. But if we make it usable for example from the module API, then at least it is used somewhere.
I don't think it matters if it is a valid pointer or not, so I agree a long cast to pointer can work. But even if the special value is made configurable, it will be impossible to store that value as a long, so there is still a limitation. What if we change the API of raxFind instead so it returns a boolean (found or not) and returns the value by reference?
int raxFind(rax *rax, unsigned char *key, size_t keylen, void **value);
Comment From: knggk
Nice! You're right my proposal is still making use of a special value that the user of rax would need to think hard about. I much prefer your solution that's generic to all uses. (And seems doable since the rax implementation itself isn't dependent on raxNotFound.)
Would you change raxFind's signature or add a new API? Does it need to be a module API to justify it? (I am happy to craft a PR for this.)
Comment From: zuiderkwast
What I say here is just what I can guess based on my experience. Finally it is up to the core team to decide what's acceptable and what's not.
I think we don't want to keep multiple APIs for the same purpose. It is just more to test and maintain. It better to change the signature of the function.
The module API was just an example. I don't know any module API that we need where this can be useful. Also, I don't know if this can be accepted if it is not needed within redis. You can try. :-)
Comment From: knggk
Understood, thanks for your insights and suggestions Viktor 🙏
Comment From: zuiderkwast
Hello again Guillaume. The module API has a dict API which is backed by rax. RM_DictSet, RM_DictGet etc, implemented here. It can store void-pointers, but there is nothing stopping the user from storing integers cast to void-pointers in this API. Thus, I believe it is possible to accidentally store the magic raxNotFound value, so probably this change is beneficial for the module API already.
@enjoy-binbin, you're a rax expert. :) Does this make sense?
Comment From: sundb
@zuiderkwast Why not save an integer pointer? The same can be done if the user wants to store a double or others.
Comment From: enjoy-binbin
:) actually, i am not a rax expert, you must have remembered it wrong
Comment From: zuiderkwast
Hehe, sorry @enjoy-binbin. @sundb, you're the real rax expert. :) Welcome to join the discussion.
To store a pointer to an integer, you first need to allocate memory for the insteger somewhere, like
int *p = RedisModule_Alloc(sizeof(int));
*p = 42;
RedisModule_DictSetC(d, "foo", strlen("foo"), p);
If you want to store a lot of integers or other values which are not bigger than size of a pointer, it is more economical to just cast it to pointer.
RedisModule_DictSetC(d, "foo", strlen("foo"), (void*)42);
I think people do tricks like this with pointers so it is better if we can support all possible pointer values.
On platforms where sizeof(double) <= sizeof(void *) it works for double too.
Comment From: sundb
@zuiderkwast Agree with you that it's a waste to save a pointer for integer. I prefer the interface you mentioned.
int raxFind(rax *rax, unsigned char *key, size_t keylen, void **value);
Comment From: zuiderkwast
Ok, @knggk do you want to go ahead and implement this?
Comment From: knggk
Nice, thanks @zuiderkwast ! That's right we'd prefer not to allocate values when we can simply cast as in your proposed improved API.
I will craft a PR shortly.
Comment From: guillaumekoenig
This surfaced: void** is not compatible with any other pointer to pointer type. I think it's somewhat ok since users would know what kind of data they insert in their rax, but it does mean all the raxFind callsites must manually cast to void**. Maybe it's one of the reasons for the initial design choice of raxNotFound.
Note that raxRemove does have a void** argument to return the previous value, so it wouldn't be completely new.
An alternative is to have a void* instead. But then the API is pretty confusing to users. They need to understand to pass &outputpointer while outputpointer would compile fine.
I can continue with void** but wanted to hear other people's thoughts on this.
Comment From: zuiderkwast
Good point. But it can be called like this?
long long value;
if (raxFind(rax, key, keylen, &(void *)value)) ...
Comment From: guillaumekoenig
Yes I believe your long long example would work. The concern is you need that cast with any type. Consider:
client *c;
if (raxFind(rax, key, keylen, &(void *)c)) ...
Or possibly:
client *c;
if (raxFind(rax, key, keylen, (void **)&c)) ...
Because client ** is not compatible with void **.
Comment From: zuiderkwast
Yes, &(void *)c. I'm fine with that everywhere.
The other variant (void **)&c gives a warning I think.
Comment From: zuiderkwast
(Closed by mistake, sorry.)
Comment From: zuiderkwast
Another possibility is
void *raxFind(rax *r, char *key, size_t keylen, int *wasfound);
where wasfound is set to 1 or 0, if the key was found or not and the value is returned. This style is used in the module API IIRC. Is it better?
I don't know what is best. It's nice to be able to use if on the return value, like if (raxFind(...)) ....
Comment From: guillaumekoenig
Update: it turns out that &(void*)c doesn't compile but (void**)&c does (when assigning an argument of type void**).
I agree that it feels more natural to do if (raxFind(..., &value)) ... rather than value = raxFind(..., &wasfound); if (wasfound) ....
Comment From: knggk
@zuiderkwast finally got around to finishing the PR based on your proposal in https://github.com/redis/redis/issues/12709#issuecomment-1788069559 and with tests passing. What do you think?
Comment From: madolson
Took a look and I also like the API. The only suggestion I had was that I think we should always do the casting after we get the (void ) object out of rax find, to avoid the casting of the object to void *. Example:
client *lookupClientByID(uint64_t id) {
id = htonu64(id);
void *c = NULL;
raxFind(server.clients_index,(unsigned char*)&id,sizeof(id),&c);
return (client *)c;
}
This seems a lot clearer to me what is happening, and more straightforward to implement correctly. We could consider something like typedef raxValue void * as well, to make it clear that we are getting a raxValue out and then casting it, but I don't feel very strongly about that. Otherwise, it seems pretty straightforward to clean up and merge.
Comment From: zuiderkwast
@knggk Did you open a PR? I can see your branch but I don't see a PR.
Comment From: madolson
There is no PR, but you can see the change here: https://github.com/redis/redis/compare/unstable...knggk:redis:unstable
Comment From: knggk
Thanks @zuiderkwast and @madolson , I've made the proposed changes in an actual PR at #12837