home *** CD-ROM | disk | FTP | other *** search
/ OpenStep 4.2J (Developer) / os42jdev.iso / NextDeveloper / Source / GNU / perl / Perl / ext / SDBM_File / sdbm / README < prev    next >
Encoding:
Text File  |  1994-10-18  |  11.2 KB  |  397 lines

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.                    sdbm - Substitute DBM
  8.                              or
  9.         Berkeley ndbm for Every UN*X[1] Made Simple
  10.  
  11.                       Ozan (oz) Yigit
  12.  
  13.             The Guild of PD Software Toolmakers
  14.                       Toronto - Canada
  15.  
  16.                      oz@nexus.yorku.ca
  17.  
  18.  
  19.  
  20. Implementation is the sincerest form of flattery. - L. Peter
  21. Deutsch
  22.  
  23. A The Clone of the ndbm library
  24.  
  25.      The sources accompanying this notice - sdbm  -  consti-
  26. tute  the  first  public  release  (Dec. 1990) of a complete
  27. clone of the Berkeley UN*X ndbm library. The sdbm library is
  28. meant  to  clone the proven functionality of ndbm as closely
  29. as possible, including a few improvements. It is  practical,
  30. easy to understand, and compatible.  The sdbm library is not
  31. derived  from  any  licensed,  proprietary  or   copyrighted
  32. software.
  33.  
  34.      The sdbm implementation is based on  a  1978  algorithm
  35. [Lar78] by P.-A. (Paul) Larson known as ``Dynamic Hashing''.
  36. In the course of searching for a substitute for ndbm, I pro-
  37. totyped  three different external-hashing algorithms [Lar78,
  38. Fag79, Lit80] and ultimately chose Larson's algorithm  as  a
  39. basis  of  the  sdbm  implementation. The Bell Labs dbm (and
  40. therefore ndbm) is based on an  algorithm  invented  by  Ken
  41. Thompson, [Tho90, Tor87] and predates Larson's work.
  42.  
  43.      The sdbm programming interface  is  totally  compatible
  44. with ndbm and includes a slight improvement in database ini-
  45. tialization.  It is also expected  to  be  binary-compatible
  46. under most UN*X versions that support the ndbm library.
  47.  
  48.      The sdbm implementation shares the shortcomings of  the
  49. ndbm library, as a side effect of various simplifications to
  50. the original Larson algorithm. It does produce holes in  the
  51. page file as it writes pages past the end of file. (Larson's
  52. paper include a clever solution to this problem  that  is  a
  53. result of using the hash value directly as a block address.)
  54. On the other hand, extensive tests  seem  to  indicate  that
  55. sdbm creates fewer holes in general, and the resulting page-
  56. files are smaller. The sdbm implementation  is  also  faster
  57. than  ndbm  in database creation.  Unlike the ndbm, the sdbm
  58. _________________________
  59.  
  60.   [1] UN*X is not a trademark of any (dis)organization.
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.                            - 2 -
  71.  
  72.  
  73. store operation will not ``wander away'' trying to split its
  74. data  pages  to insert a datum that cannot (due to elaborate
  75. worst-case situations) be inserted. (It will  fail  after  a
  76. pre-defined number of attempts.)
  77.  
  78. Important Compatibility Warning
  79.  
  80.      The sdbm and ndbm libraries cannot share databases: one
  81. cannot  read  the  (dir/pag)  database created by the other.
  82. This is due to the differences between  the  ndbm  and  sdbm
  83. algorithms[2], and the hash functions used.  It is  easy  to
  84. convert  between the dbm/ndbm databases and sdbm by ignoring
  85. the index completely: see dbd, dbu etc.
  86.  
  87.  
  88. Notice of Intellectual Property
  89.  
  90. The entire sdbm  library package, as authored by me, Ozan S.
  91. Yigit,  is  hereby placed in the public domain. As such, the
  92. author is not responsible for the  consequences  of  use  of
  93. this  software, no matter how awful, even if they arise from
  94. defects in it. There is no expressed or implied warranty for
  95. the sdbm library.
  96.  
  97.      Since the sdbm library package is in the public domain,
  98. this   original  release  or  any  additional  public-domain
  99. releases of the modified original cannot possibly (by defin-
  100. ition) be withheld from you. Also by definition, You (singu-
  101. lar) have all the rights to this code (including  the  right
  102. to sell without permission, the right to  hoard[3]  and  the
  103. right  to  do  other  icky  things as you see fit) but those
  104. rights are also granted to everyone else.
  105.  
  106.      Please note that all  previous  distributions  of  this
  107. software  contained  a  copyright  (which is now dropped) to
  108. protect its origins and its  current  public  domain  status
  109. against any possible claims and/or challenges.
  110.  
  111. Acknowledgments
  112.  
  113.      Many people have been very helpful and  supportive.   A
  114. partial  list  would  necessarily  include Rayan Zacherissen
  115. (who contributed the  man  page,  and  also  hacked  a  MMAP
  116. _________________________
  117.  
  118.   [2] Torek's   discussion   [Tor87]   indicates   that
  119. dbm/ndbm implementations use the hash value to traverse
  120. the radix trie differently than sdbm and as  a  result,
  121. the page indexes are generated in different order.  For
  122. more information, send e-mail to the author.
  123.   [3] You  cannot really hoard something that is avail-
  124. able to the public at large, but try if  it  makes  you
  125. feel any better.
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.                            - 3 -
  137.  
  138.  
  139. version of sdbm), Arnold Robbins, Chris Lewis,  Bill  David-
  140. sen,  Henry  Spencer,  Geoff  Collyer, Rich Salz (who got me
  141. started in the first place), Johannes Ruschein (who did  the
  142. minix port) and David Tilbrook. I thank you all.
  143.  
  144. Distribution Manifest and Notes
  145.  
  146. This distribution of sdbm includes (at least) the following:
  147.  
  148.     CHANGES     change log
  149.     README      this file.
  150.     biblio      a small bibliography on external hashing
  151.     dba.c       a crude (n/s)dbm page file analyzer
  152.     dbd.c       a crude (n/s)dbm page file dumper (for conversion)
  153.     dbe.1       man page for dbe.c
  154.     dbe.c       Janick's database editor
  155.     dbm.c       a dbm library emulation wrapper for ndbm/sdbm
  156.     dbm.h       header file for the above
  157.     dbu.c       a crude db management utility
  158.     hash.c      hashing function
  159.     makefile    guess.
  160.     pair.c      page-level routines (posted earlier)
  161.     pair.h      header file for the above
  162.     readme.ms   troff source for the README file
  163.     sdbm.3      man page
  164.     sdbm.c      the real thing
  165.     sdbm.h      header file for the above
  166.     tune.h      place for tuning & portability thingies
  167.     util.c      miscellaneous
  168.  
  169.      dbu is a simple database manipulation  program[4]  that
  170. tries to look like Bell Labs' cbt utility. It  is  currently
  171. incomplete in functionality.  I use dbu to test out the rou-
  172. tines: it takes (from stdin) tab separated  key/value  pairs
  173. for commands like build or insert or takes keys for commands
  174. like delete or look.
  175.  
  176.     dbu <build|creat|look|insert|cat|delete> dbmfile
  177.  
  178.      dba is a crude analyzer of dbm/sdbm/ndbm page files. It
  179. scans the entire page file, reporting page level statistics,
  180. and totals at the end.
  181.  
  182.      dbd is a crude dump  program  for  dbm/ndbm/sdbm  data-
  183. bases.  It  ignores  the bitmap, and dumps the data pages in
  184. sequence. It can be used to create input for the  dbu  util-
  185. ity.   Note that dbd will skip any NULLs in the key and data
  186. fields,  thus  is  unsuitable  to  convert   some   peculiar
  187. _________________________
  188.  
  189.   [4] The dbd, dba, dbu utilities are quick  hacks  and
  190. are  not  fit  for  production use. They were developed
  191. late one night, just to test out sdbm, and convert some
  192. databases.
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.                            - 4 -
  203.  
  204.  
  205. databases that insist in including the terminating null.
  206.  
  207.      I have also included a copy of the dbe  (ndbm  DataBase
  208. Editor)  by  Janick Bergeron [janick@bnr.ca] for your pleas-
  209. ure. You may find it more useful than the little  dbu  util-
  210. ity.
  211.  
  212.      dbm.[ch] is a dbm library emulation on top of ndbm (and
  213. hence suitable for sdbm). Written by Robert Elz.
  214.  
  215.      The sdbm library has been around in beta test for quite
  216. a  long  time,  and from whatever little feedback I received
  217. (maybe no news is good news), I believe it  has  been  func-
  218. tioning  without  any  significant  problems.  I  would,  of
  219. course, appreciate all fixes and/or improvements.  Portabil-
  220. ity enhancements would especially be useful.
  221.  
  222. Implementation Issues
  223.  
  224.      Hash functions: The algorithm behind  sdbm  implementa-
  225. tion  needs a good bit-scrambling hash function to be effec-
  226. tive. I ran into a set of constants for a simple hash  func-
  227. tion  that  seem  to  help sdbm perform better than ndbm for
  228. various inputs:
  229.  
  230.     /*
  231.      * polynomial conversion ignoring overflows
  232.      * 65599 nice. 65587 even better.
  233.      */
  234.     long
  235.     dbm_hash(char *str, int len) {
  236.         register unsigned long n = 0;
  237.  
  238.         while (len--)
  239.             n = n * 65599 + *str++;
  240.         return n;
  241.     }
  242.  
  243.      There may be better hash functions for the purposes  of
  244. dynamic hashing.  Try your favorite, and check the pagefile.
  245. If it contains too many pages with too many holes, (in rela-
  246. tion  to this one for example) or if sdbm simply stops work-
  247. ing (fails after SPLTMAX attempts to split)  when  you  feed
  248. your  NEWS  history  file  to it, you probably do not have a
  249. good hashing function.  If  you  do  better  (for  different
  250. types of input), I would like to know about the function you
  251. use.
  252.  
  253.      Block sizes: It seems (from  various  tests  on  a  few
  254. machines)  that a page file block size PBLKSIZ of 1024 is by
  255. far the best for performance, but this also happens to limit
  256. the  size  of a key/value pair. Depending on your needs, you
  257. may wish to increase the page size, and also adjust  PAIRMAX
  258. (the maximum size of a key/value pair allowed: should always
  259.  
  260.  
  261.  
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268.                            - 5 -
  269.  
  270.  
  271. be at least three words smaller than PBLKSIZ.)  accordingly.
  272. The  system-wide  version  of the library should probably be
  273. configured with 1024 (distribution default), as this appears
  274. to be sufficient for most common uses of sdbm.
  275.  
  276. Portability
  277.  
  278.      This package has been tested in many  different  UN*Xes
  279. even including minix, and appears to be reasonably portable.
  280. This does not mean it will port easily to non-UN*X systems.
  281.  
  282. Notes and Miscellaneous
  283.  
  284.      The sdbm is not a very complicated  package,  at  least
  285. not  after  you  familiarize yourself with the literature on
  286. external hashing. There are other interesting algorithms  in
  287. existence  that ensure (approximately) single-read access to
  288. a data value associated with any key. These  are  directory-
  289. less schemes such as linear hashing [Lit80] (+ Larson varia-
  290. tions), spiral storage [Mar79] or directory schemes such  as
  291. extensible  hashing  [Fag79] by Fagin et al. I do hope these
  292. sources provide a reasonable playground for  experimentation
  293. with  other algorithms.  See the June 1988 issue of ACM Com-
  294. puting Surveys [Enb88] for  an  excellent  overview  of  the
  295. field.
  296.  
  297. References
  298.  
  299.  
  300. [Lar78]
  301.     P.-A. Larson, ``Dynamic Hashing'', BIT, vol.   18,   pp.
  302.     184-201, 1978.
  303.  
  304. [Tho90]
  305.     Ken Thompson, private communication, Nov. 1990
  306.  
  307. [Lit80]
  308.     W. Litwin, `` Linear Hashing: A new tool  for  file  and
  309.     table addressing'', Proceedings of the 6th Conference on
  310.     Very Large  Dabatases  (Montreal), pp.   212-223,   Very
  311.     Large Database Foundation, Saratoga, Calif., 1980.
  312.  
  313. [Fag79]
  314.     R. Fagin, J.  Nievergelt,  N.  Pippinger,  and   H.   R.
  315.     Strong,  ``Extendible Hashing - A Fast Access Method for
  316.     Dynamic Files'', ACM  Trans.  Database  Syst.,  vol.  4,
  317.     no.3, pp. 315-344, Sept. 1979.
  318.  
  319. [Wal84]
  320.     Rich Wales, ``Discussion of "dbm"  data  base  system'',
  321.     USENET newsgroup unix.wizards, Jan. 1984.
  322.  
  323. [Tor87]
  324.     Chris Torek,  ``Re:   dbm.a   and   ndbm.a   archives'',
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.  
  332.  
  333.  
  334.                            - 6 -
  335.  
  336.  
  337.     USENET newsgroup comp.unix, 1987.
  338.  
  339. [Mar79]
  340.     G. N. Martin, ``Spiral Storage: Incrementally   Augment-
  341.     able   Hash  Addressed  Storage'', Technical Report #27,
  342.     University of Varwick, Coventry, U.K., 1979.
  343.  
  344. [Enb88]
  345.     R.  J.  Enbody  and  H.   C.   Du,   ``Dynamic   Hashing
  346.     Schemes'',ACM  Computing  Surveys,  vol.  20, no. 2, pp.
  347.     85-113, June 1988.
  348.  
  349.  
  350.  
  351.  
  352.  
  353.  
  354.  
  355.  
  356.  
  357.  
  358.  
  359.  
  360.  
  361.  
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368.  
  369.  
  370.  
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377.  
  378.  
  379.  
  380.  
  381.  
  382.  
  383.  
  384.  
  385.  
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394.  
  395.  
  396.  
  397.