UnsafeFreeList: CEDAR DEFINITIONS LOCKS ct USING ct: Context ~ BEGIN Context: TYPE = REF ContextRep; ContextRep: PRIVATE TYPE = MONITORED RECORD [ lim: INT ¬ 0, --counter for how many more elements can be include in list. first: POINTER TO Block ¬ NIL, --front of list; where elements are removed last: POINTER TO Block ¬ NIL --tail of list; where new free elements are queued ]; Block: PRIVATE TYPE = RECORD [next: POINTER TO Block <>]; NewContext: PUBLIC PROC [capacity: INT ¬ 20] RETURNS [Context] = INLINE { RETURN [NEW[ContextRep ¬ [lim: capacity]]]; }; Free: PUBLIC UNSAFE PROC [ct: Context, ptr: POINTER] = TRUSTED INLINE { IF ptr#NIL AND ct.lim>0 THEN EntryFree[ct, LOOPHOLE[ptr]] }; EntryFree: PRIVATE ENTRY PROC [ct: Context, d: POINTER TO Block] = TRUSTED INLINE { ct.lim ¬ ct.lim-1; d.next ¬ NIL; IF ct.last#NIL THEN ct.last.next ¬ d ELSE ct.first ¬ d; ct.last ¬ d }; Get: PUBLIC PROC [ct: Context] RETURNS [POINTER ¬ NIL] = TRUSTED INLINE { IF ct.first#NIL THEN RETURN [LOOPHOLE[EntryGet[ct]]]; }; EntryGet: PRIVATE ENTRY PROC [ct: Context] RETURNS [d: POINTER TO Block] = TRUSTED INLINE { IF (d ¬ ct.first)#NIL THEN { ct.lim ¬ ct.lim+1; ct.first ¬ d.next; IF ct.first=NIL THEN ct.last ¬ NIL; d.next ¬ NIL; }; }; FreeCapacity: PUBLIC PROC [ct: Context] RETURNS [INT] = INLINE { RETURN [ct.lim]; }; END. < UnsafeFreeList.mesa Copyright Ó 1992 by Xerox Corporation. All rights reserved. Created by Christian Jacobi, April 9, 1992 11:48:58 am PDT Christian Jacobi, April 13, 1992 3:15 pm PDT "Template module" to handle free-lists of client data blocks. This is a quite simple task. However, by using an extra module more detailed care is given to this problem then any single user likely would invest. It is probably worth being fast since the garbage collector provides nicer functionality in any case were speed or fragmentation doesn't matter. It is aimed at multi-threaded applications; single threaded applications don't need fancy locking like UnsafeFreeList. This package is not defying garbage collection; quite the opposite is true. Due to garbage collection it makes sense to utilize many but quite short free-lists. We overwrite the data blocks directly for linking them together in the free list. As this is quite unsafe, we propose that clients of UnsafeFreeList do not export or share the UnsafeFreeList.Context's used. Typical usage pattern xFreeList: UnsafeFreeList.Context ~ UnsafeFreeList.NewContext[100]; NewX: PROC [] RETURNS [x: REF X] = TRUSTED { x ¬ LOOPHOLE[UnsafeFreeList.Get[xFreeList]]; IF x=NIL THEN x ¬ NEW[X] }; FreeX: PROC [x: REF X] = TRUSTED { UnsafeFreeList.Free[xFreeList, LOOPHOLE[x]]; }; We also propose to use non-global free lists (to reduce sharing the monitor lock among processors in a multi-processor environment). A context represents one particular free-list. The context is the unit of mutual exclusion. Note that lim is accessed outside the monitor lock, as the exact value doesn't really matter. Allocates a free-list context willing of holding up to capacity elements Hangs ptr^ onto the free-list designated by ct Removes and returns an element from free-list, or returns NIL in case the free-list is empty. We are using first in first out order. Returns approximate number of additional elements the free list is willing to remember. This is really approximate: there exist race conditions which could make this negative... ÊX•NewlineDelimiter –(cedarcode) style™codešœ™Kšœ Ïeœ1™