technical/api-hash.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
   2     "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
   3 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
   4 <head>
   5 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
   6 <meta name="generator" content="AsciiDoc 8.5.2" />
   7 <title>hash API</title>
   8 <style type="text/css">
   9 /* Debug borders */
  10 p, li, dt, dd, div, pre, h1, h2, h3, h4, h5, h6 {
  11 /*
  12   border: 1px solid red;
  13 */
  14 }
  15
  16 body {
  17   margin: 1em 5% 1em 5%;
  18 }
  19
  20 a {
  21   color: blue;
  22   text-decoration: underline;
  23 }
  24 a:visited {
  25   color: fuchsia;
  26 }
  27
  28 em {
  29   font-style: italic;
  30   color: navy;
  31 }
  32
  33 strong {
  34   font-weight: bold;
  35   color: #083194;
  36 }
  37
  38 tt {
  39   color: navy;
  40 }
  41
  42 h1, h2, h3, h4, h5, h6 {
  43   color: #527bbd;
  44   font-family: sans-serif;
  45   margin-top: 1.2em;
  46   margin-bottom: 0.5em;
  47   line-height: 1.3;
  48 }
  49
  50 h1, h2, h3 {
  51   border-bottom: 2px solid silver;
  52 }
  53 h2 {
  54   padding-top: 0.5em;
  55 }
  56 h3 {
  57   float: left;
  58 }
  59 h3 + * {
  60   clear: left;
  61 }
  62
  63 div.sectionbody {
  64   font-family: serif;
  65   margin-left: 0;
  66 }
  67
  68 hr {
  69   border: 1px solid silver;
  70 }
  71
  72 p {
  73   margin-top: 0.5em;
  74   margin-bottom: 0.5em;
  75 }
  76
  77 ul, ol, li > p {
  78   margin-top: 0;
  79 }
  80
  81 pre {
  82   padding: 0;
  83   margin: 0;
  84 }
  85
  86 span#author {
  87   color: #527bbd;
  88   font-family: sans-serif;
  89   font-weight: bold;
  90   font-size: 1.1em;
  91 }
  92 span#email {
  93 }
  94 span#revnumber, span#revdate, span#revremark {
  95   font-family: sans-serif;
  96 }
  97
  98 div#footer {
  99   font-family: sans-serif;
 100   font-size: small;
 101   border-top: 2px solid silver;
 102   padding-top: 0.5em;
 103   margin-top: 4.0em;
 104 }
 105 div#footer-text {
 106   float: left;
 107   padding-bottom: 0.5em;
 108 }
 109 div#footer-badges {
 110   float: right;
 111   padding-bottom: 0.5em;
 112 }
 113
 114 div#preamble {
 115   margin-top: 1.5em;
 116   margin-bottom: 1.5em;
 117 }
 118 div.tableblock, div.imageblock, div.exampleblock, div.verseblock,
 119 div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
 120 div.admonitionblock {
 121   margin-top: 1.0em;
 122   margin-bottom: 1.5em;
 123 }
 124 div.admonitionblock {
 125   margin-top: 2.0em;
 126   margin-bottom: 2.0em;
 127   margin-right: 10%;
 128   color: #606060;
 129 }
 130
 131 div.content { /* Block element content. */
 132   padding: 0;
 133 }
 134
 135 /* Block element titles. */
 136 div.title, caption.title {
 137   color: #527bbd;
 138   font-family: sans-serif;
 139   font-weight: bold;
 140   text-align: left;
 141   margin-top: 1.0em;
 142   margin-bottom: 0.5em;
 143 }
 144 div.title + * {
 145   margin-top: 0;
 146 }
 147
 148 td div.title:first-child {
 149   margin-top: 0.0em;
 150 }
 151 div.content div.title:first-child {
 152   margin-top: 0.0em;
 153 }
 154 div.content + div.title {
 155   margin-top: 0.0em;
 156 }
 157
 158 div.sidebarblock > div.content {
 159   background: #ffffee;
 160   border: 1px solid silver;
 161   padding: 0.5em;
 162 }
 163
 164 div.listingblock > div.content {
 165   border: 1px solid silver;
 166   background: #f4f4f4;
 167   padding: 0.5em;
 168 }
 169
 170 div.quoteblock, div.verseblock {
 171   padding-left: 1.0em;
 172   margin-left: 1.0em;
 173   margin-right: 10%;
 174   border-left: 5px solid #dddddd;
 175   color: #777777;
 176 }
 177
 178 div.quoteblock > div.attribution {
 179   padding-top: 0.5em;
 180   text-align: right;
 181 }
 182
 183 div.verseblock > div.content {
 184   white-space: pre;
 185 }
 186 div.verseblock > div.attribution {
 187   padding-top: 0.75em;
 188   text-align: left;
 189 }
 190 /* DEPRECATED: Pre version 8.2.7 verse style literal block. */
 191 div.verseblock + div.attribution {
 192   text-align: left;
 193 }
 194
 195 div.admonitionblock .icon {
 196   vertical-align: top;
 197   font-size: 1.1em;
 198   font-weight: bold;
 199   text-decoration: underline;
 200   color: #527bbd;
 201   padding-right: 0.5em;
 202 }
 203 div.admonitionblock td.content {
 204   padding-left: 0.5em;
 205   border-left: 3px solid #dddddd;
 206 }
 207
 208 div.exampleblock > div.content {
 209   border-left: 3px solid #dddddd;
 210   padding-left: 0.5em;
 211 }
 212
 213 div.imageblock div.content { padding-left: 0; }
 214 span.image img { border-style: none; }
 215 a.image:visited { color: white; }
 216
 217 dl {
 218   margin-top: 0.8em;
 219   margin-bottom: 0.8em;
 220 }
 221 dt {
 222   margin-top: 0.5em;
 223   margin-bottom: 0;
 224   font-style: normal;
 225   color: navy;
 226 }
 227 dd > *:first-child {
 228   margin-top: 0.1em;
 229 }
 230
 231 ul, ol {
 232     list-style-position: outside;
 233 }
 234 ol.arabic {
 235   list-style-type: decimal;
 236 }
 237 ol.loweralpha {
 238   list-style-type: lower-alpha;
 239 }
 240 ol.upperalpha {
 241   list-style-type: upper-alpha;
 242 }
 243 ol.lowerroman {
 244   list-style-type: lower-roman;
 245 }
 246 ol.upperroman {
 247   list-style-type: upper-roman;
 248 }
 249
 250 div.compact ul, div.compact ol,
 251 div.compact p, div.compact p,
 252 div.compact div, div.compact div {
 253   margin-top: 0.1em;
 254   margin-bottom: 0.1em;
 255 }
 256
 257 div.tableblock > table {
 258   border: 3px solid #527bbd;
 259 }
 260 thead, p.table.header {
 261   font-family: sans-serif;
 262   font-weight: bold;
 263 }
 264 tfoot {
 265   font-weight: bold;
 266 }
 267 td > div.verse {
 268   white-space: pre;
 269 }
 270 p.table {
 271   margin-top: 0;
 272 }
 273 /* Because the table frame attribute is overriden by CSS in most browsers. */
 274 div.tableblock > table[frame="void"] {
 275   border-style: none;
 276 }
 277 div.tableblock > table[frame="hsides"] {
 278   border-left-style: none;
 279   border-right-style: none;
 280 }
 281 div.tableblock > table[frame="vsides"] {
 282   border-top-style: none;
 283   border-bottom-style: none;
 284 }
 285
 286
 287 div.hdlist {
 288   margin-top: 0.8em;
 289   margin-bottom: 0.8em;
 290 }
 291 div.hdlist tr {
 292   padding-bottom: 15px;
 293 }
 294 dt.hdlist1.strong, td.hdlist1.strong {
 295   font-weight: bold;
 296 }
 297 td.hdlist1 {
 298   vertical-align: top;
 299   font-style: normal;
 300   padding-right: 0.8em;
 301   color: navy;
 302 }
 303 td.hdlist2 {
 304   vertical-align: top;
 305 }
 306 div.hdlist.compact tr {
 307   margin: 0;
 308   padding-bottom: 0;
 309 }
 310
 311 .comment {
 312   background: yellow;
 313 }
 314
 315 .footnote, .footnoteref {
 316   font-size: 0.8em;
 317 }
 318
 319 span.footnote, span.footnoteref {
 320   vertical-align: super;
 321 }
 322
 323 #footnotes {
 324   margin: 20px 0 20px 0;
 325   padding: 7px 0 0 0;
 326 }
 327
 328 #footnotes div.footnote {
 329   margin: 0 0 5px 0;
 330 }
 331
 332 #footnotes hr {
 333   border: none;
 334   border-top: 1px solid silver;
 335   height: 1px;
 336   text-align: left;
 337   margin-left: 0;
 338   width: 20%;
 339   min-width: 100px;
 340 }
 341
 342
 343 @media print {
 344   div#footer-badges { display: none; }
 345 }
 346
 347 div#toc {
 348   margin-bottom: 2.5em;
 349 }
 350
 351 div#toctitle {
 352   color: #527bbd;
 353   font-family: sans-serif;
 354   font-size: 1.1em;
 355   font-weight: bold;
 356   margin-top: 1.0em;
 357   margin-bottom: 0.1em;
 358 }
 359
 360 div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 {
 361   margin-top: 0;
 362   margin-bottom: 0;
 363 }
 364 div.toclevel2 {
 365   margin-left: 2em;
 366   font-size: 0.9em;
 367 }
 368 div.toclevel3 {
 369   margin-left: 4em;
 370   font-size: 0.9em;
 371 }
 372 div.toclevel4 {
 373   margin-left: 6em;
 374   font-size: 0.9em;
 375 }
 376 /* Workarounds for IE6's broken and incomplete CSS2. */
 377
 378 div.sidebar-content {
 379   background: #ffffee;
 380   border: 1px solid silver;
 381   padding: 0.5em;
 382 }
 383 div.sidebar-title, div.image-title {
 384   color: #527bbd;
 385   font-family: sans-serif;
 386   font-weight: bold;
 387   margin-top: 0.0em;
 388   margin-bottom: 0.5em;
 389 }
 390
 391 div.listingblock div.content {
 392   border: 1px solid silver;
 393   background: #f4f4f4;
 394   padding: 0.5em;
 395 }
 396
 397 div.quoteblock-attribution {
 398   padding-top: 0.5em;
 399   text-align: right;
 400 }
 401
 402 div.verseblock-content {
 403   white-space: pre;
 404 }
 405 div.verseblock-attribution {
 406   padding-top: 0.75em;
 407   text-align: left;
 408 }
 409
 410 div.exampleblock-content {
 411   border-left: 3px solid #dddddd;
 412   padding-left: 0.5em;
 413 }
 414
 415 /* IE6 sets dynamically generated links as visited. */
 416 div#toc a:visited { color: blue; }
 417 </style>
 418 <script type="text/javascript">
 419 /*<![CDATA[*/
 420 window.onload = function(){asciidoc.footnotes();}
 421 var asciidoc = {  // Namespace.
 422
 423 /////////////////////////////////////////////////////////////////////
 424 // Table Of Contents generator
 425 /////////////////////////////////////////////////////////////////////
 426
 427 /* Author: Mihai Bazon, September 2002
 428  * http://students.infoiasi.ro/~mishoo
 429  *
 430  * Table Of Content generator
 431  * Version: 0.4
 432  *
 433  * Feel free to use this script under the terms of the GNU General Public
 434  * License, as long as you do not remove or alter this notice.
 435  */
 436
 437  /* modified by Troy D. Hanson, September 2006. License: GPL */
 438  /* modified by Stuart Rackham, 2006, 2009. License: GPL */
 439
 440 // toclevels = 1..4.
 441 toc: function (toclevels) {
 442
 443   function getText(el) {
 444     var text = "";
 445     for (var i = el.firstChild; i != null; i = i.nextSibling) {
 446       if (i.nodeType == 3 /* Node.TEXT_NODE */) // IE doesn't speak constants.
 447         text += i.data;
 448       else if (i.firstChild != null)
 449         text += getText(i);
 450     }
 451     return text;
 452   }
 453
 454   function TocEntry(el, text, toclevel) {
 455     this.element = el;
 456     this.text = text;
 457     this.toclevel = toclevel;
 458   }
 459
 460   function tocEntries(el, toclevels) {
 461     var result = new Array;
 462     var re = new RegExp('[hH]([2-'+(toclevels+1)+'])');
 463     // Function that scans the DOM tree for header elements (the DOM2
 464     // nodeIterator API would be a better technique but not supported by all
 465     // browsers).
 466     var iterate = function (el) {
 467       for (var i = el.firstChild; i != null; i = i.nextSibling) {
 468         if (i.nodeType == 1 /* Node.ELEMENT_NODE */) {
 469           var mo = re.exec(i.tagName);
 470           if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") {
 471             result[result.length] = new TocEntry(i, getText(i), mo[1]-1);
 472           }
 473           iterate(i);
 474         }
 475       }
 476     }
 477     iterate(el);
 478     return result;
 479   }
 480
 481   var toc = document.getElementById("toc");
 482   var entries = tocEntries(document.getElementById("content"), toclevels);
 483   for (var i = 0; i < entries.length; ++i) {
 484     var entry = entries[i];
 485     if (entry.element.id == "")
 486       entry.element.id = "_toc_" + i;
 487     var a = document.createElement("a");
 488     a.href = "#" + entry.element.id;
 489     a.appendChild(document.createTextNode(entry.text));
 490     var div = document.createElement("div");
 491     div.appendChild(a);
 492     div.className = "toclevel" + entry.toclevel;
 493     toc.appendChild(div);
 494   }
 495   if (entries.length == 0)
 496     toc.parentNode.removeChild(toc);
 497 },
 498
 499
 500 /////////////////////////////////////////////////////////////////////
 501 // Footnotes generator
 502 /////////////////////////////////////////////////////////////////////
 503
 504 /* Based on footnote generation code from:
 505  * http://www.brandspankingnew.net/archive/2005/07/format_footnote.html
 506  */
 507
 508 footnotes: function () {
 509   var cont = document.getElementById("content");
 510   var noteholder = document.getElementById("footnotes");
 511   var spans = cont.getElementsByTagName("span");
 512   var refs = {};
 513   var n = 0;
 514   for (i=0; i<spans.length; i++) {
 515     if (spans[i].className == "footnote") {
 516       n++;
 517       // Use [\s\S] in place of . so multi-line matches work.
 518       // Because JavaScript has no s (dotall) regex flag.
 519       note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1];
 520       noteholder.innerHTML +=
 521         "<div class='footnote' id='_footnote_" + n + "'>" +
 522         "<a href='#_footnoteref_" + n + "' title='Return to text'>" +
 523         n + "</a>. " + note + "</div>";
 524       spans[i].innerHTML =
 525         "[<a id='_footnoteref_" + n + "' href='#_footnote_" + n +
 526         "' title='View footnote' class='footnote'>" + n + "</a>]";
 527       var id =spans[i].getAttribute("id");
 528       if (id != null) refs["#"+id] = n;
 529     }
 530   }
 531   if (n == 0)
 532     noteholder.parentNode.removeChild(noteholder);
 533   else {
 534     // Process footnoterefs.
 535     for (i=0; i<spans.length; i++) {
 536       if (spans[i].className == "footnoteref") {
 537         var href = spans[i].getElementsByTagName("a")[0].getAttribute("href");
 538         href = href.match(/#.*/)[0];  // Because IE return full URL.
 539         n = refs[href];
 540         spans[i].innerHTML =
 541           "[<a href='#_footnote_" + n +
 542           "' title='View footnote' class='footnote'>" + n + "</a>]";
 543       }
 544     }
 545   }
 546 }
 547
 548 }
 549 /*]]>*/
 550 </script>
 551 </head>
 552 <body>
 553 <div id="header">
 554 <h1>hash API</h1>
 555 </div>
 556 <div id="content">
 557 <div id="preamble">
 558 <div class="sectionbody">
 559 <div class="paragraph"><p>The hash API is a collection of simple hash table functions. Users are expected
 560 to implement their own hashing.</p></div>
 561 </div>
 562 </div>
 563 <h2 id="_data_structures">Data Structures</h2>
 564 <div class="sectionbody">
 565 <div class="dlist"><dl>
 566 <dt class="hdlist1">
 567 <tt>struct hash_table</tt>
 568 </dt>
 569 <dd>
 570 <p>
 571         The hash table structure. The <tt>array</tt> member points to the hash table
 572         entries. The <tt>size</tt> member counts the total number of valid and invalid
 573         entries in the table. The <tt>nr</tt> member keeps track of the number of
 574         valid entries.
 575 </p>
 576 </dd>
 577 <dt class="hdlist1">
 578 <tt>struct hash_table_entry</tt>
 579 </dt>
 580 <dd>
 581 <p>
 582         An opaque structure representing an entry in the hash table. The <tt>hash</tt>
 583         member is the entry&#8217;s hash key and the <tt>ptr</tt> member is the entry&#8217;s
 584         value.
 585 </p>
 586 </dd>
 587 </dl></div>
 588 </div>
 589 <h2 id="_functions">Functions</h2>
 590 <div class="sectionbody">
 591 <div class="dlist"><dl>
 592 <dt class="hdlist1">
 593 <tt>init_hash</tt>
 594 </dt>
 595 <dd>
 596 <p>
 597         Initialize the hash table.
 598 </p>
 599 </dd>
 600 <dt class="hdlist1">
 601 <tt>free_hash</tt>
 602 </dt>
 603 <dd>
 604 <p>
 605         Release memory associated with the hash table.
 606 </p>
 607 </dd>
 608 <dt class="hdlist1">
 609 <tt>insert_hash</tt>
 610 </dt>
 611 <dd>
 612 <p>
 613         Insert a pointer into the hash table. If an entry with that hash
 614         already exists, a pointer to the existing entry&#8217;s value is returned.
 615         Otherwise NULL is returned.  This allows callers to implement
 616         chaining, etc.
 617 </p>
 618 </dd>
 619 <dt class="hdlist1">
 620 <tt>lookup_hash</tt>
 621 </dt>
 622 <dd>
 623 <p>
 624         Lookup an entry in the hash table. If an entry with that hash exists
 625         the entry&#8217;s value is returned. Otherwise NULL is returned.
 626 </p>
 627 </dd>
 628 <dt class="hdlist1">
 629 <tt>for_each_hash</tt>
 630 </dt>
 631 <dd>
 632 <p>
 633         Call a function for each entry in the hash table. The function is
 634         expected to take the entry&#8217;s value as its only argument and return an
 635         int. If the function returns a negative int the loop is aborted
 636         immediately.  Otherwise, the return value is accumulated and the sum
 637         returned upon completion of the loop.
 638 </p>
 639 </dd>
 640 </dl></div>
 641 </div>
 642 </div>
 643 <div id="footnotes"><hr /></div>
 644 <div id="footer">
 645 <div id="footer-text">
 646 Last updated 2011-09-21 23:01:14 PDT
 647 </div>
 648 </div>
 649 </body>
 650 </html>