Callback function wrapper, to change parameter count (HashTable implementation)

[Menachem]

Hi,

I'm getting back to C after a couple of years of Java, and I'm trying to figure out the C equivalent of a Java construct.

I'm implementing a HashMap (loosely based on Java's HashMap). I'd like to have a single iteration function that goes through all the key/value pairs, optionally stopping when a condition is reached. To loop through just the values (or just the keys), I want a wrapper function around the main iterator. Otherwise, I have to implement the iteration twice, and that's bug prone.

What I have so far:

// Iterate through the Map's entries; flag is THRU, WHILE, or UNTIL
int each_entry(struct Map *map,
int(*fn)(const char *key, void *data), int flag)
{
int count = 0;
while (/* There are more entries */) {
// TODO: Find next entry - implementation specific
int retval = fn(entry->key, entry->data);
if (flag == WHILE && !retval || flag == UNTIL && retval)
break;
else
++count;
}
return count; // count < size, if broke out early.
}

Now, how do I write the helper method each_value()? The solution I came up with, that looks like it should work:

static int (*_usr_data_fn)(void *data);
static int fn_entry_value(const char *key, void *data)
{
return _usr_data_fn(data);
}

int each_value(struct Map *map, int(*fn)(void *data), int flag)
{
_usr_data_fn = fn;
int count = each_entry(map, fn_entry_value, flag);
_usr_data_fn = (int (*)(void *)) 0;
}

In addition to being very inelegant, however, this stores the user-supplied single-parameter function in a static location, so it isn't threadsafe for use in a library.

I'm hoping to implement has_value() using the single-parameter callback function (stopping when the value is found, of course).


In Java, I can code the main foreach function like so:
int each_entry(Map map, BiFunction fn, int flag) {
int count = 0;
for (Map.Entry entry : (Set<Map.Entry>)map.entrySet()) {
Object result = fn.apply(entry.getKey(), entry.getValue());
if (flag == 1 && result != NULL || flag == 2 && result == NULL)
break;
++count;
}
return count; // The number of successful iterations.
}

And then code the helper functions with inner classes:
int each_key(Map map, Function fn, int flag) {
return each_entry(map, new BiFunction() {
public Object apply(Object key, Object val) {
return fn.apply(key);
}
}, flag);
}

Which, with lambda expressions, becomes:
int each_value(Map map, Function fn, int flag) {
return each_entry(map, (key, val) -> fn.apply(val), flag);
}

(Yes, I know that Java also has map.keySet() and map.values(). Internally, the iterators for these are based on the single Entry iterator.)

To clarify: I'm looking to use a callback function that takes a single parameter, and have it be called by an (internal) callback function that takes two parameters.

[Anton Shepelev]

Menachem:

>I'm implementing a HashMap (loosely based on Java's
>HashMap). I'd like to have a single iteration function
>that goes through all the key/value pairs, optionally
>stopping when a condition is reached. To loop through just
>the values (or just the keys), I want a wrapper function
>around the main iterator. Otherwise, I have to implement
>the iteration twice, and that's bug prone.
>
>What I have so far:
>
> // Iterate through the Map's entries; flag is THRU, WHILE, or UNTIL
> int each_entry(struct Map *map,
> int(*fn)(const char *key, void *data), int flag)
> {
> int count = 0;
> while (/* There are more entries */) {
> // TODO: Find next entry - implementation specific
> int retval = fn(entry->key, entry->data);
> if (flag == WHILE && !retval || flag == UNTIL && retval)
> break;
> else
> ++count;
> }
> return count; // count < size, if broke out early.
> }
>
>Now, how do I write the helper method each_value()?

How about stopping at that and using each_entry for looping
both over the values and over the keys? How about
implementing the whole structure via physical subtyping and
accessing it with normal C loops?

>The solution I came up with, that looks like it should
>work:
>
> static int (*_usr_data_fn)(void *data);
> static int fn_entry_value(const char *key, void *data)
> {
> return _usr_data_fn(data);
> }
>
> int each_value(struct Map *map, int(*fn)(void *data), int flag)
> {
> _usr_data_fn = fn;
> int count = each_entry(map, fn_entry_value, flag);
> _usr_data_fn = (int (*)(void *)) 0;
> }
>
>In addition to being very inelegant, however, this stores
>the user-supplied single-parameter function in a static
>location, so it isn't threadsafe for use in a library.

Pass that function wrapped in the data parameter, possibly
together with some data pointer, i.e.:

struct ev_data_t
{ int (*_usr_data_fn)(void *data)
void* data;
}
/* ... */
evdata->_usr_data_fn( evdata->data );

--
() ascii ribbon campaign - against html e-mail
/\ http://preview.tinyurl.com/qcy6mjc [archived]

[james...@alumni.caltech.edu]

On Monday, August 27, 2018 at 5:56:15 AM UTC-4, Anton Shepelev wrote:
> Menachem:
>
> >I'm implementing a HashMap (loosely based on Java's

...

Google groups thinks your message is in Hebrew, and offers to translate it. Both in the original and translated versions, it displays the message right justified, rather than left.
It hasn't shown up Mozilla Thunderbird yet - it may have triggered a message filter.

[Anton Shepelev]

I wrote:

>struct ev_data_t
>{ int (*_usr_data_fn)(void *data)
> void* data;
>}
>/* ... */
>evdata->_usr_data_fn( evdata->data );

Correct that to:

typedef int (*_usr_data_fn)(void *data);

struct ev_data_t
{ _usr_data_fn fn;
void * data;
};
/* ... */
struct ev_data_t *evdata;
/* ... */
evdata->fn( evdata->data );

[Anton Shepelev]

James Kuyper:

>Google groups thinks your message is in Hebrew, and offers
>to translate it. Both in the original and translated
>versions, it displays the message right justified, rather
>than left. It hasn't shown up Mozilla Thunderbird yet - it
>may have triggered a message filter.

It shows OK in both E.-S. and AIOE via Sylpheed, and Howard
Knight confirms:

http://al.howardknight.net/msgid.cgi?ID=153537440600

[Anton Shepelev]

Stefan Ram:

>FWIW, I am always sending
>
>Content-Language: en
>
> in the headers of each of my English-language posts.
> Not that I am believing that Google will take this into
> account. Surely Google is using advanced AI to deduce
> the language of a post.

My messages are as plain-jane vanilla w/o sugar and food
coloring as can be:

Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit

If that is not sufficinet for Google, it must clueless
beyond all conjecture.

[Menachem]

On Monday, August 27, 2018 at 5:56:15 AM UTC-4, Anton Shepelev wrote:
> Menachem:

BTW, I see the same issue that Google Groups thinks it's in Hebrew. Sometimes AI's can be unbelievably stupid. Lo chashuv (Hebrew for "not important").

>
> >
> >What I have so far:
> >
> > // Iterate through the Map's entries; flag is THRU, WHILE, or UNTIL
> > int each_entry(struct Map *map,
> > int(*fn)(const char *key, void *data), int flag)
> > {
> > int count = 0;
> > while (/* There are more entries */) {
> > // TODO: Find next entry - implementation specific
> > int retval = fn(entry->key, entry->data);
> > if (flag == WHILE && !retval || flag == UNTIL && retval)
> > break;
> > else
> > ++count;
> > }
> > return count; // count < size, if broke out early.
> > }
> >
> >Now, how do I write the helper method each_value()?
>
> How about stopping at that and using each_entry for looping
> both over the values and over the keys? How about
> implementing the whole structure via physical subtyping and
> accessing it with normal C loops?

This function is part of the public API, too, though I think I need to add a third parameter to the callback function, supplying user data such as another object to compare this to.

I'm not sure what you mean by "implementing ... via physical subtyping". If you mean I should supply an Iterator type that knows about my implementation, and implement all foreach() functions via that Iterator, that is one option I hadn't considered. It still means duplicating some of the looping construct in each foreach(), but for my specific situation none of that will involve the Map implementation, only the Iterator interface.

> >The solution I came up with, that looks like it should work:
> >
> > static int (*_usr_data_fn)(void *data);
> > static int fn_entry_value(const char *key, void *data)
> > {
> > return _usr_data_fn(data);
> > }
> >
> > int each_value(struct Map *map, int(*fn)(void *data), int flag)
> > {
> > _usr_data_fn = fn;
> > int count = each_entry(map, fn_entry_value, flag);
> > _usr_data_fn = (int (*)(void *)) 0;
> > }
> >
> >In addition to being very inelegant, however, this stores
> >the user-supplied single-parameter function in a static
> >location, so it isn't threadsafe for use in a library.
>
> Pass that function wrapped in the data parameter, possibly
> together with some data pointer, i.e.:
>

> typedef int (*_usr_data_fn)(void *data);
> struct ev_data_t
> { _usr_data_fn fn;

> void* data;
> }
> /* ... */

> struct ev_data_t *evdata;
> /* ... */
> evdata->fn( evdata->data );

(As corrected elsethread.)

If I understand you correctly, using an extra data parameter - which I suppose I need in any case - can do what I need. The extra data parameter to the entry iterator will be both the user's function pointer and the user's extra data to that function.

struct fn_data_t {
int (*fn)(void *data, void *extra);
void *extra;
};
static int fn_entry_value(const char *key, void *data, void *extra)
{
struct fn_data_t *fn_data = extra;
return fn_data->fn(data, fn_data->extra);
}

int each_value(struct Map *map, int(*fn)(void *data, void *extra),
void *extra, int flag)
{
struct fn_data_t fn_data = { fn, extra };
return each_entry(map, fn_entry_value, &fn_data, flag);
}

And of course changing the signature of each_entry() to match.

That looks like it might work. A possible use case would be:

_Bool contains_value(struct Map *map, char *str)
{
int count = each_value(map, strcmp, str, WHILE);
return count < map->size; // We stopped when strcmp return 0
}

The idea was to have the same callbacks for several sorts of containers. Adding the extra data parameter is work, but obviously necessary anyhow.

Thanks a lot, Anton. In SO parlance, I "accept" this answer.

-- Menachem Salomon

[Keith Thompson]

I see that too, but I see nothing in the headers that would cause that:

Mime-Version: 1.0

Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit

It looks fine for me under Gnus.

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Menachem]

It is possible that it saw my name as the first word, sort of correctly identified that as transliterated from Hebrew, and stupidly made an assumption about the rest.

I say only "sort of correctly" because names are more often transliterated than translated, and should be identified as being written in the target language rather than the original. So long as the name is written in English (rather than the original, מנחם), it should be recognized as such.

-- Menachem Salomon

P.S. Keith, what about my original question? I would like to hear your opinion.

[Anton Shepelev]

Menachem to Anton Shepelev:

>>How about implementing the whole structure via physical
>>subtyping and accessing it with normal C loops?
>
>This function is part of the public API, too, though I
>think I need to add a third parameter to the callback
>function, supplying user data such as another object to
>compare this to.

Yes.

>I'm not sure what you mean by "implementing ... via
>physical subtyping".

It is explained, for example, in this article:

https://www.researchgate.net/publication/2593526_Coping_with_Type_Casts_in_C

You can download the full PDF.

>>Pass that function wrapped in the data parameter, possibly
>>together with some data pointer, i.e.:
>>>
>>typedef int (*_usr_data_fn)(void *data);
>>struct ev_data_t
>>{ _usr_data_fn fn;
>> void* data;
>>}
>>/* ... */
>>struct ev_data_t *evdata;
>>/* ... */
>>evdata->fn( evdata->data );
>>(As corrected elsethread.)
>
>If I understand you correctly, using an extra data
>parameter - which I suppose I need in any case - can do
>what I need. The extra data parameter to the entry
>iterator will be both the user's function pointer and the
>user's extra data to that function.

Yes.

> struct fn_data_t {
> int (*fn)(void *data, void *extra);
> void *extra;
> };
> static int fn_entry_value(const char *key, void *data, void *extra)
> {
> struct fn_data_t *fn_data = extra;
> return fn_data->fn(data, fn_data->extra);
> }
>
> int each_value(struct Map *map, int(*fn)(void *data, void *extra),
> void *extra, int flag)
> {
> struct fn_data_t fn_data = { fn, extra };
> return each_entry(map, fn_entry_value, &fn_data, flag);
> }

This is not what I meant. In my idea, fn_data_t.fn should
take only one void*, and consequently only one void* be
passed to the generic iterator:

struct fn_data_t {
int (*fn)( void *data );
void *extra;
};

static int fn_entry_value(const char *key, void *data)
{
struct fn_data_t *fn_data = data;
return fn_data->fn(fn_data->extra);
}

The principle is to group all the necessary data (including
function pointers) into a single sturct on every level.