0000: 2f 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d /*--------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 7c 20 -------------.|
0050: 20 20 43 6f 70 79 72 69 67 68 74 20 28 43 29 20 Copyright (C)
0060: 31 39 39 39 2d 32 30 30 30 20 20 4a 6f 63 68 65 1999-2000 Joche
0070: 6e 20 43 2e 20 4c 6f 65 77 65 72 20 28 6c 6f 65 n C. Loewer (loe
0080: 77 65 72 6a 40 68 6f 74 6d 61 69 6c 2e 63 6f 6d werj@hotmail.com
0090: 29 0a 2b 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ).+-------------
00a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
00e0: 7c 0a 7c 20 20 20 24 49 64 24 0a 7c 0a 7c 0a 7c |.| $Id$.|.|.|
00f0: 20 20 20 41 20 73 70 65 63 69 61 6c 20 6d 65 6d A special mem
0100: 6f 72 79 20 61 6c 6c 6f 63 61 74 6f 72 2c 20 77 ory allocator, w
0110: 68 69 63 68 20 75 73 65 73 20 70 72 65 2d 61 6c hich uses pre-al
0120: 6c 6f 63 61 74 65 64 20 2f 20 62 69 74 20 6d 61 located / bit ma
0130: 73 6b 65 64 0a 7c 20 20 20 62 61 73 65 64 20 61 sked.| based a
0140: 64 6d 69 6e 69 73 74 72 61 74 69 6f 6e 20 6f 66 dministration of
0150: 20 6d 65 6d 6f 72 79 20 62 6c 6f 63 6b 73 20 77 memory blocks w
0160: 69 74 68 20 66 69 78 65 64 20 73 69 7a 65 73 2c ith fixed sizes,
0170: 20 6c 69 6b 65 0a 7c 20 20 20 44 4f 4d 20 6e 6f like.| DOM no
0180: 64 65 73 2e 20 54 68 69 73 20 77 69 6c 6c 20 68 des. This will h
0190: 6f 70 65 66 75 6c 6c 79 20 73 61 76 65 20 73 6f opefully save so
01a0: 6d 65 20 6d 65 6d 6f 72 79 2e 0a 7c 0a 7c 0a 7c me memory..|.|.|
01b0: 20 20 20 54 68 65 20 63 6f 6e 74 65 6e 74 73 20 The contents
01c0: 6f 66 20 74 68 69 73 20 66 69 6c 65 20 61 72 65 of this file are
01d0: 20 73 75 62 6a 65 63 74 20 74 6f 20 74 68 65 20 subject to the
01e0: 4d 6f 7a 69 6c 6c 61 20 50 75 62 6c 69 63 20 4c Mozilla Public L
01f0: 69 63 65 6e 73 65 0a 7c 20 20 20 56 65 72 73 69 icense.| Versi
0200: 6f 6e 20 32 2e 30 20 28 74 68 65 20 22 4c 69 63 on 2.0 (the "Lic
0210: 65 6e 73 65 22 29 3b 20 79 6f 75 20 6d 61 79 20 ense"); you may
0220: 6e 6f 74 20 75 73 65 20 74 68 69 73 20 66 69 6c not use this fil
0230: 65 20 65 78 63 65 70 74 20 69 6e 0a 7c 20 20 20 e except in.|
0240: 63 6f 6d 70 6c 69 61 6e 63 65 20 77 69 74 68 20 compliance with
0250: 74 68 65 20 4c 69 63 65 6e 73 65 2e 20 59 6f 75 the License. You
0260: 20 6d 61 79 20 6f 62 74 61 69 6e 20 61 20 63 6f may obtain a co
0270: 70 79 20 6f 66 20 74 68 65 20 4c 69 63 65 6e 73 py of the Licens
0280: 65 20 61 74 0a 7c 20 20 20 68 74 74 70 3a 2f 2f e at.| http://
0290: 77 77 77 2e 6d 6f 7a 69 6c 6c 61 2e 6f 72 67 2f www.mozilla.org/
02a0: 4d 50 4c 2f 0a 7c 0a 7c 20 20 20 53 6f 66 74 77 MPL/.|.| Softw
02b0: 61 72 65 20 64 69 73 74 72 69 62 75 74 65 64 20 are distributed
02c0: 75 6e 64 65 72 20 74 68 65 20 4c 69 63 65 6e 73 under the Licens
02d0: 65 20 69 73 20 64 69 73 74 72 69 62 75 74 65 64 e is distributed
02e0: 20 6f 6e 20 61 6e 20 22 41 53 20 49 53 22 0a 7c on an "AS IS".|
02f0: 20 20 20 62 61 73 69 73 2c 20 57 49 54 48 4f 55 basis, WITHOU
0300: 54 20 57 41 52 52 41 4e 54 59 20 4f 46 20 41 4e T WARRANTY OF AN
0310: 59 20 4b 49 4e 44 2c 20 65 69 74 68 65 72 20 65 Y KIND, either e
0320: 78 70 72 65 73 73 20 6f 72 20 69 6d 70 6c 69 65 xpress or implie
0330: 64 2e 20 53 65 65 20 74 68 65 0a 7c 20 20 20 4c d. See the.| L
0340: 69 63 65 6e 73 65 20 66 6f 72 20 74 68 65 20 73 icense for the s
0350: 70 65 63 69 66 69 63 20 6c 61 6e 67 75 61 67 65 pecific language
0360: 20 67 6f 76 65 72 6e 69 6e 67 20 72 69 67 68 74 governing right
0370: 73 20 61 6e 64 20 6c 69 6d 69 74 61 74 69 6f 6e s and limitation
0380: 73 0a 7c 20 20 20 75 6e 64 65 72 20 74 68 65 20 s.| under the
0390: 4c 69 63 65 6e 73 65 2e 0a 7c 0a 7c 20 20 20 54 License..|.| T
03a0: 68 65 20 4f 72 69 67 69 6e 61 6c 20 43 6f 64 65 he Original Code
03b0: 20 69 73 20 74 44 4f 4d 2e 0a 7c 0a 7c 20 20 20 is tDOM..|.|
03c0: 54 68 65 20 49 6e 69 74 69 61 6c 20 44 65 76 65 The Initial Deve
03d0: 6c 6f 70 65 72 20 6f 66 20 74 68 65 20 4f 72 69 loper of the Ori
03e0: 67 69 6e 61 6c 20 43 6f 64 65 20 69 73 20 4a 6f ginal Code is Jo
03f0: 63 68 65 6e 20 4c 6f 65 77 65 72 0a 7c 20 20 20 chen Loewer.|
0400: 50 6f 72 74 69 6f 6e 73 20 63 72 65 61 74 65 64 Portions created
0410: 20 62 79 20 4a 6f 63 68 65 6e 20 4c 6f 65 77 65 by Jochen Loewe
0420: 72 20 61 72 65 20 43 6f 70 79 72 69 67 68 74 20 r are Copyright
0430: 28 43 29 20 31 39 39 38 2c 20 31 39 39 39 0a 7c (C) 1998, 1999.|
0440: 20 20 20 4a 6f 63 68 65 6e 20 4c 6f 65 77 65 72 Jochen Loewer
0450: 2e 20 41 6c 6c 20 52 69 67 68 74 73 20 52 65 73 . All Rights Res
0460: 65 72 76 65 64 2e 0a 7c 0a 7c 20 20 20 43 6f 6e erved..|.| Con
0470: 74 72 69 62 75 74 6f 72 28 73 29 3a 0a 7c 0a 7c tributor(s):.|.|
0480: 0a 7c 20 20 20 77 72 69 74 74 65 6e 20 62 79 20 .| written by
0490: 4a 6f 63 68 65 6e 20 4c 6f 65 77 65 72 0a 7c 20 Jochen Loewer.|
04a0: 20 20 4f 63 74 6f 62 65 72 2c 20 32 30 30 30 0a October, 2000.
04b0: 7c 0a 5c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d |.\-------------
04c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
04d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
04e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
04f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a -------------*/.
0500: 0a 2f 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ./*-------------
0510: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0520: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0530: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0540: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 7c --------------.|
0550: 20 20 20 49 6e 63 6c 75 64 65 73 0a 7c 0a 5c 2d Includes.|.\-
0560: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0570: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0580: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0590: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
05a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a 23 69 6e 63 ---------*/.#inc
05b0: 6c 75 64 65 20 3c 74 63 6c 2e 68 3e 0a 23 69 6e lude <tcl.h>.#in
05c0: 63 6c 75 64 65 20 3c 73 74 64 6c 69 62 2e 68 3e clude <stdlib.h>
05d0: 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e .#include <strin
05e0: 67 2e 68 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 64 g.h>.#include <d
05f0: 6f 6d 61 6c 6c 6f 63 2e 68 3e 0a 0a 0a 2f 2a 2d omalloc.h>.../*-
0600: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0610: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0620: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0630: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0640: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 7c 20 20 20 44 ----------.| D
0650: 65 66 69 6e 65 73 0a 7c 0a 5c 2d 2d 2d 2d 2d 2d efines.|.\------
0660: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0670: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0680: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0690: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
06a0: 2d 2d 2d 2d 2a 2f 0a 23 64 65 66 69 6e 65 20 44 ----*/.#define D
06b0: 42 47 28 78 29 0a 23 64 65 66 69 6e 65 20 4d 41 BG(x).#define MA
06c0: 58 5f 42 49 4e 53 20 20 20 20 20 20 20 20 20 32 X_BINS 2
06d0: 35 36 0a 23 64 65 66 69 6e 65 20 42 49 4e 5f 48 56.#define BIN_H
06e0: 41 53 48 5f 53 49 5a 45 20 20 20 20 35 31 32 0a ASH_SIZE 512.
06f0: 23 64 65 66 69 6e 65 20 42 49 4e 5f 48 41 53 48 #define BIN_HASH
0700: 5f 4d 41 53 4b 20 20 20 20 30 78 30 31 46 46 0a _MASK 0x01FF.
0710: 23 64 65 66 69 6e 65 20 43 41 43 48 45 5f 53 49 #define CACHE_SI
0720: 5a 45 20 20 20 20 20 20 20 34 0a 23 64 65 66 69 ZE 4.#defi
0730: 6e 65 20 42 4c 4f 43 4b 5f 44 41 54 41 5f 53 49 ne BLOCK_DATA_SI
0740: 5a 45 20 20 33 31 30 30 30 0a 23 64 65 66 69 6e ZE 31000.#defin
0750: 65 20 42 4c 4f 43 4b 5f 53 49 5a 45 5f 42 49 54 e BLOCK_SIZE_BIT
0760: 53 20 20 31 36 0a 0a 0a 2f 2a 2d 2d 2d 2d 2d 2d S 16.../*------
0770: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0780: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0790: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
07a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
07b0: 2d 2d 2d 2d 2d 0a 7c 20 20 20 54 79 70 65 64 65 -----.| Typede
07c0: 66 73 0a 7c 0a 5c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d fs.|.\----------
07d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
07e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
07f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0800: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0810: 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75 63 */.typedef struc
0820: 74 20 64 6f 6d 41 6c 6c 6f 63 42 6c 6f 63 6b 20 t domAllocBlock
0830: 7b 0a 20 20 20 20 73 74 72 75 63 74 20 64 6f 6d {. struct dom
0840: 41 6c 6c 6f 63 42 69 6e 20 20 20 20 2a 20 62 69 AllocBin * bi
0850: 6e 3b 0a 20 20 20 20 76 6f 69 64 20 20 20 20 20 n;. void
0860: 20 20 20 20 20 20 20 20 20 20 20 20 20 2a 20 65 * e
0870: 6e 64 3b 0a 20 20 20 20 73 74 72 75 63 74 20 64 nd;. struct d
0880: 6f 6d 41 6c 6c 6f 63 42 6c 6f 63 6b 20 20 2a 20 omAllocBlock *
0890: 70 72 65 76 3b 0a 20 20 20 20 73 74 72 75 63 74 prev;. struct
08a0: 20 64 6f 6d 41 6c 6c 6f 63 42 6c 6f 63 6b 20 20 domAllocBlock
08b0: 2a 20 6e 65 78 74 3b 0a 20 20 20 20 69 6e 74 20 * next;. int
08c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
08d0: 20 20 20 20 68 61 73 68 49 6e 64 65 78 31 3b 0a hashIndex1;.
08e0: 20 20 20 20 73 74 72 75 63 74 20 64 6f 6d 41 6c struct domAl
08f0: 6c 6f 63 42 6c 6f 63 6b 20 20 2a 20 68 61 73 68 locBlock * hash
0900: 4e 65 78 74 31 3b 0a 20 20 20 20 69 6e 74 20 20 Next1;. int
0910: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0920: 20 20 20 68 61 73 68 49 6e 64 65 78 32 3b 0a 20 hashIndex2;.
0930: 20 20 20 73 74 72 75 63 74 20 64 6f 6d 41 6c 6c struct domAll
0940: 6f 63 42 6c 6f 63 6b 20 20 2a 20 68 61 73 68 4e ocBlock * hashN
0950: 65 78 74 32 3b 0a 20 20 20 20 69 6e 74 20 20 20 ext2;. int
0960: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0970: 20 20 73 6c 6f 74 73 3b 0a 20 20 20 20 69 6e 74 slots;. int
0980: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0990: 20 20 20 20 20 66 72 65 65 53 6c 6f 74 73 3b 0a freeSlots;.
09a0: 20 20 20 20 69 6e 74 20 20 20 20 20 20 20 20 20 int
09b0: 20 20 20 20 20 20 20 20 20 20 20 20 62 69 74 6d bitm
09c0: 61 70 73 3b 0a 20 20 20 20 69 6e 74 20 20 20 20 aps;. int
09d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
09e0: 20 66 72 65 65 50 6f 73 3b 0a 20 20 20 20 69 6e freePos;. in
09f0: 74 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 t
0a00: 20 20 20 20 20 20 66 72 65 65 42 69 74 3b 0a 20 freeBit;.
0a10: 20 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 unsigned int
0a20: 20 20 20 20 20 20 20 20 20 20 20 66 72 65 65 4d freeM
0a30: 61 73 6b 3b 0a 7d 20 64 6f 6d 41 6c 6c 6f 63 42 ask;.} domAllocB
0a40: 6c 6f 63 6b 3b 0a 0a 0a 74 79 70 65 64 65 66 20 lock;...typedef
0a50: 73 74 72 75 63 74 20 64 6f 6d 41 6c 6c 6f 63 42 struct domAllocB
0a60: 69 6e 20 7b 0a 20 20 20 20 69 6e 74 20 20 20 20 in {. int
0a70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0a80: 20 73 69 7a 65 3b 0a 20 20 20 20 69 6e 74 20 20 size;. int
0a90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0aa0: 20 20 20 6e 72 53 6c 6f 74 73 3b 0a 20 20 20 20 nrSlots;.
0ab0: 69 6e 74 20 20 20 20 20 20 20 20 20 20 20 20 20 int
0ac0: 20 20 20 20 20 20 20 20 66 72 65 65 53 6c 6f 74 freeSlot
0ad0: 73 3b 0a 20 20 20 20 69 6e 74 20 20 20 20 20 20 s;. int
0ae0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6e n
0af0: 72 42 6c 6f 63 6b 73 3b 0a 20 20 20 20 64 6f 6d rBlocks;. dom
0b00: 41 6c 6c 6f 63 42 6c 6f 63 6b 20 20 20 20 20 20 AllocBlock
0b10: 20 20 20 2a 20 66 72 65 65 42 6c 6f 63 6b 73 3b * freeBlocks;
0b20: 0a 20 20 20 20 64 6f 6d 41 6c 6c 6f 63 42 6c 6f . domAllocBlo
0b30: 63 6b 20 20 20 20 20 20 20 20 20 2a 20 75 73 65 ck * use
0b40: 64 42 6c 6f 63 6b 73 3b 0a 7d 20 64 6f 6d 41 6c dBlocks;.} domAl
0b50: 6c 6f 63 42 69 6e 3b 0a 0a 0a 74 79 70 65 64 65 locBin;...typede
0b60: 66 20 73 74 72 75 63 74 20 64 6f 6d 41 6c 6c 6f f struct domAllo
0b70: 63 42 69 6e 73 20 7b 0a 20 20 20 20 73 74 72 75 cBins {. stru
0b80: 63 74 20 64 6f 6d 41 6c 6c 6f 63 42 69 6e 20 20 ct domAllocBin
0b90: 20 2a 20 62 69 6e 5b 4d 41 58 5f 42 49 4e 53 5d * bin[MAX_BINS]
0ba0: 3b 0a 20 20 20 20 73 74 72 75 63 74 20 64 6f 6d ;. struct dom
0bb0: 41 6c 6c 6f 63 42 6c 6f 63 6b 20 2a 20 68 61 73 AllocBlock * has
0bc0: 68 65 64 42 6c 6f 63 6b 73 5b 42 49 4e 5f 48 41 hedBlocks[BIN_HA
0bd0: 53 48 5f 53 49 5a 45 5d 3b 0a 20 20 20 20 73 74 SH_SIZE];. st
0be0: 72 75 63 74 20 64 6f 6d 41 6c 6c 6f 63 42 6c 6f ruct domAllocBlo
0bf0: 63 6b 20 2a 20 62 6c 6f 63 6b 43 61 63 68 65 5b ck * blockCache[
0c00: 43 41 43 48 45 5f 53 49 5a 45 5d 3b 0a 7d 20 64 CACHE_SIZE];.} d
0c10: 6f 6d 41 6c 6c 6f 63 42 69 6e 73 3b 0a 0a 0a 2f omAllocBins;.../
0c20: 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *---------------
0c30: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0c40: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0c50: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0c60: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 7c 20 20 ------------.|
0c70: 20 47 6c 6f 62 61 6c 73 2e 20 54 68 69 73 20 69 Globals. This i
0c80: 73 20 61 20 22 73 69 6e 67 6c 65 2d 74 68 72 65 s a "single-thre
0c90: 61 64 65 64 22 20 61 6c 6c 6f 63 61 74 6f 72 2e aded" allocator.
0ca0: 0a 7c 0a 5c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .|.\------------
0cb0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0cc0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0cd0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0ce0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f --------------*/
0cf0: 0a 73 74 61 74 69 63 20 64 6f 6d 41 6c 6c 6f 63 .static domAlloc
0d00: 42 69 6e 73 20 62 69 6e 73 3b 0a 0a 23 69 66 64 Bins bins;..#ifd
0d10: 65 66 20 54 43 4c 5f 54 48 52 45 41 44 53 0a 23 ef TCL_THREADS.#
0d20: 20 64 65 66 69 6e 65 20 54 44 6f 6d 54 68 72 65 define TDomThre
0d30: 61 64 65 64 28 78 29 20 78 0a 20 20 73 74 61 74 aded(x) x. stat
0d40: 69 63 20 54 63 6c 5f 4d 75 74 65 78 20 62 69 6e ic Tcl_Mutex bin
0d50: 4d 75 74 65 78 3b 0a 23 65 6c 73 65 0a 23 20 64 Mutex;.#else.# d
0d60: 65 66 69 6e 65 20 54 44 6f 6d 54 68 72 65 61 64 efine TDomThread
0d70: 65 64 28 78 29 0a 23 65 6e 64 69 66 0a 0a 2f 2a ed(x).#endif../*
0d80: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0d90: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0da0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0db0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0dc0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 7c 20 20 20 -----------.|
0dd0: 64 6f 6d 41 6c 6c 6f 63 49 6e 69 74 0a 7c 0a 5c domAllocInit.|.\
0de0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0df0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0e00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0e10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0e20: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a 76 6f 69 ----------*/.voi
0e30: 64 0a 64 6f 6d 41 6c 6c 6f 63 49 6e 69 74 28 29 d.domAllocInit()
0e40: 0a 7b 0a 20 20 20 20 69 6e 74 20 69 3b 0a 0a 20 .{. int i;..
0e50: 20 20 20 44 42 47 28 66 70 72 69 6e 74 66 28 73 DBG(fprintf(s
0e60: 74 64 65 72 72 2c 20 22 64 6f 6d 41 6c 6c 6f 63 tderr, "domAlloc
0e70: 49 6e 69 74 2e 2e 2e 5c 6e 22 29 3b 29 0a 0a 20 Init...\n");)..
0e80: 20 20 20 66 6f 72 20 28 69 3d 30 3b 20 69 20 3c for (i=0; i <
0e90: 20 4d 41 58 5f 42 49 4e 53 3b 20 20 20 20 20 20 MAX_BINS;
0ea0: 69 2b 2b 29 20 62 69 6e 73 2e 62 69 6e 5b 69 5d i++) bins.bin[i]
0eb0: 20 20 20 20 20 20 20 20 20 20 3d 20 4e 55 4c 4c = NULL
0ec0: 3b 0a 20 20 20 20 66 6f 72 20 28 69 3d 30 3b 20 ;. for (i=0;
0ed0: 69 20 3c 20 43 41 43 48 45 5f 53 49 5a 45 3b 20 i < CACHE_SIZE;
0ee0: 20 20 20 69 2b 2b 29 20 62 69 6e 73 2e 62 6c 6f i++) bins.blo
0ef0: 63 6b 43 61 63 68 65 5b 69 5d 20 20 20 3d 20 4e ckCache[i] = N
0f00: 55 4c 4c 3b 0a 20 20 20 20 66 6f 72 20 28 69 3d ULL;. for (i=
0f10: 30 3b 20 69 20 3c 20 42 49 4e 5f 48 41 53 48 5f 0; i < BIN_HASH_
0f20: 53 49 5a 45 3b 20 69 2b 2b 29 20 62 69 6e 73 2e SIZE; i++) bins.
0f30: 68 61 73 68 65 64 42 6c 6f 63 6b 73 5b 69 5d 20 hashedBlocks[i]
0f40: 3d 20 4e 55 4c 4c 3b 0a 7d 0a 0a 0a 2f 2a 2d 2d = NULL;.}.../*--
0f50: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0f60: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0f70: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0f80: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0f90: 2d 2d 2d 2d 2d 2d 2d 2d 0a 7c 20 20 20 66 69 6c --------.| fil
0fa0: 6c 48 61 73 68 54 61 62 6c 65 0a 7c 0a 5c 2d 2d lHashTable.|.\--
0fb0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0fc0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0fd0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0fe0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0ff0: 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a 73 74 61 74 69 --------*/.stati
1000: 63 20 76 6f 69 64 0a 66 69 6c 6c 48 61 73 68 54 c void.fillHashT
1010: 61 62 6c 65 20 28 0a 20 20 20 20 64 6f 6d 41 6c able (. domAl
1020: 6c 6f 63 42 6c 6f 63 6b 20 20 2a 20 62 6c 6f 63 locBlock * bloc
1030: 6b 2c 0a 20 20 20 20 76 6f 69 64 20 20 20 20 20 k,. void
1040: 20 20 20 20 20 20 2a 20 6d 65 6d 0a 29 0a 7b 0a * mem.).{.
1050: 20 20 20 20 64 6f 6d 41 6c 6c 6f 63 42 6c 6f 63 domAllocBloc
1060: 6b 20 2a 20 68 61 73 68 65 64 42 6c 6f 63 6b 3b k * hashedBlock;
1070: 0a 20 20 20 20 75 6e 73 69 67 6e 65 64 20 69 6e . unsigned in
1080: 74 20 20 20 20 69 3b 0a 0a 20 20 20 20 69 20 3d t i;.. i =
1090: 20 28 20 28 75 6e 73 69 67 6e 65 64 20 69 6e 74 ( (unsigned int
10a0: 29 6d 65 6d 20 3e 3e 20 42 4c 4f 43 4b 5f 53 49 )mem >> BLOCK_SI
10b0: 5a 45 5f 42 49 54 53 29 20 26 20 42 49 4e 5f 48 ZE_BITS) & BIN_H
10c0: 41 53 48 5f 4d 41 53 4b 3b 0a 20 20 20 20 68 61 ASH_MASK;. ha
10d0: 73 68 65 64 42 6c 6f 63 6b 20 3d 20 62 69 6e 73 shedBlock = bins
10e0: 2e 68 61 73 68 65 64 42 6c 6f 63 6b 73 5b 69 5d .hashedBlocks[i]
10f0: 3b 0a 20 20 20 20 77 68 69 6c 65 20 28 68 61 73 ;. while (has
1100: 68 65 64 42 6c 6f 63 6b 20 21 3d 20 4e 55 4c 4c hedBlock != NULL
1110: 29 20 7b 0a 20 20 20 20 20 20 20 20 69 66 20 28 ) {. if (
1120: 68 61 73 68 65 64 42 6c 6f 63 6b 20 3d 3d 20 62 hashedBlock == b
1130: 6c 6f 63 6b 29 20 7b 0a 20 20 20 20 20 20 20 20 lock) {.
1140: 20 20 20 20 2f 2a 20 61 6c 6c 20 69 73 20 66 69 /* all is fi
1150: 6e 65 2c 20 62 6c 6f 63 6b 20 69 73 20 61 6c 72 ne, block is alr
1160: 65 61 64 79 20 69 6e 20 68 61 73 68 20 74 61 62 eady in hash tab
1170: 6c 65 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 le */.
1180: 20 20 72 65 74 75 72 6e 3b 0a 20 20 20 20 20 20 return;.
1190: 20 20 7d 0a 20 20 20 20 20 20 20 20 69 66 20 20 }. if
11a0: 20 20 20 20 28 68 61 73 68 65 64 42 6c 6f 63 6b (hashedBlock
11b0: 2d 3e 68 61 73 68 49 6e 64 65 78 31 20 3d 3d 20 ->hashIndex1 ==
11c0: 28 69 6e 74 29 69 29 20 68 61 73 68 65 64 42 6c (int)i) hashedBl
11d0: 6f 63 6b 20 3d 20 68 61 73 68 65 64 42 6c 6f 63 ock = hashedBloc
11e0: 6b 2d 3e 68 61 73 68 4e 65 78 74 31 3b 0a 20 20 k->hashNext1;.
11f0: 20 20 20 20 20 20 65 6c 73 65 20 69 66 20 28 68 else if (h
1200: 61 73 68 65 64 42 6c 6f 63 6b 2d 3e 68 61 73 68 ashedBlock->hash
1210: 49 6e 64 65 78 32 20 3d 3d 20 28 69 6e 74 29 69 Index2 == (int)i
1220: 29 20 68 61 73 68 65 64 42 6c 6f 63 6b 20 3d 20 ) hashedBlock =
1230: 68 61 73 68 65 64 42 6c 6f 63 6b 2d 3e 68 61 73 hashedBlock->has
1240: 68 4e 65 78 74 32 3b 0a 20 20 20 20 20 20 20 20 hNext2;.
1250: 65 6c 73 65 20 68 61 73 68 65 64 42 6c 6f 63 6b else hashedBlock
1260: 20 3d 20 4e 55 4c 4c 3b 0a 20 20 20 20 7d 0a 0a = NULL;. }..
1270: 20 20 20 20 2f 2a 20 61 64 64 20 62 6c 6f 63 6b /* add block
1280: 20 69 6e 20 68 61 73 68 20 74 61 62 6c 65 20 2a in hash table *
1290: 2f 0a 20 20 20 20 69 66 20 28 62 6c 6f 63 6b 2d /. if (block-
12a0: 3e 68 61 73 68 49 6e 64 65 78 31 20 3d 3d 20 2d >hashIndex1 == -
12b0: 31 29 20 7b 0a 20 20 20 20 20 20 20 20 62 6c 6f 1) {. blo
12c0: 63 6b 2d 3e 68 61 73 68 49 6e 64 65 78 31 20 3d ck->hashIndex1 =
12d0: 20 69 3b 0a 20 20 20 20 20 20 20 20 62 6c 6f 63 i;. bloc
12e0: 6b 2d 3e 68 61 73 68 4e 65 78 74 31 20 20 3d 20 k->hashNext1 =
12f0: 62 69 6e 73 2e 68 61 73 68 65 64 42 6c 6f 63 6b bins.hashedBlock
1300: 73 5b 69 5d 3b 0a 20 20 20 20 7d 20 65 6c 73 65 s[i];. } else
1310: 0a 20 20 20 20 69 66 20 28 62 6c 6f 63 6b 2d 3e . if (block->
1320: 68 61 73 68 49 6e 64 65 78 32 20 3d 3d 20 2d 31 hashIndex2 == -1
1330: 29 20 7b 0a 20 20 20 20 20 20 20 20 62 6c 6f 63 ) {. bloc
1340: 6b 2d 3e 68 61 73 68 49 6e 64 65 78 32 20 3d 20 k->hashIndex2 =
1350: 69 3b 0a 20 20 20 20 20 20 20 20 62 6c 6f 63 6b i;. block
1360: 2d 3e 68 61 73 68 4e 65 78 74 32 20 20 3d 20 62 ->hashNext2 = b
1370: 69 6e 73 2e 68 61 73 68 65 64 42 6c 6f 63 6b 73 ins.hashedBlocks
1380: 5b 69 5d 3b 0a 20 20 20 20 7d 20 65 6c 73 65 20 [i];. } else
1390: 7b 0a 20 20 20 20 20 20 20 20 44 42 47 28 0a 20 {. DBG(.
13a0: 20 20 20 20 20 20 20 20 20 20 20 66 70 72 69 6e fprin
13b0: 74 66 28 73 74 64 65 72 72 2c 20 22 5c 6e 74 6f tf(stderr, "\nto
13c0: 6f 20 6d 61 6e 79 20 68 61 73 68 20 65 6e 74 72 o many hash entr
13d0: 69 65 73 20 66 6f 72 20 25 78 20 25 78 2d 3e 25 ies for %x %x->%
13e0: 64 20 25 64 2c 25 64 21 5c 6e 22 2c 0a 20 20 20 d %d,%d!\n",.
13f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1400: 20 28 75 6e 73 69 67 6e 65 64 20 69 6e 74 29 62 (unsigned int)b
1410: 6c 6f 63 6b 2c 0a 20 20 20 20 20 20 20 20 20 20 lock,.
1420: 20 20 20 20 20 20 20 20 20 20 28 75 6e 73 69 67 (unsig
1430: 6e 65 64 20 69 6e 74 29 6d 65 6d 2c 20 69 2c 20 ned int)mem, i,
1440: 62 6c 6f 63 6b 2d 3e 68 61 73 68 49 6e 64 65 78 block->hashIndex
1450: 31 2c 20 62 6c 6f 63 6b 2d 3e 68 61 73 68 49 6e 1, block->hashIn
1460: 64 65 78 32 29 3b 29 0a 20 20 20 20 7d 0a 20 20 dex2);). }.
1470: 20 20 62 69 6e 73 2e 68 61 73 68 65 64 42 6c 6f bins.hashedBlo
1480: 63 6b 73 5b 69 5d 20 3d 20 62 6c 6f 63 6b 3b 0a cks[i] = block;.
1490: 7d 0a 0a 2f 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d }../*-----------
14a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
14b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
14c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
14d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
14e0: 7c 20 20 20 64 6f 6d 41 6c 6c 6f 63 0a 7c 0a 5c | domAlloc.|.\
14f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1500: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1510: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1520: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1530: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a 76 6f 69 ----------*/.voi
1540: 64 20 2a 0a 64 6f 6d 41 6c 6c 6f 63 20 28 0a 20 d *.domAlloc (.
1550: 20 20 20 69 6e 74 20 20 73 69 7a 65 0a 29 0a 7b int size.).{
1560: 0a 20 20 20 20 64 6f 6d 41 6c 6c 6f 63 42 69 6e . domAllocBin
1570: 20 20 20 2a 20 62 69 6e 3b 0a 20 20 20 20 64 6f * bin;. do
1580: 6d 41 6c 6c 6f 63 42 6c 6f 63 6b 20 2a 20 62 6c mAllocBlock * bl
1590: 6f 63 6b 3b 0a 20 20 20 20 64 6f 6d 41 6c 6c 6f ock;. domAllo
15a0: 63 42 6c 6f 63 6b 20 2a 20 68 61 73 68 65 64 42 cBlock * hashedB
15b0: 6c 6f 63 6b 3b 0a 20 20 20 20 69 6e 74 20 20 20 lock;. int
15c0: 20 20 20 20 20 20 20 20 20 20 69 2c 20 6a 2c 20 i, j,
15d0: 73 6c 6f 74 73 2c 20 62 69 74 6d 61 70 73 2c 20 slots, bitmaps,
15e0: 62 6c 6f 63 6b 53 69 7a 65 3b 0a 20 20 20 20 75 blockSize;. u
15f0: 6e 73 69 67 6e 65 64 20 69 6e 74 20 20 20 20 6d nsigned int m
1600: 61 73 6b 3b 0a 20 20 20 20 63 68 61 72 20 20 20 ask;. char
1610: 20 20 20 20 20 20 20 2a 20 6d 65 6d 3b 0a 20 20 * mem;.
1620: 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 20 unsigned int
1630: 2a 20 75 73 65 64 42 69 74 6d 61 70 3b 0a 0a 0a * usedBitmap;...
1640: 20 20 20 20 44 42 47 28 66 70 72 69 6e 74 66 28 DBG(fprintf(
1650: 73 74 64 65 72 72 2c 20 22 5c 6e 64 6f 6d 41 6c stderr, "\ndomAl
1660: 6c 6f 63 20 25 64 20 5c 6e 22 2c 20 73 69 7a 65 loc %d \n", size
1670: 29 3b 29 0a 0a 20 20 20 20 69 66 20 28 73 69 7a );).. if (siz
1680: 65 20 3e 3d 20 4d 41 58 5f 42 49 4e 53 29 20 7b e >= MAX_BINS) {
1690: 0a 20 20 20 20 20 20 20 20 44 42 47 28 66 70 72 . DBG(fpr
16a0: 69 6e 74 66 28 73 74 64 65 72 72 2c 20 22 5c 6e intf(stderr, "\n
16b0: 53 69 7a 65 20 74 6f 6f 20 6c 61 72 67 65 20 61 Size too large a
16c0: 73 20 75 73 65 64 20 66 6f 72 20 62 69 6e 21 5c s used for bin!\
16d0: 6e 22 29 3b 29 0a 20 20 20 20 20 20 20 20 72 65 n");). re
16e0: 74 75 72 6e 20 4e 55 4c 4c 3b 0a 20 20 20 20 7d turn NULL;. }
16f0: 0a 0a 20 20 20 20 2f 2a 2d 2d 2d 2d 2d 2d 2d 2d .. /*--------
1700: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1710: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1720: 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 20 20 20 20 7c ---------. |
1730: 20 20 20 46 49 58 4d 45 0a 20 20 20 20 20 7c 0a FIXME. |.
1740: 20 20 20 20 20 7c 20 20 20 52 65 77 72 69 74 65 | Rewrite
1750: 20 77 69 74 68 20 54 53 44 2d 62 61 73 65 64 20 with TSD-based
1760: 62 69 6e 73 20 74 6f 20 61 76 6f 69 64 20 6d 75 bins to avoid mu
1770: 74 65 78 0a 20 20 20 20 20 7c 20 20 20 63 6f 6e tex. | con
1780: 74 65 6e 74 69 6f 6e 2e 20 54 68 72 65 61 64 73 tention. Threads
1790: 20 61 72 65 20 67 6f 69 6e 67 20 74 6f 20 73 74 are going to st
17a0: 65 70 20 6f 6e 0a 20 20 20 20 20 7c 20 20 20 65 ep on. | e
17b0: 61 63 68 20 6f 74 68 65 72 20 74 6f 65 73 20 68 ach other toes h
17c0: 65 72 65 20 77 68 69 63 68 20 69 73 20 6e 6f 74 ere which is not
17d0: 20 77 68 61 74 20 77 65 0a 20 20 20 20 20 7c 20 what we. |
17e0: 20 20 77 6f 75 6c 64 20 6c 69 6b 65 20 74 6f 20 would like to
17f0: 68 61 76 65 2c 20 64 6f 6e 27 74 20 77 65 20 3f have, don't we ?
1800: 20 20 28 7a 76 29 0a 20 20 20 20 20 5c 2d 2d 2d (zv). \---
1810: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1820: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1830: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a -------------*/.
1840: 0a 20 20 20 20 54 44 6f 6d 54 68 72 65 61 64 65 . TDomThreade
1850: 64 28 54 63 6c 5f 4d 75 74 65 78 4c 6f 63 6b 28 d(Tcl_MutexLock(
1860: 26 62 69 6e 4d 75 74 65 78 29 3b 29 20 2f 2a 20 &binMutex);) /*
1870: 4c 4f 43 4b 20 21 2a 2f 0a 0a 20 20 20 20 69 66 LOCK !*/.. if
1880: 20 28 62 69 6e 73 2e 62 69 6e 5b 73 69 7a 65 5d (bins.bin[size]
1890: 20 3d 3d 20 4e 55 4c 4c 29 20 7b 0a 20 20 20 20 == NULL) {.
18a0: 20 20 20 20 2f 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d /*----------
18b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
18c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
18d0: 2d 2d 2d 2d 2d 2d 2d 0a 20 20 20 20 20 20 20 20 -------.
18e0: 7c 20 20 20 63 72 65 61 74 65 20 6e 65 77 20 62 | create new b
18f0: 69 6e 0a 20 20 20 20 20 20 20 20 5c 2d 2d 2d 2d in. \----
1900: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1910: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1920: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a 20 ------------*/.
1930: 20 20 20 20 20 20 20 62 69 6e 20 3d 20 28 64 6f bin = (do
1940: 6d 41 6c 6c 6f 63 42 69 6e 20 2a 29 6d 61 6c 6c mAllocBin *)mall
1950: 6f 63 28 73 69 7a 65 6f 66 28 64 6f 6d 41 6c 6c oc(sizeof(domAll
1960: 6f 63 42 69 6e 29 29 3b 0a 20 20 20 20 20 20 20 ocBin));.
1970: 20 62 69 6e 2d 3e 73 69 7a 65 20 20 20 20 20 20 bin->size
1980: 20 20 3d 20 73 69 7a 65 3b 0a 20 20 20 20 20 20 = size;.
1990: 20 20 62 69 6e 2d 3e 6e 72 53 6c 6f 74 73 20 20 bin->nrSlots
19a0: 20 20 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 = 0;.
19b0: 62 69 6e 2d 3e 66 72 65 65 53 6c 6f 74 73 20 20 bin->freeSlots
19c0: 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 62 69 = 0;. bi
19d0: 6e 2d 3e 6e 72 42 6c 6f 63 6b 73 20 20 20 20 3d n->nrBlocks =
19e0: 20 30 3b 0a 20 20 20 20 20 20 20 20 62 69 6e 2d 0;. bin-
19f0: 3e 66 72 65 65 42 6c 6f 63 6b 73 20 20 3d 20 4e >freeBlocks = N
1a00: 55 4c 4c 3b 0a 20 20 20 20 20 20 20 20 62 69 6e ULL;. bin
1a10: 2d 3e 75 73 65 64 42 6c 6f 63 6b 73 20 20 3d 20 ->usedBlocks =
1a20: 4e 55 4c 4c 3b 0a 0a 20 20 20 20 20 20 20 20 62 NULL;.. b
1a30: 69 6e 73 2e 62 69 6e 5b 73 69 7a 65 5d 20 3d 20 ins.bin[size] =
1a40: 62 69 6e 3b 0a 0a 20 20 20 20 7d 20 65 6c 73 65 bin;.. } else
1a50: 20 7b 0a 20 20 20 20 20 20 20 20 62 69 6e 20 3d {. bin =
1a60: 20 62 69 6e 73 2e 62 69 6e 5b 73 69 7a 65 5d 3b bins.bin[size];
1a70: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 69 66 20 28 . }.. if (
1a80: 62 69 6e 2d 3e 66 72 65 65 53 6c 6f 74 73 20 3d bin->freeSlots =
1a90: 3d 20 30 29 20 7b 0a 20 20 20 20 20 20 20 20 44 = 0) {. D
1aa0: 42 47 28 66 70 72 69 6e 74 66 28 73 74 64 65 72 BG(fprintf(stder
1ab0: 72 2c 20 22 61 6c 6c 6f 63 61 74 69 6e 67 20 6e r, "allocating n
1ac0: 65 77 20 62 6c 6f 63 6b 20 2e 2e 2e 20 5c 6e 22 ew block ... \n"
1ad0: 29 3b 29 0a 20 20 20 20 20 20 20 20 2f 2a 2d 2d );). /*--
1ae0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1af0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1b00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1b10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 --------------.
1b20: 20 20 20 20 20 20 20 7c 20 20 20 61 6c 6c 6f 63 | alloc
1b30: 61 74 65 20 61 6e 64 20 69 6e 69 74 69 61 6c 69 ate and initiali
1b40: 7a 65 20 61 20 6e 65 77 20 62 6c 6f 63 6b 0a 20 ze a new block.
1b50: 20 20 20 20 20 20 20 7c 0a 20 20 20 20 20 20 20 |.
1b60: 20 5c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d \--------------
1b70: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1b80: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1b90: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1ba0: 2d 2a 2f 0a 20 20 20 20 20 20 20 20 62 69 74 6d -*/. bitm
1bb0: 61 70 73 20 20 20 3d 20 28 42 4c 4f 43 4b 5f 44 aps = (BLOCK_D
1bc0: 41 54 41 5f 53 49 5a 45 20 20 2f 20 73 69 7a 65 ATA_SIZE / size
1bd0: 29 20 2f 20 33 32 3b 0a 20 20 20 20 20 20 20 20 ) / 32;.
1be0: 73 6c 6f 74 73 20 20 20 20 20 3d 20 62 69 74 6d slots = bitm
1bf0: 61 70 73 20 2a 20 33 32 3b 0a 20 20 20 20 20 20 aps * 32;.
1c00: 20 20 62 6c 6f 63 6b 53 69 7a 65 20 3d 20 73 69 blockSize = si
1c10: 7a 65 6f 66 28 64 6f 6d 41 6c 6c 6f 63 42 6c 6f zeof(domAllocBlo
1c20: 63 6b 29 20 2b 20 62 69 74 6d 61 70 73 2a 34 20 ck) + bitmaps*4
1c30: 2b 20 73 6c 6f 74 73 2a 73 69 7a 65 3b 0a 0a 20 + slots*size;..
1c40: 20 20 20 20 20 20 20 62 6c 6f 63 6b 20 3d 20 28 block = (
1c50: 64 6f 6d 41 6c 6c 6f 63 42 6c 6f 63 6b 20 2a 29 domAllocBlock *)
1c60: 6d 61 6c 6c 6f 63 28 20 62 6c 6f 63 6b 53 69 7a malloc( blockSiz
1c70: 65 20 29 3b 0a 20 20 20 20 20 20 20 20 62 6c 6f e );. blo
1c80: 63 6b 2d 3e 62 69 6e 20 20 20 20 20 20 20 20 3d ck->bin =
1c90: 20 62 69 6e 3b 0a 20 20 20 20 20 20 20 20 62 6c bin;. bl
1ca0: 6f 63 6b 2d 3e 65 6e 64 20 20 20 20 20 20 20 20 ock->end
1cb0: 3d 20 28 63 68 61 72 2a 29 62 6c 6f 63 6b 20 2b = (char*)block +
1cc0: 20 62 6c 6f 63 6b 53 69 7a 65 3b 0a 20 20 20 20 blockSize;.
1cd0: 20 20 20 20 62 6c 6f 63 6b 2d 3e 73 6c 6f 74 73 block->slots
1ce0: 20 20 20 20 20 20 3d 20 73 6c 6f 74 73 3b 0a 20 = slots;.
1cf0: 20 20 20 20 20 20 20 62 6c 6f 63 6b 2d 3e 66 72 block->fr
1d00: 65 65 53 6c 6f 74 73 20 20 3d 20 73 6c 6f 74 73 eeSlots = slots
1d10: 3b 0a 20 20 20 20 20 20 20 20 62 6c 6f 63 6b 2d ;. block-
1d20: 3e 62 69 74 6d 61 70 73 20 20 20 20 3d 20 62 69 >bitmaps = bi
1d30: 74 6d 61 70 73 3b 0a 20 20 20 20 20 20 20 20 62 tmaps;. b
1d40: 6c 6f 63 6b 2d 3e 66 72 65 65 50 6f 73 20 20 20 lock->freePos
1d50: 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 62 6c = 0;. bl
1d60: 6f 63 6b 2d 3e 66 72 65 65 42 69 74 20 20 20 20 ock->freeBit
1d70: 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 62 6c 6f = 0;. blo
1d80: 63 6b 2d 3e 66 72 65 65 4d 61 73 6b 20 20 20 3d ck->freeMask =
1d90: 20 30 78 38 30 30 30 30 30 30 30 3b 0a 20 20 20 0x80000000;.
1da0: 20 20 20 20 20 62 6c 6f 63 6b 2d 3e 68 61 73 68 block->hash
1db0: 49 6e 64 65 78 31 20 3d 20 2d 31 3b 0a 20 20 20 Index1 = -1;.
1dc0: 20 20 20 20 20 62 6c 6f 63 6b 2d 3e 68 61 73 68 block->hash
1dd0: 4e 65 78 74 31 20 20 3d 20 4e 55 4c 4c 3b 0a 20 Next1 = NULL;.
1de0: 20 20 20 20 20 20 20 62 6c 6f 63 6b 2d 3e 68 61 block->ha
1df0: 73 68 49 6e 64 65 78 32 20 3d 20 2d 31 3b 0a 20 shIndex2 = -1;.
1e00: 20 20 20 20 20 20 20 62 6c 6f 63 6b 2d 3e 68 61 block->ha
1e10: 73 68 4e 65 78 74 32 20 20 3d 20 4e 55 4c 4c 3b shNext2 = NULL;
1e20: 0a 0a 20 20 20 20 20 20 20 20 75 73 65 64 42 69 .. usedBi
1e30: 74 6d 61 70 20 3d 20 28 75 6e 73 69 67 6e 65 64 tmap = (unsigned
1e40: 20 69 6e 74 20 2a 29 20 28 28 63 68 61 72 2a 29 int *) ((char*)
1e50: 62 6c 6f 63 6b 20 2b 20 73 69 7a 65 6f 66 28 64 block + sizeof(d
1e60: 6f 6d 41 6c 6c 6f 63 42 6c 6f 63 6b 29 29 3b 0a omAllocBlock));.
1e70: 20 20 20 20 20 20 20 20 6d 65 6d 73 65 74 28 75 memset(u
1e80: 73 65 64 42 69 74 6d 61 70 2c 20 30 2c 20 62 69 sedBitmap, 0, bi
1e90: 74 6d 61 70 73 20 2a 20 34 29 3b 0a 0a 20 20 20 tmaps * 4);..
1ea0: 20 20 20 20 20 62 69 6e 2d 3e 6e 72 53 6c 6f 74 bin->nrSlot
1eb0: 73 20 20 20 2b 3d 20 73 6c 6f 74 73 3b 0a 20 20 s += slots;.
1ec0: 20 20 20 20 20 20 62 69 6e 2d 3e 66 72 65 65 53 bin->freeS
1ed0: 6c 6f 74 73 20 2b 3d 20 73 6c 6f 74 73 3b 0a 20 lots += slots;.
1ee0: 20 20 20 20 20 20 20 62 69 6e 2d 3e 6e 72 42 6c bin->nrBl
1ef0: 6f 63 6b 73 2b 2b 3b 0a 0a 20 20 20 20 20 20 20 ocks++;..
1f00: 20 62 6c 6f 63 6b 2d 3e 70 72 65 76 20 20 20 20 block->prev
1f10: 20 3d 20 4e 55 4c 4c 3b 20 20 20 20 20 20 20 20 = NULL;
1f20: 20 20 20 20 2f 2a 20 70 72 65 70 65 6e 64 20 74 /* prepend t
1f30: 68 69 73 20 6e 65 77 20 62 6c 6f 63 6b 20 74 6f his new block to
1f40: 20 66 72 65 65 20 6c 69 73 74 20 2a 2f 0a 20 20 free list */.
1f50: 20 20 20 20 20 20 62 6c 6f 63 6b 2d 3e 6e 65 78 block->nex
1f60: 74 20 20 20 20 20 3d 20 62 69 6e 2d 3e 66 72 65 t = bin->fre
1f70: 65 42 6c 6f 63 6b 73 3b 0a 20 20 20 20 20 20 20 eBlocks;.
1f80: 20 62 69 6e 2d 3e 66 72 65 65 42 6c 6f 63 6b 73 bin->freeBlocks
1f90: 20 3d 20 62 6c 6f 63 6b 3b 0a 0a 20 20 20 20 20 = block;..
1fa0: 20 20 20 2f 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d /*-----------
1fb0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1fc0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1fd0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 --------------.
1fe0: 20 20 20 20 20 20 20 7c 20 20 20 65 6e 74 65 72 | enter
1ff0: 20 62 6c 6f 63 6b 20 69 6e 20 27 68 61 73 68 27 block in 'hash'
2000: 20 74 61 62 6c 65 3a 0a 20 20 20 20 20 20 20 20 table:.
2010: 7c 20 20 20 20 20 66 69 72 73 74 20 61 6e 64 20 | first and
2020: 6c 61 73 74 20 6d 65 6d 6f 72 79 20 6c 6f 63 61 last memory loca
2030: 74 69 6f 6e 20 63 6f 75 6c 64 20 68 61 76 65 20 tion could have
2040: 64 69 66 66 65 72 65 6e 74 0a 20 20 20 20 20 20 different.
2050: 20 20 7c 20 20 20 20 20 68 61 73 68 20 65 6e 74 | hash ent
2060: 72 69 65 73 20 64 75 65 20 74 6f 20 64 69 66 66 ries due to diff
2070: 65 72 65 6e 74 20 75 70 70 65 72 20 61 64 64 72 erent upper addr
2080: 65 73 73 20 62 69 74 73 0a 20 20 20 20 20 20 20 ess bits.
2090: 20 5c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d \--------------
20a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
20b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
20c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a 20 20 20 ----------*/.
20d0: 20 20 20 20 20 6d 65 6d 20 3d 20 28 63 68 61 72 mem = (char
20e0: 2a 29 75 73 65 64 42 69 74 6d 61 70 20 2b 20 62 *)usedBitmap + b
20f0: 69 74 6d 61 70 73 20 2a 20 34 3b 0a 20 20 20 20 itmaps * 4;.
2100: 20 20 20 20 66 69 6c 6c 48 61 73 68 54 61 62 6c fillHashTabl
2110: 65 20 28 62 6c 6f 63 6b 2c 20 6d 65 6d 29 3b 0a e (block, mem);.
2120: 20 20 20 20 20 20 20 20 6d 65 6d 20 2b 3d 20 28 mem += (
2130: 73 6c 6f 74 73 2d 31 29 20 2a 20 73 69 7a 65 3b slots-1) * size;
2140: 0a 20 20 20 20 20 20 20 20 66 69 6c 6c 48 61 73 . fillHas
2150: 68 54 61 62 6c 65 20 28 62 6c 6f 63 6b 2c 20 6d hTable (block, m
2160: 65 6d 29 3b 0a 0a 20 20 20 20 7d 20 65 6c 73 65 em);.. } else
2170: 20 7b 0a 20 20 20 20 20 20 20 20 62 6c 6f 63 6b {. block
2180: 20 3d 20 62 69 6e 2d 3e 66 72 65 65 42 6c 6f 63 = bin->freeBloc
2190: 6b 73 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f ks;. }.. /
21a0: 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *---------------
21b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
21c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
21d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
21e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 20 20 20 7c 20 ---------. |
21f0: 20 20 66 69 6e 64 20 66 72 65 65 20 73 6c 6f 74 find free slot
2200: 20 69 6e 20 28 70 61 72 74 69 61 6c 29 20 66 72 in (partial) fr
2210: 65 65 20 62 6c 6f 63 6b 0a 20 20 20 20 7c 0a 20 ee block. |.
2220: 20 20 20 5c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d \------------
2230: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2240: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2250: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2260: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a 20 20 -----------*/.
2270: 20 20 75 73 65 64 42 69 74 6d 61 70 20 3d 20 28 usedBitmap = (
2280: 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 2a 29 20 unsigned int *)
2290: 28 28 63 68 61 72 2a 29 62 6c 6f 63 6b 20 2b 20 ((char*)block +
22a0: 73 69 7a 65 6f 66 28 64 6f 6d 41 6c 6c 6f 63 42 sizeof(domAllocB
22b0: 6c 6f 63 6b 29 29 3b 0a 20 20 20 20 69 20 20 20 lock));. i
22c0: 20 3d 20 62 6c 6f 63 6b 2d 3e 66 72 65 65 50 6f = block->freePo
22d0: 73 3b 20 20 2f 2a 20 73 74 61 72 74 20 61 74 20 s; /* start at
22e0: 6f 6c 64 20 70 6f 73 20 74 6f 20 71 75 69 63 6b old pos to quick
22f0: 6c 79 20 66 69 6e 64 20 61 20 66 72 65 65 20 73 ly find a free s
2300: 6c 6f 74 20 2a 2f 0a 20 20 20 20 6a 20 20 20 20 lot */. j
2310: 3d 20 62 6c 6f 63 6b 2d 3e 66 72 65 65 42 69 74 = block->freeBit
2320: 3b 0a 20 20 20 20 6d 61 73 6b 20 3d 20 62 6c 6f ;. mask = blo
2330: 63 6b 2d 3e 66 72 65 65 4d 61 73 6b 3b 0a 20 20 ck->freeMask;.
2340: 20 20 64 6f 20 7b 0a 20 20 20 20 20 20 20 20 44 do {. D
2350: 42 47 28 66 70 72 69 6e 74 66 28 73 74 64 65 72 BG(fprintf(stder
2360: 72 2c 20 22 6c 6f 6f 6b 69 6e 67 20 25 64 20 73 r, "looking %d s
2370: 6c 6f 74 20 69 3d 25 64 20 6a 3d 25 64 20 25 78 lot i=%d j=%d %x
2380: 20 6d 61 73 6b 20 25 78 5c 6e 22 2c 0a 20 20 20 mask %x\n",.
2390: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
23a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
23b0: 20 20 20 20 20 73 69 7a 65 2c 20 69 2c 20 6a 2c size, i, j,
23c0: 20 75 73 65 64 42 69 74 6d 61 70 5b 69 5d 2c 20 usedBitmap[i],
23d0: 6d 61 73 6b 29 3b 20 29 0a 20 20 20 20 20 20 20 mask); ).
23e0: 20 69 66 20 28 75 73 65 64 42 69 74 6d 61 70 5b if (usedBitmap[
23f0: 69 5d 20 21 3d 20 30 78 46 46 46 46 46 46 46 46 i] != 0xFFFFFFFF
2400: 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 ) {.
2410: 64 6f 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 do {.
2420: 20 20 20 20 20 69 66 20 28 28 75 73 65 64 42 69 if ((usedBi
2430: 74 6d 61 70 5b 69 5d 20 26 20 6d 61 73 6b 29 3d tmap[i] & mask)=
2440: 3d 30 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 =0) {.
2450: 20 20 20 20 20 20 20 20 20 20 44 42 47 28 66 70 DBG(fp
2460: 72 69 6e 74 66 28 73 74 64 65 72 72 2c 20 22 66 rintf(stderr, "f
2470: 6f 75 6e 64 20 66 72 65 65 20 73 6c 6f 74 20 69 ound free slot i
2480: 3d 25 64 20 6a 3d 25 64 20 25 78 20 6d 61 73 6b =%d j=%d %x mask
2490: 20 25 78 5c 6e 22 2c 0a 20 20 20 20 20 20 20 20 %x\n",.
24a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
24b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
24c0: 69 2c 20 6a 2c 20 75 73 65 64 42 69 74 6d 61 70 i, j, usedBitmap
24d0: 5b 69 5d 2c 20 6d 61 73 6b 29 3b 20 29 0a 20 20 [i], mask); ).
24e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
24f0: 20 20 6d 65 6d 20 3d 20 28 28 63 68 61 72 2a 29 mem = ((char*)
2500: 75 73 65 64 42 69 74 6d 61 70 29 20 2b 20 28 34 usedBitmap) + (4
2510: 2a 62 6c 6f 63 6b 2d 3e 62 69 74 6d 61 70 73 29 *block->bitmaps)
2520: 20 2b 20 28 28 69 2a 33 32 29 2b 6a 29 20 2a 20 + ((i*32)+j) *
2530: 73 69 7a 65 3b 0a 20 20 20 20 20 20 20 20 20 20 size;.
2540: 20 20 20 20 20 20 20 20 20 20 75 73 65 64 42 69 usedBi
2550: 74 6d 61 70 5b 69 5d 20 7c 3d 20 6d 61 73 6b 3b tmap[i] |= mask;
2560: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .
2570: 20 20 20 20 20 62 6c 6f 63 6b 2d 3e 66 72 65 65 block->free
2580: 53 6c 6f 74 73 2d 2d 3b 0a 20 20 20 20 20 20 20 Slots--;.
2590: 20 20 20 20 20 20 20 20 20 20 20 20 20 62 69 6e bin
25a0: 2d 3e 66 72 65 65 53 6c 6f 74 73 2d 2d 3b 0a 20 ->freeSlots--;.
25b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
25c0: 20 20 20 69 66 20 28 62 6c 6f 63 6b 2d 3e 66 72 if (block->fr
25d0: 65 65 53 6c 6f 74 73 20 3d 3d 20 30 29 20 7b 0a eeSlots == 0) {.
25e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
25f0: 20 20 20 20 20 20 20 20 44 42 47 28 66 70 72 69 DBG(fpri
2600: 6e 74 66 28 73 74 64 65 72 72 2c 20 22 66 72 65 ntf(stderr, "fre
2610: 65 53 6c 6f 74 73 20 3d 3d 20 30 5c 6e 22 29 3b eSlots == 0\n");
2620: 29 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 )..
2630: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 28 62 if (b
2640: 6c 6f 63 6b 2d 3e 70 72 65 76 20 3d 3d 20 4e 55 lock->prev == NU
2650: 4c 4c 29 20 7b 20 20 20 20 20 20 2f 2a 20 72 65 LL) { /* re
2660: 6d 6f 76 65 20 62 6c 6f 63 6b 20 66 72 6f 6d 20 move block from
2670: 66 72 65 65 20 6c 69 73 74 20 2a 2f 0a 20 20 20 free list */.
2680: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2690: 20 20 20 20 20 20 20 20 20 62 69 6e 2d 3e 66 72 bin->fr
26a0: 65 65 42 6c 6f 63 6b 73 20 20 20 3d 20 62 6c 6f eeBlocks = blo
26b0: 63 6b 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 20 20 ck->next;.
26c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
26d0: 20 20 7d 20 65 6c 73 65 20 7b 0a 20 20 20 20 20 } else {.
26e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
26f0: 20 20 20 20 20 20 20 62 6c 6f 63 6b 2d 3e 70 72 block->pr
2700: 65 76 2d 3e 6e 65 78 74 20 3d 20 62 6c 6f 63 6b ev->next = block
2710: 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 20 20 20 20 ->next;.
2720: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2730: 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 }.
2740: 20 20 20 20 20 20 20 20 20 20 69 66 20 28 62 6c if (bl
2750: 6f 63 6b 2d 3e 6e 65 78 74 29 20 62 6c 6f 63 6b ock->next) block
2760: 2d 3e 6e 65 78 74 2d 3e 70 72 65 76 20 3d 20 62 ->next->prev = b
2770: 6c 6f 63 6b 2d 3e 70 72 65 76 3b 0a 0a 20 20 20 lock->prev;..
2780: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2790: 20 20 20 20 20 62 6c 6f 63 6b 2d 3e 6e 65 78 74 block->next
27a0: 20 20 20 20 20 3d 20 62 69 6e 2d 3e 75 73 65 64 = bin->used
27b0: 42 6c 6f 63 6b 73 3b 20 20 2f 2a 20 61 64 64 20 Blocks; /* add
27c0: 62 6c 6f 63 6b 20 74 6f 20 75 73 65 64 20 6c 69 block to used li
27d0: 73 74 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 st */.
27e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66 if
27f0: 20 28 62 6c 6f 63 6b 2d 3e 6e 65 78 74 29 20 62 (block->next) b
2800: 6c 6f 63 6b 2d 3e 6e 65 78 74 2d 3e 70 72 65 76 lock->next->prev
2810: 20 3d 20 62 6c 6f 63 6b 3b 0a 20 20 20 20 20 20 = block;.
2820: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2830: 20 20 62 6c 6f 63 6b 2d 3e 70 72 65 76 20 20 20 block->prev
2840: 20 20 3d 20 4e 55 4c 4c 3b 0a 20 20 20 20 20 20 = NULL;.
2850: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2860: 20 20 62 69 6e 2d 3e 75 73 65 64 42 6c 6f 63 6b bin->usedBlock
2870: 73 20 3d 20 62 6c 6f 63 6b 3b 0a 0a 20 20 20 20 s = block;..
2880: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2890: 20 20 20 20 2f 2a 20 63 68 65 63 6b 20 63 6f 6e /* check con
28a0: 73 69 73 74 65 6e 63 79 20 2a 2f 0a 20 20 20 20 sistency */.
28b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
28c0: 20 20 20 20 68 61 73 68 65 64 42 6c 6f 63 6b 20 hashedBlock
28d0: 3d 20 62 6c 6f 63 6b 2d 3e 62 69 6e 2d 3e 66 72 = block->bin->fr
28e0: 65 65 42 6c 6f 63 6b 73 3b 0a 20 20 20 20 20 20 eeBlocks;.
28f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2900: 20 20 77 68 69 6c 65 20 28 68 61 73 68 65 64 42 while (hashedB
2910: 6c 6f 63 6b 29 20 7b 0a 20 20 20 20 20 20 20 20 lock) {.
2920: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2930: 20 20 20 20 69 66 20 28 68 61 73 68 65 64 42 6c if (hashedBl
2940: 6f 63 6b 20 3d 3d 20 62 6c 6f 63 6b 29 20 7b 0a ock == block) {.
2950: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2960: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2970: 44 42 47 28 66 70 72 69 6e 74 66 28 73 74 64 65 DBG(fprintf(stde
2980: 72 72 2c 20 22 73 74 72 61 6e 67 65 20 62 6c 6f rr, "strange blo
2990: 63 6b 20 73 74 69 6c 6c 20 69 6e 20 66 72 65 65 ck still in free
29a0: 20 6c 69 73 74 20 5c 6e 22 29 3b 29 0a 20 20 20 list \n");).
29b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
29c0: 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 }.
29d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
29e0: 20 20 20 20 20 20 20 68 61 73 68 65 64 42 6c 6f hashedBlo
29f0: 63 6b 20 3d 20 68 61 73 68 65 64 42 6c 6f 63 6b ck = hashedBlock
2a00: 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 20 20 20 20 ->next;.
2a10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2a20: 7d 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 }..
2a30: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 }.
2a40: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
2a50: 6b 65 65 70 20 66 6f 75 6e 64 20 66 72 65 65 20 keep found free
2a60: 70 6f 73 69 74 69 6f 6e 20 66 6f 72 20 6c 61 74 position for lat
2a70: 65 72 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 er,.
2a80: 20 20 20 20 20 20 20 20 20 2a 20 73 6f 20 74 68 * so th
2a90: 61 74 20 6e 65 78 74 20 73 6c 6f 74 73 20 63 61 at next slots ca
2aa0: 6e 20 62 65 20 66 6f 75 6e 64 20 71 75 69 63 6b n be found quick
2ab0: 6c 79 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 ly.
2ac0: 20 20 20 20 20 20 20 20 2a 2f 0a 20 20 20 20 20 */.
2ad0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 62 b
2ae0: 6c 6f 63 6b 2d 3e 66 72 65 65 50 6f 73 20 20 3d lock->freePos =
2af0: 20 69 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 i;.
2b00: 20 20 20 20 20 20 20 20 6a 2b 2b 3b 20 6d 61 73 j++; mas
2b10: 6b 20 3d 20 6d 61 73 6b 20 3e 3e 20 31 3b 0a 20 k = mask >> 1;.
2b20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2b30: 20 20 20 69 66 20 28 6a 20 3e 3d 20 33 32 29 20 if (j >= 32)
2b40: 7b 20 6a 20 3d 20 30 3b 20 6d 61 73 6b 20 3d 20 { j = 0; mask =
2b50: 30 78 38 30 30 30 30 30 30 30 3b 20 7d 0a 20 20 0x80000000; }.
2b60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2b70: 20 20 62 6c 6f 63 6b 2d 3e 66 72 65 65 42 69 74 block->freeBit
2b80: 20 20 3d 20 6a 3b 0a 20 20 20 20 20 20 20 20 20 = j;.
2b90: 20 20 20 20 20 20 20 20 20 20 20 62 6c 6f 63 6b block
2ba0: 2d 3e 66 72 65 65 4d 61 73 6b 20 3d 20 6d 61 73 ->freeMask = mas
2bb0: 6b 3b 0a 0a 20 20 20 20 20 20 20 20 20 20 20 20 k;..
2bc0: 20 20 20 20 20 20 20 20 54 44 6f 6d 54 68 72 65 TDomThre
2bd0: 61 64 65 64 28 54 63 6c 5f 4d 75 74 65 78 55 6e aded(Tcl_MutexUn
2be0: 6c 6f 63 6b 28 26 62 69 6e 4d 75 74 65 78 29 3b lock(&binMutex);
2bf0: 29 20 2f 2a 20 55 4e 4c 4f 43 4b 20 21 2a 2f 0a ) /* UNLOCK !*/.
2c00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2c10: 20 20 20 20 72 65 74 75 72 6e 20 6d 65 6d 3b 0a return mem;.
2c20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2c30: 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 }.
2c40: 20 20 6a 2b 2b 3b 20 6d 61 73 6b 20 3d 20 6d 61 j++; mask = ma
2c50: 73 6b 20 3e 3e 20 31 3b 0a 20 20 20 20 20 20 20 sk >> 1;.
2c60: 20 20 20 20 20 20 20 20 20 69 66 20 28 6a 20 3e if (j >
2c70: 3d 20 33 32 29 20 7b 20 6a 20 3d 20 30 3b 20 6d = 32) { j = 0; m
2c80: 61 73 6b 20 3d 20 30 78 38 30 30 30 30 30 30 30 ask = 0x80000000
2c90: 3b 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20 ; }.
2ca0: 7d 20 77 68 69 6c 65 20 28 6a 20 21 3d 20 62 6c } while (j != bl
2cb0: 6f 63 6b 2d 3e 66 72 65 65 42 69 74 29 3b 0a 20 ock->freeBit);.
2cc0: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 }.
2cd0: 20 69 2b 2b 3b 0a 20 20 20 20 20 20 20 20 69 66 i++;. if
2ce0: 20 28 69 20 3e 3d 20 62 6c 6f 63 6b 2d 3e 62 69 (i >= block->bi
2cf0: 74 6d 61 70 73 29 20 69 20 3d 20 30 3b 0a 20 20 tmaps) i = 0;.
2d00: 20 20 7d 20 77 68 69 6c 65 20 28 69 20 21 3d 20 } while (i !=
2d10: 62 6c 6f 63 6b 2d 3e 66 72 65 65 50 6f 73 29 3b block->freePos);
2d20: 0a 0a 20 20 20 20 2f 2a 20 54 44 6f 6d 54 68 72 .. /* TDomThr
2d30: 65 61 64 65 64 28 54 63 6c 5f 4d 75 74 65 78 55 eaded(Tcl_MutexU
2d40: 6e 6c 6f 63 6b 28 26 62 69 6e 4d 75 74 65 78 29 nlock(&binMutex)
2d50: 3b 29 20 2a 2f 0a 0a 20 20 20 20 44 42 47 28 66 ;) */.. DBG(f
2d60: 70 72 69 6e 74 66 28 73 74 64 65 72 72 2c 20 22 printf(stderr, "
2d70: 5c 6e 64 6f 6d 41 6c 6c 6f 63 3a 20 63 61 6e 27 \ndomAlloc: can'
2d80: 74 20 68 61 70 70 65 6e 21 20 5c 6e 22 29 3b 29 t happen! \n");)
2d90: 0a 20 20 20 20 2a 28 28 63 68 61 72 2a 29 30 29 . *((char*)0)
2da0: 20 3d 20 30 3b 20 2f 2a 20 55 73 65 20 54 63 6c = 0; /* Use Tcl
2db0: 5f 50 61 6e 69 63 28 29 20 66 6f 72 20 74 68 69 _Panic() for thi
2dc0: 73 20 3f 20 2a 2f 0a 20 20 20 20 72 65 74 75 72 s ? */. retur
2dd0: 6e 20 4e 55 4c 4c 3b 0a 7d 0a 0a 0a 2f 2a 2d 2d n NULL;.}.../*--
2de0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2df0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2e00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2e10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2e20: 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 7c 20 20 20 64 6f ---------.| do
2e30: 6d 46 72 65 65 0a 7c 0a 5c 2d 2d 2d 2d 2d 2d 2d mFree.|.\-------
2e40: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2e50: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2e60: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2e70: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2e80: 2d 2d 2d 2a 2f 0a 76 6f 69 64 0a 64 6f 6d 46 72 ---*/.void.domFr
2e90: 65 65 20 28 0a 20 20 20 20 76 6f 69 64 20 20 2a ee (. void *
2ea0: 20 6d 65 6d 0a 29 0a 7b 0a 20 20 20 20 64 6f 6d mem.).{. dom
2eb0: 41 6c 6c 6f 63 42 6c 6f 63 6b 20 2a 20 62 6c 6f AllocBlock * blo
2ec0: 63 6b 3b 0a 20 20 20 20 64 6f 6d 41 6c 6c 6f 63 ck;. domAlloc
2ed0: 42 6c 6f 63 6b 20 2a 20 68 61 73 68 65 64 42 6c Block * hashedBl
2ee0: 6f 63 6b 3b 0a 20 20 20 20 64 6f 6d 41 6c 6c 6f ock;. domAllo
2ef0: 63 42 6c 6f 63 6b 20 2a 20 70 72 65 76 42 6c 6f cBlock * prevBlo
2f00: 63 6b 3b 0a 20 20 20 20 69 6e 74 20 20 20 20 20 ck;. int
2f10: 20 20 20 20 20 20 20 20 73 6c 6f 74 4e 72 2c 20 slotNr,
2f20: 69 2c 20 66 6f 75 6e 64 49 6e 43 61 63 68 65 3b i, foundInCache;
2f30: 0a 20 20 20 20 75 6e 73 69 67 6e 65 64 20 69 6e . unsigned in
2f40: 74 20 20 2a 20 75 73 65 64 42 69 74 6d 61 70 3b t * usedBitmap;
2f50: 0a 20 20 20 20 75 6e 73 69 67 6e 65 64 20 69 6e . unsigned in
2f60: 74 20 20 20 20 6d 61 73 6b 3b 0a 0a 20 20 20 20 t mask;..
2f70: 44 42 47 28 66 70 72 69 6e 74 66 28 73 74 64 65 DBG(fprintf(stde
2f80: 72 72 2c 20 22 64 6f 6d 46 72 65 65 2e 2e 2e 5c rr, "domFree...\
2f90: 6e 22 29 3b 29 0a 0a 20 20 20 20 69 66 20 28 6d n");).. if (m
2fa0: 65 6d 20 3d 3d 20 4e 55 4c 4c 29 20 72 65 74 75 em == NULL) retu
2fb0: 72 6e 3b 0a 0a 20 20 20 20 2f 2a 2d 2d 2d 2d 2d rn;.. /*-----
2fc0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2fd0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2fe0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 20 20 ------------.
2ff0: 20 20 7c 20 20 20 46 49 58 4d 45 20 28 73 65 65 | FIXME (see
3000: 20 64 6f 6d 41 6c 6c 6f 63 20 63 6f 6d 6d 65 6e domAlloc commen
3010: 74 73 29 0a 20 20 20 20 20 7c 0a 20 20 20 20 20 ts). |.
3020: 5c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d \---------------
3030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3040: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3050: 2d 2a 2f 0a 0a 20 20 20 20 54 44 6f 6d 54 68 72 -*/.. TDomThr
3060: 65 61 64 65 64 28 54 63 6c 5f 4d 75 74 65 78 4c eaded(Tcl_MutexL
3070: 6f 63 6b 28 26 62 69 6e 4d 75 74 65 78 29 3b 29 ock(&binMutex);)
3080: 0a 0a 20 20 20 20 2f 2a 2d 2d 2d 2d 2d 2d 2d 2d .. /*--------
3090: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
30a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
30b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
30c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 20 20 20 -----------.
30d0: 7c 20 20 20 46 69 6e 64 20 74 68 65 20 62 6c 6f | Find the blo
30e0: 63 6b 2c 20 77 68 69 63 68 20 63 6f 72 72 65 73 ck, which corres
30f0: 70 6f 6e 64 73 20 74 6f 20 74 68 65 20 67 69 76 ponds to the giv
3100: 65 6e 20 6d 65 6d 6f 72 79 20 6c 6f 63 61 74 69 en memory locati
3110: 6f 6e 0a 20 20 20 20 7c 0a 20 20 20 20 7c 20 20 on. |. |
3120: 20 2d 20 46 69 72 73 74 20 74 72 79 20 74 6f 20 - First try to
3130: 6c 6f 6f 6b 20 69 6e 20 74 68 65 20 6d 65 6d 6f look in the memo
3140: 72 79 20 72 61 6e 67 65 20 63 61 63 68 65 2e 0a ry range cache..
3150: 20 20 20 20 7c 0a 20 20 20 20 5c 2d 2d 2d 2d 2d |. \-----
3160: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3170: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3180: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3190: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a -------------*/.
31a0: 20 20 20 20 62 6c 6f 63 6b 20 3d 20 4e 55 4c 4c block = NULL
31b0: 3b 0a 20 20 20 20 66 6f 75 6e 64 49 6e 43 61 63 ;. foundInCac
31c0: 68 65 20 3d 20 30 3b 0a 20 20 20 20 66 6f 72 20 he = 0;. for
31d0: 28 69 3d 30 3b 20 69 20 3c 20 43 41 43 48 45 5f (i=0; i < CACHE_
31e0: 53 49 5a 45 3b 20 69 2b 2b 29 20 7b 0a 20 20 20 SIZE; i++) {.
31f0: 20 20 20 20 20 69 66 20 28 28 62 69 6e 73 2e 62 if ((bins.b
3200: 6c 6f 63 6b 43 61 63 68 65 5b 69 5d 20 21 3d 20 lockCache[i] !=
3210: 4e 55 4c 4c 29 20 26 26 0a 20 20 20 20 20 20 20 NULL) &&.
3220: 20 20 20 20 20 28 6d 65 6d 20 3e 20 28 76 6f 69 (mem > (voi
3230: 64 2a 29 28 62 69 6e 73 2e 62 6c 6f 63 6b 43 61 d*)(bins.blockCa
3240: 63 68 65 5b 69 5d 29 29 20 26 26 0a 20 20 20 20 che[i])) &&.
3250: 20 20 20 20 20 20 20 20 28 6d 65 6d 20 3c 20 28 (mem < (
3260: 76 6f 69 64 2a 29 28 62 69 6e 73 2e 62 6c 6f 63 void*)(bins.bloc
3270: 6b 43 61 63 68 65 5b 69 5d 2d 3e 65 6e 64 29 29 kCache[i]->end))
3280: 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 62 ) {. b
3290: 6c 6f 63 6b 20 3d 20 62 69 6e 73 2e 62 6c 6f 63 lock = bins.bloc
32a0: 6b 43 61 63 68 65 5b 69 5d 3b 0a 20 20 20 20 20 kCache[i];.
32b0: 20 20 20 20 20 20 66 6f 75 6e 64 49 6e 43 61 63 foundInCac
32c0: 68 65 20 3d 20 31 3b 0a 20 20 20 20 20 20 20 20 he = 1;.
32d0: 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 break;.
32e0: 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 2f 2a }. }. /*
32f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3300: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3310: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3320: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3330: 2d 2d 2d 0a 20 20 20 20 7c 20 20 20 2d 20 4f 74 ---. | - Ot
3340: 68 65 72 77 69 73 65 20 74 72 79 20 74 6f 20 6c herwise try to l
3350: 6f 6f 6b 75 70 20 63 6f 72 72 65 73 70 6f 6e 64 ookup correspond
3360: 69 6e 67 20 62 6c 6f 63 6b 20 69 6e 20 68 61 73 ing block in has
3370: 68 74 61 62 6c 65 0a 20 20 20 20 7c 0a 20 20 20 htable. |.
3380: 20 5c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d \--------------
3390: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
33a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
33b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
33c0: 2d 2d 2d 2d 2a 2f 0a 20 20 20 20 69 66 20 28 21 ----*/. if (!
33d0: 66 6f 75 6e 64 49 6e 43 61 63 68 65 29 20 7b 0a foundInCache) {.
33e0: 20 20 20 20 20 20 20 20 69 20 3d 20 28 20 28 75 i = ( (u
33f0: 6e 73 69 67 6e 65 64 20 69 6e 74 29 6d 65 6d 20 nsigned int)mem
3400: 3e 3e 20 42 4c 4f 43 4b 5f 53 49 5a 45 5f 42 49 >> BLOCK_SIZE_BI
3410: 54 53 29 20 26 20 42 49 4e 5f 48 41 53 48 5f 4d TS) & BIN_HASH_M
3420: 41 53 4b 3b 0a 20 20 20 20 20 20 20 20 62 6c 6f ASK;. blo
3430: 63 6b 20 3d 20 62 69 6e 73 2e 68 61 73 68 65 64 ck = bins.hashed
3440: 42 6c 6f 63 6b 73 5b 69 5d 3b 0a 20 20 20 20 20 Blocks[i];.
3450: 20 20 20 77 68 69 6c 65 20 28 62 6c 6f 63 6b 20 while (block
3460: 21 3d 20 4e 55 4c 4c 29 20 7b 0a 20 20 20 20 20 != NULL) {.
3470: 20 20 20 20 20 20 20 69 66 20 28 28 6d 65 6d 20 if ((mem
3480: 3e 20 28 76 6f 69 64 2a 29 62 6c 6f 63 6b 29 20 > (void*)block)
3490: 26 26 20 28 6d 65 6d 20 3c 20 28 76 6f 69 64 2a && (mem < (void*
34a0: 29 28 62 6c 6f 63 6b 2d 3e 65 6e 64 29 29 29 20 )(block->end)))
34b0: 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 20 20 20 break;.
34c0: 20 20 20 69 66 20 20 20 20 20 20 28 62 6c 6f 63 if (bloc
34d0: 6b 2d 3e 68 61 73 68 49 6e 64 65 78 31 20 3d 3d k->hashIndex1 ==
34e0: 20 69 29 20 62 6c 6f 63 6b 20 3d 20 62 6c 6f 63 i) block = bloc
34f0: 6b 2d 3e 68 61 73 68 4e 65 78 74 31 3b 0a 20 20 k->hashNext1;.
3500: 20 20 20 20 20 20 20 20 20 20 65 6c 73 65 20 69 else i
3510: 66 20 28 62 6c 6f 63 6b 2d 3e 68 61 73 68 49 6e f (block->hashIn
3520: 64 65 78 32 20 3d 3d 20 69 29 20 62 6c 6f 63 6b dex2 == i) block
3530: 20 3d 20 62 6c 6f 63 6b 2d 3e 68 61 73 68 4e 65 = block->hashNe
3540: 78 74 32 3b 0a 20 20 20 20 20 20 20 20 20 20 20 xt2;.
3550: 20 65 6c 73 65 20 62 6c 6f 63 6b 20 3d 20 4e 55 else block = NU
3560: 4c 4c 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 LL;. }.
3570: 20 20 7d 0a 0a 20 20 20 20 69 66 20 28 62 6c 6f }.. if (blo
3580: 63 6b 20 3d 3d 20 4e 55 4c 4c 29 20 7b 0a 20 20 ck == NULL) {.
3590: 20 20 20 20 20 20 44 42 47 28 66 70 72 69 6e 74 DBG(fprint
35a0: 66 28 73 74 64 65 72 72 2c 20 22 5c 6e 20 75 6e f(stderr, "\n un
35b0: 61 62 6c 65 20 74 6f 20 66 72 65 65 20 6d 65 6d able to free mem
35c0: 20 25 78 20 21 5c 6e 22 2c 20 28 75 6e 73 69 67 %x !\n", (unsig
35d0: 6e 65 64 20 69 6e 74 29 6d 65 6d 29 3b 29 0a 20 ned int)mem);).
35e0: 20 20 20 20 20 20 20 54 44 6f 6d 54 68 72 65 61 TDomThrea
35f0: 64 65 64 28 54 63 6c 5f 4d 75 74 65 78 55 6e 6c ded(Tcl_MutexUnl
3600: 6f 63 6b 28 26 62 69 6e 4d 75 74 65 78 29 3b 29 ock(&binMutex);)
3610: 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 3b . return;
3620: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a 2d 2d . }.. /*--
3630: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3640: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3650: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3660: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3670: 2d 0a 20 20 20 20 7c 20 20 20 63 6c 65 61 72 20 -. | clear
3680: 74 68 65 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 62 the allocation b
3690: 69 74 0a 20 20 20 20 5c 2d 2d 2d 2d 2d 2d 2d 2d it. \--------
36a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
36b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
36c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
36d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a 20 20 20 ----------*/.
36e0: 20 75 73 65 64 42 69 74 6d 61 70 20 3d 20 28 75 usedBitmap = (u
36f0: 6e 73 69 67 6e 65 64 20 69 6e 74 20 2a 29 20 28 nsigned int *) (
3700: 28 63 68 61 72 2a 29 62 6c 6f 63 6b 20 2b 20 73 (char*)block + s
3710: 69 7a 65 6f 66 28 64 6f 6d 41 6c 6c 6f 63 42 6c izeof(domAllocBl
3720: 6f 63 6b 29 29 3b 0a 20 20 20 20 73 6c 6f 74 4e ock));. slotN
3730: 72 20 3d 20 28 20 28 63 68 61 72 2a 29 6d 65 6d r = ( (char*)mem
3740: 20 2d 20 28 63 68 61 72 2a 29 75 73 65 64 42 69 - (char*)usedBi
3750: 74 6d 61 70 20 2d 20 62 6c 6f 63 6b 2d 3e 62 69 tmap - block->bi
3760: 74 6d 61 70 73 2a 34 20 29 20 2f 20 62 6c 6f 63 tmaps*4 ) / bloc
3770: 6b 2d 3e 62 69 6e 2d 3e 73 69 7a 65 3b 0a 20 20 k->bin->size;.
3780: 20 20 44 42 47 28 0a 20 20 20 20 69 66 20 28 73 DBG(. if (s
3790: 6c 6f 74 4e 72 20 3e 3d 20 62 6c 6f 63 6b 2d 3e lotNr >= block->
37a0: 73 6c 6f 74 73 29 20 7b 0a 20 20 20 20 20 20 20 slots) {.
37b0: 20 66 70 72 69 6e 74 66 28 73 74 64 65 72 72 2c fprintf(stderr,
37c0: 20 22 61 73 73 65 72 74 69 6f 6e 20 66 61 69 6c "assertion fail
37d0: 65 64 3a 20 73 6c 6f 74 4e 72 20 3d 20 25 64 20 ed: slotNr = %d
37e0: 5c 6e 22 2c 20 73 6c 6f 74 4e 72 29 3b 0a 20 20 \n", slotNr);.
37f0: 20 20 7d 29 0a 20 20 20 20 69 20 3d 20 73 6c 6f }). i = slo
3800: 74 4e 72 20 3e 3e 20 35 20 3b 20 20 2f 2a 20 73 tNr >> 5 ; /* s
3810: 6c 6f 74 4e 72 20 2f 20 33 32 20 2a 2f 0a 20 20 lotNr / 32 */.
3820: 20 20 6d 61 73 6b 20 3d 20 30 78 38 30 30 30 30 mask = 0x80000
3830: 30 30 30 20 3e 3e 20 28 73 6c 6f 74 4e 72 20 25 000 >> (slotNr %
3840: 20 33 32 29 3b 0a 20 20 20 20 75 73 65 64 42 69 32);. usedBi
3850: 74 6d 61 70 5b 69 5d 20 26 3d 20 7e 6d 61 73 6b tmap[i] &= ~mask
3860: 3b 0a 20 20 20 20 62 6c 6f 63 6b 2d 3e 66 72 65 ;. block->fre
3870: 65 53 6c 6f 74 73 2b 2b 3b 0a 20 20 20 20 62 6c eSlots++;. bl
3880: 6f 63 6b 2d 3e 62 69 6e 2d 3e 66 72 65 65 53 6c ock->bin->freeSl
3890: 6f 74 73 2b 2b 3b 0a 0a 20 20 20 20 44 42 47 28 ots++;.. DBG(
38a0: 0a 20 20 20 20 69 66 20 28 28 62 6c 6f 63 6b 2d . if ((block-
38b0: 3e 66 72 65 65 53 6c 6f 74 73 20 3c 20 31 29 20 >freeSlots < 1)
38c0: 7c 7c 20 28 62 6c 6f 63 6b 2d 3e 66 72 65 65 53 || (block->freeS
38d0: 6c 6f 74 73 20 3e 20 62 6c 6f 63 6b 2d 3e 73 6c lots > block->sl
38e0: 6f 74 73 29 29 20 7b 0a 20 20 20 20 20 20 20 20 ots)) {.
38f0: 66 70 72 69 6e 74 66 28 73 74 64 65 72 72 2c 20 fprintf(stderr,
3900: 22 61 73 73 65 72 74 69 6f 6e 20 66 61 69 6c 65 "assertion faile
3910: 64 3a 20 66 72 65 65 53 6c 6f 74 73 20 3d 20 25 d: freeSlots = %
3920: 64 20 5c 6e 22 2c 20 62 6c 6f 63 6b 2d 3e 66 72 d \n", block->fr
3930: 65 65 53 6c 6f 74 73 29 3b 0a 20 20 20 20 7d 29 eeSlots);. })
3940: 0a 0a 20 20 20 20 2f 2a 2d 2d 2d 2d 2d 2d 2d 2d .. /*--------
3950: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3960: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3970: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3980: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 20 20 20 -----------.
3990: 7c 20 20 20 75 70 64 61 74 65 20 66 72 65 65 2f | update free/
39a0: 75 73 65 64 20 6c 69 73 74 73 0a 20 20 20 20 5c used lists. \
39b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
39c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
39d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
39e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
39f0: 2d 2d 2a 2f 0a 20 20 20 20 69 66 20 28 62 6c 6f --*/. if (blo
3a00: 63 6b 2d 3e 66 72 65 65 53 6c 6f 74 73 20 3d 3d ck->freeSlots ==
3a10: 20 31 29 20 7b 0a 20 20 20 20 20 20 20 20 69 66 1) {. if
3a20: 20 28 62 6c 6f 63 6b 2d 3e 70 72 65 76 20 3d 3d (block->prev ==
3a30: 20 4e 55 4c 4c 29 20 7b 20 20 20 20 20 20 2f 2a NULL) { /*
3a40: 20 72 65 6d 6f 76 65 20 62 6c 6f 63 6b 20 66 72 remove block fr
3a50: 6f 6d 20 75 73 65 64 20 6c 69 73 74 20 2a 2f 0a om used list */.
3a60: 20 20 20 20 20 20 20 20 20 20 20 20 62 6c 6f 63 bloc
3a70: 6b 2d 3e 62 69 6e 2d 3e 75 73 65 64 42 6c 6f 63 k->bin->usedBloc
3a80: 6b 73 20 3d 20 62 6c 6f 63 6b 2d 3e 6e 65 78 74 ks = block->next
3a90: 3b 0a 20 20 20 20 20 20 20 20 7d 20 65 6c 73 65 ;. } else
3aa0: 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 62 {. b
3ab0: 6c 6f 63 6b 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 lock->prev->next
3ac0: 20 3d 20 62 6c 6f 63 6b 2d 3e 6e 65 78 74 3b 0a = block->next;.
3ad0: 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 }.
3ae0: 20 20 69 66 20 28 62 6c 6f 63 6b 2d 3e 6e 65 78 if (block->nex
3af0: 74 29 20 62 6c 6f 63 6b 2d 3e 6e 65 78 74 2d 3e t) block->next->
3b00: 70 72 65 76 20 3d 20 62 6c 6f 63 6b 2d 3e 70 72 prev = block->pr
3b10: 65 76 3b 0a 0a 20 20 20 20 20 20 20 20 62 6c 6f ev;.. blo
3b20: 63 6b 2d 3e 6e 65 78 74 20 20 20 20 20 20 20 20 ck->next
3b30: 20 20 20 20 3d 20 62 6c 6f 63 6b 2d 3e 62 69 6e = block->bin
3b40: 2d 3e 66 72 65 65 42 6c 6f 63 6b 73 3b 20 20 2f ->freeBlocks; /
3b50: 2a 20 61 64 64 20 62 6c 6f 63 6b 20 74 6f 20 66 * add block to f
3b60: 72 65 65 20 6c 69 73 74 20 2a 2f 0a 20 20 20 20 ree list */.
3b70: 20 20 20 20 69 66 20 28 62 6c 6f 63 6b 2d 3e 6e if (block->n
3b80: 65 78 74 29 20 62 6c 6f 63 6b 2d 3e 6e 65 78 74 ext) block->next
3b90: 2d 3e 70 72 65 76 20 3d 20 62 6c 6f 63 6b 3b 0a ->prev = block;.
3ba0: 20 20 20 20 20 20 20 20 62 6c 6f 63 6b 2d 3e 70 block->p
3bb0: 72 65 76 20 20 20 20 20 20 20 20 20 20 20 20 3d rev =
3bc0: 20 4e 55 4c 4c 3b 0a 20 20 20 20 20 20 20 20 62 NULL;. b
3bd0: 6c 6f 63 6b 2d 3e 62 69 6e 2d 3e 66 72 65 65 42 lock->bin->freeB
3be0: 6c 6f 63 6b 73 20 3d 20 62 6c 6f 63 6b 3b 0a 0a locks = block;..
3bf0: 20 20 20 20 20 20 20 20 44 42 47 28 0a 20 20 20 DBG(.
3c00: 20 20 20 20 20 2f 2a 20 63 68 65 63 6b 20 63 6f /* check co
3c10: 6e 73 69 73 74 65 6e 63 79 20 2a 2f 0a 20 20 20 nsistency */.
3c20: 20 20 20 20 20 68 61 73 68 65 64 42 6c 6f 63 6b hashedBlock
3c30: 20 3d 20 62 6c 6f 63 6b 2d 3e 62 69 6e 2d 3e 75 = block->bin->u
3c40: 73 65 64 42 6c 6f 63 6b 73 3b 0a 20 20 20 20 20 sedBlocks;.
3c50: 20 20 20 77 68 69 6c 65 20 28 68 61 73 68 65 64 while (hashed
3c60: 42 6c 6f 63 6b 29 20 7b 0a 20 20 20 20 20 20 20 Block) {.
3c70: 20 20 20 20 20 69 66 20 28 68 61 73 68 65 64 42 if (hashedB
3c80: 6c 6f 63 6b 20 3d 3d 20 62 6c 6f 63 6b 29 20 7b lock == block) {
3c90: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 .
3ca0: 20 66 70 72 69 6e 74 66 28 73 74 64 65 72 72 2c fprintf(stderr,
3cb0: 20 22 73 74 72 61 6e 67 65 20 62 6c 6f 63 6b 20 "strange block
3cc0: 73 74 69 6c 6c 20 69 6e 20 75 73 65 64 20 6c 69 still in used li
3cd0: 73 74 20 5c 6e 22 29 3b 0a 20 20 20 20 20 20 20 st \n");.
3ce0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 }.
3cf0: 20 20 20 68 61 73 68 65 64 42 6c 6f 63 6b 20 3d hashedBlock =
3d00: 20 68 61 73 68 65 64 42 6c 6f 63 6b 2d 3e 6e 65 hashedBlock->ne
3d10: 78 74 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 xt;. }.
3d20: 20 20 20 20 20 20 29 0a 20 20 20 20 7d 0a 0a 20 ). }..
3d30: 20 20 20 2f 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d /*-----------
3d40: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3d50: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3d60: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3d70: 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 20 20 20 7c 20 20 --------. |
3d80: 20 66 72 65 65 20 74 68 65 20 77 68 6f 6c 65 20 free the whole
3d90: 62 6c 6f 63 6b 2c 20 77 68 65 6e 20 61 6c 6c 20 block, when all
3da0: 73 6c 6f 74 73 20 61 72 65 20 66 72 65 65 64 0a slots are freed.
3db0: 20 20 20 20 5c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d \-----------
3dc0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3dd0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3de0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3df0: 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a 20 20 20 20 69 66 -------*/. if
3e00: 20 28 62 6c 6f 63 6b 2d 3e 66 72 65 65 53 6c 6f (block->freeSlo
3e10: 74 73 20 3d 3d 20 62 6c 6f 63 6b 2d 3e 73 6c 6f ts == block->slo
3e20: 74 73 29 20 7b 0a 0a 20 20 20 20 20 20 20 20 44 ts) {.. D
3e30: 42 47 28 66 70 72 69 6e 74 66 28 73 74 64 65 72 BG(fprintf(stder
3e40: 72 2c 20 22 62 6c 6f 63 6b 20 63 6f 6d 70 6c 65 r, "block comple
3e50: 74 65 6c 79 20 66 72 65 65 64 20 25 78 5c 6e 22 tely freed %x\n"
3e60: 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ,.
3e70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 28 (
3e80: 75 6e 73 69 67 6e 65 64 20 69 6e 74 29 62 6c 6f unsigned int)blo
3e90: 63 6b 29 3b 29 0a 0a 20 20 20 20 20 20 20 20 69 ck);).. i
3ea0: 66 20 28 62 6c 6f 63 6b 2d 3e 70 72 65 76 20 3d f (block->prev =
3eb0: 3d 20 4e 55 4c 4c 29 20 7b 20 20 20 20 20 20 2f = NULL) { /
3ec0: 2a 20 72 65 6d 6f 76 65 20 62 6c 6f 63 6b 20 66 * remove block f
3ed0: 72 6f 6d 20 66 72 65 65 20 6c 69 73 74 20 2a 2f rom free list */
3ee0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 62 6c 6f . blo
3ef0: 63 6b 2d 3e 62 69 6e 2d 3e 66 72 65 65 42 6c 6f ck->bin->freeBlo
3f00: 63 6b 73 20 3d 20 62 6c 6f 63 6b 2d 3e 6e 65 78 cks = block->nex
3f10: 74 3b 0a 20 20 20 20 20 20 20 20 7d 20 65 6c 73 t;. } els
3f20: 65 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 e {.
3f30: 62 6c 6f 63 6b 2d 3e 70 72 65 76 2d 3e 6e 65 78 block->prev->nex
3f40: 74 20 3d 20 62 6c 6f 63 6b 2d 3e 6e 65 78 74 3b t = block->next;
3f50: 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 . }.
3f60: 20 20 20 69 66 20 28 62 6c 6f 63 6b 2d 3e 6e 65 if (block->ne
3f70: 78 74 29 20 62 6c 6f 63 6b 2d 3e 6e 65 78 74 2d xt) block->next-
3f80: 3e 70 72 65 76 20 3d 20 62 6c 6f 63 6b 2d 3e 70 >prev = block->p
3f90: 72 65 76 3b 0a 0a 20 20 20 20 20 20 20 20 62 6c rev;.. bl
3fa0: 6f 63 6b 2d 3e 62 69 6e 2d 3e 6e 72 53 6c 6f 74 ock->bin->nrSlot
3fb0: 73 20 20 20 2d 3d 20 62 6c 6f 63 6b 2d 3e 73 6c s -= block->sl
3fc0: 6f 74 73 3b 0a 20 20 20 20 20 20 20 20 62 6c 6f ots;. blo
3fd0: 63 6b 2d 3e 62 69 6e 2d 3e 66 72 65 65 53 6c 6f ck->bin->freeSlo
3fe0: 74 73 20 2d 3d 20 62 6c 6f 63 6b 2d 3e 73 6c 6f ts -= block->slo
3ff0: 74 73 3b 0a 20 20 20 20 20 20 20 20 62 6c 6f 63 ts;. bloc
4000: 6b 2d 3e 62 69 6e 2d 3e 6e 72 42 6c 6f 63 6b 73 k->bin->nrBlocks
4010: 2d 2d 3b 0a 0a 20 20 20 20 20 20 20 20 2f 2a 2d --;.. /*-
4020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4040: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4050: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4060: 2d 2d 2d 0a 20 20 20 20 20 20 20 20 7c 20 20 20 ---. |
4070: 72 65 6d 6f 76 65 20 62 6c 6f 63 6b 20 66 72 6f remove block fro
4080: 6d 20 28 74 77 6f 29 20 68 61 73 68 20 6c 69 73 m (two) hash lis
4090: 74 73 0a 20 20 20 20 20 20 20 20 5c 2d 2d 2d 2d ts. \----
40a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
40b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
40c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
40d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2a ---------------*
40e0: 2f 0a 20 20 20 20 20 20 20 20 69 20 3d 20 62 6c /. i = bl
40f0: 6f 63 6b 2d 3e 68 61 73 68 49 6e 64 65 78 31 3b ock->hashIndex1;
4100: 0a 20 20 20 20 20 20 20 20 69 66 20 28 69 20 21 . if (i !
4110: 3d 20 2d 31 29 20 7b 0a 20 20 20 20 20 20 20 20 = -1) {.
4120: 20 20 20 20 44 42 47 28 66 70 72 69 6e 74 66 28 DBG(fprintf(
4130: 73 74 64 65 72 72 2c 20 22 72 65 6d 6f 76 65 20 stderr, "remove
4140: 66 72 6f 6d 20 68 61 73 68 20 6c 69 73 74 20 25 from hash list %
4150: 64 20 5c 6e 22 2c 20 69 29 3b 29 0a 20 20 20 20 d \n", i);).
4160: 20 20 20 20 20 20 20 20 70 72 65 76 42 6c 6f 63 prevBloc
4170: 6b 20 3d 20 4e 55 4c 4c 3b 0a 20 20 20 20 20 20 k = NULL;.
4180: 20 20 20 20 20 20 68 61 73 68 65 64 42 6c 6f 63 hashedBloc
4190: 6b 20 3d 20 62 69 6e 73 2e 68 61 73 68 65 64 42 k = bins.hashedB
41a0: 6c 6f 63 6b 73 5b 69 5d 3b 0a 20 20 20 20 20 20 locks[i];.
41b0: 20 20 20 20 20 20 77 68 69 6c 65 20 28 68 61 73 while (has
41c0: 68 65 64 42 6c 6f 63 6b 29 20 7b 0a 20 20 20 20 hedBlock) {.
41d0: 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20 28 if (
41e0: 68 61 73 68 65 64 42 6c 6f 63 6b 20 3d 3d 20 62 hashedBlock == b
41f0: 6c 6f 63 6b 29 20 62 72 65 61 6b 3b 0a 20 20 20 lock) break;.
4200: 20 20 20 20 20 20 20 20 20 20 20 20 20 70 72 65 pre
4210: 76 42 6c 6f 63 6b 20 3d 20 68 61 73 68 65 64 42 vBlock = hashedB
4220: 6c 6f 63 6b 3b 0a 20 20 20 20 20 20 20 20 20 20 lock;.
4230: 20 20 20 20 20 20 69 66 20 20 20 20 20 20 28 68 if (h
4240: 61 73 68 65 64 42 6c 6f 63 6b 2d 3e 68 61 73 68 ashedBlock->hash
4250: 49 6e 64 65 78 31 20 3d 3d 20 69 29 20 68 61 73 Index1 == i) has
4260: 68 65 64 42 6c 6f 63 6b 20 3d 20 68 61 73 68 65 hedBlock = hashe
4270: 64 42 6c 6f 63 6b 2d 3e 68 61 73 68 4e 65 78 74 dBlock->hashNext
4280: 31 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 1;.
4290: 20 20 20 65 6c 73 65 20 69 66 20 28 68 61 73 68 else if (hash
42a0: 65 64 42 6c 6f 63 6b 2d 3e 68 61 73 68 49 6e 64 edBlock->hashInd
42b0: 65 78 32 20 3d 3d 20 69 29 20 68 61 73 68 65 64 ex2 == i) hashed
42c0: 42 6c 6f 63 6b 20 3d 20 68 61 73 68 65 64 42 6c Block = hashedBl
42d0: 6f 63 6b 2d 3e 68 61 73 68 4e 65 78 74 32 3b 0a ock->hashNext2;.
42e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
42f0: 65 6c 73 65 20 68 61 73 68 65 64 42 6c 6f 63 6b else hashedBlock
4300: 20 3d 20 4e 55 4c 4c 3b 0a 20 20 20 20 20 20 20 = NULL;.
4310: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 }.
4320: 20 20 20 69 66 20 28 70 72 65 76 42 6c 6f 63 6b if (prevBlock
4330: 20 3d 3d 20 4e 55 4c 4c 29 20 7b 0a 20 20 20 20 == NULL) {.
4340: 20 20 20 20 20 20 20 20 20 20 20 20 62 69 6e 73 bins
4350: 2e 68 61 73 68 65 64 42 6c 6f 63 6b 73 5b 69 5d .hashedBlocks[i]
4360: 20 3d 20 62 6c 6f 63 6b 2d 3e 68 61 73 68 4e 65 = block->hashNe
4370: 78 74 31 3b 0a 20 20 20 20 20 20 20 20 20 20 20 xt1;.
4380: 20 7d 20 65 6c 73 65 20 7b 0a 20 20 20 20 20 20 } else {.
4390: 20 20 20 20 20 20 20 20 20 20 69 66 20 20 20 20 if
43a0: 20 20 28 70 72 65 76 42 6c 6f 63 6b 2d 3e 68 61 (prevBlock->ha
43b0: 73 68 49 6e 64 65 78 31 20 3d 3d 20 69 29 20 70 shIndex1 == i) p
43c0: 72 65 76 42 6c 6f 63 6b 2d 3e 68 61 73 68 4e 65 revBlock->hashNe
43d0: 78 74 31 20 3d 20 62 6c 6f 63 6b 2d 3e 68 61 73 xt1 = block->has
43e0: 68 4e 65 78 74 31 3b 0a 20 20 20 20 20 20 20 20 hNext1;.
43f0: 20 20 20 20 20 20 20 20 65 6c 73 65 20 69 66 20 else if
4400: 28 70 72 65 76 42 6c 6f 63 6b 2d 3e 68 61 73 68 (prevBlock->hash
4410: 49 6e 64 65 78 32 20 3d 3d 20 69 29 20 70 72 65 Index2 == i) pre
4420: 76 42 6c 6f 63 6b 2d 3e 68 61 73 68 4e 65 78 74 vBlock->hashNext
4430: 32 20 3d 20 62 6c 6f 63 6b 2d 3e 68 61 73 68 4e 2 = block->hashN
4440: 65 78 74 31 3b 0a 20 20 20 20 20 20 20 20 20 20 ext1;.
4450: 20 20 7d 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 }. }.
4460: 20 20 20 20 20 20 69 20 3d 20 62 6c 6f 63 6b 2d i = block-
4470: 3e 68 61 73 68 49 6e 64 65 78 32 3b 0a 20 20 20 >hashIndex2;.
4480: 20 20 20 20 20 69 66 20 28 69 20 21 3d 20 2d 31 if (i != -1
4490: 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 ) {.
44a0: 44 42 47 28 66 70 72 69 6e 74 66 28 73 74 64 65 DBG(fprintf(stde
44b0: 72 72 2c 20 22 72 65 6d 6f 76 65 20 66 72 6f 6d rr, "remove from
44c0: 20 68 61 73 68 20 6c 69 73 74 20 25 64 20 5c 6e hash list %d \n
44d0: 22 2c 20 69 29 3b 29 0a 20 20 20 20 20 20 20 20 ", i);).
44e0: 20 20 20 20 70 72 65 76 42 6c 6f 63 6b 20 3d 20 prevBlock =
44f0: 4e 55 4c 4c 3b 0a 20 20 20 20 20 20 20 20 20 20 NULL;.
4500: 20 20 68 61 73 68 65 64 42 6c 6f 63 6b 20 3d 20 hashedBlock =
4510: 62 69 6e 73 2e 68 61 73 68 65 64 42 6c 6f 63 6b bins.hashedBlock
4520: 73 5b 69 5d 3b 0a 20 20 20 20 20 20 20 20 20 20 s[i];.
4530: 20 20 77 68 69 6c 65 20 28 68 61 73 68 65 64 42 while (hashedB
4540: 6c 6f 63 6b 29 20 7b 0a 20 20 20 20 20 20 20 20 lock) {.
4550: 20 20 20 20 20 20 20 20 69 66 20 28 68 61 73 68 if (hash
4560: 65 64 42 6c 6f 63 6b 20 3d 3d 20 62 6c 6f 63 6b edBlock == block
4570: 29 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 20 ) break;.
4580: 20 20 20 20 20 20 20 20 20 70 72 65 76 42 6c 6f prevBlo
4590: 63 6b 20 3d 20 68 61 73 68 65 64 42 6c 6f 63 6b ck = hashedBlock
45a0: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ;.
45b0: 20 20 69 66 20 20 20 20 20 20 28 68 61 73 68 65 if (hashe
45c0: 64 42 6c 6f 63 6b 2d 3e 68 61 73 68 49 6e 64 65 dBlock->hashInde
45d0: 78 31 20 3d 3d 20 69 29 20 68 61 73 68 65 64 42 x1 == i) hashedB
45e0: 6c 6f 63 6b 20 3d 20 68 61 73 68 65 64 42 6c 6f lock = hashedBlo
45f0: 63 6b 2d 3e 68 61 73 68 4e 65 78 74 31 3b 0a 20 ck->hashNext1;.
4600: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 65 e
4610: 6c 73 65 20 69 66 20 28 68 61 73 68 65 64 42 6c lse if (hashedBl
4620: 6f 63 6b 2d 3e 68 61 73 68 49 6e 64 65 78 32 20 ock->hashIndex2
4630: 3d 3d 20 69 29 20 68 61 73 68 65 64 42 6c 6f 63 == i) hashedBloc
4640: 6b 20 3d 20 68 61 73 68 65 64 42 6c 6f 63 6b 2d k = hashedBlock-
4650: 3e 68 61 73 68 4e 65 78 74 32 3b 0a 20 20 20 20 >hashNext2;.
4660: 20 20 20 20 20 20 20 20 20 20 20 20 65 6c 73 65 else
4670: 20 68 61 73 68 65 64 42 6c 6f 63 6b 20 3d 20 4e hashedBlock = N
4680: 55 4c 4c 3b 0a 20 20 20 20 20 20 20 20 20 20 20 ULL;.
4690: 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 }. i
46a0: 66 20 28 70 72 65 76 42 6c 6f 63 6b 20 3d 3d 20 f (prevBlock ==
46b0: 4e 55 4c 4c 29 20 7b 0a 20 20 20 20 20 20 20 20 NULL) {.
46c0: 20 20 20 20 20 20 20 20 62 69 6e 73 2e 68 61 73 bins.has
46d0: 68 65 64 42 6c 6f 63 6b 73 5b 69 5d 20 3d 20 62 hedBlocks[i] = b
46e0: 6c 6f 63 6b 2d 3e 68 61 73 68 4e 65 78 74 32 3b lock->hashNext2;
46f0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 7d 20 65 . } e
4700: 6c 73 65 20 7b 0a 20 20 20 20 20 20 20 20 20 20 lse {.
4710: 20 20 20 20 20 20 69 66 20 20 20 20 20 20 28 70 if (p
4720: 72 65 76 42 6c 6f 63 6b 2d 3e 68 61 73 68 49 6e revBlock->hashIn
4730: 64 65 78 31 20 3d 3d 20 69 29 20 70 72 65 76 42 dex1 == i) prevB
4740: 6c 6f 63 6b 2d 3e 68 61 73 68 4e 65 78 74 31 20 lock->hashNext1
4750: 3d 20 62 6c 6f 63 6b 2d 3e 68 61 73 68 4e 65 78 = block->hashNex
4760: 74 32 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 t2;.
4770: 20 20 20 20 65 6c 73 65 20 69 66 20 28 70 72 65 else if (pre
4780: 76 42 6c 6f 63 6b 2d 3e 68 61 73 68 49 6e 64 65 vBlock->hashInde
4790: 78 32 20 3d 3d 20 69 29 20 70 72 65 76 42 6c 6f x2 == i) prevBlo
47a0: 63 6b 2d 3e 68 61 73 68 4e 65 78 74 32 20 3d 20 ck->hashNext2 =
47b0: 62 6c 6f 63 6b 2d 3e 68 61 73 68 4e 65 78 74 32 block->hashNext2
47c0: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a ;. }.
47d0: 20 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 }..
47e0: 20 20 20 2f 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d /*-----------
47f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4800: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4810: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 20 20 20 -----------.
4820: 20 20 20 20 7c 20 20 20 72 65 6d 6f 76 65 20 62 | remove b
4830: 6c 6f 63 6b 20 66 72 6f 6d 20 63 61 63 68 65 2c lock from cache,
4840: 20 69 66 20 66 6f 75 6e 64 0a 20 20 20 20 20 20 if found.
4850: 20 20 5c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d \-------------
4860: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4870: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4880: 2d 2d 2d 2d 2d 2d 2d 2d 2a 2f 0a 20 20 20 20 20 --------*/.
4890: 20 20 20 66 6f 72 20 28 69 3d 30 3b 20 69 20 3c for (i=0; i <
48a0: 20 43 41 43 48 45 5f 53 49 5a 45 3b 20 69 2b 2b CACHE_SIZE; i++
48b0: 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 ) {.
48c0: 69 66 20 28 62 69 6e 73 2e 62 6c 6f 63 6b 43 61 if (bins.blockCa
48d0: 63 68 65 5b 69 5d 20 3d 3d 20 62 6c 6f 63 6b 29 che[i] == block)
48e0: 20 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 {.
48f0: 20 20 20 62 69 6e 73 2e 62 6c 6f 63 6b 43 61 63 bins.blockCac
4900: 68 65 5b 69 5d 20 3d 20 4e 55 4c 4c 3b 0a 20 20 he[i] = NULL;.
4910: 20 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 }.
4920: 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 20 20 44 }.. D
4930: 42 47 28 0a 20 20 20 20 20 20 20 20 2f 2a 20 63 BG(. /* c
4940: 68 65 63 6b 20 63 6f 6e 73 69 73 74 65 6e 63 79 heck consistency
4950: 20 2a 2f 0a 20 20 20 20 20 20 20 20 66 6f 72 20 */. for
4960: 28 69 3d 30 3b 20 69 20 3c 20 62 6c 6f 63 6b 2d (i=0; i < block-
4970: 3e 62 69 74 6d 61 70 73 3b 20 69 2b 2b 29 20 7b >bitmaps; i++) {
4980: 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20 . if
4990: 28 75 73 65 64 42 69 74 6d 61 70 5b 69 5d 20 21 (usedBitmap[i] !
49a0: 3d 20 30 29 20 7b 0a 20 20 20 20 20 20 20 20 20 = 0) {.
49b0: 20 20 20 20 20 20 20 66 70 72 69 6e 74 66 28 73 fprintf(s
49c0: 74 64 65 72 72 2c 20 22 73 74 72 61 6e 67 65 20 tderr, "strange
49d0: 62 69 74 6d 61 70 20 25 64 20 69 73 20 25 78 20 bitmap %d is %x
49e0: 5c 6e 22 2c 20 69 2c 20 75 73 65 64 42 69 74 6d \n", i, usedBitm
49f0: 61 70 5b 69 5d 29 3b 0a 20 20 20 20 20 20 20 20 ap[i]);.
4a00: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 7d 0a }. }.
4a10: 20 20 20 20 20 20 20 20 66 6f 72 20 28 69 3d 30 for (i=0
4a20: 3b 20 69 20 3c 20 42 49 4e 5f 48 41 53 48 5f 53 ; i < BIN_HASH_S
4a30: 49 5a 45 3b 20 69 2b 2b 29 20 7b 0a 20 20 20 20 IZE; i++) {.
4a40: 20 20 20 20 20 20 20 20 68 61 73 68 65 64 42 6c hashedBl
4a50: 6f 63 6b 20 3d 20 62 69 6e 73 2e 68 61 73 68 65 ock = bins.hashe
4a60: 64 42 6c 6f 63 6b 73 5b 69 5d 3b 0a 20 20 20 20 dBlocks[i];.
4a70: 20 20 20 20 20 20 20 20 77 68 69 6c 65 20 28 68 while (h
4a80: 61 73 68 65 64 42 6c 6f 63 6b 29 20 7b 0a 20 20 ashedBlock) {.
4a90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66 if
4aa0: 20 28 68 61 73 68 65 64 42 6c 6f 63 6b 20 3d 3d (hashedBlock ==
4ab0: 20 62 6c 6f 63 6b 29 20 7b 0a 20 20 20 20 20 20 block) {.
4ac0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66 70 fp
4ad0: 72 69 6e 74 66 28 73 74 64 65 72 72 2c 20 22 73 rintf(stderr, "s
4ae0: 74 72 61 6e 67 65 20 62 6c 6f 63 6b 20 25 64 20 trange block %d
4af0: 73 74 69 6c 6c 20 69 6e 20 68 61 73 68 20 74 61 still in hash ta
4b00: 62 6c 65 20 5c 6e 22 2c 20 69 29 3b 0a 20 20 20 ble \n", i);.
4b10: 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a 20 }.
4b20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 i
4b30: 66 20 20 20 20 20 20 28 68 61 73 68 65 64 42 6c f (hashedBl
4b40: 6f 63 6b 2d 3e 68 61 73 68 49 6e 64 65 78 31 20 ock->hashIndex1
4b50: 3d 3d 20 69 29 20 68 61 73 68 65 64 42 6c 6f 63 == i) hashedBloc
4b60: 6b 20 3d 20 68 61 73 68 65 64 42 6c 6f 63 6b 2d k = hashedBlock-
4b70: 3e 68 61 73 68 4e 65 78 74 31 3b 0a 20 20 20 20 >hashNext1;.
4b80: 20 20 20 20 20 20 20 20 20 20 20 20 65 6c 73 65 else
4b90: 20 69 66 20 28 68 61 73 68 65 64 42 6c 6f 63 6b if (hashedBlock
4ba0: 2d 3e 68 61 73 68 49 6e 64 65 78 32 20 3d 3d 20 ->hashIndex2 ==
4bb0: 69 29 20 68 61 73 68 65 64 42 6c 6f 63 6b 20 3d i) hashedBlock =
4bc0: 20 68 61 73 68 65 64 42 6c 6f 63 6b 2d 3e 68 61 hashedBlock->ha
4bd0: 73 68 4e 65 78 74 32 3b 0a 20 20 20 20 20 20 20 shNext2;.
4be0: 20 20 20 20 20 20 20 20 20 65 6c 73 65 20 68 61 else ha
4bf0: 73 68 65 64 42 6c 6f 63 6b 20 3d 20 4e 55 4c 4c shedBlock = NULL
4c00: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a ;. }.
4c10: 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 }.
4c20: 20 20 68 61 73 68 65 64 42 6c 6f 63 6b 20 3d 20 hashedBlock =
4c30: 62 6c 6f 63 6b 2d 3e 62 69 6e 2d 3e 66 72 65 65 block->bin->free
4c40: 42 6c 6f 63 6b 73 3b 0a 20 20 20 20 20 20 20 20 Blocks;.
4c50: 77 68 69 6c 65 20 28 68 61 73 68 65 64 42 6c 6f while (hashedBlo
4c60: 63 6b 29 20 7b 0a 20 20 20 20 20 20 20 20 20 20 ck) {.
4c70: 20 20 69 66 20 28 68 61 73 68 65 64 42 6c 6f 63 if (hashedBloc
4c80: 6b 20 3d 3d 20 62 6c 6f 63 6b 29 20 7b 0a 20 20 k == block) {.
4c90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66 70 fp
4ca0: 72 69 6e 74 66 28 73 74 64 65 72 72 2c 20 22 73 rintf(stderr, "s
4cb0: 74 72 61 6e 67 65 20 62 6c 6f 63 6b 20 73 74 69 trange block sti
4cc0: 6c 6c 20 69 6e 20 66 72 65 65 20 6c 69 73 74 20 ll in free list
4cd0: 5c 6e 22 29 3b 0a 20 20 20 20 20 20 20 20 20 20 \n");.
4ce0: 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20 20 }.
4cf0: 68 61 73 68 65 64 42 6c 6f 63 6b 20 3d 20 68 61 hashedBlock = ha
4d00: 73 68 65 64 42 6c 6f 63 6b 2d 3e 6e 65 78 74 3b shedBlock->next;
4d10: 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 . }.
4d20: 20 20 20 68 61 73 68 65 64 42 6c 6f 63 6b 20 3d hashedBlock =
4d30: 20 62 6c 6f 63 6b 2d 3e 62 69 6e 2d 3e 75 73 65 block->bin->use
4d40: 64 42 6c 6f 63 6b 73 3b 0a 20 20 20 20 20 20 20 dBlocks;.
4d50: 20 77 68 69 6c 65 20 28 68 61 73 68 65 64 42 6c while (hashedBl
4d60: 6f 63 6b 29 20 7b 0a 20 20 20 20 20 20 20 20 20 ock) {.
4d70: 20 20 20 69 66 20 28 68 61 73 68 65 64 42 6c 6f if (hashedBlo
4d80: 63 6b 20 3d 3d 20 62 6c 6f 63 6b 29 20 7b 0a 20 ck == block) {.
4d90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66 f
4da0: 70 72 69 6e 74 66 28 73 74 64 65 72 72 2c 20 22 printf(stderr, "
4db0: 73 74 72 61 6e 67 65 20 62 6c 6f 63 6b 20 73 74 strange block st
4dc0: 69 6c 6c 20 69 6e 20 75 73 65 64 20 6c 69 73 74 ill in used list
4dd0: 20 5c 6e 22 29 3b 0a 20 20 20 20 20 20 20 20 20 \n");.
4de0: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 20 20 20 }.
4df0: 20 68 61 73 68 65 64 42 6c 6f 63 6b 20 3d 20 68 hashedBlock = h
4e00: 61 73 68 65 64 42 6c 6f 63 6b 2d 3e 6e 65 78 74 ashedBlock->next
4e10: 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 ;. }.
4e20: 20 20 20 20 29 0a 20 20 20 20 20 20 20 20 66 72 ). fr
4e30: 65 65 28 28 63 68 61 72 2a 29 62 6c 6f 63 6b 29 ee((char*)block)
4e40: 3b 0a 0a 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a ;.. } else {.
4e50: 20 20 20 20 20 20 20 20 2f 2a 2d 2d 2d 2d 2d 2d /*------
4e60: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4e70: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4e80: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4e90: 2d 2d 2d 2d 2d 0a 20 20 20 20 20 20 20 20 7c 20 -----. |
4ea0: 20 20 75 70 64 61 74 65 20 63 61 63 68 65 0a 20 update cache.
4eb0: 20 20 20 20 20 20 20 5c 2d 2d 2d 2d 2d 2d 2d 2d \--------
4ec0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4ed0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4ee0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4ef0: 2d 2d 2a 2f 0a 20 20 20 20 20 20 20 20 69 66 20 --*/. if
4f00: 28 21 66 6f 75 6e 64 49 6e 43 61 63 68 65 29 20 (!foundInCache)
4f10: 7b 0a 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a {. /*
4f20: 20 72 65 6d 6f 76 65 20 6f 6c 64 65 73 74 20 65 remove oldest e
4f30: 6e 74 72 79 20 61 6e 64 20 61 64 64 20 74 68 69 ntry and add thi
4f40: 73 20 62 6c 6f 63 6b 20 2a 2f 0a 20 20 20 20 20 s block */.
4f50: 20 20 20 20 20 20 20 66 6f 72 20 28 69 3d 31 3b for (i=1;
4f60: 20 69 20 3c 20 43 41 43 48 45 5f 53 49 5a 45 3b i < CACHE_SIZE;
4f70: 20 69 2b 2b 29 20 7b 0a 20 20 20 20 20 20 20 20 i++) {.
4f80: 20 20 20 20 20 20 20 20 62 69 6e 73 2e 62 6c 6f bins.blo
4f90: 63 6b 43 61 63 68 65 5b 69 2d 31 5d 20 3d 20 62 ckCache[i-1] = b
4fa0: 69 6e 73 2e 62 6c 6f 63 6b 43 61 63 68 65 5b 69 ins.blockCache[i
4fb0: 5d 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 7d ];. }
4fc0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 62 69 6e . bin
4fd0: 73 2e 62 6c 6f 63 6b 43 61 63 68 65 5b 43 41 43 s.blockCache[CAC
4fe0: 48 45 5f 53 49 5a 45 2d 31 5d 20 3d 20 62 6c 6f HE_SIZE-1] = blo
4ff0: 63 6b 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 ck;. }.
5000: 20 20 7d 0a 20 20 20 20 54 44 6f 6d 54 68 72 65 }. TDomThre
5010: 61 64 65 64 28 54 63 6c 5f 4d 75 74 65 78 55 6e aded(Tcl_MutexUn
5020: 6c 6f 63 6b 28 26 62 69 6e 4d 75 74 65 78 29 3b lock(&binMutex);
5030: 29 20 2f 2a 20 55 4e 4c 4f 43 4b 20 21 2a 2f 0a ) /* UNLOCK !*/.
5040: 7d 0a }.