#ifndef HASH_H
#define HASH_H

/* Hash table implementation from the GIT project. */
/* Copyright 2008 (C) Linus Torvalds, GPL version 2 */
/*
 * These are some simple generic hash table helper functions.
 * Not necessarily suitable for all users, but good for things
 * where you want to just keep track of a list of things, and
 * have a good hash to use on them.
 *
 * It keeps the hash table at roughly 50-75% free, so the memory
 * cost of the hash table itself is roughly
 *
 *	3 * 2*sizeof(void *) * nr_of_objects
 *
 * bytes.
 *
 * FIXME: on 64-bit architectures, we waste memory. It would be
 * good to have just 32-bit pointers, requiring a special allocator
 * for hashed entries or something.
 */

#include <stdio.h>

#define alloc_nr(x) (((x) + 16) * 3 / 2)
#define INSERT_HASH_PROTOS(ops, table)					\
	do {								\
		void **pos = insert_hash((ops).key, &(ops), &(table));	\
		/* We already had an entry there? */			\
		if (pos) {						\
			(ops).next = *pos;				\
			*pos = &(ops);					\
		}							\
	} while (0)

struct hash_table_entry {
	unsigned int hash;
	void *ptr;
};

struct hash_table {
	unsigned int size, nr;
	struct hash_table_entry *array;
};

extern void *lookup_hash(unsigned int hash, const struct hash_table *table);
extern void **insert_hash(unsigned int hash, void *ptr,
			  struct hash_table *table);
extern void *remove_hash(unsigned int hash, void *ptr, void *ptr_next,
			 struct hash_table *table);
extern int for_each_hash(const struct hash_table *table, int (*fn)(void *));
extern int for_each_hash_int(const struct hash_table *table,
			     int (*fn)(void *, int), int arg);
extern void free_hash(struct hash_table *table);

static inline void init_hash(struct hash_table *table)
{
	table->size = 0;
	table->nr = 0;
	table->array = NULL;
}

static inline unsigned char icase_hash(unsigned char c)
{
	return c & ~((c & 0x40) >> 1);
}

static inline unsigned int hash_name(const char *name, int namelen)
{
	unsigned int hash = 0x123;
	do {
		unsigned char c = *name++;
		c = icase_hash(c);
		hash = hash * 101 + c;
	} while (--namelen);
	return hash;
}

#endif /* HASH_H */
get' action='/cgit.cgi/linux/net-next.git/log/'>
<input type='hidden' name='id' value='3be134e5152f08e8bd3c2afdaac723f64d93c2bb'/><select name='qt'>
<option value='grep'>log msg</option>
<option value='author'>author</option>
<option value='committer'>committer</option>
<option value='range'>range</option>
</select>
<input class='txt' type='search' size='10' name='q' value=''/>
<input type='submit' value='search'/>
</form>
</td></tr></table>
<div class='content'><div class='cgit-panel'><b>diff options</b><form method='get'><input type='hidden' name='id' value='3be134e5152f08e8bd3c2afdaac723f64d93c2bb'/><table><tr><td colspan='2'/></tr><tr><td class='label'>context:</td><td class='ctrl'><select name='context' onchange='this.form.submit();'><option value='1'>1</option><option value='2'>2</option><option value='3' selected='selected'>3</option><option value='4'>4</option><option value='5'>5</option><option value='6'>6</option><option value='7'>7</option><option value='8'>8</option><option value='9'>9</option><option value='10'>10</option><option value='15'>15</option><option value='20'>20</option><option value='25'>25</option><option value='30'>30</option><option value='35'>35</option><option value='40'>40</option></select></td></tr><tr><td class='label'>space:</td><td class='ctrl'><select name='ignorews' onchange='this.form.submit();'><option value='0' selected='selected'>include</option><option value='1'>ignore</option></select></td></tr><tr><td class='label'>mode:</td><td class='ctrl'><select name='dt' onchange='this.form.submit();'><option value='0' selected='selected'>unified</option><option value='1'>ssdiff</option><option value='2'>stat only</option></select></td></tr><tr><td/><td class='ctrl'><noscript><input type='submit' value='reload'/></noscript></td></tr></table></form></div><table summary='commit info' class='commit-info'>
<tr><th>author</th><td>Linus Torvalds &lt;torvalds@linux-foundation.org&gt;</td><td class='right'>2016-12-18 15:49:10 -0800</td></tr>
<tr><th>committer</th><td>Linus Torvalds &lt;torvalds@linux-foundation.org&gt;</td><td class='right'>2016-12-18 15:49:10 -0800</td></tr>
<tr><th>commit</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/?id=3be134e5152f08e8bd3c2afdaac723f64d93c2bb'>3be134e5152f08e8bd3c2afdaac723f64d93c2bb</a> (<a href='/cgit.cgi/linux/net-next.git/patch/?id=3be134e5152f08e8bd3c2afdaac723f64d93c2bb'>patch</a>)</td></tr>
<tr><th>tree</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/tree/?id=3be134e5152f08e8bd3c2afdaac723f64d93c2bb'>ba325ebb1a9f79a4a8451a8f5eaeed9cbd1c2e04</a></td></tr>
<tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/?id=8421c60446290c0fef1858a806261871a40ebf76'>8421c60446290c0fef1858a806261871a40ebf76</a> (<a href='/cgit.cgi/linux/net-next.git/diff/?id=3be134e5152f08e8bd3c2afdaac723f64d93c2bb&amp;id2=8421c60446290c0fef1858a806261871a40ebf76'>diff</a>)</td></tr><tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/?id=c44ef859ceff45db1c72f9ccbfae96843c4b1501'>c44ef859ceff45db1c72f9ccbfae96843c4b1501</a> (<a href='/cgit.cgi/linux/net-next.git/diff/?id=3be134e5152f08e8bd3c2afdaac723f64d93c2bb&amp;id2=c44ef859ceff45db1c72f9ccbfae96843c4b1501'>diff</a>)</td></tr></table>
<div class='commit-subject'>Merge tag 'libnvdimm-for-4.10' of git://git.kernel.org/pub/scm/linux/kernel/git/nvdimm/nvdimm</div><div class='commit-msg'>Pull libnvdimm updates from Dan Williams:
 "The libnvdimm pull request is relatively small this time around due to
  some development topics being deferred to 4.11.

  As for this pull request the bulk of it has been in -next for several
  releases leading to one late fix being added (commit 868f036fee4b
  ("libnvdimm: fix mishandled nvdimm_clear_poison() return value")). It
  has received a build success notification from the 0day-kbuild robot
  and passes the latest libnvdimm unit tests.

  Summary:

   - Dynamic label support: To date namespace label support has been
     limited to disambiguating cases where PMEM (direct load/store) and
     BLK (mmio aperture) accessed-capacity alias on the same DIMM. Since
     4.9 added support for multiple namespaces per PMEM-region there is
     value to support namespace labels even in the non-aliasing case.
     The presence of a valid namespace index block force-enables label
     support when the kernel would otherwise rely on region boundaries,
     and permits the region to be sub-divided.

   - Handle media errors in namespace metadata: Complement the error
     handling for media errors in namespace data areas with support for
     clearing errors on writes, and downgrading potential machine-check
     exceptions to simple i/o errors on read.

   - Device-DAX region attributes: Add 'align', 'id', and 'size' as
     attributes for device-dax regions. In particular this enables
     userspace tooling to generically size memory mapping and i/o
     operations. Prevent userspace from growing assumptions /
     dependencies about the parent device topology for a dax region. A
     libnvdimm namespace may not always be the parent device of a dax
     region.

   - Various cleanups and small fixes"

* tag 'libnvdimm-for-4.10' of git://git.kernel.org/pub/scm/linux/kernel/git/nvdimm/nvdimm:
  dax: add region 'id', 'size', and 'align' attributes
  libnvdimm: fix mishandled nvdimm_clear_poison() return value
  libnvdimm: replace mutex_is_locked() warnings with lockdep_assert_held
  libnvdimm, pfn: fix align attribute
  libnvdimm, e820: use module_platform_driver
  libnvdimm, namespace: use octal for permissions
  libnvdimm, namespace: avoid multiple sector calculations
  libnvdimm: remove else after return in nsio_rw_bytes()
  libnvdimm, namespace: fix the type of name variable
  libnvdimm: use consistent naming for request_mem_region()
  nvdimm: use the right length of "pmem"
  libnvdimm: check and clear poison before writing to pmem
  tools/testing/nvdimm: dynamic label support
  libnvdimm: allow a platform to force enable label support
  libnvdimm: use generic iostat interfaces
</div><div class='diffstat-header'><a href='/cgit.cgi/linux/net-next.git/diff/?id=3be134e5152f08e8bd3c2afdaac723f64d93c2bb'>Diffstat</a></div><table summary='diffstat' class='diffstat'>