From nobody Mon Feb 9 19:08:05 2026 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=quarantine dis=none) header.from=suse.com ARC-Seal: i=1; a=rsa-sha256; t=1611307440; cv=none; d=zohomail.com; s=zohoarc; b=LiZ9XXVQWsjcH5gb9AoFk8Z0Lg39eu3N51h5tzpHHLzaFZSrWPY6fKXyNZma/pfMmUInEugF++UfP+9w+hPsjKU/7GHKtNuw+IW8MD3EQXXmOYYdBlsW3EsK8AQ4ohhR2tl2du5r/2ChOrgK1aN2osiA6QEE5n7PmxvapMkevEk= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1611307440; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=vw3JfTLt9lsKfJRPXabRbaapZoM5jDAcQulm7FKWQ/I=; b=OPAFkDedQGO6BkOGqj/9P/a4jinbc8nCKz9cGrEbVek3CiiiO+GzDcpIu2UMuou7VIk2mhkNnBw8fQs8GIOgYnLi67g3zHdFi/z0t8bvw4x+dD1gYucXRgS7jvW/X3zR4sfbhE8L5DeYfYYB5sYOyuffu2TKc3pZyjJBMgi8sHg= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=quarantine dis=none) header.from= Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 1611307440204633.745604795091; Fri, 22 Jan 2021 01:24:00 -0800 (PST) Received: from list by lists.xenproject.org with outflank-mailman.72609.130809 (Exim 4.92) (envelope-from ) id 1l2sfQ-0003MX-L1; Fri, 22 Jan 2021 09:23:44 +0000 Received: by outflank-mailman (output) from mailman id 72609.130809; Fri, 22 Jan 2021 09:23:44 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1l2sfQ-0003MN-Gw; Fri, 22 Jan 2021 09:23:44 +0000 Received: by outflank-mailman (input) for mailman id 72609; Fri, 22 Jan 2021 09:23:42 +0000 Received: from us1-rack-iad1.inumbo.com ([172.99.69.81]) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1l2sfO-00039U-Mh for xen-devel@lists.xenproject.org; Fri, 22 Jan 2021 09:23:42 +0000 Received: from mx2.suse.de (unknown [195.135.220.15]) by us1-rack-iad1.inumbo.com (Halon) with ESMTPS id 594f7922-4ac8-4967-bc77-89285bcc797d; Fri, 22 Jan 2021 09:23:27 +0000 (UTC) Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 7050AB804; Fri, 22 Jan 2021 09:23:26 +0000 (UTC) X-Outflank-Mailman: Message body and most headers restored to incoming version X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 594f7922-4ac8-4967-bc77-89285bcc797d X-Virus-Scanned: by amavisd-new at test-mx.suse.de DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=susede1; t=1611307406; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=vw3JfTLt9lsKfJRPXabRbaapZoM5jDAcQulm7FKWQ/I=; b=tnRifQ7V6oFcoDuCG4S5Ij8kgIm0KJR1lsiZ0kzwnecCVqMmFFMfyoO/CQNdE4dfnKDNfT 7Fl0NL7sTpo/STfNiBqBljTXUfQhqN5BbjY6C8CH35Ov1UnshgFoSj+fHjONCwUTRV1GaD dIuRnHDfzIBjD+xOx+l8Oukrl9wCIio= From: Juergen Gross To: xen-devel@lists.xenproject.org Cc: Juergen Gross , Ian Jackson , Wei Liu Subject: [PATCH RFC 3/4] tools/xenstore: rework hashtable interfaces Date: Fri, 22 Jan 2021 10:23:23 +0100 Message-Id: <20210122092324.7178-4-jgross@suse.com> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20210122092324.7178-1-jgross@suse.com> References: <20210122092324.7178-1-jgross@suse.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @suse.com) Content-Type: text/plain; charset="utf-8" Rework the interfaces to the hashtable code in order to adapt it better to Xenstore: - don't use user-specified hash- and compare-functions - modify the type of the key to be const char * - instead of using calloc() and free() switch to the talloc interfaces - drop the due to talloc usage no longer needed free_values parameter from hashtable_destroy() - add a hashtable name parameter to create_hashtable() for the talloc context - drop the minsize parameter from create_hashtable() - merge hashtable_private.h into hashtable.c - add a hashtable_traverse() function to iterate over all entries - add a hashtable_replace() function to replace an existing entry - change hashtable_remove() to free the entry and return an int - modify all int return values to 0 for success - introduce a define for "no value" - remove unused macros - fix a bug in hashtable_expand() Signed-off-by: Juergen Gross --- tools/xenstore/hashtable.c | 234 ++++++++++++++++--------- tools/xenstore/hashtable.h | 137 +++++---------- tools/xenstore/hashtable_private.h | 85 --------- tools/xenstore/xenstored_core.c | 49 ++---- tools/xenstore/xenstored_transaction.c | 4 +- 5 files changed, 211 insertions(+), 298 deletions(-) delete mode 100644 tools/xenstore/hashtable_private.h diff --git a/tools/xenstore/hashtable.c b/tools/xenstore/hashtable.c index 394b1cf9d0..6438ec78bf 100644 --- a/tools/xenstore/hashtable.c +++ b/tools/xenstore/hashtable.c @@ -1,12 +1,28 @@ /* Copyright (C) 2004 Christopher Clark = */ =20 #include "hashtable.h" -#include "hashtable_private.h" #include #include #include #include #include +#include "talloc.h" + +struct entry +{ + const char *k; + void *v; + unsigned int h; + struct entry *next; +}; + +struct hashtable { + unsigned int tablelength; + struct entry **table; + unsigned int entrycount; + unsigned int loadlimit; + unsigned int primeindex; +}; =20 /* Credit for primes table: Aaron Krowne @@ -25,51 +41,57 @@ static const unsigned int primes[] =3D { const unsigned int prime_table_length =3D sizeof(primes)/sizeof(primes[0]); const unsigned int max_load_factor =3D 65; /* percentage */ =20 +/*************************************************************************= ****/ +/* indexFor */ +static inline unsigned int +indexFor(unsigned int tablelength, unsigned int hashvalue) { + return (hashvalue % tablelength); +} + +static unsigned int +loadlimit(unsigned int pindex) +{ + return (unsigned int)(((uint64_t)primes[pindex] * max_load_factor) / 1= 00); +} + /*************************************************************************= ****/ struct hashtable * -create_hashtable(unsigned int minsize, - unsigned int (*hashf) (void*), - int (*eqf) (void*,void*)) +create_hashtable(const char *name) { struct hashtable *h; - unsigned int pindex, size =3D primes[0]; =20 - /* Check requested hashtable isn't too large */ - if (minsize > (1u << 30)) return NULL; - - /* Enforce size as prime */ - for (pindex=3D0; pindex < prime_table_length; pindex++) { - if (primes[pindex] > minsize) { size =3D primes[pindex]; break; } - } - - h =3D (struct hashtable *)calloc(1, sizeof(struct hashtable)); + h =3D talloc_zero(NULL, struct hashtable); + talloc_set_name_const(h, name); if (NULL =3D=3D h) goto err0; - h->table =3D (struct entry **)calloc(size, sizeof(struct entry *)); + h->table =3D talloc_zero_array(h, struct entry *, primes[0]); if (NULL =3D=3D h->table) goto err1; =20 - h->tablelength =3D size; - h->primeindex =3D pindex; + h->tablelength =3D primes[0]; + h->primeindex =3D 0; h->entrycount =3D 0; - h->hashfn =3D hashf; - h->eqfn =3D eqf; - h->loadlimit =3D (unsigned int)(((uint64_t)size * max_load_factor) = / 100); + h->loadlimit =3D loadlimit(0); return h; =20 err1: - free(h); + talloc_free(h); err0: return NULL; } =20 /*************************************************************************= ****/ -unsigned int -hash(struct hashtable *h, void *k) +static unsigned int +hash(struct hashtable *h, const char *k) { + unsigned int i =3D 5381; + char c; + + while ((c =3D *k++)) + i =3D ((i << 5) + i) + c; + /* Aim to protect against poor hash functions by adding logic here * - logic taken from java 1.4 hashtable source */ - unsigned int i =3D h->hashfn(k); i +=3D ~(i << 9); i ^=3D ((i >> 14) | (i << 18)); /* >>> */ i +=3D (i << 4); @@ -78,7 +100,7 @@ hash(struct hashtable *h, void *k) } =20 /*************************************************************************= ****/ -static int +static void hashtable_expand(struct hashtable *h) { /* Double the size of the table to accomodate more entries */ @@ -87,10 +109,10 @@ hashtable_expand(struct hashtable *h) struct entry **pE; unsigned int newsize, i, index; /* Check we're not hitting max capacity */ - if (h->primeindex =3D=3D (prime_table_length - 1)) return 0; + if (h->primeindex =3D=3D (prime_table_length - 1)) return; newsize =3D primes[++(h->primeindex)]; =20 - newtable =3D (struct entry **)calloc(newsize, sizeof(struct entry*)); + newtable =3D talloc_zero_array(h, struct entry *, newsize); if (NULL !=3D newtable) { /* This algorithm is not 'stable'. ie. it reverses the list @@ -103,17 +125,17 @@ hashtable_expand(struct hashtable *h) newtable[index] =3D e; } } - free(h->table); + talloc_free(h->table); h->table =3D newtable; } /* Plan B: realloc instead */ else=20 { - newtable =3D (struct entry **) - realloc(h->table, newsize * sizeof(struct entry *)); - if (NULL =3D=3D newtable) { (h->primeindex)--; return 0; } + newtable =3D talloc_realloc(h, h->table, struct entry *, newsize); + if (NULL =3D=3D newtable) { (h->primeindex)--; return; } h->table =3D newtable; - memset(newtable[h->tablelength], 0, newsize - h->tablelength); + memset(newtable + h->tablelength, 0, + (newsize - h->tablelength) * sizeof(*newtable)); for (i =3D 0; i < h->tablelength; i++) { for (pE =3D &(newtable[i]), e =3D *pE; e !=3D NULL; e =3D *pE)= { index =3D indexFor(newsize,e->h); @@ -131,9 +153,7 @@ hashtable_expand(struct hashtable *h) } } h->tablelength =3D newsize; - h->loadlimit =3D (unsigned int) - (((uint64_t)newsize * max_load_factor) / 100); - return -1; + h->loadlimit =3D loadlimit(h->primeindex); } =20 /*************************************************************************= ****/ @@ -145,11 +165,71 @@ hashtable_count(struct hashtable *h) =20 /*************************************************************************= ****/ int -hashtable_insert(struct hashtable *h, void *k, void *v) +hashtable_traverse(struct hashtable *h, + int (fn)(struct hashtable *, const char *, void *, void= *), + void *par) +{ + unsigned int i; + struct entry *e; + struct entry **table =3D h->table; + int ret; + + for (i =3D 0; i < h->tablelength; i++) + { + e =3D table[i]; + for (e =3D table[i]; e; e =3D e->next) + { + ret =3D fn(h, e->k, e->v, par); + if (ret) + return ret; + } + } + return 0; +} + +/*************************************************************************= ****/ +static struct entry * +find_entry(struct hashtable *h, const char *k) +{ + struct entry *e; + unsigned int hashvalue, index; + + hashvalue =3D hash(h,k); + index =3D indexFor(h->tablelength,hashvalue); + e =3D h->table[index]; + while (NULL !=3D e) + { + /* Check hash value to short circuit heavier comparison */ + if ((hashvalue =3D=3D e->h) && !strcmp(k, e->k)) return e; + e =3D e->next; + } + return NULL; +} + +/*************************************************************************= ****/ +static int +insert_or_replace(struct hashtable *h, const char *k, void *v, int r) { - /* This method allows duplicate keys - but they shouldn't be used */ unsigned int index; struct entry *e; + + e =3D find_entry(h, k); + if (e) + { + if (!r) + return -1; + if (e->v !=3D HASHTABLE_NO_VALUE && e->v !=3D v) + talloc_free(e->v); + if (e->k !=3D k) + talloc_free((void *)e->k); + e->k =3D k; + talloc_steal(e, k); + e->v =3D v; + if (v !=3D HASHTABLE_NO_VALUE) + talloc_steal(e, v); + return 0; + } + if (++(h->entrycount) > h->loadlimit) { /* Ignore the return value. If expand fails, we should @@ -158,45 +238,53 @@ hashtable_insert(struct hashtable *h, void *k, void *= v) * element may be ok. Next time we insert, we'll try expanding aga= in.*/ hashtable_expand(h); } - e =3D (struct entry *)calloc(1, sizeof(struct entry)); - if (NULL =3D=3D e) { --(h->entrycount); return 0; } /*oom*/ + e =3D talloc_zero(h, struct entry); + if (NULL =3D=3D e) { --(h->entrycount); return -1; } /*oom*/ e->h =3D hash(h,k); index =3D indexFor(h->tablelength,e->h); e->k =3D k; + talloc_steal(e, k); e->v =3D v; + if (v !=3D HASHTABLE_NO_VALUE) + talloc_steal(e, v); e->next =3D h->table[index]; h->table[index] =3D e; - return -1; + return 0; +} + +/*************************************************************************= ****/ +int +hashtable_insert(struct hashtable *h, const char *k, void *v) +{ + return insert_or_replace(h, k, v, 0); +} + +/*************************************************************************= ****/ +int +hashtable_replace(struct hashtable *h, const char *k, void *v) +{ + return insert_or_replace(h, k, v, 1); } =20 /*************************************************************************= ****/ void * /* returns value associated with key */ -hashtable_search(struct hashtable *h, void *k) +hashtable_search(struct hashtable *h, const char *k) { struct entry *e; - unsigned int hashvalue, index; - hashvalue =3D hash(h,k); - index =3D indexFor(h->tablelength,hashvalue); - e =3D h->table[index]; - while (NULL !=3D e) - { - /* Check hash value to short circuit heavier comparison */ - if ((hashvalue =3D=3D e->h) && (h->eqfn(k, e->k))) return e->v; - e =3D e->next; - } - return NULL; + + e =3D find_entry(h, k); + return e ? e->v : NULL; } =20 /*************************************************************************= ****/ -void * /* returns value associated with key */ -hashtable_remove(struct hashtable *h, void *k) +int +hashtable_remove(struct hashtable *h, const char *k) { /* TODO: consider compacting the table when the load factor drops enou= gh, * or provide a 'compact' method. */ =20 struct entry *e; struct entry **pE; - void *v; unsigned int hashvalue, index; =20 hashvalue =3D hash(h,k); @@ -206,49 +294,25 @@ hashtable_remove(struct hashtable *h, void *k) while (NULL !=3D e) { /* Check hash value to short circuit heavier comparison */ - if ((hashvalue =3D=3D e->h) && (h->eqfn(k, e->k))) + if ((hashvalue =3D=3D e->h) && !strcmp(k, e->k)) { *pE =3D e->next; h->entrycount--; - v =3D e->v; - freekey(e->k); - free(e); - return v; + talloc_free(e); + return 0; } pE =3D &(e->next); e =3D e->next; } - return NULL; + return -1; } =20 /*************************************************************************= ****/ /* destroy */ void -hashtable_destroy(struct hashtable *h, int free_values) +hashtable_destroy(struct hashtable *h) { - unsigned int i; - struct entry *e, *f; - struct entry **table =3D h->table; - if (free_values) - { - for (i =3D 0; i < h->tablelength; i++) - { - e =3D table[i]; - while (NULL !=3D e) - { f =3D e; e =3D e->next; freekey(f->k); free(f->v); free(f); } - } - } - else - { - for (i =3D 0; i < h->tablelength; i++) - { - e =3D table[i]; - while (NULL !=3D e) - { f =3D e; e =3D e->next; freekey(f->k); free(f); } - } - } - free(h->table); - free(h); + talloc_free(h); } =20 /* diff --git a/tools/xenstore/hashtable.h b/tools/xenstore/hashtable.h index b90781abd4..c470a6d585 100644 --- a/tools/xenstore/hashtable.h +++ b/tools/xenstore/hashtable.h @@ -5,76 +5,18 @@ =20 struct hashtable; =20 -/* Example of use: - * - * struct hashtable *h; - * struct some_key *k; - * struct some_value *v; - * - * static unsigned int hash_from_key_fn( void *k ); - * static int keys_equal_fn ( void *key1, void *key2= ); - * - * h =3D create_hashtable(16, hash_from_key_fn, keys_equal_fn); - * k =3D (struct some_key *) malloc(sizeof(struct some_key)); - * v =3D (struct some_value *) malloc(sizeof(struct some_value)); - * - * (initialise k and v to suitable values) - *=20 - * if (! hashtable_insert(h,k,v) ) - * { exit(-1); } - * - * if (NULL =3D=3D (found =3D hashtable_search(h,k) )) - * { printf("not found!"); } - * - * if (NULL =3D=3D (found =3D hashtable_remove(h,k) )) - * { printf("Not found\n"); } - * - */ - -/* Macros may be used to define type-safe(r) hashtable access functions, w= ith - * methods specialized to take known key and value types as parameters. - *=20 - * Example: - * - * Insert this at the start of your file: - * - * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value= ); - * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value= ); - * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value= ); - * - * This defines the functions 'insert_some', 'search_some' and 'remove_som= e'. - * These operate just like hashtable_insert etc., with the same parameters, - * but their function signatures have 'struct some_key *' rather than - * 'void *', and hence can generate compile time errors if your program is - * supplying incorrect data as a key (and similarly for value). - * - * Note that the hash and key equality functions passed to create_hashtable - * still take 'void *' parameters instead of 'some key *'. This shouldn't = be - * a difficult issue as they're only defined and passed once, and the other - * functions will ensure that only valid keys are supplied to them. - * - * The cost for this checking is increased code size and runtime overhead - * - if performance is important, it may be worth switching back to the - * unsafe methods once your program has been debugged with the safe method= s. - * This just requires switching to some simple alternative defines - eg: - * #define insert_some hashtable_insert - * - */ +#define HASHTABLE_NO_VALUE (void *)1 =20 /*************************************************************************= **** * create_hashtable =20 * @name create_hashtable - * @param minsize minimum initial size of hashtable - * @param hashfunction function for hashing keys - * @param key_eq_fn function for determining key equality + * @param name talloc name of the hashtable * @return newly created hashtable or NULL on failure */ =20 struct hashtable * -create_hashtable(unsigned int minsize, - unsigned int (*hashfunction) (void*), - int (*key_eq_fn) (void*,void*)); +create_hashtable(const char *name); =20 /*************************************************************************= **** * hashtable_insert @@ -82,27 +24,37 @@ create_hashtable(unsigned int minsize, * @name hashtable_insert * @param h the hashtable to insert into * @param k the key - hashtable claims ownership and will free on remo= val - * @param v the value - does not claim ownership - * @return non-zero for successful insertion + * @param v the value - hashtable claims ownership and will free on re= moval + * @return zero for successful insertion * * This function will cause the table to expand if the insertion would take * the ratio of entries to table size over the maximum load factor. * - * This function does not check for repeated insertions with a duplicate k= ey. - * The value returned when using a duplicate key is undefined -- when - * the hashtable changes size, the order of retrieval of duplicate key - * entries is reversed. - * If in doubt, remove before insert. + * This function fails in case of trying to insert an entry with an already + * existing key. */ =20 int=20 -hashtable_insert(struct hashtable *h, void *k, void *v); +hashtable_insert(struct hashtable *h, const char *k, void *v); =20 -#define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \ -int fnname (struct hashtable *h, keytype *k, valuetype *v) \ -{ \ - return hashtable_insert(h,k,v); \ -} +/*************************************************************************= **** + * hashtable_replace + + * @name hashtable_replace + * @param h the hashtable to insert into + * @param k the key - hashtable claims ownership and will free on remo= val + * @param v the value - hashtable claims ownership and will free on re= moval + * @return zero for successful insertion + * + * This function will cause the table to expand if the insertion would take + * the ratio of entries to table size over the maximum load factor. + * + * In case an entry with the specified key is existing already it will be + * replaced. + */ + +int +hashtable_replace(struct hashtable *h, const char *k, void *v); =20 /*************************************************************************= **** * hashtable_search @@ -114,13 +66,7 @@ int fnname (struct hashtable *h, keytype *k, valuetype = *v) \ */ =20 void * -hashtable_search(struct hashtable *h, void *k); - -#define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \ -valuetype * fnname (struct hashtable *h, keytype *k) \ -{ \ - return (valuetype *) (hashtable_search(h,k)); \ -} +hashtable_search(struct hashtable *h, const char *k); =20 /*************************************************************************= **** * hashtable_remove @@ -128,18 +74,11 @@ valuetype * fnname (struct hashtable *h, keytype *k) \ * @name hashtable_remove * @param h the hashtable to remove the item from * @param k the key to search for - does not claim ownership - * @return the value associated with the key, or NULL if none found + * @return zero for successful removal */ =20 -void * /* returns value */ -hashtable_remove(struct hashtable *h, void *k); - -#define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \ -valuetype * fnname (struct hashtable *h, keytype *k) \ -{ \ - return (valuetype *) (hashtable_remove(h,k)); \ -} - +int +hashtable_remove(struct hashtable *h, const char *k); =20 /*************************************************************************= **** * hashtable_count @@ -151,17 +90,29 @@ valuetype * fnname (struct hashtable *h, keytype *k) \ unsigned int hashtable_count(struct hashtable *h); =20 +/*************************************************************************= **** + * hashtable_traverse + + * @name hashtable_traverse + * @param h the hashtable + * @param fn function to call for each entry + * @param par private parameter for fn + * @return 0 for success, fn return value else + */ +int +hashtable_traverse(struct hashtable *h,=20 + int (fn)(struct hashtable *, const char *, void *, void= *), + void *par); =20 /*************************************************************************= **** * hashtable_destroy =20 * @name hashtable_destroy * @param h the hashtable - * @param free_values whether to call 'free' on the remaining va= lues */ =20 void -hashtable_destroy(struct hashtable *h, int free_values); +hashtable_destroy(struct hashtable *h); =20 #endif /* __HASHTABLE_CWC22_H__ */ =20 diff --git a/tools/xenstore/hashtable_private.h b/tools/xenstore/hashtable_= private.h deleted file mode 100644 index 3e95f60057..0000000000 --- a/tools/xenstore/hashtable_private.h +++ /dev/null @@ -1,85 +0,0 @@ -/* Copyright (C) 2002, 2004 Christopher Clark */ - -#ifndef __HASHTABLE_PRIVATE_CWC22_H__ -#define __HASHTABLE_PRIVATE_CWC22_H__ - -#include "hashtable.h" - -/*************************************************************************= ****/ -struct entry -{ - void *k, *v; - unsigned int h; - struct entry *next; -}; - -struct hashtable { - unsigned int tablelength; - struct entry **table; - unsigned int entrycount; - unsigned int loadlimit; - unsigned int primeindex; - unsigned int (*hashfn) (void *k); - int (*eqfn) (void *k1, void *k2); -}; - -/*************************************************************************= ****/ -unsigned int -hash(struct hashtable *h, void *k); - -/*************************************************************************= ****/ -/* indexFor */ -static inline unsigned int -indexFor(unsigned int tablelength, unsigned int hashvalue) { - return (hashvalue % tablelength); -}; - -/* Only works if tablelength =3D=3D 2^N */ -/*static inline unsigned int -indexFor(unsigned int tablelength, unsigned int hashvalue) -{ - return (hashvalue & (tablelength - 1u)); -} -*/ - -/*************************************************************************= ****/ -#define freekey(X) free(X) -/*define freekey(X) ; */ - - -/*************************************************************************= ****/ - -#endif /* __HASHTABLE_PRIVATE_CWC22_H__*/ - -/* - * Copyright (c) 2002, Christopher Clark - * All rights reserved. - *=20 - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - *=20 - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - *=20 - * * 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. - *=20 - * * Neither the name of the original author; nor the names of any contrib= utors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - *=20 - *=20 - * 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 O= WNER - * 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. -*/ diff --git a/tools/xenstore/xenstored_core.c b/tools/xenstore/xenstored_cor= e.c index a957055d87..0deaa1a45d 100644 --- a/tools/xenstore/xenstored_core.c +++ b/tools/xenstore/xenstored_core.c @@ -1793,25 +1793,6 @@ static void setup_structure(bool live_update) check_store(); } =20 -static unsigned int hash_from_key_fn(void *k) -{ - char *str =3D k; - unsigned int hash =3D 5381; - char c; - - while ((c =3D *str++)) - hash =3D ((hash << 5) + hash) + (unsigned int)c; - - return hash; -} - - -static int keys_equal_fn(void *key1, void *key2) -{ - return 0 =3D=3D strcmp((char *)key1, (char *)key2); -} - - static char *child_name(const char *s1, const char *s2) { if (strcmp(s1, "/")) { @@ -1825,12 +1806,11 @@ static char *child_name(const char *s1, const char = *s2) =20 int remember_string(struct hashtable *hash, const char *str) { - char *k =3D malloc(strlen(str) + 1); + char *k =3D talloc_strdup(hash, str); =20 if (!k) - return 0; - strcpy(k, str); - return hashtable_insert(hash, k, (void *)1); + return -1; + return hashtable_insert(hash, k, HASHTABLE_NO_VALUE); } =20 =20 @@ -1856,10 +1836,15 @@ static int check_store_(const char *name, struct ha= shtable *reachable) size_t i =3D 0; =20 struct hashtable * children =3D - create_hashtable(16, hash_from_key_fn, keys_equal_fn); + create_hashtable("children"); + + if (!children) { + log("check_store: ENOMEM"); + return ENOMEM; + } =20 - if (!remember_string(reachable, name)) { - hashtable_destroy(children, 0); + if (remember_string(reachable, name)) { + hashtable_destroy(children); log("check_store: ENOMEM"); return ENOMEM; } @@ -1889,8 +1874,8 @@ static int check_store_(const char *name, struct hash= table *reachable) } } else { - if (!remember_string(children, - childname)) { + if (remember_string(children, + childname)) { log("check_store: ENOMEM"); talloc_free(childnode); talloc_free(childname); @@ -1918,8 +1903,7 @@ static int check_store_(const char *name, struct hash= table *reachable) i +=3D childlen + 1; } =20 - hashtable_destroy(children, 0 /* Don't free values (they are - all (void *)1) */); + hashtable_destroy(children); talloc_free(node); } else if (errno !=3D ENOMEM) { /* Impossible, because no database should ever be without the @@ -1983,7 +1967,7 @@ void check_store(void) { char * root =3D talloc_strdup(NULL, "/"); struct hashtable * reachable =3D - create_hashtable(16, hash_from_key_fn, keys_equal_fn); + create_hashtable("reachable"); =20 if (!reachable) { log("check_store: ENOMEM"); @@ -1996,8 +1980,7 @@ void check_store(void) clean_store(reachable); log("Checking store complete."); =20 - hashtable_destroy(reachable, 0 /* Don't free values (they are all - (void *)1) */); + hashtable_destroy(reachable); talloc_free(root); } =20 diff --git a/tools/xenstore/xenstored_transaction.c b/tools/xenstore/xensto= red_transaction.c index cd07fb0f21..8b8b38cea7 100644 --- a/tools/xenstore/xenstored_transaction.c +++ b/tools/xenstore/xenstored_transaction.c @@ -607,7 +607,7 @@ int check_transactions(struct hashtable *hash) list_for_each_entry(trans, &conn->transaction_list, list) { tname =3D talloc_asprintf(trans, "%"PRIu64, trans->generation); - if (!tname || !remember_string(hash, tname)) + if (!tname || remember_string(hash, tname)) goto nomem; =20 list_for_each_entry(i, &trans->accessed, list) { @@ -615,7 +615,7 @@ int check_transactions(struct hashtable *hash) continue; tnode =3D transaction_get_node_name(tname, trans, i->node); - if (!tnode || !remember_string(hash, tnode)) + if (!tnode || remember_string(hash, tnode)) goto nomem; talloc_free(tnode); } --=20 2.26.2