From e055b6d878d7fa60e629b195e82618f7d6bacb9b Mon Sep 17 00:00:00 2001 From: MORIOKA Tomohiko Date: Tue, 23 Apr 2013 23:35:06 +0900 Subject: [PATCH] New files. --- cos-hash.c | 182 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ hash-i.h | 54 ++++++++++++++++++ 2 files changed, 236 insertions(+) create mode 100644 cos-hash.c create mode 100644 hash-i.h diff --git a/cos-hash.c b/cos-hash.c new file mode 100644 index 0000000..37acf1c --- /dev/null +++ b/cos-hash.c @@ -0,0 +1,182 @@ +/* Copyright (C) 2013 MORIOKA Tomohiko + This file is part of the CONCORD Library. + + The CONCORD Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The CONCORD Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the CONCORD Library; if not, write to the Free + Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA + 02111-1307 USA. */ + +#include +#include "cos.h" +#include "cos-i.h" +#include "concord-name.h" +#include "cos-hash.h" +#include "hash-i.h" + +COS_Hash_Table +cos_make_hash_table () +{ + return concord_make_hash_table (256); +} + +void +cos_destroy_hash_table (COS_Hash_Table table) +{ + size_t i; + + for (i = 0; i < table->size; i++) + { + COS_Hash_Table_Entry entry = table->data[i]; + + if (entry.key != NULL) + { + cos_release_object (entry.key); + cos_release_object (entry.value); + } + } + concord_destroy_hash_table (table); +} + +unsigned long cos_symbol_hash_string (COS_String string); + +/* #### for a 64-bit machine, we should substitute a prime just over 2^32 */ +#define GOOD_HASH 65599 /* prime number just over 2^16; Dragon book, p. 435 */ +#define HASH2(a,b) (GOOD_HASH * (a) + (b)) +#define HASH3(a,b,c) (GOOD_HASH * HASH2 (a,b) + (c)) +#define HASH4(a,b,c,d) (GOOD_HASH * HASH3 (a,b,c) + (d)) +#define HASH5(a,b,c,d,e) (GOOD_HASH * HASH4 (a,b,c,d) + (e)) +#define HASH6(a,b,c,d,e,f) (GOOD_HASH * HASH5 (a,b,c,d,e) + (f)) +#define HASH7(a,b,c,d,e,f,g) (GOOD_HASH * HASH6 (a,b,c,d,e,f) + (g)) +#define HASH8(a,b,c,d,e,f,g,h) (GOOD_HASH * HASH7 (a,b,c,d,e,f,g) + (h)) +#define HASH9(a,b,c,d,e,f,g,h,i) (GOOD_HASH * HASH8 (a,b,c,d,e,f,g,h) + (i)) + +static size_t +cos_hash_object0 (COS_object obj, int depth) +{ + if ( obj == NULL ) + return 0; + else if ( COS_OBJECT_INT_P (obj) ) + return cos_int_value (obj); + else if ( COS_OBJECT_CHAR_P (obj) ) + return cos_char_id (obj); + else if ( COS_OBJECT_STRING_P (obj) ) + return cos_symbol_hash_string (obj); + else if ( COS_OBJECT_SYMBOL_P (obj) ) + return cos_symbol_hash_string (cos_symbol_name (obj)); + else if ( COS_OBJECT_CONS_P (obj) ) + { + if ( depth > 5 ) + return 0; + else + return HASH2 (cos_hash_object0 (cos_car (obj), depth + 1), + cos_hash_object0 (cos_cdr (obj), depth + 1)); + } + + return (size_t)obj; +} + +size_t +cos_hash_object (COS_object obj) +{ + return cos_hash_object0 (obj, 0); +} + +int +cos_hash_table_put (COS_Hash_Table table, + COS_object key, COS_object value) +{ + unsigned long i, index; + COS_Hash_Table_Entry* entry; + + if (table == NULL) + return -1; + + index = cos_hash_object (key) % table->size; + for (i = index; i < table->size; i++) + { + entry = &table->data[i]; + if (entry->key == NULL) + { + cos_retain_object (key); + cos_retain_object (value); + entry->key = key; + entry->value = value; + return 0; + } + else if (entry->key == key) + { + cos_release_object (entry->value); + cos_retain_object (value); + entry->value = value; + return 0; + } + } + if (cos_hash_table_grow (table) == 0) + return cos_hash_table_put (table, key, value); + return -1; +} + +COS_object +cos_hash_table_get (COS_Hash_Table table, COS_object key) +{ + unsigned long i, index; + COS_Hash_Table_Entry* entry; + + if (table == NULL) + return NULL; + + index = cos_hash_object (key) % table->size; + for (i = index; i < table->size; i++) + { + entry = &table->data[i]; + if (entry->key == NULL) + return NULL; + else if (entry->key == key) + return entry->value; + } + return NULL; +} + +int +cos_hash_table_grow (COS_Hash_Table table) +{ + COS_Hash_Table new_table + = concord_make_hash_table ( table->size * 2 + /* - (table->size * 4 / 5) */ ); + size_t i; + + if (new_table == NULL) + return -1; + + for (i = 0; i < table->size; i++) + { + COS_Hash_Table_Entry* entry = &table->data[i]; + + if ( (entry->key != NULL) && (entry->value != NULL) ) + { + int status + = cos_hash_table_put (new_table, entry->key, entry->value); + + if (status != 0) + { + concord_destroy_hash_table (new_table); + return -1; + } + } + } + free (table->data); + table->size = new_table->size; + table->data = new_table->data; + free (new_table); + return 0; +} diff --git a/hash-i.h b/hash-i.h new file mode 100644 index 0000000..5ee3238 --- /dev/null +++ b/hash-i.h @@ -0,0 +1,54 @@ +/* Copyright (C) 2003, 2004, 2005, 2006, 2013 MORIOKA Tomohiko + This file is part of the CONCORD Library. + + The CONCORD Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The CONCORD Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the CONCORD Library; if not, write to the Free + Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA + 02111-1307 USA. */ + +#ifndef _HASH_I_H +#define _HASH_I_H + +#ifdef __cplusplus +extern "C" { +#endif +#if 0 +} +#endif + +struct CONCORD_HASH_TABLE_ENTRY +{ + void *key; + void *value; +}; + +struct CONCORD_HASH_TABLE +{ + size_t size; + CONCORD_HASH_TABLE_ENTRY *data; +}; + +CONCORD_HASH_TABLE* concord_make_hash_table (size_t size); + +void concord_destroy_hash_table (CONCORD_HASH_TABLE* hash); + +unsigned long concord_hash_c_string (const unsigned char *ptr); + +#if 0 +{ +#endif +#ifdef __cplusplus +} +#endif + +#endif /* !_HASH_I_H */ -- 1.7.10.4