/* Copyright 2002 Christopher Clark */ /* Copyright 2005-2012 Nick Mathewson */ /* Copyright 2009-2012 Niels Provos and Nick Mathewson */ /* See license at end. */ /* Based on ideas by Christopher Clark and interfaces from Niels Provos. */ #ifndef HT_INTERNAL_H_INCLUDED_#define HT_INTERNAL_H_INCLUDED_#define HT_HEAD(name, type) \struct name { \/* The hash table itself. */ \ struct type **hth_table; \/* How long is the hash table? */ \ unsigned hth_table_length; \/* How many elements does the table contain? */ \ unsigned hth_n_entries; \/* How many elements will we allow in the table before resizing it? */ \ unsigned hth_load_limit; \/* Position of hth_table_length in the primes table. */ \ #define HT_INITIALIZER() \0 , 0 , 0 , -1 }#ifdef HT_NO_CACHE_HASH_VALUES#define HT_ENTRY(type) \struct { \struct type *hte_next; \#else #define HT_ENTRY(type) \struct { \struct type *hte_next; \unsigned hte_hash; \#endif #define HT_EMPTY(head) \0 )/* How many elements in 'head'? */ #define HT_SIZE(head) \/* Return memory usage for a hashtable (not counting the entries themselves) */ #define HT_MEM_USAGE(head) \sizeof (*head) + (head)->hth_table_length * sizeof (void *))#define HT_FIND(name, head, elm) name## _HT_FIND((head), (elm))#define HT_INSERT(name, head, elm) name## _HT_INSERT((head), (elm))#define HT_REPLACE(name, head, elm) name## _HT_REPLACE((head), (elm))#define HT_REMOVE(name, head, elm) name## _HT_REMOVE((head), (elm))#define HT_START(name, head) name## _HT_START(head)#define HT_NEXT(name, head, elm) name## _HT_NEXT((head), (elm))#define HT_NEXT_RMV(name, head, elm) name## _HT_NEXT_RMV((head), (elm))#define HT_CLEAR(name, head) name## _HT_CLEAR(head)#define HT_INIT(name, head) name## _HT_INIT(head)/* Helper: */ static inline unsigned unsigned h)/* Aim to protect against poor hash functions by adding logic here 9 );14 ) | (h << 18 )); /* >>> */ 4 );10 ) | (h << 22 )); /* >>> */ return h;#if 0 /** Basic string hash function, from Java standard String.hashCode(). */ static inline unsigned const char *s)unsigned h = 0 ;1 ;while (*s) {signed char)*s++)*m;5 )-1 ; /* m *= 31 */ return h;#endif /** Basic string hash function, from Python's str.__hash__() */ static inline unsigned const char *s)unsigned h;const unsigned char *cp = (const unsigned char *)s;7 ;while (*cp) {1000003 *h) ^ *cp++;/* This conversion truncates the length of the string, but that's ok. */ unsigned )(cp-(const unsigned char*)s);return h;#ifndef HT_NO_CACHE_HASH_VALUES#define HT_SET_HASH_(elm, field, hashfn) \do { (elm)->field.hte_hash = hashfn(elm); } while (0 )#define HT_SET_HASHVAL_(elm, field, val) \do { (elm)->field.hte_hash = (val); } while (0 )#define HT_ELT_HASH_(elm, field, hashfn) \#else #define HT_SET_HASH_(elm, field, hashfn) \void )0 )#define HT_ELT_HASH_(elm, field, hashfn) \#define HT_SET_HASHVAL_(elm, field, val) \void )0 )#endif /* Helper: alias for the bucket containing 'elm'. */ #define HT_BUCKET_(head, field, elm, hashfn) \#define HT_FOREACH(x, name, head) \#define HT_PROTOTYPE(name, type, field, hashfn, eqfn) \## _HT_GROW(struct name *ht, unsigned min_capacity); \void name## _HT_CLEAR(struct name *ht); \## _HT_REP_IS_BAD_(const struct name *ht); \static inline void \## _HT_INIT(struct name *head) { \0 ; \0 ; \0 ; \1 ; \/* Helper: returns a pointer to the right location in the table \ \static inline struct type ** \## _HT_FIND_P_(struct name *head, struct type *elm) \struct type **p; \return NULL; \while (*p) { \return p; \return p; \/* Return a pointer to the element in the table 'head' matching 'elm', \ \static inline struct type * \## _HT_FIND(const struct name *head, struct type *elm) \struct type **p; \struct name *h = (struct name *) head; \## _HT_FIND_P_(h, elm); \return p ? *p : NULL; \/* Insert the element 'elm' into the table 'head'. Do not call this \ \static inline void \## _HT_INSERT(struct name *head, struct type *elm) \struct type **p; \## _HT_GROW(head, head->hth_n_entries+1 ); \/* Insert the element 'elm' into the table 'head'. If there already \ * a matching element in the table , replace that element and return \ \static inline struct type * \## _HT_REPLACE(struct name *head, struct type *elm) \struct type **p, *r; \## _HT_GROW(head, head->hth_n_entries+1 ); \## _HT_FIND_P_(head, elm); \return r; \else { \return NULL; \/* Remove any element matching 'elm' from the table 'head'. If such \ \static inline struct type * \## _HT_REMOVE(struct name *head, struct type *elm) \struct type **p, *r; \## _HT_FIND_P_(head,elm); \return NULL; \return r; \/* Invoke the function 'fn' on every element of the table 'head', \ * using ' data ' as its second argument . If the function returns \ * nonzero , remove the most recently examined element before invoking \ \static inline void \## _HT_FOREACH_FN(struct name *head, \struct type *, void *), \void *data) \unsigned idx; \struct type **p, **nextp, *next; \return ; \0 ; idx < head->hth_table_length; ++idx) { \while (*p) { \else { \/* Return a pointer to the first element in the table 'head', under \ * an arbitrary order . This order is stable under remove operations , \ \static inline struct type ** \## _HT_START(struct name *head) \unsigned b = 0 ; \while (b < head->hth_table_length) { \return &head->hth_table[b]; \return NULL; \/* Return the next element in 'head' after 'elm', under the arbitrary \ * order used by HT_START . If there are no more elements , return \ * NULL . If ' elm ' is to be removed from the table , you must call \ * this function for the next value before you remove it . \ \static inline struct type ** \## _HT_NEXT(struct name *head, struct type **elm) \return &(*elm)->field.hte_next; \else { \unsigned b = (HT_ELT_HASH_(*elm, field, hashfn) % head->hth_table_length)+1 ; \while (b < head->hth_table_length) { \return &head->hth_table[b]; \return NULL; \static inline struct type ** \## _HT_NEXT_RMV(struct name *head, struct type **elm) \unsigned h = HT_ELT_HASH_(*elm, field, hashfn); \return elm; \else { \unsigned b = (h % head->hth_table_length)+1 ; \while (b < head->hth_table_length) { \return &head->hth_table[b]; \return NULL; \#define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn, \static unsigned name## _PRIMES[] = { \53 , 97 , 193 , 389 , \769 , 1543 , 3079 , 6151 , \12289 , 24593 , 49157 , 98317 , \196613 , 393241 , 786433 , 1572869 , \3145739 , 6291469 , 12582917 , 25165843 , \50331653 , 100663319 , 201326611 , 402653189 , \805306457 , 1610612741 \static unsigned name## _N_PRIMES = \unsigned )(sizeof (name## _PRIMES)/sizeof (name## _PRIMES[0 ])); \/* Expand the internal table of 'head' until it is large enough to \ * hold ' size ' elements . Return 0 on success , - 1 on allocation \ \## _HT_GROW(struct name *head, unsigned size) \unsigned new_len, new_load_limit; \struct type **new_table; \## _N_PRIMES - 1 ) \return 0 ; \return 0 ; \do { \## _PRIMES[++prime_idx]; \unsigned )(load*new_len); \while (new_load_limit <= size && \## _N_PRIMES); \sizeof (struct type*)))) { \unsigned b; \0 , new_len*sizeof (struct type*)); \0 ; b < head->hth_table_length; ++b) { \struct type *elm, *next; \unsigned b2; \while (elm) { \else { \unsigned b, b2; \sizeof (struct type*)); \return -1 ; \0 , \sizeof (struct type*)); \0 ; b < head->hth_table_length; ++b) { \struct type *e, **pE; \else { \return 0 ; \/* Free all storage held by 'head'. Does not free 'head' itself, or \ \void \## _HT_CLEAR(struct name *head) \## _HT_INIT(head); \/* Debugging helper: return false iff the representation of 'head' is \ \## _HT_REP_IS_BAD_(const struct name *head) \unsigned n, i; \struct type *elm; \1 ) \return 0 ; \else \return 1 ; \0 || \return 2 ; \return 3 ; \## _PRIMES[head->hth_prime_idx]) \return 4 ; \unsigned )(load*head->hth_table_length)) \return 5 ; \0 ; i < head->hth_table_length; ++i) { \return 1000 + i; \return 10000 + i; \return 6 ; \return 0 ; \/** Implements an over-optimized "find and insert if absent" block; * not meant for direct usage by typical code , or usage outside the critical #define HT_FIND_OR_INSERT_(name, field, hashfn, head, eltype, elm, var, y, n) \struct name *var## _head_ = head; \struct eltype **var; \## _head_->hth_table || \## _head_->hth_n_entries >= var## _head_->hth_load_limit) \## _HT_GROW(var## _head_, var## _head_->hth_n_entries+1 ); \## _HT_FIND_P_(var## _head_, (elm)); \else { \#define HT_FOI_INSERT_(field, head, elm, newent, var) \/* * Copyright 2005 , Nick Mathewson . Implementation logic is adapted from code * by Christopher Clark , retrofit to allow drop - in memory management , and to * use the same interface as Niels Provos ' s tree . h . This is probably still * a derived work , so the original license below still applies . * * Copyright ( c ) 2002 , Christopher Clark * All rights reserved . * * Redistribution and use in source and binary forms , with or without * modification , are permitted provided that the following conditions * are met : * * * Redistributions of source code must retain the above copyright * notice , this list of conditions and the following disclaimer . * * * Redistributions in binary form must reproduce the above copyright * notice , this list of conditions and the following disclaimer in the * documentation and / or other materials provided with the distribution . * * * Neither the name of the original author ; nor the names of any contributors * may be used to endorse or promote products derived from this software * without specific prior written permission . * * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * " AS IS " AND ANY EXPRESS OR IMPLIED WARRANTIES , INCLUDING , BUT NOT * LIMITED TO , THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED . IN NO EVENT SHALL THE COPYRIGHT OWNER * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT , INDIRECT , INCIDENTAL , SPECIAL , * EXEMPLARY , OR CONSEQUENTIAL DAMAGES ( INCLUDING , BUT NOT LIMITED TO , * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES ; LOSS OF USE , DATA , OR * PROFITS ; OR BUSINESS INTERRUPTION ) HOWEVER CAUSED AND ON ANY THEORY OF * LIABILITY , WHETHER IN CONTRACT , STRICT LIABILITY , OR TORT ( INCLUDING * NEGLIGENCE OR OTHERWISE ) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE , EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE . #endif
Messung V0.5 in Prozent C=94 H=91 G=92
¤ Dauer der Verarbeitung: 0.15 Sekunden
¤ *© Formatika GbR, Deutschland
