Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:1853 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 72442 invoked from network); 21 May 2003 14:59:38 -0000 Received: from unknown (HELO carmine.bestweb.net) (209.94.102.73) by pb1.pair.com with SMTP; 21 May 2003 14:59:38 -0000 Received: from [192.168.1.101] (ip216-179-71-153.cust.bestweb.net [216.179.71.153]) by carmine.bestweb.net (Postfix) with ESMTP id 2AC5122F79; Wed, 21 May 2003 09:59:32 -0500 (EST) To: internals@lists.php.net Cc: zeev@zend.com, andi@zend.com Content-Type: multipart/mixed; boundary="=-PSabTSRzliGQ0GzFuO+O" Organization: Message-ID: <1053524019.2177.35.camel@hasele> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.4 Date: 21 May 2003 09:33:39 -0400 Subject: zend_fast_hash From: sterling@bumblebury.com (Sterling Hughes) --=-PSabTSRzliGQ0GzFuO+O Content-Type: text/plain Content-Transfer-Encoding: 7bit Hi, I've implemented a very lightweight, efficient hash table for zend engine 2. This is a table that's appropriate for usage in many of the areas where then Zend hash table implementation is unnecessarily complex (which is pretty much everywhere except for PHP arrays themselves.) I've attached the implementation, and a patch which integrates the new hashtable implementation with Zend, including a "case-study," where I've converted over EG(included_files) to use the new hashtable implementation. Right now the hash table code is very simple, as its just there for initial perusal, it can of course be improved upon. So, when can I integrate it? ;-) -Sterling -- "A business that makes nothing but money is a poor kind of business." - Henry Ford --=-PSabTSRzliGQ0GzFuO+O Content-Disposition: attachment; filename=fast_hash.diff Content-Type: text/plain; name=fast_hash.diff; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit ? fast_hash ? fast_hash.diff ? zend_fast_hash.c ? zend_fast_hash.h Index: Makefile.am =================================================================== RCS file: /repository/ZendEngine2/Makefile.am,v retrieving revision 1.52 diff -u -r1.52 Makefile.am --- Makefile.am 23 Mar 2003 04:32:23 -0000 1.52 +++ Makefile.am 21 May 2003 14:53:41 -0000 @@ -14,7 +14,7 @@ zend_variables.c zend.c zend_API.c zend_extensions.c zend_hash.c \ zend_list.c zend_indent.c zend_builtin_functions.c zend_sprintf.c \ zend_ini.c zend_qsort.c zend_objects.c zend_object_handlers.c \ - zend_objects_API.c zend_ts_hash.c zend_stream.c zend_mm.c zend_default_classes.c + zend_objects_API.c zend_ts_hash.c zend_stream.c zend_mm.c zend_default_classes.c zend_fast_hash.c libZend_la_LDFLAGS = libZend_la_LIBADD = @ZEND_EXTRA_LIBS@ Index: zend_builtin_functions.c =================================================================== RCS file: /repository/ZendEngine2/zend_builtin_functions.c,v retrieving revision 1.187 diff -u -r1.187 zend_builtin_functions.c --- zend_builtin_functions.c 21 Apr 2003 17:01:34 -0000 1.187 +++ zend_builtin_functions.c 21 May 2003 14:53:46 -0000 @@ -24,6 +24,7 @@ #include "zend_builtin_functions.h" #include "zend_constants.h" #include "zend_ini.h" +#include "zend_fast_hash.h" #undef ZEND_TEST_EXCEPTIONS @@ -944,16 +945,23 @@ Returns an array with the file names that were include_once()'d */ ZEND_FUNCTION(get_included_files) { - char *entry; + zend_fast_hash *files; + zend_fast_hash_slist *current; + int i; + if (ZEND_NUM_ARGS() != 0) { ZEND_WRONG_PARAM_COUNT(); } array_init(return_value); - zend_hash_internal_pointer_reset(&EG(included_files)); - while (zend_hash_get_current_key(&EG(included_files), &entry, NULL, 1) == HASH_KEY_IS_STRING) { - add_next_index_string(return_value, entry, 0); - zend_hash_move_forward(&EG(included_files)); + + files = (zend_fast_hash *) &EG(included_files); + for (i = 0; i < files->slots; ++i) { + current = files->table[i]; + while (current) { + add_next_index_string(return_value, current->key, 0); + current = current->next; + } } } /* }}} */ Index: zend_execute.c =================================================================== RCS file: /repository/ZendEngine2/zend_execute.c,v retrieving revision 1.462 diff -u -r1.462 zend_execute.c --- zend_execute.c 21 May 2003 11:48:55 -0000 1.462 +++ zend_execute.c 21 May 2003 14:53:54 -0000 @@ -3383,7 +3383,7 @@ file_handle.opened_path = estrndup(inc_filename->value.str.val, inc_filename->value.str.len); } - if (zend_hash_add(&EG(included_files), file_handle.opened_path, strlen(file_handle.opened_path)+1, (void *)&dummy, sizeof(int), NULL)==SUCCESS) { + if (zend_fast_hash_update(&EG(included_files), file_handle.opened_path, strlen(file_handle.opened_path)+1, (void *)&dummy TSRMLS_CC)==SUCCESS) { CG(active_namespace) = EG(global_namespace_ptr); new_op_array = zend_compile_file(&file_handle, (EX(opline)->op2.u.constant.value.lval==ZEND_INCLUDE_ONCE?ZEND_INCLUDE:ZEND_REQUIRE) TSRMLS_CC); zend_destroy_file_handle(&file_handle TSRMLS_CC); Index: zend_execute_API.c =================================================================== RCS file: /repository/ZendEngine2/zend_execute_API.c,v retrieving revision 1.204 diff -u -r1.204 zend_execute_API.c --- zend_execute_API.c 20 May 2003 18:28:14 -0000 1.204 +++ zend_execute_API.c 21 May 2003 14:53:56 -0000 @@ -156,7 +156,7 @@ EG(opline_ptr) = NULL; EG(garbage_ptr) = 0; - zend_hash_init(&EG(included_files), 5, NULL, NULL, 0); + zend_fast_hash_init(&EG(included_files), 5, 0, NULL TSRMLS_CC); EG(ticks_count) = 0; @@ -269,7 +269,7 @@ signal(SIGSEGV, original_sigsegv_handler); #endif - zend_hash_destroy(&EG(included_files)); + zend_fast_hash_destroy(&EG(included_files)); if (EG(user_error_handler)) { zval_dtor(EG(user_error_handler)); --=-PSabTSRzliGQ0GzFuO+O Content-Disposition: attachment; filename=zend_fast_hash.c Content-Type: text/x-c; name=zend_fast_hash.c; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit /* +----------------------------------------------------------------------+ | Zend Engine | +----------------------------------------------------------------------+ | Copyright (c) 1998-2003 Zend Technologies Ltd. (http://www.zend.com) | +----------------------------------------------------------------------+ | This source file is subject to version 2.00 of the Zend license, | | that is bundled with this package in the file LICENSE, and is | | available at through the world-wide-web at | | http://www.zend.com/license/2_00.txt. | | If you did not receive a copy of the Zend license and are unable to | | obtain it through the world-wide-web, please send a note to | | license@zend.com so we can mail you a copy immediately. | +----------------------------------------------------------------------+ | Authors: Sterling Hughes | +----------------------------------------------------------------------+ */ /* $Id: $ */ #include "zend.h" #include "zend_fast_hash.h" static inline unsigned long zend_fast_hash_hash(char *key, uint key_len) { register ulong hash = 5381; for (; key_len >= 8; key_len -= 8) { hash = ((hash << 5) + hash) + *key++; hash = ((hash << 5) + hash) + *key++; hash = ((hash << 5) + hash) + *key++; hash = ((hash << 5) + hash) + *key++; hash = ((hash << 5) + hash) + *key++; hash = ((hash << 5) + hash) + *key++; hash = ((hash << 5) + hash) + *key++; hash = ((hash << 5) + hash) + *key++; } switch (key_len) { case 7: hash = ((hash << 5) + hash) + *key++; case 6: hash = ((hash << 5) + hash) + *key++; case 5: hash = ((hash << 5) + hash) + *key++; case 4: hash = ((hash << 5) + hash) + *key++; case 3: hash = ((hash << 5) + hash) + *key++; case 2: hash = ((hash << 5) + hash) + *key++; case 1: hash = ((hash << 5) + hash) + *key++; break; case 0: break; } return hash; } ZEND_API void zend_fast_hash_init(zend_fast_hash *h, int slots, zend_bool persistent, zend_fast_hash_dtor_func_t dtor TSRMLS_DC) { h->dtor = dtor; h->size = 0; h->slots = slots; h->persistent = persistent; h->table = (zend_fast_hash_slist **) pemalloc(slots * sizeof(zend_fast_hash_slist), persistent); memset(h->table, 0, sizeof(zend_fast_hash_slist) * slots); } #define QUICK_COMPARE(k1, k1l, k2, k2l) ((k1l) == (k2l) && memcmp(k1, k2, k1l)) ZEND_API int zend_fast_hash_update(zend_fast_hash *h, char *key, int key_len, const void *p TSRMLS_DC) { register zend_fast_hash_slist *current; zend_fast_hash_slist *prev; zend_fast_hash_slist **start; int loc; unsigned long hval; hval = zend_fast_hash_hash(key, key_len); loc = hval % h->slots; current = h->table[loc]; while (current) { if (current->hval == hval && QUICK_COMPARE(key, key_len, current->key, current->key_len)) { if (h->dtor) { h->dtor(current->ptr TSRMLS_CC); } current->ptr = (void *) p; return SUCCESS; } current = current->next; } current = pemalloc(sizeof(zend_fast_hash_slist), h->persistent); current->hval = hval; current->ptr = (void *) p; current->key = estrndup(key, key_len); current->key_len = key_len; current->next = NULL; start = &h->table[loc]; if (*start) { current->next = *start; } *start = current; h->size++; return SUCCESS; } ZEND_API int zend_fast_hash_find(zend_fast_hash *h, char *key, int key_len, void **p TSRMLS_DC) { register zend_fast_hash_slist *current; unsigned long hval; hval = zend_fast_hash_hash(key, key_len); current = h->table[hval % h->slots]; while (current) { if (current->hval == hval && QUICK_COMPARE(key, key_len, current->key, current->key_len)) { *p = current->ptr; return SUCCESS; } current = current->next; } return FAILURE; } ZEND_API int zend_fast_hash_delete(zend_fast_hash *h, char *key, int key_len TSRMLS_DC) { zend_fast_hash_slist *current; zend_fast_hash_slist **prev; unsigned long hval; hval = zend_fast_hash_hash(key, key_len); current = h->table[hval % h->slots]; prev = ¤t; while (current) { if (current->hval == hval && QUICK_COMPARE(key, key_len, current->key, current->key_len)) { if (current->next) { (*prev)->next = current->next->next; } else { (*prev)->next = NULL; } *prev = current->next; if (h->dtor) { h->dtor(current->ptr TSRMLS_CC); } pefree(current, h->persistent); h->size--; return SUCCESS; } prev = ¤t; current = current->next; } return FAILURE; } ZEND_API int zend_fast_hash_count(zend_fast_hash *h TSRMLS_DC) { return h->size; } ZEND_API void zend_fast_hash_copy(zend_fast_hash *target, zend_fast_hash *source TSRMLS_DC) { register zend_fast_hash_slist *current; register int i; for (i = 0; i < source->slots; ++i) { current = source->table[i]; while (current) { zend_fast_hash_update(target, current->key, current->key_len, current->ptr TSRMLS_CC); current = current->next; } } } ZEND_API void zend_fast_hash_apply(zend_fast_hash *h, apply_func_t apply_func TSRMLS_DC) { register zend_fast_hash_slist *current; register int i; for (i = 0; i < h->slots; ++i) { current = h->table[i]; while (current) { apply_func(current->ptr TSRMLS_CC); current = current->next; } } } ZEND_API void zend_fast_hash_apply_with_argument(zend_fast_hash *h, apply_func_arg_t apply_func, void *arg TSRMLS_DC) { register zend_fast_hash_slist *current; register int i; for (i = 0; i < h->slots; ++i) { current = h->table[i]; while (current) { apply_func(current->ptr, arg TSRMLS_CC); current = current->next; } } } ZEND_API void zend_fast_hash_display(zend_fast_hash *h TSRMLS_DC) { register zend_fast_hash_slist *current; register int i; for (i = 0; i < h->slots; ++i) { current = h->table[i]; while (current) { printf("Bucket = %d, Key = %s, Value = %x\n", i, current->key, current->ptr); current = current->next; } } } ZEND_API void zend_fast_hash_clean(zend_fast_hash *h TSRMLS_DC) { register zend_fast_hash_slist *current; register zend_fast_hash_slist *next; register int i; for (i = 0; i < h->slots; ++i) { current = h->table[i]; while (current) { next = current->next; if (h->dtor) { h->dtor(current->ptr TSRMLS_CC); } pefree(current, h->persistent); current = next; } } memset(h->table, 0, h->size * sizeof(zend_fast_hash_slist *)); } ZEND_API void zend_fast_hash_destroy(zend_fast_hash *h TSRMLS_DC) { zend_fast_hash_clean(h); efree(h->table); } /* * Local variables: * tab-width: 4 * c-basic-offset: 4 * indent-tabs-mode: t * End: * vim600: fdm=marker * vim: noet sw=4 ts=4 */ --=-PSabTSRzliGQ0GzFuO+O Content-Disposition: attachment; filename=zend_fast_hash.h Content-Type: text/x-c-header; name=zend_fast_hash.h; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit /* +----------------------------------------------------------------------+ | Zend Engine | +----------------------------------------------------------------------+ | Copyright (c) 1998-2003 Zend Technologies Ltd. (http://www.zend.com) | +----------------------------------------------------------------------+ | This source file is subject to version 2.00 of the Zend license, | | that is bundled with this package in the file LICENSE, and is | | available at through the world-wide-web at | | http://www.zend.com/license/2_00.txt. | | If you did not receive a copy of the Zend license and are unable to | | obtain it through the world-wide-web, please send a note to | | license@zend.com so we can mail you a copy immediately. | +----------------------------------------------------------------------+ | Authors: Sterling Hughes | +----------------------------------------------------------------------+ */ /* $Id: $ */ #ifndef ZEND_FAST_HASH_H #define ZEND_FAST_HASH_H #include "zend.h" BEGIN_EXTERN_C() typedef int (*zend_fast_hash_dtor_func_t)(void * TSRMLS_DC); typedef struct _zend_fast_hash_slist { struct _zend_fast_hash_slist *next; char *key; int key_len; unsigned long hval; void *ptr; } zend_fast_hash_slist; typedef struct { zend_fast_hash_slist **table; int slots; int size; zend_bool persistent; zend_fast_hash_dtor_func_t dtor; } zend_fast_hash; ZEND_API void zend_fast_hash_init(zend_fast_hash *, int, zend_bool, zend_fast_hash_dtor_func_t TSRMLS_DC); ZEND_API int zend_fast_hash_update(zend_fast_hash *, char *, int, const void * TSRMLS_DC); ZEND_API int zend_fast_hash_find(zend_fast_hash *, char *, int, void ** TSRMLS_DC); ZEND_API int zend_fast_hash_delete(zend_fast_hash *, char *, int TSRMLS_DC); ZEND_API void zend_fast_hash_apply(zend_fast_hash *, apply_func_t TSRMLS_DC); ZEND_API void zend_fast_hash_apply_with_argument(zend_fast_hash *, apply_func_arg_t, void * TSRMLS_DC); ZEND_API int zend_fast_hash_count(zend_fast_hash * TSRMLS_DC); ZEND_API void zend_fast_hash_clean(zend_fast_hash * TSRMLS_DC); ZEND_API void zend_fast_hash_destroy(zend_fast_hash * TSRMLS_DC); END_EXTERN_C() #endif /* * Local variables: * tab-width: 4 * c-basic-offset: 4 * indent-tabs-mode: t * End: */ --=-PSabTSRzliGQ0GzFuO+O--