Thread: Using an array with a hashmap

You're going to have to actually tell us what the problem is. Even if your description is right, and why not, the problem would still lie in the code for HashGetOne (and maybe HashReplace), which is conspicuously absent.

Things my Hat tells me: don't you want to do a HashReplace in the case where the array is found too? I don't know what it does, so I can't say. Although the change should be reflected in the original array that d points to, so that's ok. Does the spend function take the money out of p's account, or do we need to do that too?

I don't really think the workings of the hashmap utilities are relevant here, but if you think it will help here you go:

Code:

typedef struct HashEntry
{
	struct HashEntry *next;
	void *p;
	char key[1];
} HashEntry;

struct HashTable
{
	int bucketsm1, ents;
	int maxload; /* percent out of 100 */
	HashEntry **lists;
};

void *HashGetOne(HashTable *h, const char *s)
{
	int slot;
	HashEntry *l;

	slot = hash_string(s) & h->bucketsm1;
	l = h->lists[slot];

	while (l)
	{
		if (!strcasecmp(s, l->key))
			return l->p;
		l = l->next;
	}
	return NULL;
}

void HashReplace(HashTable *h, const char *s, const void *p)
{
	int slot;
	HashEntry *l, *last;

	slot = hash_string(s) & h->bucketsm1;
	l = h->lists[slot];

	/* try to find it */
	while (l)
	{
		if (!strcasecmp(s, l->key))
		{
			/* found it, replace data and return */
			l->p = (void*)p;
			/* no need to modify h->ents */
			return;
		}
		last = l;
		l = l->next;
	}

	/* it's not in the table, add normally */
	HashAdd(h, s, p);
}

For the record, I only use hashreplace because I specifically only want one of each key in my mappings. Theoretically since my adding and searching is fine I could probably just use hashadd and get the same results, I just decided to use hashreplace.

The hash map utilities were provided to me by someone who doesn't suck at programming, so I'm confident there are no errors in it and the error is definitely in the code I originally provided.

And yes, Spend_Pts checks the players account, withdraws the money if it is available, or if not available, returns 0 and does not withdraw any points.

For errors, on this line:
newdock[ship] = newdock[ship] + 1;
I get an "incompatible types on assignment" error.

Maybe that's the only problem, but I can't be sure since I haven't been able to get to runtime yet. For certain, my understanding of converting a void pointer to a typedef int array is terrible; I seem to have a problem grasping this concept.

-R

Originally Posted by Reaem

For errors, on this line:
newdock[ship] = newdock[ship] + 1;
I get an "incompatible types on assignment" error.

Not possible. The following code compiles perfectly well:

Code:

typedef int Dock[8];

int main(void){
    Dock newdock = {0,0,0,0,0,0,0,0};
    int ship = 4;

    newdock[ship] = newdock[ship] + 1;

    return 0;
}

And since it's basically identical to your code, that means your code compiles fine too. If there's really a problem, try using (newdock[ship])++, which does the same thing (adds 1 to newdock[ship]); if that doesn't work, then we know there's something screwy.

Originally Posted by reaem

Maybe that's the only problem, but I can't be sure since I haven't been able to get to runtime yet. For certain, my understanding of converting a void pointer to a typedef int array is terrible; I seem to have a problem grasping this concept.

-R

The part that worries me is that you think there is a concept here to grasp. void * just means "a pointer" -- this way a function can take a pointer to a struct, or a pointer to a double, or a pointer to a long, or .... (Granted, the code inside has to know how to handle whatever is being pointed to.) In this case, your HashEntry doesn't care what the data is, it just wants a pointer to it to put in the struct with everything else.

You have a slight flaw in your logic. In C, when you declare an array in block scope, the compiler allocates space for that array on the stack.

Example:

Code:

void function(void) {
   int newdock[8] = {0,0,0,0,0,0,0,0};  // all 8 of these ints will be on the stack
}

You can verify this by checking the results of this program:

Code:

#include <stdio.h>

typedef int Dock[8];

int main(void) {
  int i = 0;
  Dock dock1 = {0,0,0,0,0,0,0,0};
  int *dock2 = calloc(8, sizeof(int));
  
  printf("%-9s = %d\n", "&i", &i);
  
  printf("%-9s = %d\n", "&dock1", &dock1);
  printf("%-9s = %d\n", "&dock1[0]", &dock1[0]);
  
  printf("%-9s = %d\n", "&dock2", &dock2);
  printf("%-9s = %d\n", "&dock2[0]", &dock2[0]);
  
  free(dock2);
  return 0;
}

It should print something similar to this:

Code:

&i        = 2293612  Clearly this must be on the stack
&dock1    = 2293568
&dock1[0] = 2293568  The first element of the array is on the stack
&dock2    = 2293564  The int* is on the stack
&dock2[0] = 4007088  The first element of the int* 'array' is on the heap

Your hash table stores void pointers. That is, it doesn't make a copy of whatever the pointer is pointing to and store THAT in the array, it just stores a copy of the pointer. If you try to declare an array on the stack:

Code:

   Dock newdock = {0,0,0,0,0,0,0,0};
   newdock[ship] = newdock[ship] + 1;
   HashReplace(docks, p->name, newdock);

you cannot store that in your hash table. You would be storing a pointer to an array allocated on the stack, and that memory is going to disappear after the function returns.

Instead, you could make your dock an int pointer. That way you can heap allocate the memory using malloc (or calloc, which will zero it for you). Storing a pointer to heap allocated memory in your hash table is perfectly valid, you just have to member to free it when you're done with it (that may require a modification to your hash table).

This shouldn't change the way you use the dock at all since you can use an int pointer as if it were an array anyway. Make sure to do proper bounds checking (which you would need to do with an array anyway), and you should be all set.

Now, with all that being said, I don't see any problem with you using a struct. You can heap allocate the struct just as easily, plus if you ever need to add anything to the dock in the future, it won't require too much effort, just add an additional field to the struct. I think this would actually make your code seem cleaner, and it won't hurt efficiency. I would much rather see this:

Code:

   dock->ship[n] // The nth ship in the dock

than this:

Code:

   dock[n] // The nth dock??

But that's just a matter of personal preference.

FINALLY some real answers, thank you arps =)