From 53865aad225ffbe5cf3c42736e5a2095092f9fff Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 21 Jan 2022 21:53:50 +0800 Subject: temporary save point Just to save some work. --- src/ht.h | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 53 insertions(+), 5 deletions(-) (limited to 'src/ht.h') diff --git a/src/ht.h b/src/ht.h index 54c0497..e5d16f7 100644 --- a/src/ht.h +++ b/src/ht.h @@ -4,20 +4,68 @@ enum { HT_INIT_CAP = 257 }; +/* TODO: Modify the probing algorithm. Imitate the algorithm used by + python's hash tables. The source code of the python dict object + can be found in the following URL: + + */ + +/* TODO: Generalize the type of the keys, so that we can use anything + as the key. The type of the keys should satisfy the following + conditions. + + - Hash-able: We must know how to produce the hash value of a + key. + + - Comparable: We must know how to compare two keys, in order to + know if two keys are "equal". */ + +/* type for a hash function */ +typedef NUM (*hash_func_t) (void *key); + +/* comparison function type */ +typedef BOOL (*compare_func_t) (void *keya, void *keyb); + +struct ht_s { + NUM *keys; + void **values; + NUM *indices; + UNUM capability; + /* REVIEW: What is the purpose of SIZE? */ + /* ANSWER: For looping over keys / values. */ + int size; + /* hash_func_t hf; + * compare_func_t cf; */ +}; + typedef struct ht_s ht; +/* On error return NULL */ ht *new_ht(UNUM size); -void destroy_ht(ht * restrict htp, int flag); +enum HT_DESTROY_FLAG_e { + DESTROY_NONE_NO_SELF, + DESTROY_NONE_SELF, + DESTROY_EVERY_NO_SELF, + DESTROY_EVERY_SELF, + DESTROY_FIRST_NO_SELF, + DESTROY_FIRST_SELF +}; + +typedef enum HT_DESTROY_FLAG_e HT_DESTROY_FLAG; +void destroy_ht(ht * restrict htp, HT_DESTROY_FLAG flag); BOOL ht_insert(ht *htp, NUM key, void *value); -/* This is just for the completeness. In theory I do not need to - delete keys. +P_ATTR NUM ht_size(CCR_MOD(ht *) htp); + +P_ATTR void **ht_values(CCR_MOD(ht *) htp); + +P_ATTR NUM *ht_keys(CCR_MOD(ht *) htp); - If FLAG is non-zero, also free the value pointer. */ +/* If FLAG is non-zero, also free the value pointer. */ BOOL ht_delete(ht * const restrict htp, NUM key, int flag); -void *ht_find(ht * const restrict htp, NUM key); +P_ATTR void *ht_find(CCR_MOD(ht *) htp, NUM key); #endif -- cgit v1.2.3-18-g5258