"Fossies" - the Fresh Open Source Software Archive

Member "perl-5.30.0/ext/SDBM_File/README" (27 Jun 2018, 11429 Bytes) of package /linux/misc/perl-5.30.0.tar.xz:


As a special service "Fossies" has tried to format the requested text file into HTML format (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    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         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