0

I'm trying to port a codebase from C to Rust. Type casting is very implicit and manually trying to control memory makes it very difficult to figure out the best solution. The data structure I am trying to port implements a hashtable:

// An entry in the hash table
typedef struct DataEntryStruct
{
    char   *key;
    int    data;
    struct DataEntryStruct *next;
} DataEntry;

typedef struct DataEntryStruct *HashTable;

// Hash a string to an integer
unsigned int gethash(char *str)
{
    unsigned int hash = 5381;
    unsigned int retHash;
    int c;
    while ((c = *str++))
    {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }
    retHash = hash % HASHTABLEMAXSIZE;
    return retHash;
}

// Produce a duplicate string
char *dupstr(const char *s)
{
    size_t size = strlen(s) + 1;
    char *p = malloc(size);
    if (p) memcpy(p, s, size);
    return p;
}

// Create a hash table
HashTable *hashtable_create()
{
    int i;
    HashTable *ht = (HashTable *) calloc(HASHTABLEMAXSIZE, sizeof(HashTable));
    if (ht != NULL)
    {
        for (i = 0; i < HASHTABLEMAXSIZE; i++) ht[i] = NULL;
    }
    return ht;
}

I think I have figured out how to implement the first blocks, but not the last one with memory allocation:

struct DataEntry {
    key: &str,
    data: u32,
    next: Option<&mut HashTable>,
}

let HashTable = &mut DataEntry;

// get hash for a string
fn gethash(val: &str) -> u32 {
    let mut hash: u32 = 5381;

    for c in val.chars() {
        hash = (hash << 5 as u32).wrapping_add(hash).wrapping_add(c as u32);
    }

    return hash % HASHTABLEMAXSIZE;
}

// Produce a duplcate string
fn dupstr(val: &str) -> &str {
    // only use rust .clone func
    val.clone()
}

How do I implement hashtable_create while being as true as I can to the source?

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
ziedTn
  • 262
  • 5
  • 17
  • Trust your compiler `hash = ((hash << 5) + hash) + c; /* hash * 33 + c */` --> `hash = 33u*hash + c;` - in both languages. – chux - Reinstate Monica Jul 19 '21 at 19:13
  • `retHash = hash % HASHTABLEMAXSIZE;` is suspicious. Is `HASHTABLEMAXSIZE` the current table size or the maximum table size? – chux - Reinstate Monica Jul 19 '21 at 19:16
  • 1
    `HASHTABLEMAXSIZE` is defined as constant, and it's used to within the `hashtable_create` function to generate the `Hashtable` with total size of `HASHTABLEMAXSIZE` – ziedTn Jul 19 '21 at 19:35
  • The _max_ in `HASHTABLEMAXSIZE` hints otherwise. That implies the hash table size could be other values and `HASHTABLEMAXSIZE` is just the _max_. Perhaps `HASHTABLESIZE` instead? BTW, as used, `HASHTABLEMAXSIZE` has an advantage if it is [prime](https://stackoverflow.com/a/32915815/2410359). – chux - Reinstate Monica Jul 19 '21 at 19:49
  • i see, `HASHTABLEMAXSIZE` is defined as constant `#define HASHTABLEMAXSIZE 128000` and it's used to create the hashtable part of ```int i; HashTable *ht = (HashTable *) calloc(HASHTABLEMAXSIZE, sizeof(HashTable)); ``` – ziedTn Jul 19 '21 at 20:04
  • @chux-ReinstateMonica i think that the right way to approach in rust will be using hashmap with custom hash function, however i cannot really figure out a way to port the same `hashtable_create` to rust while as true as i can – ziedTn Jul 19 '21 at 20:08
  • Why do you zero the contents of `ht` twice in the C code? Once because [`calloc` does it](https://linux.die.net/man/3/calloc), then the second time in the `for` loop… – Jmb Jul 20 '21 at 06:55
  • In C, `DataEntry.next` is an optional `DataEntry`. Why is it an optional `HashTable` in Rust? – Jmb Jul 20 '21 at 06:58
  • The closest match for the type of `HashTable` in Rust would be `Vec – Jmb Jul 20 '21 at 07:01
  • thanks @Jmb, this looks the best way to proceed, just a question, why two options to proceed as i thibk the `Vec – ziedTn Jul 21 '21 at 09:09
  • `Vec – Jmb Jul 21 '21 at 10:28
  • thanks @Jmb i think i will skip one to one translation, and explore hashmap and extend it to fit in this context – ziedTn Jul 21 '21 at 11:03

0 Answers0