libcwal  Hex Artifact Content

Artifact fd08be7f499b7e8963a3c206610ef00dfb14a874:

Wiki page [cwal_weak_ref] by stephan 2014-04-13 14:31:42.
0000: 44 20 32 30 31 34 2d 30 34 2d 31 33 54 31 34 3a  D 2014-04-13T14:
0010: 33 31 3a 34 32 2e 36 37 37 0a 4c 20 63 77 61 6c  31:42.677.L cwal
0020: 5f 77 65 61 6b 5f 72 65 66 0a 50 20 33 36 66 37  _weak_ref.P 36f7
0030: 62 66 31 36 66 62 36 35 39 31 61 65 36 39 31 34  bf16fb6591ae6914
0040: 35 31 37 32 65 39 35 66 39 32 38 32 33 64 35 66  5172e95f92823d5f
0050: 37 64 31 33 0a 55 20 73 74 65 70 68 61 6e 0a 57  7d13.U stephan.W
0060: 20 35 36 36 31 0a 3c 68 31 3e 63 77 61 6c 5f 77   5661.<h1>cwal_w
0070: 65 61 6b 5f 72 65 66 3c 2f 68 31 3e 0d 0a 0d 0a  eak_ref</h1>....
0080: 54 68 65 20 3c 74 74 3e 63 77 61 6c 5f 77 65 61  The <tt>cwal_wea
0090: 6b 5f 72 65 66 3c 2f 74 74 3e 20 74 79 70 65 20  k_ref</tt> type 
00a0: 28 68 65 72 65 61 66 74 65 72 20 63 61 6c 6c 65  (hereafter calle
00b0: 64 20 43 57 52 20 6f 72 20 22 77 65 61 6b 20 72  d CWR or "weak r
00c0: 65 66 22 29 20 61 6c 6c 6f 77 73 20 61 20 63 6c  ef") allows a cl
00d0: 69 65 6e 74 20 74 6f 20 74 61 6b 65 20 61 20 22  ient to take a "
00e0: 77 65 61 6b 22 20 72 65 66 65 72 65 6e 63 65 20  weak" reference 
00f0: 74 6f 20 61 20 76 61 6c 75 65 2e 20 54 68 69 73  to a value. This
0100: 20 64 6f 65 73 20 6e 6f 74 20 63 68 61 6e 67 65   does not change
0110: 20 74 68 65 20 72 65 66 65 72 65 6e 63 65 20 63   the reference c
0120: 6f 75 6e 74 20 6f 66 20 74 68 65 20 76 61 6c 75  ount of the valu
0130: 65 2c 20 62 75 74 20 77 68 65 6e 20 74 68 65 20  e, but when the 
0140: 76 61 6c 75 65 20 69 73 20 64 65 73 74 72 6f 79  value is destroy
0150: 65 64 20 28 61 73 20 69 74 20 65 76 65 6e 74 75  ed (as it eventu
0160: 61 6c 6c 79 20 77 69 6c 6c 20 62 65 29 20 74 68  ally will be) th
0170: 65 6e 20 74 68 69 73 20 72 65 66 65 72 65 6e 63  en this referenc
0180: 65 20 69 73 20 69 6e 76 61 6c 69 64 61 74 65 64  e is invalidated
0190: 2c 20 73 75 63 68 20 74 68 61 74 20 74 68 65 20  , such that the 
01a0: 75 73 65 72 20 63 61 6e 20 64 65 74 65 72 6d 69  user can determi
01b0: 6e 65 20 74 68 61 74 20 74 68 65 20 76 61 6c 75  ne that the valu
01c0: 65 20 69 74 20 22 77 65 61 6b 6c 79 22 20 70 6f  e it "weakly" po
01d0: 69 6e 74 73 20 74 6f 20 68 61 73 20 62 65 65 6e  ints to has been
01e0: 20 64 65 73 74 72 6f 79 65 64 2e 20 41 20 73 69   destroyed. A si
01f0: 6d 70 6c 65 20 65 78 61 6d 70 6c 65 3a 0d 0a 0d  mple example:...
0200: 0a 3c 6e 6f 77 69 6b 69 3e 3c 70 72 65 3e 0d 0a  .<nowiki><pre>..
0210: 63 77 61 6c 5f 65 6e 67 69 6e 65 20 2a 20 65 20  cwal_engine * e 
0220: 3d 20 2e 2e 2e 3b 0d 0a 63 77 61 6c 5f 76 61 6c  = ...;..cwal_val
0230: 75 65 20 2a 20 76 20 3d 20 63 77 61 6c 5f 6e 65  ue * v = cwal_ne
0240: 77 5f 69 6e 74 65 67 65 72 28 20 65 2c 20 34 32  w_integer( e, 42
0250: 20 29 3b 0d 0a 63 77 61 6c 5f 77 65 61 6b 5f 72   );..cwal_weak_r
0260: 65 66 20 2a 20 72 20 3d 20 63 77 61 6c 5f 77 65  ef * r = cwal_we
0270: 61 6b 5f 72 65 66 5f 6e 65 77 28 76 29 3b 0d 0a  ak_ref_new(v);..
0280: 61 73 73 65 72 74 28 76 20 3d 3d 20 63 77 61 6c  assert(v == cwal
0290: 5f 77 65 61 6b 5f 72 65 66 5f 76 61 6c 75 65 28  _weak_ref_value(
02a0: 72 29 29 3b 0d 0a 63 77 61 6c 5f 76 61 6c 75 65  r));..cwal_value
02b0: 5f 75 6e 72 65 66 28 76 29 3b 0d 0a 61 73 73 65  _unref(v);..asse
02c0: 72 74 28 21 63 77 61 6c 5f 77 65 61 6b 5f 72 65  rt(!cwal_weak_re
02d0: 66 5f 76 61 6c 75 65 28 72 29 29 3b 0d 0a 2e 2e  f_value(r));....
02e0: 2e 0d 0a 63 77 61 6c 5f 77 65 61 6b 5f 72 65 66  ...cwal_weak_ref
02f0: 5f 66 72 65 65 28 65 2c 20 72 29 3b 0d 0a 3c 2f  _free(e, r);..</
0300: 70 72 65 3e 3c 2f 6e 6f 77 69 6b 69 3e 0d 0a 0d  pre></nowiki>...
0310: 0a 54 68 65 20 69 6d 70 6c 65 6d 65 6e 74 61 74  .The implementat
0320: 69 6f 6e 20 69 6e 76 61 6c 69 64 61 74 65 73 20  ion invalidates 
0330: 61 6c 6c 20 77 65 61 6b 20 72 65 66 65 72 65 6e  all weak referen
0340: 63 65 73 20 74 6f 20 61 20 76 61 6c 75 65 20 61  ces to a value a
0350: 74 20 74 68 65 20 6d 6f 6d 65 6e 74 20 74 68 65  t the moment the
0360: 20 76 61 6c 75 65 20 69 73 20 63 6c 65 61 6e 65   value is cleane
0370: 64 20 75 70 2c 20 61 73 20 6f 70 70 6f 73 65 64  d up, as opposed
0380: 20 74 6f 20 63 68 65 63 6b 69 6e 67 20 22 69 73   to checking "is
0390: 20 74 68 69 73 20 61 64 64 72 65 73 73 20 76 61   this address va
03a0: 6c 69 64 22 20 77 68 65 6e 20 3c 74 74 3e 63 77  lid" when <tt>cw
03b0: 61 6c 5f 77 65 61 6b 5f 72 65 66 5f 76 61 6c 75  al_weak_ref_valu
03c0: 65 28 29 3c 2f 74 74 3e 20 69 73 20 63 61 6c 6c  e()</tt> is call
03d0: 65 64 2e 20 54 68 65 20 6c 61 74 74 65 72 20 77  ed. The latter w
03e0: 6f 75 6c 64 20 68 61 76 65 20 74 68 65 20 73 75  ould have the su
03f0: 62 74 6c 65 20 70 72 6f 62 6c 65 6d 20 74 68 61  btle problem tha
0400: 74 20 72 65 2d 61 6c 6c 6f 63 61 74 69 6e 67 20  t re-allocating 
0410: 76 61 6c 75 65 73 20 61 74 20 74 68 65 20 73 61  values at the sa
0420: 6d 65 20 61 64 64 72 65 73 73 65 73 20 77 6f 75  me addresses wou
0430: 6c 64 20 65 76 65 6e 74 75 61 6c 6c 79 20 6c 65  ld eventually le
0440: 61 64 20 69 74 20 74 6f 20 44 6f 20 54 68 65 20  ad it to Do The 
0450: 57 72 6f 6e 67 20 54 68 69 6e 67 2e 20 54 68 65  Wrong Thing. The
0460: 20 6f 76 65 72 68 65 61 64 20 69 73 20 6d 69 6e   overhead is min
0470: 69 6d 61 6c 2e 20 46 6f 72 20 6e 6f 6e 2d 77 65  imal. For non-we
0480: 61 6b 2d 72 65 66 65 72 65 6e 63 65 64 20 76 61  ak-referenced va
0490: 6c 75 65 73 20 74 68 65 72 65 20 69 73 20 6f 6e  lues there is on
04a0: 65 20 61 64 64 69 74 69 6f 6e 61 6c 20 4f 28 31  e additional O(1
04b0: 29 20 73 65 61 72 63 68 20 6f 70 65 72 61 74 69  ) search operati
04c0: 6f 6e 20 61 74 20 63 6c 65 61 6e 75 70 20 61 6e  on at cleanup an
04d0: 64 20 66 6f 72 20 77 65 61 6b 2d 72 65 66 65 72  d for weak-refer
04e0: 65 6e 63 65 64 20 6f 6e 65 73 20 74 68 65 72 65  enced ones there
04f0: 20 69 73 20 61 6e 20 61 64 64 69 74 69 6f 6e 61   is an additiona
0500: 6c 20 4f 28 4e 29 20 63 6f 73 74 20 28 4e 3d 6e  l O(N) cost (N=n
0510: 75 6d 62 65 72 20 6f 66 20 61 6c 6c 20 77 65 61  umber of all wea
0520: 6b 20 72 65 66 65 72 65 6e 63 65 73 20 74 6f 20  k references to 
0530: 76 61 6c 75 65 73 20 3c 65 6d 3e 6f 66 20 74 68  values <em>of th
0540: 65 20 73 61 6d 65 20 74 79 70 65 3c 2f 65 6d 3e  e same type</em>
0550: 29 2c 20 62 75 74 20 74 68 61 74 20 6f 6e 65 20  ), but that one 
0560: 69 73 20 61 20 66 61 73 74 20 6c 6f 6f 70 2e 0d  is a fast loop..
0570: 0a 0d 0a 54 68 65 20 6d 61 69 6e 20 72 65 61 73  ...The main reas
0580: 6f 6e 20 66 6f 72 20 77 61 6e 74 69 6e 67 20 61  on for wanting a
0590: 20 77 65 61 6b 20 72 65 66 65 72 65 6e 63 65 20   weak reference 
05a0: 69 73 20 77 68 65 6e 20 74 77 6f 20 28 6f 72 20  is when two (or 
05b0: 6d 6f 72 65 29 20 73 63 72 69 70 74 2d 62 6f 75  more) script-bou
05c0: 6e 64 20 6e 61 74 69 76 65 20 76 61 6c 75 65 73  nd native values
05d0: 20 68 61 76 65 20 61 20 6d 75 74 75 61 6c 20 72   have a mutual r
05e0: 65 6c 61 74 69 6f 6e 73 68 69 70 20 61 6e 64 20  elationship and 
05f0: 6e 65 65 64 20 74 6f 20 6b 6e 6f 77 20 69 66 20  need to know if 
0600: 74 68 65 69 72 20 70 61 72 74 6e 65 72 20 69 73  their partner is
0610: 20 76 61 6c 69 64 2e 20 54 68 69 73 20 69 73 20   valid. This is 
0620: 70 61 72 74 69 63 75 6c 61 72 6c 79 20 69 6d 70  particularly imp
0630: 6f 72 74 61 6e 74 20 77 68 65 6e 20 47 43 20 64  ortant when GC d
0640: 65 73 74 72 6f 79 73 20 74 68 65 6d 2c 20 61 73  estroys them, as
0650: 20 47 43 20 6d 61 79 20 64 65 73 74 72 6f 79 20   GC may destroy 
0660: 6f 6e 65 20 73 69 64 65 20 6f 72 20 74 68 65 20  one side or the 
0670: 6f 74 68 65 72 20 6f 66 20 74 68 65 20 70 61 72  other of the par
0680: 74 6e 65 72 73 68 69 70 20 66 69 72 73 74 2e 20  tnership first. 
0690: 54 68 69 73 20 63 61 6e 20 62 65 20 70 72 6f 62  This can be prob
06a0: 6c 65 6d 61 74 69 63 20 77 68 65 6e 20 64 65 61  lematic when dea
06b0: 6c 69 6e 67 20 77 69 74 68 20 70 61 72 65 6e 74  ling with parent
06c0: 2f 63 68 69 6c 64 20 6f 72 20 64 61 74 61 62 61  /child or databa
06d0: 73 65 2f 73 74 61 74 65 6d 65 6e 74 20 72 65 6c  se/statement rel
06e0: 61 74 69 6f 6e 73 68 69 70 73 2c 20 61 6e 64 20  ationships, and 
06f0: 77 65 61 6b 20 72 65 66 65 72 65 6e 63 65 73 20  weak references 
0700: 70 72 6f 76 69 64 65 20 61 20 77 61 79 20 66 6f  provide a way fo
0710: 72 20 6f 6e 65 20 65 6e 64 70 6f 69 6e 74 20 74  r one endpoint t
0720: 6f 20 73 61 66 65 6c 79 20 64 65 74 65 72 6d 69  o safely determi
0730: 6e 65 20 69 66 20 74 68 65 20 6f 74 68 65 72 20  ne if the other 
0740: 65 6e 64 20 69 73 20 73 74 69 6c 6c 20 61 6c 69  end is still ali
0750: 76 65 2e 0d 0a 0d 0a 55 6e 6c 69 6b 65 20 76 61  ve.....Unlike va
0760: 6c 75 65 73 2c 20 77 65 61 6b 20 72 65 66 65 72  lues, weak refer
0770: 65 6e 63 65 73 20 61 72 65 20 6e 6f 74 20 6f 77  ences are not ow
0780: 6e 65 64 20 62 79 20 61 20 73 63 6f 70 65 2e 20  ned by a scope. 
0790: 54 68 65 79 20 61 72 65 20 65 66 66 65 63 74 69  They are effecti
07a0: 76 65 6c 79 20 67 6c 6f 62 61 6c 20 66 6f 72 20  vely global for 
07b0: 61 20 67 69 76 65 6e 20 3c 74 74 3e 63 77 61 6c  a given <tt>cwal
07c0: 5f 65 6e 67 69 6e 65 3c 2f 74 74 3e 20 69 6e 73  _engine</tt> ins
07d0: 74 61 6e 63 65 2e 20 54 68 65 79 20 68 61 76 65  tance. They have
07e0: 20 3c 65 6d 3e 6e 6f 20 65 66 66 65 63 74 3c 2f   <em>no effect</
07f0: 65 6d 3e 20 6f 6e 20 74 68 65 20 6c 69 66 65 74  em> on the lifet
0800: 69 6d 65 73 20 6f 66 20 74 68 65 20 76 61 6c 75  imes of the valu
0810: 65 73 20 74 68 65 79 20 70 6f 69 6e 74 20 74 6f  es they point to
0820: 2c 20 74 68 65 79 20 73 69 6d 70 6c 79 20 61 63  , they simply ac
0830: 74 20 61 73 20 61 20 66 6c 61 67 20 77 68 69 63  t as a flag whic
0840: 68 20 67 65 74 73 20 63 6c 65 61 72 65 64 20 77  h gets cleared w
0850: 68 65 6e 20 74 68 65 20 70 6f 69 6e 74 65 64 2d  hen the pointed-
0860: 74 6f 20 76 61 6c 75 65 20 69 73 20 64 65 73 74  to value is dest
0870: 72 6f 79 65 64 2e 20 49 66 20 61 20 63 6c 69 65  royed. If a clie
0880: 6e 74 20 66 61 69 6c 73 20 74 6f 20 66 72 65 65  nt fails to free
0890: 20 61 20 77 65 61 6b 20 72 65 66 65 72 65 6e 63   a weak referenc
08a0: 65 2c 20 74 68 65 20 65 6e 67 69 6e 65 20 77 69  e, the engine wi
08b0: 6c 6c 20 66 72 65 65 20 69 74 20 77 68 65 6e 20  ll free it when 
08c0: 69 74 20 69 73 20 64 65 73 74 72 6f 79 65 64 2e  it is destroyed.
08d0: 0d 0a 0d 0a 4c 69 6b 65 20 76 61 6c 75 65 73 2c  ....Like values,
08e0: 20 77 65 61 6b 20 72 65 66 65 72 65 6e 63 65 73   weak references
08f0: 20 61 72 65 20 72 65 63 79 63 6c 65 64 20 62 79   are recycled by
0900: 20 64 65 66 61 75 6c 74 20 28 74 68 69 73 20 69   default (this i
0910: 73 20 63 6f 6e 66 69 67 75 72 61 62 6c 65 29 2e  s configurable).
0920: 20 54 68 69 73 20 6d 61 6b 65 73 20 66 72 65 65   This makes free
0930: 69 6e 67 20 61 6e 64 20 72 65 61 6c 6c 6f 63 61  ing and realloca
0940: 74 69 6e 67 20 74 68 65 6d 20 63 68 65 61 70 20  ting them cheap 
0950: 61 6e 64 20 66 61 73 74 2e 0d 0a 0d 0a 54 68 65  and fast.....The
0960: 20 41 50 49 20 73 75 70 70 6f 72 74 73 20 77 65   API supports we
0970: 61 6b 2d 72 65 66 65 72 65 6e 63 69 6e 67 20 61  ak-referencing a
0980: 72 62 69 74 72 61 72 79 20 76 6f 69 64 20 70 6f  rbitrary void po
0990: 69 6e 74 65 72 73 20 74 68 69 73 20 77 61 79 2c  inters this way,
09a0: 20 62 75 74 20 66 6f 72 20 6e 6f 6e 2d 56 61 6c   but for non-Val
09b0: 75 65 20 74 79 70 65 73 20 69 74 20 72 65 71 75  ue types it requ
09c0: 69 72 65 73 20 74 68 61 74 20 63 6c 69 65 6e 74  ires that client
09d0: 73 20 72 65 67 69 73 74 65 72 20 61 6e 64 20 64  s register and d
09e0: 65 72 65 67 69 73 74 65 72 20 77 65 61 6b 2d 72  eregister weak-r
09f0: 65 66 65 72 65 6e 63 65 64 20 6d 65 6d 6f 72 79  eferenced memory
0a00: 20 61 73 20 74 68 61 74 20 6d 65 6d 6f 72 79 20   as that memory 
0a10: 69 74 20 62 65 63 6f 6d 65 73 20 61 76 61 69 6c  it becomes avail
0a20: 61 62 6c 65 20 72 65 73 70 2e 20 75 6e 61 76 61  able resp. unava
0a30: 69 6c 61 62 6c 65 2e 0d 0a 0d 0a 0d 0a 54 4f 44  ilable.......TOD
0a40: 4f 73 3a 0d 0a 0d 0a 20 20 20 2a 20 20 43 6f 6e  Os:....   *  Con
0a50: 73 69 64 65 72 20 61 64 64 69 6e 67 20 61 20 63  sider adding a c
0a60: 77 61 6c 5f 65 6e 67 69 6e 65 20 70 6f 69 6e 74  wal_engine point
0a70: 65 72 20 74 6f 20 74 68 65 20 63 77 61 6c 5f 77  er to the cwal_w
0a80: 65 61 6b 5f 72 65 66 20 74 79 70 65 20 73 6f 20  eak_ref type so 
0a90: 74 68 61 74 20 63 77 61 6c 5f 77 65 61 6b 5f 72  that cwal_weak_r
0aa0: 65 66 5f 66 72 65 65 28 29 20 63 61 6e 20 62 65  ef_free() can be
0ab0: 20 63 61 6c 6c 65 64 20 77 69 74 68 20 6f 6e 65   called with one
0ac0: 20 70 61 72 61 6d 65 74 65 72 2e 0d 0a 0d 0a 0d   parameter......
0ad0: 0a 3c 68 32 3e 48 6f 77 20 57 65 61 6b 20 52 65  .<h2>How Weak Re
0ae0: 66 73 20 61 72 65 20 49 6d 70 6c 65 6d 65 6e 74  fs are Implement
0af0: 65 64 3c 2f 68 32 3e 0d 0a 0d 0a 63 77 61 6c 27  ed</h2>....cwal'
0b00: 73 20 65 6e 67 69 6e 65 20 68 61 73 20 64 61 74  s engine has dat
0b10: 61 20 73 74 72 75 63 74 75 72 65 20 28 3c 74 74  a structure (<tt
0b20: 3e 63 77 61 6c 5f 70 74 72 5f 74 61 62 6c 65 3c  >cwal_ptr_table<
0b30: 2f 74 74 3e 29 20 77 68 69 63 68 20 61 63 74 73  /tt>) which acts
0b40: 20 73 6f 6d 65 77 68 61 74 20 6c 69 6b 65 20 61   somewhat like a
0b50: 20 3c 74 74 3e 73 65 74 3c 2f 74 74 3e 20 66 72   <tt>set</tt> fr
0b60: 6f 6d 20 74 68 65 20 43 2b 2b 20 53 54 4c 2e 20  om the C++ STL. 
0b70: 49 74 20 69 73 20 61 20 68 61 73 68 20 74 61 62  It is a hash tab
0b80: 6c 65 20 77 68 69 63 68 20 63 6f 6e 74 61 69 6e  le which contain
0b90: 73 20 6f 6e 6c 79 20 6b 65 79 73 20 28 77 68 69  s only keys (whi
0ba0: 63 68 20 61 72 65 20 74 68 65 69 72 20 6f 77 6e  ch are their own
0bb0: 20 76 61 6c 75 65 73 29 20 69 6e 20 74 68 65 20   values) in the 
0bc0: 66 6f 72 6d 20 6f 66 20 76 6f 69 64 20 70 6f 69  form of void poi
0bd0: 6e 74 65 72 73 2e 20 54 68 65 20 70 72 69 6d 61  nters. The prima
0be0: 72 79 20 75 73 65 20 6f 66 20 74 68 65 20 73 74  ry use of the st
0bf0: 72 75 63 74 75 72 65 20 69 73 20 74 6f 20 61 6c  ructure is to al
0c00: 6c 6f 77 20 75 73 20 74 6f 20 63 72 65 61 74 65  low us to create
0c10: 20 61 72 62 69 74 72 61 72 79 20 22 6d 65 6d 6f   arbitrary "memo
0c20: 72 79 20 58 20 62 65 6c 6f 6e 67 73 20 74 6f 20  ry X belongs to 
0c30: 63 61 74 65 67 6f 72 79 20 59 22 20 6d 61 70 70  category Y" mapp
0c40: 69 6e 67 73 2e 20 53 74 72 69 6e 67 20 69 6e 74  ings. String int
0c50: 65 72 6e 61 6c 69 7a 61 74 69 6f 6e 20 69 73 20  ernalization is 
0c60: 69 6d 70 6c 65 6d 65 6e 74 65 64 20 74 68 69 73  implemented this
0c70: 20 77 61 79 20 2d 20 77 68 65 6e 20 69 74 20 69   way - when it i
0c80: 73 20 65 6e 61 62 6c 65 64 2c 20 6e 65 77 20 73  s enabled, new s
0c90: 74 72 69 6e 67 73 20 61 72 65 20 61 64 64 65 64  trings are added
0ca0: 20 74 6f 20 74 68 69 73 20 74 61 62 6c 65 2e 20   to this table. 
0cb0: 57 68 65 6e 20 77 65 20 63 72 65 61 74 65 20 61  When we create a
0cc0: 20 73 74 72 69 6e 67 2c 20 77 65 20 63 68 65 63   string, we chec
0cd0: 6b 20 74 68 69 73 20 74 61 62 6c 65 20 74 6f 20  k this table to 
0ce0: 73 65 65 20 69 66 20 77 65 20 68 61 76 65 20 61  see if we have a
0cf0: 20 6d 61 74 63 68 69 6e 67 20 73 74 72 69 6e 67   matching string
0d00: 20 28 74 68 65 20 68 61 73 68 69 6e 67 20 77 6f   (the hashing wo
0d10: 72 6b 73 20 64 69 66 66 65 72 65 6e 74 6c 79 20  rks differently 
0d20: 66 6f 72 20 74 68 69 73 20 70 61 72 74 69 63 75  for this particu
0d30: 6c 61 72 20 74 61 62 6c 65 2c 20 62 75 74 20 74  lar table, but t
0d40: 68 6f 73 65 20 61 72 65 20 62 6f 72 69 6e 67 20  hose are boring 
0d50: 64 65 74 61 69 6c 73 29 2e 20 54 68 65 20 73 74  details). The st
0d60: 72 69 6e 67 20 69 74 73 65 6c 66 20 64 6f 65 73  ring itself does
0d70: 20 6e 6f 74 20 22 6b 6e 6f 77 22 20 74 68 61 74   not "know" that
0d80: 20 69 74 20 69 73 20 69 6e 74 65 72 6e 65 64 2c   it is interned,
0d90: 20 69 2e 65 2e 20 69 74 20 68 61 73 20 6e 6f 20   i.e. it has no 
0da0: 66 6c 61 67 20 77 68 69 63 68 20 69 6e 64 69 63  flag which indic
0db0: 61 74 65 73 20 74 68 61 74 2e 20 49 6e 73 74 65  ates that. Inste
0dc0: 61 64 20 77 65 20 61 64 64 20 74 68 65 20 73 74  ad we add the st
0dd0: 72 69 6e 67 20 28 77 69 74 68 6f 75 74 20 69 74  ring (without it
0de0: 20 22 6b 6e 6f 77 69 6e 67 22 29 20 69 6e 74 6f   "knowing") into
0df0: 20 74 68 65 20 70 6f 69 6e 74 65 72 20 74 61 62   the pointer tab
0e00: 6c 65 2e 20 57 68 65 6e 20 61 20 73 74 72 69 6e  le. When a strin
0e10: 67 20 69 73 20 63 6c 65 61 6e 65 64 20 75 70 2c  g is cleaned up,
0e20: 20 69 74 20 72 65 6d 6f 76 65 73 20 69 74 73 20   it removes its 
0e30: 65 6e 74 72 79 20 28 69 66 20 61 6e 79 29 20 66  entry (if any) f
0e40: 72 6f 6d 20 74 68 65 20 69 6e 74 65 72 6e 69 6e  rom the internin
0e50: 67 20 74 61 62 6c 65 2e 0d 0a 0d 0a 57 65 61 6b  g table.....Weak
0e60: 20 72 65 66 65 72 65 6e 63 65 73 20 61 72 65 20   references are 
0e70: 64 6f 6e 65 20 74 68 65 20 73 61 6d 65 20 77 61  done the same wa
0e80: 79 2e 20 57 65 20 66 69 72 73 74 20 61 64 64 20  y. We first add 
0e90: 61 20 6d 65 6d 6f 72 79 20 61 64 64 72 65 73 73  a memory address
0ea0: 20 28 61 6e 20 61 72 62 69 74 72 61 72 79 20 76   (an arbitrary v
0eb0: 6f 69 64 20 70 6f 69 6e 74 65 72 29 20 69 6e 74  oid pointer) int
0ec0: 6f 20 74 68 65 20 74 61 62 6c 65 2e 20 54 68 65  o the table. The
0ed0: 6e 20 77 65 20 63 72 65 61 74 65 20 61 20 77 65  n we create a we
0ee0: 61 6b 20 72 65 66 65 72 65 6e 63 65 20 77 68 69  ak reference whi
0ef0: 63 68 20 77 72 61 70 73 20 74 68 61 74 20 61 64  ch wraps that ad
0f00: 64 72 65 73 73 2e 20 57 68 65 6e 20 74 68 65 20  dress. When the 
0f10: 65 6e 67 69 6e 65 20 63 6c 65 61 6e 73 20 75 70  engine cleans up
0f20: 20 74 68 61 74 20 6d 65 6d 6f 72 79 2c 20 69 74   that memory, it
0f30: 20 72 65 6d 6f 76 65 73 20 74 68 61 74 20 65 6e   removes that en
0f40: 74 72 79 20 66 72 6f 6d 20 74 68 65 20 77 65 61  try from the wea
0f50: 6b 20 72 65 66 65 72 65 6e 63 65 20 74 61 62 6c  k reference tabl
0f60: 65 2e 20 54 68 61 74 20 70 72 6f 63 65 73 73 20  e. That process 
0f70: 74 68 65 6e 20 77 61 6c 6b 73 20 74 68 72 6f 75  then walks throu
0f80: 67 68 20 74 68 65 20 61 63 74 69 76 65 20 77 65  gh the active we
0f90: 61 6b 20 72 65 66 65 72 65 6e 63 65 73 20 61 6e  ak references an
0fa0: 64 20 63 6c 65 61 72 73 20 6f 75 74 20 61 6e 79  d clears out any
0fb0: 20 77 68 69 63 68 20 70 6f 69 6e 74 20 74 6f 20   which point to 
0fc0: 74 68 61 74 20 6d 65 6d 6f 72 79 2e 20 4c 69 76  that memory. Liv
0fd0: 65 20 77 65 61 6b 20 72 65 66 65 72 65 6e 63 65  e weak reference
0fe0: 73 20 61 72 65 20 67 72 6f 75 70 65 64 20 62 79  s are grouped by
0ff0: 20 6d 65 6d 6f 72 79 20 74 79 70 65 20 28 69 6e   memory type (in
1000: 74 65 67 65 72 2c 20 6f 62 6a 65 63 74 2c 20 65  teger, object, e
1010: 74 63 2e 29 20 73 6f 20 74 68 65 20 6c 69 73 74  tc.) so the list
1020: 20 6f 66 20 77 65 61 6b 20 72 65 66 73 20 77 68   of weak refs wh
1030: 69 63 68 20 6e 65 65 64 73 20 74 6f 20 62 65 20  ich needs to be 
1040: 63 68 65 63 6b 65 64 2f 69 6e 76 61 6c 69 64 61  checked/invalida
1050: 74 65 64 20 66 6f 72 20 61 6e 79 20 67 69 76 65  ted for any give
1060: 6e 20 72 65 6d 6f 76 61 6c 20 69 73 20 6c 69 6d  n removal is lim
1070: 69 74 65 64 20 74 6f 20 74 68 65 20 6e 75 6d 62  ited to the numb
1080: 65 72 20 6f 66 20 77 65 61 6b 20 72 65 66 65 72  er of weak refer
1090: 65 6e 63 65 73 20 74 6f 20 76 61 6c 75 65 73 20  ences to values 
10a0: 6f 66 20 74 68 65 20 73 61 6d 65 20 62 61 73 65  of the same base
10b0: 20 74 79 70 65 2e 20 49 74 20 22 69 73 20 6e 6f   type. It "is no
10c0: 74 20 65 78 70 65 63 74 65 64 22 20 61 70 70 6c  t expected" appl
10d0: 69 63 61 74 69 6f 6e 73 20 77 69 6c 6c 20 6e 65  ications will ne
10e0: 65 64 20 6d 6f 72 65 20 74 68 61 6e 20 61 20 66  ed more than a f
10f0: 65 77 20 77 65 61 6b 20 72 65 66 65 72 65 6e 63  ew weak referenc
1100: 65 73 20 28 69 66 20 61 6e 79 20 2d 20 6d 6f 73  es (if any - mos
1110: 74 20 61 70 70 73 20 77 6f 6e 27 74 20 6e 65 65  t apps won't nee
1120: 64 20 74 68 65 6d 20 61 74 20 61 6c 6c 29 2e 0d  d them at all)..
1130: 0a 0d 0a 54 68 65 20 70 6f 69 6e 74 65 72 20 74  ...The pointer t
1140: 61 62 6c 65 20 69 74 73 65 6c 66 20 69 73 20 73  able itself is s
1150: 74 72 75 63 74 75 72 65 64 20 6d 75 63 68 20 64  tructured much d
1160: 69 66 66 65 72 65 6e 74 6c 79 20 66 72 6f 6d 20  ifferently from 
1170: 61 20 6e 6f 72 6d 61 6c 20 68 61 73 68 20 74 61  a normal hash ta
1180: 62 6c 65 2e 20 49 6e 73 74 65 61 64 20 6f 66 20  ble. Instead of 
1190: 61 6c 6c 6f 63 61 74 69 6e 67 20 6f 6e 65 20 68  allocating one h
11a0: 61 73 68 20 65 6e 74 72 79 20 70 65 72 20 6b 65  ash entry per ke
11b0: 79 2f 76 61 6c 75 65 2c 20 69 74 20 63 72 65 61  y/value, it crea
11c0: 74 65 73 20 70 61 67 65 73 20 6f 66 20 70 6f 69  tes pages of poi
11d0: 6e 74 65 72 73 20 28 74 68 65 20 70 61 67 65 20  nters (the page 
11e0: 73 69 7a 65 20 65 71 75 61 6c 73 20 74 68 65 20  size equals the 
11f0: 63 6f 6e 76 65 6e 74 69 6f 6e 61 6c 20 68 61 73  conventional has
1200: 68 20 74 61 62 6c 65 20 73 69 7a 65 29 2e 20 53  h table size). S
1210: 6f 20 69 66 20 74 68 65 20 74 61 62 6c 65 20 68  o if the table h
1220: 61 73 20 61 20 68 61 73 68 20 73 69 7a 65 20 6f  as a hash size o
1230: 66 20 32 37 2c 20 69 74 20 63 72 65 61 74 65 73  f 27, it creates
1240: 20 70 61 67 65 73 20 62 69 67 20 65 6e 6f 75 67   pages big enoug
1250: 68 20 66 6f 72 20 32 37 20 76 6f 69 64 20 70 6f  h for 27 void po
1260: 69 6e 74 65 72 73 2e 20 45 61 63 68 20 74 69 6d  inters. Each tim
1270: 65 20 74 68 65 72 65 20 69 73 20 61 20 63 6f 6c  e there is a col
1280: 6c 69 73 69 6f 6e 20 77 68 69 63 68 20 73 70 61  lision which spa
1290: 6e 73 20 61 6c 6c 20 63 75 72 72 65 6e 74 20 70  ns all current p
12a0: 61 67 65 73 2c 20 69 74 20 61 64 64 73 20 61 20  ages, it adds a 
12b0: 6e 65 77 20 70 61 67 65 2e 20 54 68 65 20 68 61  new page. The ha
12c0: 73 68 69 6e 67 20 61 6c 67 6f 72 69 74 68 6d 2c  shing algorithm,
12d0: 20 62 61 73 65 64 20 6f 6e 20 74 68 65 20 61 64   based on the ad
12e0: 64 72 65 73 73 20 6f 66 20 74 68 65 20 65 6e 74  dress of the ent
12f0: 72 69 65 73 2c 20 70 65 72 66 6f 72 6d 73 20 71  ries, performs q
1300: 75 69 74 65 20 77 65 6c 6c 20 69 6e 20 74 65 72  uite well in ter
1310: 6d 73 20 6f 66 20 74 68 65 20 6e 75 6d 62 65 72  ms of the number
1320: 20 65 6e 74 72 69 65 73 20 69 74 20 77 69 6c 6c   entries it will
1330: 20 66 69 74 20 6f 6e 20 61 20 70 61 67 65 20 62   fit on a page b
1340: 65 66 6f 72 65 20 69 74 20 68 61 73 20 61 20 63  efore it has a c
1350: 6f 6c 6c 69 73 69 6f 6e 20 61 6e 64 20 68 61 73  ollision and has
1360: 20 74 6f 20 61 64 64 20 61 20 6e 65 77 20 70 61   to add a new pa
1370: 67 65 2e 20 69 27 76 65 20 73 65 65 6e 2c 20 69  ge. i've seen, i
1380: 6e 20 73 6f 6d 65 20 74 65 73 74 73 2c 20 68 69  n some tests, hi
1390: 74 20 72 61 74 65 73 20 6f 66 20 39 30 25 20 69  t rates of 90% i
13a0: 6e 20 74 68 65 20 66 69 72 73 74 20 70 61 67 65  n the first page
13b0: 20 61 6e 64 20 39 39 25 20 69 6e 20 74 68 65 20   and 99% in the 
13c0: 73 65 63 6f 6e 64 20 66 6f 72 20 63 65 72 74 61  second for certa
13d0: 69 6e 20 63 6f 6d 62 69 6e 61 74 69 6f 6e 73 20  in combinations 
13e0: 6f 66 20 74 61 62 6c 65 20 73 69 7a 65 73 20 61  of table sizes a
13f0: 6e 64 20 6e 75 6d 62 65 72 73 20 6f 66 20 65 6e  nd numbers of en
1400: 74 72 69 65 73 2c 20 62 75 74 20 69 20 73 75 73  tries, but i sus
1410: 70 65 63 74 20 74 68 6f 73 65 20 77 65 72 65 20  pect those were 
1420: 66 61 69 72 6c 79 20 69 64 65 61 6c 20 63 6f 6e  fairly ideal con
1430: 64 69 74 69 6f 6e 73 2e 20 49 6e 20 61 6e 79 20  ditions. In any 
1440: 63 61 73 65 2c 20 74 68 65 20 61 70 70 72 6f 61  case, the approa
1450: 63 68 20 6f 66 20 61 6c 6c 6f 63 61 74 69 6e 67  ch of allocating
1460: 20 77 68 6f 6c 65 20 70 61 67 65 73 20 65 6e 64   whole pages end
1470: 73 20 75 70 20 63 6f 73 74 69 6e 67 20 6c 65 73  s up costing les
1480: 73 20 6d 65 6d 6f 72 79 2c 20 63 6f 6d 70 61 72  s memory, compar
1490: 65 64 20 74 6f 20 61 6c 6c 6f 63 61 74 69 6e 67  ed to allocating
14a0: 20 69 6e 64 69 76 69 64 75 61 6c 20 68 61 73 68   individual hash
14b0: 20 74 61 62 6c 65 20 65 6e 74 72 69 65 73 2c 20   table entries, 
14c0: 6f 6e 63 65 20 61 20 74 61 62 6c 65 20 69 73 20  once a table is 
14d0: 61 62 6f 75 74 20 31 2f 33 72 64 20 66 75 6c 6c  about 1/3rd full
14e0: 20 62 65 63 61 75 73 65 20 74 68 65 20 6d 65 6d   because the mem
14f0: 6f 72 79 20 6f 76 65 72 68 65 61 64 20 6f 66 20  ory overhead of 
1500: 61 6c 6c 6f 63 61 74 69 6e 67 20 69 6e 64 69 76  allocating indiv
1510: 69 64 75 61 6c 20 68 61 73 68 20 74 61 62 6c 65  idual hash table
1520: 20 65 6e 74 72 69 65 73 20 69 73 20 73 6f 20 68   entries is so h
1530: 69 67 68 2e 20 41 6c 6c 6f 63 61 74 69 6e 67 20  igh. Allocating 
1540: 77 68 6f 6c 65 20 70 61 67 65 73 20 61 6c 73 6f  whole pages also
1550: 20 6c 65 61 64 73 20 74 6f 20 6d 61 6e 79 20 66   leads to many f
1560: 65 77 65 72 20 74 6f 74 61 6c 20 61 6c 6c 6f 63  ewer total alloc
1570: 61 74 69 6f 6e 73 20 63 6f 6d 70 61 72 65 64 20  ations compared 
1580: 74 6f 20 63 6f 6e 76 65 6e 74 69 6f 6e 61 6c 20  to conventional 
1590: 68 61 73 68 20 74 61 62 6c 65 73 2e 20 49 6e 20  hash tables. In 
15a0: 74 65 73 74 69 6e 67 20 75 73 69 6e 67 20 6c 6f  testing using lo
15b0: 74 73 20 6f 66 20 70 73 65 75 64 6f 2d 72 61 6e  ts of pseudo-ran
15c0: 64 6f 6d 20 73 74 72 69 6e 67 73 2c 20 69 20 68  dom strings, i h
15d0: 61 76 65 20 6e 65 76 65 72 20 73 65 65 6e 20 6d  ave never seen m
15e0: 6f 72 65 20 74 68 61 6e 20 37 20 6f 72 20 38 20  ore than 7 or 8 
15f0: 70 61 67 65 73 20 61 74 20 61 20 74 69 6d 65 2c  pages at a time,
1600: 20 62 75 74 20 69 6e 20 74 68 65 20 22 6d 69 64   but in the "mid
1610: 2d 73 69 7a 65 64 20 73 63 72 69 70 74 73 22 20  -sized scripts" 
1620: 69 27 76 65 20 63 68 65 63 6b 65 64 2c 20 32 2d  i've checked, 2-
1630: 33 20 69 6e 74 65 72 6e 69 6e 67 20 70 61 67 65  3 interning page
1640: 73 20 73 65 65 6d 73 20 74 6f 20 62 65 20 74 68  s seems to be th
1650: 65 20 6e 6f 72 6d 2e 20 46 6f 72 20 73 6d 61 6c  e norm. For smal
1660: 6c 20 73 63 72 69 70 74 73 2c 20 31 2d 32 20 70  l scripts, 1-2 p
1670: 61 67 65 73 20 69 73 20 74 68 65 20 6e 6f 72 6d  ages is the norm
1680: 2e 0d 0a 0a 5a 20 61 62 36 61 32 35 65 39 36 65  ....Z ab6a25e96e
1690: 34 36 63 62 61 34 62 38 33 38 61 61 33 39 33 63  46cba4b838aa393c
16a0: 34 30 34 37 31 30 0a                             404710.