Mercurial > hg > xemacs-beta
comparison src/elhash.c @ 504:bcda0b3445a6
[xemacs-hg @ 2001-05-05 08:19:18 by martinb]
add Ben comment
| author | martinb |
|---|---|
| date | Sat, 05 May 2001 08:19:18 +0000 |
| parents | 11b53bb7daf5 |
| children | 183866b06e0b |
comparison
equal
deleted
inserted
replaced
| 503:98fb34b6fbe9 | 504:bcda0b3445a6 |
|---|---|
| 21 Boston, MA 02111-1307, USA. */ | 21 Boston, MA 02111-1307, USA. */ |
| 22 | 22 |
| 23 /* Synched up with: Not in FSF. */ | 23 /* Synched up with: Not in FSF. */ |
| 24 | 24 |
| 25 /* This file implements the hash table lisp object type. | 25 /* This file implements the hash table lisp object type. |
| 26 | |
| 27 This implementation was mostly written by Martin Buchholz in 1997. | |
| 28 | |
| 29 The Lisp-level API (derived from Common Lisp) is almost completely | |
| 30 compatible with GNU Emacs 21, even though the implementations are | |
| 31 totally independent. | |
| 26 | 32 |
| 27 The hash table technique used is "linear probing". Collisions are | 33 The hash table technique used is "linear probing". Collisions are |
| 28 resolved by putting the item in the next empty place in the array | 34 resolved by putting the item in the next empty place in the array |
| 29 following the collision. Finding a hash entry performs a linear | 35 following the collision. Finding a hash entry performs a linear |
| 30 search in the cluster starting at the hash value. | 36 search in the cluster starting at the hash value. |
| 1231 function in perl has this limitation. | 1237 function in perl has this limitation. |
| 1232 | 1238 |
| 1233 Note: We GCPRO memory on the heap, not on the stack. There is no | 1239 Note: We GCPRO memory on the heap, not on the stack. There is no |
| 1234 obvious reason why this is bad, but as of this writing this is the | 1240 obvious reason why this is bad, but as of this writing this is the |
| 1235 only known occurrence of this technique in the code. | 1241 only known occurrence of this technique in the code. |
| 1242 | |
| 1243 -- Martin | |
| 1244 */ | |
| 1245 | |
| 1246 /* Ben disagrees with the "copying hentries" design, and says: | |
| 1247 | |
| 1248 Another solution is the same as I've already proposed -- when | |
| 1249 mapping, mark the table as "change-unsafe", and in this case, use a | |
| 1250 secondary table to maintain changes. this could be basically a | |
| 1251 standard hash table, but with entries only for added or deleted | |
| 1252 entries in the primary table, and a marker like Qunbound to | |
| 1253 indicate a deleted entry. puthash, gethash and remhash need a | |
| 1254 single extra check for this secondary table -- totally | |
| 1255 insignificant speedwise. if you really cared about making | |
| 1256 recursive maphashes completely correct, you'd have to do a bit of | |
| 1257 extra work here -- when maphashing, if the secondary table exists, | |
| 1258 make a copy of it, and use the copy in conjunction with the primary | |
| 1259 table when mapping. the advantages of this are | |
| 1260 | |
| 1261 [a] easy to demonstrate correct, even with weak hashtables. | |
| 1262 | |
| 1263 [b] no extra overhead in the general maphash case -- only when you | |
| 1264 modify the table while maphashing, and even then the overhead is | |
| 1265 very small. | |
| 1236 */ | 1266 */ |
| 1237 | 1267 |
| 1238 static Lisp_Object | 1268 static Lisp_Object |
| 1239 maphash_unwind (Lisp_Object unwind_obj) | 1269 maphash_unwind (Lisp_Object unwind_obj) |
| 1240 { | 1270 { |