<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" | |
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> | |
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"> | |
<head> | |
<meta http-equiv="Content-Type" content="application/xhtml+xml; charset=UTF-8" /> | |
<meta name="generator" content="AsciiDoc 8.6.9" /> | |
<title>hashmap API</title> | |
<style type="text/css"> | |
/* Shared CSS for AsciiDoc xhtml11 and html5 backends */ | |
/* Default font. */ | |
body { | |
font-family: Georgia,serif; | |
} | |
/* Title font. */ | |
h1, h2, h3, h4, h5, h6, | |
div.title, caption.title, | |
thead, p.table.header, | |
#toctitle, | |
#author, #revnumber, #revdate, #revremark, | |
#footer { | |
font-family: Arial,Helvetica,sans-serif; | |
} | |
body { | |
margin: 1em 5% 1em 5%; | |
} | |
a { | |
color: blue; | |
text-decoration: underline; | |
} | |
a:visited { | |
color: fuchsia; | |
} | |
em { | |
font-style: italic; | |
color: navy; | |
} | |
strong { | |
font-weight: bold; | |
color: #083194; | |
} | |
h1, h2, h3, h4, h5, h6 { | |
color: #527bbd; | |
margin-top: 1.2em; | |
margin-bottom: 0.5em; | |
line-height: 1.3; | |
} | |
h1, h2, h3 { | |
border-bottom: 2px solid silver; | |
} | |
h2 { | |
padding-top: 0.5em; | |
} | |
h3 { | |
float: left; | |
} | |
h3 + * { | |
clear: left; | |
} | |
h5 { | |
font-size: 1.0em; | |
} | |
div.sectionbody { | |
margin-left: 0; | |
} | |
hr { | |
border: 1px solid silver; | |
} | |
p { | |
margin-top: 0.5em; | |
margin-bottom: 0.5em; | |
} | |
ul, ol, li > p { | |
margin-top: 0; | |
} | |
ul > li { color: #aaa; } | |
ul > li > * { color: black; } | |
.monospaced, code, pre { | |
font-family: "Courier New", Courier, monospace; | |
font-size: inherit; | |
color: navy; | |
padding: 0; | |
margin: 0; | |
} | |
pre { | |
white-space: pre-wrap; | |
} | |
#author { | |
color: #527bbd; | |
font-weight: bold; | |
font-size: 1.1em; | |
} | |
#email { | |
} | |
#revnumber, #revdate, #revremark { | |
} | |
#footer { | |
font-size: small; | |
border-top: 2px solid silver; | |
padding-top: 0.5em; | |
margin-top: 4.0em; | |
} | |
#footer-text { | |
float: left; | |
padding-bottom: 0.5em; | |
} | |
#footer-badges { | |
float: right; | |
padding-bottom: 0.5em; | |
} | |
#preamble { | |
margin-top: 1.5em; | |
margin-bottom: 1.5em; | |
} | |
div.imageblock, div.exampleblock, div.verseblock, | |
div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock, | |
div.admonitionblock { | |
margin-top: 1.0em; | |
margin-bottom: 1.5em; | |
} | |
div.admonitionblock { | |
margin-top: 2.0em; | |
margin-bottom: 2.0em; | |
margin-right: 10%; | |
color: #606060; | |
} | |
div.content { /* Block element content. */ | |
padding: 0; | |
} | |
/* Block element titles. */ | |
div.title, caption.title { | |
color: #527bbd; | |
font-weight: bold; | |
text-align: left; | |
margin-top: 1.0em; | |
margin-bottom: 0.5em; | |
} | |
div.title + * { | |
margin-top: 0; | |
} | |
td div.title:first-child { | |
margin-top: 0.0em; | |
} | |
div.content div.title:first-child { | |
margin-top: 0.0em; | |
} | |
div.content + div.title { | |
margin-top: 0.0em; | |
} | |
div.sidebarblock > div.content { | |
background: #ffffee; | |
border: 1px solid #dddddd; | |
border-left: 4px solid #f0f0f0; | |
padding: 0.5em; | |
} | |
div.listingblock > div.content { | |
border: 1px solid #dddddd; | |
border-left: 5px solid #f0f0f0; | |
background: #f8f8f8; | |
padding: 0.5em; | |
} | |
div.quoteblock, div.verseblock { | |
padding-left: 1.0em; | |
margin-left: 1.0em; | |
margin-right: 10%; | |
border-left: 5px solid #f0f0f0; | |
color: #888; | |
} | |
div.quoteblock > div.attribution { | |
padding-top: 0.5em; | |
text-align: right; | |
} | |
div.verseblock > pre.content { | |
font-family: inherit; | |
font-size: inherit; | |
} | |
div.verseblock > div.attribution { | |
padding-top: 0.75em; | |
text-align: left; | |
} | |
/* DEPRECATED: Pre version 8.2.7 verse style literal block. */ | |
div.verseblock + div.attribution { | |
text-align: left; | |
} | |
div.admonitionblock .icon { | |
vertical-align: top; | |
font-size: 1.1em; | |
font-weight: bold; | |
text-decoration: underline; | |
color: #527bbd; | |
padding-right: 0.5em; | |
} | |
div.admonitionblock td.content { | |
padding-left: 0.5em; | |
border-left: 3px solid #dddddd; | |
} | |
div.exampleblock > div.content { | |
border-left: 3px solid #dddddd; | |
padding-left: 0.5em; | |
} | |
div.imageblock div.content { padding-left: 0; } | |
span.image img { border-style: none; vertical-align: text-bottom; } | |
a.image:visited { color: white; } | |
dl { | |
margin-top: 0.8em; | |
margin-bottom: 0.8em; | |
} | |
dt { | |
margin-top: 0.5em; | |
margin-bottom: 0; | |
font-style: normal; | |
color: navy; | |
} | |
dd > *:first-child { | |
margin-top: 0.1em; | |
} | |
ul, ol { | |
list-style-position: outside; | |
} | |
ol.arabic { | |
list-style-type: decimal; | |
} | |
ol.loweralpha { | |
list-style-type: lower-alpha; | |
} | |
ol.upperalpha { | |
list-style-type: upper-alpha; | |
} | |
ol.lowerroman { | |
list-style-type: lower-roman; | |
} | |
ol.upperroman { | |
list-style-type: upper-roman; | |
} | |
div.compact ul, div.compact ol, | |
div.compact p, div.compact p, | |
div.compact div, div.compact div { | |
margin-top: 0.1em; | |
margin-bottom: 0.1em; | |
} | |
tfoot { | |
font-weight: bold; | |
} | |
td > div.verse { | |
white-space: pre; | |
} | |
div.hdlist { | |
margin-top: 0.8em; | |
margin-bottom: 0.8em; | |
} | |
div.hdlist tr { | |
padding-bottom: 15px; | |
} | |
dt.hdlist1.strong, td.hdlist1.strong { | |
font-weight: bold; | |
} | |
td.hdlist1 { | |
vertical-align: top; | |
font-style: normal; | |
padding-right: 0.8em; | |
color: navy; | |
} | |
td.hdlist2 { | |
vertical-align: top; | |
} | |
div.hdlist.compact tr { | |
margin: 0; | |
padding-bottom: 0; | |
} | |
.comment { | |
background: yellow; | |
} | |
.footnote, .footnoteref { | |
font-size: 0.8em; | |
} | |
span.footnote, span.footnoteref { | |
vertical-align: super; | |
} | |
#footnotes { | |
margin: 20px 0 20px 0; | |
padding: 7px 0 0 0; | |
} | |
#footnotes div.footnote { | |
margin: 0 0 5px 0; | |
} | |
#footnotes hr { | |
border: none; | |
border-top: 1px solid silver; | |
height: 1px; | |
text-align: left; | |
margin-left: 0; | |
width: 20%; | |
min-width: 100px; | |
} | |
div.colist td { | |
padding-right: 0.5em; | |
padding-bottom: 0.3em; | |
vertical-align: top; | |
} | |
div.colist td img { | |
margin-top: 0.3em; | |
} | |
@media print { | |
#footer-badges { display: none; } | |
} | |
#toc { | |
margin-bottom: 2.5em; | |
} | |
#toctitle { | |
color: #527bbd; | |
font-size: 1.1em; | |
font-weight: bold; | |
margin-top: 1.0em; | |
margin-bottom: 0.1em; | |
} | |
div.toclevel0, div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 { | |
margin-top: 0; | |
margin-bottom: 0; | |
} | |
div.toclevel2 { | |
margin-left: 2em; | |
font-size: 0.9em; | |
} | |
div.toclevel3 { | |
margin-left: 4em; | |
font-size: 0.9em; | |
} | |
div.toclevel4 { | |
margin-left: 6em; | |
font-size: 0.9em; | |
} | |
span.aqua { color: aqua; } | |
span.black { color: black; } | |
span.blue { color: blue; } | |
span.fuchsia { color: fuchsia; } | |
span.gray { color: gray; } | |
span.green { color: green; } | |
span.lime { color: lime; } | |
span.maroon { color: maroon; } | |
span.navy { color: navy; } | |
span.olive { color: olive; } | |
span.purple { color: purple; } | |
span.red { color: red; } | |
span.silver { color: silver; } | |
span.teal { color: teal; } | |
span.white { color: white; } | |
span.yellow { color: yellow; } | |
span.aqua-background { background: aqua; } | |
span.black-background { background: black; } | |
span.blue-background { background: blue; } | |
span.fuchsia-background { background: fuchsia; } | |
span.gray-background { background: gray; } | |
span.green-background { background: green; } | |
span.lime-background { background: lime; } | |
span.maroon-background { background: maroon; } | |
span.navy-background { background: navy; } | |
span.olive-background { background: olive; } | |
span.purple-background { background: purple; } | |
span.red-background { background: red; } | |
span.silver-background { background: silver; } | |
span.teal-background { background: teal; } | |
span.white-background { background: white; } | |
span.yellow-background { background: yellow; } | |
span.big { font-size: 2em; } | |
span.small { font-size: 0.6em; } | |
span.underline { text-decoration: underline; } | |
span.overline { text-decoration: overline; } | |
span.line-through { text-decoration: line-through; } | |
div.unbreakable { page-break-inside: avoid; } | |
/* | |
* xhtml11 specific | |
* | |
* */ | |
div.tableblock { | |
margin-top: 1.0em; | |
margin-bottom: 1.5em; | |
} | |
div.tableblock > table { | |
border: 3px solid #527bbd; | |
} | |
thead, p.table.header { | |
font-weight: bold; | |
color: #527bbd; | |
} | |
p.table { | |
margin-top: 0; | |
} | |
/* Because the table frame attribute is overriden by CSS in most browsers. */ | |
div.tableblock > table[frame="void"] { | |
border-style: none; | |
} | |
div.tableblock > table[frame="hsides"] { | |
border-left-style: none; | |
border-right-style: none; | |
} | |
div.tableblock > table[frame="vsides"] { | |
border-top-style: none; | |
border-bottom-style: none; | |
} | |
/* | |
* html5 specific | |
* | |
* */ | |
table.tableblock { | |
margin-top: 1.0em; | |
margin-bottom: 1.5em; | |
} | |
thead, p.tableblock.header { | |
font-weight: bold; | |
color: #527bbd; | |
} | |
p.tableblock { | |
margin-top: 0; | |
} | |
table.tableblock { | |
border-width: 3px; | |
border-spacing: 0px; | |
border-style: solid; | |
border-color: #527bbd; | |
border-collapse: collapse; | |
} | |
th.tableblock, td.tableblock { | |
border-width: 1px; | |
padding: 4px; | |
border-style: solid; | |
border-color: #527bbd; | |
} | |
table.tableblock.frame-topbot { | |
border-left-style: hidden; | |
border-right-style: hidden; | |
} | |
table.tableblock.frame-sides { | |
border-top-style: hidden; | |
border-bottom-style: hidden; | |
} | |
table.tableblock.frame-none { | |
border-style: hidden; | |
} | |
th.tableblock.halign-left, td.tableblock.halign-left { | |
text-align: left; | |
} | |
th.tableblock.halign-center, td.tableblock.halign-center { | |
text-align: center; | |
} | |
th.tableblock.halign-right, td.tableblock.halign-right { | |
text-align: right; | |
} | |
th.tableblock.valign-top, td.tableblock.valign-top { | |
vertical-align: top; | |
} | |
th.tableblock.valign-middle, td.tableblock.valign-middle { | |
vertical-align: middle; | |
} | |
th.tableblock.valign-bottom, td.tableblock.valign-bottom { | |
vertical-align: bottom; | |
} | |
/* | |
* manpage specific | |
* | |
* */ | |
body.manpage h1 { | |
padding-top: 0.5em; | |
padding-bottom: 0.5em; | |
border-top: 2px solid silver; | |
border-bottom: 2px solid silver; | |
} | |
body.manpage h2 { | |
border-style: none; | |
} | |
body.manpage div.sectionbody { | |
margin-left: 3em; | |
} | |
@media print { | |
body.manpage div#toc { display: none; } | |
} | |
</style> | |
<script type="text/javascript"> | |
/*<![CDATA[*/ | |
var asciidoc = { // Namespace. | |
///////////////////////////////////////////////////////////////////// | |
// Table Of Contents generator | |
///////////////////////////////////////////////////////////////////// | |
/* Author: Mihai Bazon, September 2002 | |
* http://students.infoiasi.ro/~mishoo | |
* | |
* Table Of Content generator | |
* Version: 0.4 | |
* | |
* Feel free to use this script under the terms of the GNU General Public | |
* License, as long as you do not remove or alter this notice. | |
*/ | |
/* modified by Troy D. Hanson, September 2006. License: GPL */ | |
/* modified by Stuart Rackham, 2006, 2009. License: GPL */ | |
// toclevels = 1..4. | |
toc: function (toclevels) { | |
function getText(el) { | |
var text = ""; | |
for (var i = el.firstChild; i != null; i = i.nextSibling) { | |
if (i.nodeType == 3 /* Node.TEXT_NODE */) // IE doesn't speak constants. | |
text += i.data; | |
else if (i.firstChild != null) | |
text += getText(i); | |
} | |
return text; | |
} | |
function TocEntry(el, text, toclevel) { | |
this.element = el; | |
this.text = text; | |
this.toclevel = toclevel; | |
} | |
function tocEntries(el, toclevels) { | |
var result = new Array; | |
var re = new RegExp('[hH]([1-'+(toclevels+1)+'])'); | |
// Function that scans the DOM tree for header elements (the DOM2 | |
// nodeIterator API would be a better technique but not supported by all | |
// browsers). | |
var iterate = function (el) { | |
for (var i = el.firstChild; i != null; i = i.nextSibling) { | |
if (i.nodeType == 1 /* Node.ELEMENT_NODE */) { | |
var mo = re.exec(i.tagName); | |
if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") { | |
result[result.length] = new TocEntry(i, getText(i), mo[1]-1); | |
} | |
iterate(i); | |
} | |
} | |
} | |
iterate(el); | |
return result; | |
} | |
var toc = document.getElementById("toc"); | |
if (!toc) { | |
return; | |
} | |
// Delete existing TOC entries in case we're reloading the TOC. | |
var tocEntriesToRemove = []; | |
var i; | |
for (i = 0; i < toc.childNodes.length; i++) { | |
var entry = toc.childNodes[i]; | |
if (entry.nodeName.toLowerCase() == 'div' | |
&& entry.getAttribute("class") | |
&& entry.getAttribute("class").match(/^toclevel/)) | |
tocEntriesToRemove.push(entry); | |
} | |
for (i = 0; i < tocEntriesToRemove.length; i++) { | |
toc.removeChild(tocEntriesToRemove[i]); | |
} | |
// Rebuild TOC entries. | |
var entries = tocEntries(document.getElementById("content"), toclevels); | |
for (var i = 0; i < entries.length; ++i) { | |
var entry = entries[i]; | |
if (entry.element.id == "") | |
entry.element.id = "_toc_" + i; | |
var a = document.createElement("a"); | |
a.href = "#" + entry.element.id; | |
a.appendChild(document.createTextNode(entry.text)); | |
var div = document.createElement("div"); | |
div.appendChild(a); | |
div.className = "toclevel" + entry.toclevel; | |
toc.appendChild(div); | |
} | |
if (entries.length == 0) | |
toc.parentNode.removeChild(toc); | |
}, | |
///////////////////////////////////////////////////////////////////// | |
// Footnotes generator | |
///////////////////////////////////////////////////////////////////// | |
/* Based on footnote generation code from: | |
* http://www.brandspankingnew.net/archive/2005/07/format_footnote.html | |
*/ | |
footnotes: function () { | |
// Delete existing footnote entries in case we're reloading the footnodes. | |
var i; | |
var noteholder = document.getElementById("footnotes"); | |
if (!noteholder) { | |
return; | |
} | |
var entriesToRemove = []; | |
for (i = 0; i < noteholder.childNodes.length; i++) { | |
var entry = noteholder.childNodes[i]; | |
if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute("class") == "footnote") | |
entriesToRemove.push(entry); | |
} | |
for (i = 0; i < entriesToRemove.length; i++) { | |
noteholder.removeChild(entriesToRemove[i]); | |
} | |
// Rebuild footnote entries. | |
var cont = document.getElementById("content"); | |
var spans = cont.getElementsByTagName("span"); | |
var refs = {}; | |
var n = 0; | |
for (i=0; i<spans.length; i++) { | |
if (spans[i].className == "footnote") { | |
n++; | |
var note = spans[i].getAttribute("data-note"); | |
if (!note) { | |
// Use [\s\S] in place of . so multi-line matches work. | |
// Because JavaScript has no s (dotall) regex flag. | |
note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1]; | |
spans[i].innerHTML = | |
"[<a id='_footnoteref_" + n + "' href='#_footnote_" + n + | |
"' title='View footnote' class='footnote'>" + n + "</a>]"; | |
spans[i].setAttribute("data-note", note); | |
} | |
noteholder.innerHTML += | |
"<div class='footnote' id='_footnote_" + n + "'>" + | |
"<a href='#_footnoteref_" + n + "' title='Return to text'>" + | |
n + "</a>. " + note + "</div>"; | |
var id =spans[i].getAttribute("id"); | |
if (id != null) refs["#"+id] = n; | |
} | |
} | |
if (n == 0) | |
noteholder.parentNode.removeChild(noteholder); | |
else { | |
// Process footnoterefs. | |
for (i=0; i<spans.length; i++) { | |
if (spans[i].className == "footnoteref") { | |
var href = spans[i].getElementsByTagName("a")[0].getAttribute("href"); | |
href = href.match(/#.*/)[0]; // Because IE return full URL. | |
n = refs[href]; | |
spans[i].innerHTML = | |
"[<a href='#_footnote_" + n + | |
"' title='View footnote' class='footnote'>" + n + "</a>]"; | |
} | |
} | |
} | |
}, | |
install: function(toclevels) { | |
var timerId; | |
function reinstall() { | |
asciidoc.footnotes(); | |
if (toclevels) { | |
asciidoc.toc(toclevels); | |
} | |
} | |
function reinstallAndRemoveTimer() { | |
clearInterval(timerId); | |
reinstall(); | |
} | |
timerId = setInterval(reinstall, 500); | |
if (document.addEventListener) | |
document.addEventListener("DOMContentLoaded", reinstallAndRemoveTimer, false); | |
else | |
window.onload = reinstallAndRemoveTimer; | |
} | |
} | |
asciidoc.install(); | |
/*]]>*/ | |
</script> | |
</head> | |
<body class="article"> | |
<div id="header"> | |
<h1>hashmap API</h1> | |
</div> | |
<div id="content"> | |
<div id="preamble"> | |
<div class="sectionbody"> | |
<div class="paragraph"><p>The hashmap API is a generic implementation of hash-based key-value mappings.</p></div> | |
</div> | |
</div> | |
<div class="sect1"> | |
<h2 id="_data_structures">Data Structures</h2> | |
<div class="sectionbody"> | |
<div class="dlist"><dl> | |
<dt class="hdlist1"> | |
<code>struct hashmap</code> | |
</dt> | |
<dd> | |
<p> | |
The hash table structure. Members can be used as follows, but should | |
not be modified directly: | |
</p> | |
<div class="paragraph"><p>The <code>size</code> member keeps track of the total number of entries (0 means the | |
hashmap is empty).</p></div> | |
<div class="paragraph"><p><code>tablesize</code> is the allocated size of the hash table. A non-0 value indicates | |
that the hashmap is initialized. It may also be useful for statistical purposes | |
(i.e. <code>size / tablesize</code> is the current load factor).</p></div> | |
<div class="paragraph"><p><code>cmpfn</code> stores the comparison function specified in <code>hashmap_init()</code>. In | |
advanced scenarios, it may be useful to change this, e.g. to switch between | |
case-sensitive and case-insensitive lookup.</p></div> | |
<div class="paragraph"><p>When <code>disallow_rehash</code> is set, automatic rehashes are prevented during inserts | |
and deletes.</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>struct hashmap_entry</code> | |
</dt> | |
<dd> | |
<p> | |
An opaque structure representing an entry in the hash table, which must | |
be used as first member of user data structures. Ideally it should be | |
followed by an int-sized member to prevent unused memory on 64-bit | |
systems due to alignment. | |
</p> | |
<div class="paragraph"><p>The <code>hash</code> member is the entry’s hash code and the <code>next</code> member points to the | |
next entry in case of collisions (i.e. if multiple entries map to the same | |
bucket).</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>struct hashmap_iter</code> | |
</dt> | |
<dd> | |
<p> | |
An iterator structure, to be used with hashmap_iter_* functions. | |
</p> | |
</dd> | |
</dl></div> | |
</div> | |
</div> | |
<div class="sect1"> | |
<h2 id="_types">Types</h2> | |
<div class="sectionbody"> | |
<div class="dlist"><dl> | |
<dt class="hdlist1"> | |
<code>int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)</code> | |
</dt> | |
<dd> | |
<p> | |
User-supplied function to test two hashmap entries for equality. Shall | |
return 0 if the entries are equal. | |
</p> | |
<div class="paragraph"><p>This function is always called with non-NULL <code>entry</code> / <code>entry_or_key</code> | |
parameters that have the same hash code. When looking up an entry, the <code>key</code> | |
and <code>keydata</code> parameters to hashmap_get and hashmap_remove are always passed | |
as second and third argument, respectively. Otherwise, <code>keydata</code> is NULL.</p></div> | |
</dd> | |
</dl></div> | |
</div> | |
</div> | |
<div class="sect1"> | |
<h2 id="_functions">Functions</h2> | |
<div class="sectionbody"> | |
<div class="dlist"><dl> | |
<dt class="hdlist1"> | |
<code>unsigned int strhash(const char *buf)</code> | |
</dt> | |
<dt class="hdlist1"> | |
<code>unsigned int strihash(const char *buf)</code> | |
</dt> | |
<dt class="hdlist1"> | |
<code>unsigned int memhash(const void *buf, size_t len)</code> | |
</dt> | |
<dt class="hdlist1"> | |
<code>unsigned int memihash(const void *buf, size_t len)</code> | |
</dt> | |
<dt class="hdlist1"> | |
<code>unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)</code> | |
</dt> | |
<dd> | |
<p> | |
Ready-to-use hash functions for strings, using the FNV-1 algorithm (see | |
<a href="http://www.isthe.com/chongo/tech/comp/fnv">http://www.isthe.com/chongo/tech/comp/fnv</a>). | |
</p> | |
<div class="paragraph"><p><code>strhash</code> and <code>strihash</code> take 0-terminated strings, while <code>memhash</code> and | |
<code>memihash</code> operate on arbitrary-length memory.</p></div> | |
<div class="paragraph"><p><code>strihash</code> and <code>memihash</code> are case insensitive versions.</p></div> | |
<div class="paragraph"><p><code>memihash_cont</code> is a variant of <code>memihash</code> that allows a computation to be | |
continued with another chunk of data.</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>unsigned int sha1hash(const unsigned char *sha1)</code> | |
</dt> | |
<dd> | |
<p> | |
Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code | |
for use in hash tables. Cryptographic hashes are supposed to have | |
uniform distribution, so in contrast to <code>memhash()</code>, this just copies | |
the first <code>sizeof(int)</code> bytes without shuffling any bits. Note that | |
the results will be different on big-endian and little-endian | |
platforms, so they should not be stored or transferred over the net. | |
</p> | |
</dd> | |
<dt class="hdlist1"> | |
<code>void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size)</code> | |
</dt> | |
<dd> | |
<p> | |
Initializes a hashmap structure. | |
</p> | |
<div class="paragraph"><p><code>map</code> is the hashmap to initialize.</p></div> | |
<div class="paragraph"><p>The <code>equals_function</code> can be specified to compare two entries for equality. | |
If NULL, entries are considered equal if their hash codes are equal.</p></div> | |
<div class="paragraph"><p>If the total number of entries is known in advance, the <code>initial_size</code> | |
parameter may be used to preallocate a sufficiently large table and thus | |
prevent expensive resizing. If 0, the table is dynamically resized.</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>void hashmap_free(struct hashmap *map, int free_entries)</code> | |
</dt> | |
<dd> | |
<p> | |
Frees a hashmap structure and allocated memory. | |
</p> | |
<div class="paragraph"><p><code>map</code> is the hashmap to free.</p></div> | |
<div class="paragraph"><p>If <code>free_entries</code> is true, each hashmap_entry in the map is freed as well | |
(using stdlib’s free()).</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>void hashmap_entry_init(void *entry, unsigned int hash)</code> | |
</dt> | |
<dd> | |
<p> | |
Initializes a hashmap_entry structure. | |
</p> | |
<div class="paragraph"><p><code>entry</code> points to the entry to initialize.</p></div> | |
<div class="paragraph"><p><code>hash</code> is the hash code of the entry.</p></div> | |
<div class="paragraph"><p>The hashmap_entry structure does not hold references to external resources, | |
and it is safe to just discard it once you are done with it (i.e. if | |
your structure was allocated with xmalloc(), you can just free(3) it, | |
and if it is on stack, you can just let it go out of scope).</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)</code> | |
</dt> | |
<dd> | |
<p> | |
Returns the hashmap entry for the specified key, or NULL if not found. | |
</p> | |
<div class="paragraph"><p><code>map</code> is the hashmap structure.</p></div> | |
<div class="paragraph"><p><code>key</code> is a hashmap_entry structure (or user data structure that starts with | |
hashmap_entry) that has at least been initialized with the proper hash code | |
(via <code>hashmap_entry_init</code>).</p></div> | |
<div class="paragraph"><p>If an entry with matching hash code is found, <code>key</code> and <code>keydata</code> are passed | |
to <code>hashmap_cmp_fn</code> to decide whether the entry matches the key.</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>void *hashmap_get_from_hash(const struct hashmap *map, unsigned int hash, const void *keydata)</code> | |
</dt> | |
<dd> | |
<p> | |
Returns the hashmap entry for the specified hash code and key data, | |
or NULL if not found. | |
</p> | |
<div class="paragraph"><p><code>map</code> is the hashmap structure.</p></div> | |
<div class="paragraph"><p><code>hash</code> is the hash code of the entry to look up.</p></div> | |
<div class="paragraph"><p>If an entry with matching hash code is found, <code>keydata</code> is passed to | |
<code>hashmap_cmp_fn</code> to decide whether the entry matches the key. The | |
<code>entry_or_key</code> parameter points to a bogus hashmap_entry structure that | |
should not be used in the comparison.</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>void *hashmap_get_next(const struct hashmap *map, const void *entry)</code> | |
</dt> | |
<dd> | |
<p> | |
Returns the next equal hashmap entry, or NULL if not found. This can be | |
used to iterate over duplicate entries (see <code>hashmap_add</code>). | |
</p> | |
<div class="paragraph"><p><code>map</code> is the hashmap structure.</p></div> | |
<div class="paragraph"><p><code>entry</code> is the hashmap_entry to start the search from, obtained via a previous | |
call to <code>hashmap_get</code> or <code>hashmap_get_next</code>.</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>void hashmap_add(struct hashmap *map, void *entry)</code> | |
</dt> | |
<dd> | |
<p> | |
Adds a hashmap entry. This allows to add duplicate entries (i.e. | |
separate values with the same key according to hashmap_cmp_fn). | |
</p> | |
<div class="paragraph"><p><code>map</code> is the hashmap structure.</p></div> | |
<div class="paragraph"><p><code>entry</code> is the entry to add.</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>void *hashmap_put(struct hashmap *map, void *entry)</code> | |
</dt> | |
<dd> | |
<p> | |
Adds or replaces a hashmap entry. If the hashmap contains duplicate | |
entries equal to the specified entry, only one of them will be replaced. | |
</p> | |
<div class="paragraph"><p><code>map</code> is the hashmap structure.</p></div> | |
<div class="paragraph"><p><code>entry</code> is the entry to add or replace.</p></div> | |
<div class="paragraph"><p>Returns the replaced entry, or NULL if not found (i.e. the entry was added).</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)</code> | |
</dt> | |
<dd> | |
<p> | |
Removes a hashmap entry matching the specified key. If the hashmap | |
contains duplicate entries equal to the specified key, only one of | |
them will be removed. | |
</p> | |
<div class="paragraph"><p><code>map</code> is the hashmap structure.</p></div> | |
<div class="paragraph"><p><code>key</code> is a hashmap_entry structure (or user data structure that starts with | |
hashmap_entry) that has at least been initialized with the proper hash code | |
(via <code>hashmap_entry_init</code>).</p></div> | |
<div class="paragraph"><p>If an entry with matching hash code is found, <code>key</code> and <code>keydata</code> are | |
passed to <code>hashmap_cmp_fn</code> to decide whether the entry matches the key.</p></div> | |
<div class="paragraph"><p>Returns the removed entry, or NULL if not found.</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>void hashmap_disallow_rehash(struct hashmap *map, unsigned value)</code> | |
</dt> | |
<dd> | |
<p> | |
Disallow/allow automatic rehashing of the hashmap during inserts | |
and deletes. | |
</p> | |
<div class="paragraph"><p>This is useful if the caller knows that the hashmap will be accessed | |
by multiple threads.</p></div> | |
<div class="paragraph"><p>The caller is still responsible for any necessary locking; this simply | |
prevents unexpected rehashing. The caller is also responsible for properly | |
sizing the initial hashmap to ensure good performance.</p></div> | |
<div class="paragraph"><p>A call to allow rehashing does not force a rehash; that might happen | |
with the next insert or delete.</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)</code> | |
</dt> | |
<dt class="hdlist1"> | |
<code>void *hashmap_iter_next(struct hashmap_iter *iter)</code> | |
</dt> | |
<dt class="hdlist1"> | |
<code>void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)</code> | |
</dt> | |
<dd> | |
<p> | |
Used to iterate over all entries of a hashmap. Note that it is | |
not safe to add or remove entries to the hashmap while | |
iterating. | |
</p> | |
<div class="paragraph"><p><code>hashmap_iter_init</code> initializes a <code>hashmap_iter</code> structure.</p></div> | |
<div class="paragraph"><p><code>hashmap_iter_next</code> returns the next hashmap_entry, or NULL if there are no | |
more entries.</p></div> | |
<div class="paragraph"><p><code>hashmap_iter_first</code> is a combination of both (i.e. initializes the iterator | |
and returns the first entry, if any).</p></div> | |
</dd> | |
<dt class="hdlist1"> | |
<code>const char *strintern(const char *string)</code> | |
</dt> | |
<dt class="hdlist1"> | |
<code>const void *memintern(const void *data, size_t len)</code> | |
</dt> | |
<dd> | |
<p> | |
Returns the unique, interned version of the specified string or data, | |
similar to the <code>String.intern</code> API in Java and .NET, respectively. | |
Interned strings remain valid for the entire lifetime of the process. | |
</p> | |
<div class="paragraph"><p>Can be used as <code>[x]strdup()</code> or <code>xmemdupz</code> replacement, except that interned | |
strings / data must not be modified or freed.</p></div> | |
<div class="paragraph"><p>Interned strings are best used for short strings with high probability of | |
duplicates.</p></div> | |
<div class="paragraph"><p>Uses a hashmap to store the pool of interned strings.</p></div> | |
</dd> | |
</dl></div> | |
</div> | |
</div> | |
<div class="sect1"> | |
<h2 id="_usage_example">Usage example</h2> | |
<div class="sectionbody"> | |
<div class="paragraph"><p>Here’s a simple usage example that maps long keys to double values.</p></div> | |
<div class="listingblock"> | |
<div class="content"> | |
<pre><code>struct hashmap map; | |
struct long2double { | |
struct hashmap_entry ent; /* must be the first member! */ | |
long key; | |
double value; | |
}; | |
static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused) | |
{ | |
return !(e1->key == e2->key); | |
} | |
void long2double_init(void) | |
{ | |
hashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0); | |
} | |
void long2double_free(void) | |
{ | |
hashmap_free(&map, 1); | |
} | |
static struct long2double *find_entry(long key) | |
{ | |
struct long2double k; | |
hashmap_entry_init(&k, memhash(&key, sizeof(long))); | |
k.key = key; | |
return hashmap_get(&map, &k, NULL); | |
} | |
double get_value(long key) | |
{ | |
struct long2double *e = find_entry(key); | |
return e ? e->value : 0; | |
} | |
void set_value(long key, double value) | |
{ | |
struct long2double *e = find_entry(key); | |
if (!e) { | |
e = malloc(sizeof(struct long2double)); | |
hashmap_entry_init(e, memhash(&key, sizeof(long))); | |
e->key = key; | |
hashmap_add(&map, e); | |
} | |
e->value = value; | |
}</code></pre> | |
</div></div> | |
</div> | |
</div> | |
<div class="sect1"> | |
<h2 id="_using_variable_sized_keys">Using variable-sized keys</h2> | |
<div class="sectionbody"> | |
<div class="paragraph"><p>The <code>hashmap_entry_get</code> and <code>hashmap_entry_remove</code> functions expect an ordinary | |
<code>hashmap_entry</code> structure as key to find the correct entry. If the key data is | |
variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable | |
to create a full-fledged entry structure on the heap and copy all the key data | |
into the structure.</p></div> | |
<div class="paragraph"><p>In this case, the <code>keydata</code> parameter can be used to pass | |
variable-sized key data directly to the comparison function, and the <code>key</code> | |
parameter can be a stripped-down, fixed size entry structure allocated on the | |
stack.</p></div> | |
<div class="paragraph"><p>See test-hashmap.c for an example using arbitrary-length strings as keys.</p></div> | |
</div> | |
</div> | |
</div> | |
<div id="footnotes"><hr /></div> | |
<div id="footer"> | |
<div id="footer-text"> | |
Last updated 2017-03-28 15:01:30 PDT | |
</div> | |
</div> | |
</body> | |
</html> |