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.

Try Common Lisp. It's data types are polymorphic by default and you dont have to worry about nuances.

And now you want what?

>>3
He wants to read http://www.gigamonkeys.com/book/

I can't use anything other than C.

As for what I want:
I'd like to know how to write code to first declare the hash table ADT, and second I want to be able to understand what I'm supposed to do after that, because I'm not sure if I should be making a hash table filled with linked lists that point to the data itself, or something else completely.

>>5
I can't use anything other than C.
God forbids?

Polymorphism, efficiency, C programming language: pick any two.

(Yes, I like C and use it daily. Fuck off with your ad hominems you fucking faggot.)

Yes, I like C and use it daily. Fuck off with your ad hominems you fucking faggot.
Better being a faggot, than a Unix/C++ retard.

>>6
>>7

I'm in a C programming class, therefore I can only use C to program.

>>1
You shouldn't be allowed to get within five feet of a computer.

Hey OP. If you can't implement an associative hash table with chaining for conflict resolution, using void pointers for key-value pairs and a function pointer for a polymorphic hash function, from the description of what a hash table is on Wikipedia, you'll never be able to hold down a job as software developer in the real world.

Consider this a life-or-death test. If you can't do it, you might as well give up now, because the best job you'll be able to get with your degree will be at Geek Squad doing tech support for minimum wage. Don't expect anyone to help you out.

http://en.wikipedia.org/wiki/Hash_table

>>11

I'm not studying to be a software engineer or anything that has to do with coding. This is my last programming class I need to take for my major and I just need help with this project. I understand learning this kinda stuff would be beneficial to me in the future if my major had any coding in it, however it doesn't and I just want to get it done with.

>>12
You're learning to program because you don't want to program?

>>12
Sounds like you're either a math or physics major, or some type of engineering.

Hate to break it to you, but all of the current high-paying jobs outside of academia in those sectors require serious software development skills. Enjoy eating the scraps at the bottom of the food chain.

>>13

A lot of schools require varying amounts of CS classes for math/physics majors.

>>14

Thanks, I appreciate the lecture, however I just want some help with starting the program.

I start with a .h file that looks like this:

/*
 * hash.h
 *

 Interfaces for hash table ADT

 *
 */



typedef struct hash_table_ {

  /* structure definition goes here */

} 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);

My question is, how do I define the structure if I'm making the data type polymorphic?

>>11
So wait, the hashing function is supposed to take the internal array size? That makes things easier.
I still don't get how you're supposed to sort the data.

>>16
Okay. Well, get started. Why so hung up?

>>17
No, it doesn't take the internal array size, that's something that can be factored into the common hash table code because it's not something specific to a certain data-type's hash function. Just take the remainder of the hash function result divided by the array size. If it's a power of two, then it's just a simple shift.

>>16
Add a
typedef struct linked_list_
{
    void *data;
    struct linked_list_ *next;
} linked_list, *Plinked_list;
before the hash_table_ definition,
and
int (*hash_func)(char *);
int (*cmp_func)(void *, void *);
int size;
Plinked_list buckets[];
in the structure definition.
You should be able to solve it from here.

>>18
Yeah, I realized that you can just % the hash to make it fit. Do I feel silly now.
Though I think it could be possible that the hash function writer would find a way of truncating the key that would result in fewer collisions.

>>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.