Thread: HashTable help?

  1. #46
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,794
    for example make your HashTableLookUp return list_ptr, in this case you will have no problem to update list_ptr->value
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  2. #47
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    if it returns an address to the old value then changing that address wouldn't work right because the list->value still points to the old address

  3. #48
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,794
    Quote Originally Posted by -EquinoX- View Post
    if it returns an address to the old value then changing that address wouldn't work right because the list->value still points to the old address
    if you write

    list->value = <new value> ; it will defiitely not point to the old address.

    so what do you mean?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  4. #49
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    deleted
    Last edited by -EquinoX-; 03-29-2008 at 08:40 AM.

  5. #50
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    one simple question, do I have to include cstr.h or cstr.c in hash.c in order to use the StringHash that I created in the cstr module?

  6. #51
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,794
    probably cstr.h - look at your warnings about explicitely defined functions to be sure
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  7. #52
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    I tried cstr.h and it doesn't works, I tried cstr.c and it works

  8. #53
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,794
    You should not include one c file into another
    but you should compile them together
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  9. #54
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    okay I got it

  10. #55
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    check out my new version of insert, do you think it's perfect now??

    Code:
    boolean HashTableInsert(HashTable *this, const char* key, const char* value)
    {
      list_t *new_list, *temp;
    
      int_u4 hashval = StringHash(key) &#37; this->length;
      /* Attempt to allocate memory for list */
      if ((new_list = malloc(sizeof(list_t))) == NULL)
        outOfMemory_(__LINE__, __FILE__, "struct node creation");
    
      /* Does item already exist? */
      if (HashTableContains(this, key) == true){
        for (temp = this->table[hashval]; temp!= NULL; temp = temp->next){
          if (strcmp(key, temp->key) == 0){
            StringDestruct(temp->value);
            temp->value = StringConstruct(value);
            return false;
          }
        }
      }
      else{
      /* Insert into list */
        new_list->key = StringConstruct(key);
        new_list->value = StringConstruct(value);
        new_list->next = this->table[hashval];
        this->table[hashval] = new_list;
        this->length = this->length + 1;
        return true;
      }
    }
    StringDestruct basically just removes old value from the heap space, basically it just calls free to the pointer of temp-> value at that time after it free's the old value it creates a copy of the new value in the heap space and then have temp->value to that address

  11. #56
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,794
    1. new_list is used only in else - but allocated anyway - you get memory leak in the if case
    2. if this->table[hashval] was not NULL in the else case - you effectivly loosing this value
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  12. #57
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    so I just should use either new_list or temp for both??

  13. #58
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,794
    so you should allocate new_list only in the else branch - becase when the key is found - you do not need to create the new node - instead you are replacing value of the existing node
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  14. #59
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    I see and that would solve problem no.1 that you mentioned above right? but how about number 2? I don't get what you mean

    what about now:

    Code:
    boolean HashTableInsert(HashTable *this, const char* key, const char* value)
    {
      list_t *temp;
    
      int_u4 hashval = StringHash(key) &#37; this->length;
    
      /* Does item already exist? */
      if (HashTableContains(this, key) == true){
        for (temp = this->table[hashval]; temp!= NULL; temp = temp->next){
          if (strcmp(key, temp->key) == 0){
            StringDestruct(temp->value);
            temp->value = StringConstruct(value);
            return false;
          }
        }
      }
      else if (temp == NULL){
      /* Insert into list */
        list_t *new_list;
        if ((new_list = malloc(sizeof(list_t))) == NULL)
          outOfMemory_(__LINE__, __FILE__, "struct node creation");
        new_list->key = StringConstruct(key);
        new_list->value = StringConstruct(value);
        new_list->next = this->table[hashval];
        this->table[hashval] = new_list;
        this->length = this->length + 1;
        return true;
      }
    }
    Last edited by -EquinoX-; 03-29-2008 at 10:59 AM.

  15. #60
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,794
    in your else branch you could have already several links connected to the same have entry
    so the list could be not empty.

    How would you go about adding new node to the list if you know that the new node is pointed by new_list pointer and list head is stored in the this->table[hashval] pointer?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hashtable v.s. Dictionary
    By George2 in forum C# Programming
    Replies: 1
    Last Post: 06-06-2008, 02:09 AM
  2. Missing Entries in Hashtable
    By wuzzo87 in forum C Programming
    Replies: 3
    Last Post: 05-13-2007, 12:46 AM
  3. Replies: 12
    Last Post: 10-22-2006, 08:37 PM
  4. game hashtable
    By disks86 in forum C++ Programming
    Replies: 1
    Last Post: 12-16-2005, 01:42 PM
  5. oh me oh my hash maps up the wazoo
    By DarkDays in forum C++ Programming
    Replies: 5
    Last Post: 11-30-2001, 12:54 PM