Using an array with a hashmap

This is a discussion on Using an array with a hashmap within the C Programming forums, part of the General Programming Boards category; I'm a bit fuzzy on the workings of c, and google/tutorials haven't helped me figure out the best way to ...

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    3

    Question Using an array with a hashmap

    I'm a bit fuzzy on the workings of c, and google/tutorials haven't helped me figure out the best way to do this.
    I'm trying to create a typdef'd array of 8 ints to be inserted into a hashmap to be recalled later as a variable of the same type. So, this is what I did:

    Code:
    typedef int Dock[8];
    
    void Cbuyship(const char *tc, const char *params, Player *p, const Target *target)
    {
    	int ship = atoi(params);
    	if (ship < 1 || ship > 8)
    		return;
    	
    	ship--; //for convenience
    	
    	//cost checking
    	if (!Spend_Pts(p, ship_costs[ship]))
    		return;
    	else
    	{
    		Dock *d = HashGetOne(docks, p->name);
    		
    		if (!d)
    		{
    			Dock newdock = {0,0,0,0,0,0,0,0};
    			newdock[ship] = newdock[ship] + 1;
    			HashReplace(docks, p->name, newdock);
    		}
    		else
    		{
    			*d[ship] = *d[ship] + 1;
    		}
    		chat->SendMessage(p,"Ship purchased");
    	}
    }
    The basic idea of Cbuyship is it's a command where the user types !buyship # (out of 8 ship choices) and one of those is added to the player's dock. If the player doesn't have a dock listed somewhere in the hashmap, null is returned and, in the if block, a new one is created. # gets passed as "params".

    Obviously, my implementation up there doesn't work for a number of reasons.

    I could find ways around this (one idea was to make a struct with the array in it), but I really should learn how to do this correctly anyways, and my code will be much cleaner and more efficient.

    So the question is, how is this done correctly?
    Thanks in advance and regards,
    -Reaem
    Last edited by Reaem; 03-15-2008 at 08:54 PM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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?

  3. #3
    Registered User
    Join Date
    Mar 2008
    Posts
    3
    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

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Reaem View Post
    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.

    Quote Originally Posted by reaem View Post
    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.

  5. #5
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    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.

  6. #6
    Registered User
    Join Date
    Mar 2008
    Posts
    3
    FINALLY some real answers, thank you arps =)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 08:25 PM
  2. Replies: 6
    Last Post: 11-09-2006, 03:28 AM
  3. [question]Analyzing data in a two-dimensional array
    By burbose in forum C Programming
    Replies: 2
    Last Post: 06-13-2005, 08:31 AM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 10:54 AM
  5. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 08:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21