Fuck my life, I could use some help

So I started a project for my programming class that I thought was due on Friday since projects are always due Friday, however I checked the due date and apparently it's today at midnight, so if anyone could help me with some of this id be eternally grateful.

I'm supposed to build a hash table abstract data type, where the ADT will permit me to insert and search for data records in the hash table. The preliminary description of the program is as follows (this is being programmed in C):

_____________________________________________________________

"In this project, you will build a hash table abstract data type. Your ADT will permit
users to insert and search for data records in the hash table; it will also allow users to sort
data records within the hash table, and to examine them in sorted order. Your ADT will
be polymorphic, permitting the data record type to be defined by the user, and permitting
the user to control hashing and sorting by user-provided functions accessed from the ADT
via function pointers. In addition to building the hash table ADT, you will also rewrite
the parse.c example from lecture to use your new ADT. Lastly, you will also write test
vectors to test part of the ADT interface.
1 Hash Table
You are to implement a hash table as an abstract data type. As described in lecture, a
hash table allows users to insert and search for data in the hash table efficiently. Hash
table operations require the user to provide a “key” that uniquely identifies the data the
user is referring to. In this project, the hash table keys are strings. Hence, all data stored
in the hash table must be associated with a string that uniquely identifies the data. A
“hash function” is applied on the key to specify a bucket (linked list) within the hash table
where the data is located. For insert operations, the data is added to the hashed linked
list; for search operations, a linear search through the hashed linked list is performed to
find the data.
1.1 Polymorphism
Your hash table ADT will be polymorphic, allowing users to define their own data records
stored in the hash table. Your ADT will not place any constraints on the size or composition of the user’s data records. (This will permit your ADT to be very flexible, and
usable in a large number of applications). To facilitate this, the per-bucket linked lists
will employ self-referencing structures defined in your ADT. However, rather than embed
the user’s data in these structures, your linked list structures will instead point to the
user-defined data records through generic pointers.
Figure 1 illustrates the use of generic pointers. In Figure 1, user-defined structures are
denoted by shaded boxes while ADT structures are denoted by white boxes. Furthermore,
normal pointers are denoted by arrows with filled arrowheads while generic pointers are
denoted by arrows with white arrowheads. Figure 1 illustrates the structures of the ADT,
including the main “hash table” struct which contains a pointer to a buckets array. Each
element in the buckets array points to a linked list consisting of “hash entry” structs.
_____________________________________________________________

tl;dr: I'm supposed to build a hash table abstract data type, where the ADT will permit me to insert and search for data records in the hash table, except I have no idea how to make an abstract data type. This is being programmed in C.

>>16
Start with declaring the data types. Since you're using chaining, each hash table bucket is a linked list. It's best to use a doubly-linked list with a sentinel node as it provides the most efficient insertion and deletion of nodes.


typedef struct hash_table_link_
{
    struct hash_table_link_ *next;
    struct hash_table_link_ *prev;
}
hash_table_link;

typedef struct hash_table_node_
{
    hash_table_link link;
    void* object;
}
hash_table_node;

typedef struct hash_table_
{
    hash_table_link *buckets;
    size_t bucket_size;
    size_t size;
    int (*hash_func)(char *);
    int (*cmp_func)(void *, void *)
}
hash_table, *Phash_table;

Was that so hard?

>>16
This is very important. You need to rename "hash.h" to "void.h" which should handle all the common functions,#defines,#ifdefs and #includes.

>>22
+2 Susscoins.

>>22,23
"void.h" is an anti-pattern. Kind of like having a generic "utilities.h" header, or naming modules or classes with the "Manager" suffix.

>>19
That's a declaration, not a defintion you fucking moron. Christ, go learn what static typing is before you make another retarded ass statement.

>>25
Yes. >>19-baka also recommended to use a array type without a length specifier for the buckets element, which is simply wrong. A novice /prog/rider indeed.

>>21-san's design is a better starting point.

>>26
>>21 here. I just re-read the OPs problem statement and have updated the code, it's actually an associative key-value hash map, not a hash set, so one needs to store both the key and value in each node. Therefore:

typedef struct hash_table_node_
{
    hash_table_link link;
    char *key;
    void *value;
}
hash_table_node;

I'm not a novice /prog/rider okay I can program in Haskell I just don't do that much stuff in C okay ;~;
I thought that an array without its length specified is equivalent to a pointer?

>>28
I thought that an array without its length specified is equivalent to a pointer?
Only as an argument to a function. It's not compliant standard C89/C99 when used as an element type in a structure. Many C compilers like GCC or Clang allow it as an extension when placed at the end of a structure, in which case it's equivalent to a zero-sized array, meaning that you need to manually allocate space for it. Not suitable for an ADT because you only allocate the hash_table ADT once and therefore you can't dynamically resize how many buckets you have.

>>28
A one dimensional array is equivalent to a pointer when it's used in a functions parameters.

functions parameters
Function argument is the correct C nomenclature.

ISO/IEC 9899:1999 WG14 N1256, Section 3.3 Clause 1

argument

actual argument
actual parameter (deprecated)

Expression in the comma-separated list bounded by the parentheses in a function call expression, or a sequence of preprocessing tokens in the comma-separated list bounded by the parentheses in a function-like macro invocation.

MY AUTISM IS ANGRY WITH THIS THREAD. YOU CAN'T IMPLEMENT PROPER AUTISTIC ZOMG-OPTIMIZED POLYMORPHISM IN C BECAUSE FUNCTION POINTERS DON'T GET INLINED (NO SHIT SHERLOCK). FUCK YOU FAGGOTS.

>>31
I was using K&R terminology.

>>33
K&R is deprecated. People who still go by K&R terminology are like people who still use COBOL instead of Java or C# for ENTERPRISE.

>>32
Virtual member function calls in C++ don't get inlined either unless it can be statically resolved by the compiler at compile time, which means that you would need to explicitly use a concrete type in the data structure code, which would make it non-polymorphic.

That said, C++ provides a much better form of compile-time polymorphism through the use of templates.

>>34
"That said, C++ provides a much better form of compile-time polymorphism through the use of templates. "

But that is weak when compared to Haskell.

>>34
Are you honestly suggesting the use of C++ as an alternative to C? Because you really seem to.

>>35
Weak? Haskell's type polymorphism is a strictly runtime mechanism, and it's type monomorphism is equivalent to C++'s ability to statically resolve virtual member function bindings at compile time if it can conclude that an object's actual type is only ever that of a single specific concrete type. C++'s templates provide a strict mechanism and elicit programmer intent for compile-time polymorphism.

>>36
Yes, as a pragmatic alternative. In fact, now is a good time to get back into C++ with the C++0x/C++11 standard being ratified next month. C++11 fixes a lot of the problems in C++98/03. I think anyone suggesting higher-level pure functional languages as an alternative to C are not very pragmatic.

I will defend my position, so please spare the use of ad hominem.

I wonder if the OP has given up and hung himself in his dorm room closet.

>>37
Haskell's type polymorphism is a strictly runtime mechanism
What.

>>38
Assembly is an alternative to C. Too much low-level for you?

>>38
spare the use of ad hominem

If there is a user ID attached to a user, a discussion tends to become a criticizing game. On the other hand, under the anonymous system, even though your opinion/information is criticized, you don't know with whom to be upset. Also with a user ID, those who participate in the site for a long time tend to have authority, and it becomes difficult for a user to disagree with them. Under a perfectly anonymous system, you can say, "it's boring," if it is actually boring. All information is treated equally; only an accurate argument will work.

>>39

Haha I wish
I got some starting help from my professor, so far I have this:

project4.h:

typedef struct linked_list_
{
    void *data;
    struct linked_list_ *next;
    char* key;
} linked_list, *Plinked_list;

typedef struct hash_table_
{
    Plinked_list *buckets;
    int size;
    int (*hash_func)(char *);
    int (*cmp_func)(void *, void *)
} hash_table, *Phash_table;


Phash_table new_hash(int size, int (*hash_func)(char *), int (*cmp_func)(void *, void *));
void free_hash(Phash_table table);
void insert_hash(Phash_table table, char *key, void *data);
void *find_hash(Phash_table table, char *key);
void stat_hash(Phash_table table, int *total, int *largest, float *average);
void *start_hash_walk(Phash_table table);
void *next_hash_walk(Phash_table table);

project4.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pr4.h"

Phash_table new_hash (int size, int(*hash_func)(char*), int(*cmp_func)(void*, void*);
void free_hash(Phash_table table);
void insert_hash(Phash_table table, char *key, void *data);
void *find_hash(Phash_table table, char *key);
void stat_hash(Phash_table table, int *total, int *largest, float *average);
void *start_hash_walk(Phash_table table);
void *next_hash_walk(Phash_table table);

void main()
{
}

Phash_table new_hash (int size, int(*hash_func)(char*), int(*cmp_func)(void*, void*)
{
    Phash_table t = (Phash_table)malloc(sizeof(hash_table));
    t->buckets = (Plinked_list*)malloc(sizeof(Plinked_list)*size);
    t->size = size;
    t->hash_func = hash_func;   
}
void insert_hash(Phash_table table, char *key, void *data)
{
    Plinked_list new = (Plinked_list)malloc(sizeof(linked_list));
    new -> key = (char *)malloc(sizeof(char)*strlen(key));
    strcpy(new -> key, key);
}

The functions hash_func and cmp_func are both written by a different user in a different file, hash_func matches a bucket with a specific key while cmp_func is used to compare the data in each bucket by returning a greater than, equal to, or less than which is then used to sort the info.
Anyone have any clue as to how I could start *find_hash?

Also, in the function insert_hash I want to make a pointer from a linked_list node to the data. What declaration would I use for this if I want to malloc that memory?

Right now I have this

void insert_hash(Phash_table table, char *key, void *data)
{
    Plinked_list new = (Plinked_list)malloc(sizeof(linked_list));
    new->key = (char *)malloc(sizeof(char)*strlen(key));
    new->data = (void *)malloc(sizeof(void)*strlen(data));
    strcpy(new -> key, key);
    Phash_table t = table;
    t->buckets[index] = new;
    t->index++;
}

however this is just a guess, I'm not sure if "new->data = (void *)malloc(sizeof(void)*strlen(data));" is correct.

>>39
Didn't >>21-san already finish OP-chan's assignment.

>>44
insert_hash() won't insert anything if you have two different key values that happen to have the same index.

#include "uthash.h"

>>46

hows this

void insert_hash(Phash_table table, char *key, void *data)
{
    Plinked_list new = (Plinked_list)malloc(sizeof(linked_list));
    new->key = (char *)malloc(sizeof(char)*strlen(key));
    new->data = (void *)malloc(sizeof(void)*strlen(data));
    strcpy(new -> key, key);
    Phash_table t = table;
    if(t->buckets[0] == NULL)
        t->buckets[0] = new;
    else
    {
        int i;
        for(i = 0; t->buckets[i] != NULL; i ++)
        {
            if(strcmp(t->buckets[i]->key, hash_func) == 0)
                t->buckets[i] = new;
        }
    }
    t->total++;
}

OK, updated code:

project4.h

#include <stdio.h>
#include <stdlib.h>

typedef struct linked_list_
{
    void *data;
    struct linked_list_ *next;
    char* key;
} linked_list, *Plinked_list;

typedef struct hash_table_
{
    Plinked_list *buckets;
    int size;
    int (*hash_func)(char *);
    int (*cmp_func)(void *, void *);
    void ** sortarray;
    int index = 0;
    int total = 0;
    int sortnum = 0;
} hash_table, *Phash_table;


Phash_table new_hash(int size, int (*hash_func)(char *), int (*cmp_func)(void *, void *));
void free_hash(Phash_table table);
void insert_hash(Phash_table table, char *key, void *data);
void *find_hash(Phash_table table, char *key);
void stat_hash(Phash_table table, int *total, int *largest, float *average);
void *start_hash_walk(Phash_table table);
void *next_hash_walk(Phash_table table);

project4.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pr4.h"

Phash_table new_hash (int size, int(*hash_func)(char*), int(*cmp_func)(void*, void*))
{
    int i;
    Phash_table t = (Phash_table)malloc(sizeof(hash_table));
    t->buckets = (Plinked_list*)malloc(sizeof(Plinked_list)*size);
    t->size = size;
    t->hash_func = hash_func;
    t->cmp_func = cmp_func;
    for(i=0; t->buckets[i] != NULL; i++)
    {
        t->buckets[i] = NULL;
    }
}

void free_hash(Phash_table table)
{
    int i;
    for(i = 0; i < table->size; i ++)
    {
        for(table->buckets[i]; table->buckets[i]->next != NULL; table->buckets[i] = table->buckets[i]->next)
        {
            free(table->buckets[i]->key);
            free(table->buckets[i]->data);
        }
        free(table->buckets[i]);
    }
    free(table->sortarray);
    free(table);
}

void insert_hash(Phash_table table, char *key, void *data)
{
    Plinked_list new = (Plinked_list)malloc(sizeof(linked_list));
    new->key = (char *)malloc(sizeof(char)*strlen(key));
    new->data = data;
    strcpy(new -> key, key);
    Phash_table t = table;
    int index = t->hash_func;
    t->buckets[index] = new;
    t->total++;
}

void *find_hash(Phash_table table, char *key)
{
    int i;
    Phash_table t = table;
    for(i = 0; t->size; i ++)
    {
        for(t->buckets[i]; t->buckets[i]-> next != NULL; t->buckets[i] = t->buckets[i] -> next)
        {
            if(strcmp(t->buckets[i]-> key, key) == 0)
                return *data;
        }
    }
    return NULL;   
}

void stat_hash(Phash_table table, int *total, int *largest, float *average)
{
    Phash_table t = table;
    int arraysize = t-> size;
    int nodenums[arraysize];
    int i, count = 0;
    for(i = 0; i < arraysize; i ++)
    {
        for(t->buckets[i]; t->buckets[i]->next != NULL; t->buckets[i] = t->buckets[i]->next)
        {
            count ++;
        }
        nodenums[i] = count;
        count = 0;
    }
    int big = 0;
    for(j = 0; j < arraysize; j ++)
    {
        if(nodenums[j] > big)
            big = nodenums[j];
    }
   
    *total = t-> total;
    *largest = big;
    average = t->total / t->size;
}

void *start_hash_walk(Phash_table table)
{
    Phash_table t = table
    Phash_table temp = table;
    t->sortarray = (void**)malloc(sizeof(void*)*t->total);
    int i, j, k;
    for(i = 0; i < total; i ++)
    {
        for(t->buckets[i]; t->buckets[i]->next != NULL; t->buckets[i] = t->buckets[i]->next)
        {
            t->sortarray[i] = t->buckets[i]->data;
        }
    }
   
    for(j = (total - 1); j > 0; j --)
    {
        for(k = 1; k <= j; k ++)
        {
            if(t->cmp_func(t->sortarray[k-1], t->sortarray[k]) == 1)
            {
                temp -> buckets[0] -> data = t->sortarray[k-1];
                t->sortarray[k-1] = t->sortarray[k];
                t->sortarray[k] = temp ->buckets[0] -> data;
            }
        }
    }
    return t->sortarray[sortnum];
}

void *next_hash_walk(Phash_table table)
{
    Phash_table t = table;
    t-> sortnum ++;
    return t-> sortarray[t->sortnum];
}

I'm having trouble with project.h, every time I try to compile it gives me an error because I'm not initializing the pointer array correctly.

Phash_table
Stop using Hungarian notation. Now I can't stop thinking about how to pronounce 'phash'.

Your indenting is also disgusting.

Thanks, I'll be sure to fix that once my code works

>>50
"fash"

MORE LIKE
PERL COULD DO THIS SHIT IN 2 SECONDS
AMIRITE LOLLLLLLLLLLLLLLLLLLLLLLLZzz!!11oNE!!1ONE1!

>>50
Pointer to the hash table.

You guys have been immensely helpful, thanks

>>54
Shouldn't most struct variables be pointers? And if not, they'd have a shorter name that's only slightly less descriptive.

>>50
fæsh.

I GO HARD IN THE MOTHERFUCKING PAINT NIGGA

please post the entire texts of your programming assignments here, it's a good place for them.

>>38
All programming languages suck. Some suck less, some more. If you want your perfect programming language, shut the fuck up and write your own (and if you do, please don't post code samples on /prog/ before rendering the reference implementation public!). Some programming languages have a tendency to attract bad programmers and let bad programs work. C++ seems to do that. This doesn't apply to C, where a faulty program is very likely to crash and burn.

That being said, I must answer to the ad hominem prediction in your post, you fucking cock sucking AIDS-ridden nigger faggot.

When we did hash tables for my CS3 class, we were using Java, so the polymorphism was easy as fuck. We just had to define an interface for a generic hash function and take a reference to any hash function as part of the constructor for the hash table object.

Enjoy your shitty OOP, C-fags.

>>62
`>Java
`>polymorphism
lol.jpg

How about say that you got sick and you work on it for the next two days.