1
`
`GOOGLE-1016
`Google Inc. v. Micrografx LLC
`IPR2014-00532
`
`

`

`US. Patent
`
`Jul. 13,1999
`
`Sheet 1 0f 7
`
`5,923,877
`
`12
`
`14
`
`24
`
`OBJECT
`
`22
`
`
`
`FOREIGN
`POINTER
`
`CLASS
`
`
`
`iNHERlT
`FOREIGN
`OBJECT
`
`CLASS
`
`
`TYPE OF
`FOREIGN
`
`POINTER
`
`
`INSTANTIATE
`INSTANTIATE
`
`
`
`
` FOREIGN POINTER
`
`FOREIGN
`
`
`ENCLOSING
`OBJECT 18
`
`
`
`
`FIG.
`1
`
`LISTS
`
`16
`
`30
`
`FOREIGN
`OBJECT
`
`32
`
`
`
`ACTIVE
`RESTRICTIVE
`POINTER
`POINTER
`
`
`LIST
`LIST
`
`
`
`36
`
`
`
`
`PASSIVE
`
`POINTER
`
`LIST
`
`
`
`
`
`
`
`
`
`
`FOREIGN
`FOREIGN
`FOREIGN
`FOREIGN
`POINTER
`POINTER
`POINTER
`POINTER
`
`
`
`
`
`
`
`
`FOREIGN
`POINTER
`
`FOREIGN
`POINTER
`
`FIG. 2
`
`2
`
`

`

`US. Patent
`
`Jul. 13,1999
`
`Sheet 2 0f7
`
`5,923,877
`
`I?[(?.
`
`{3
`
`DESTROY
`FOREIGN OBJECT
`
`FIG. 3
`
`OPTIONALLY SEND "WILL INVALIDATE"
`MESSAGE TO EACH FOREIGN POINTER
`
`
`
`
`
`
`
`
`
`
`EACH FOREIGN POINTER FOLLOWS OWN
`WILL INVALIDATE STRATEGY
`
`SEND “INVALIDATE" MESSAGE TO
`EACH FOREIGN POINTER
`
`EACH FOREIGN POINTER FOLLOWS
`OWN INVALIDATE STRATEGY
`
`EACH FOREIGN POINTER STOPS
`POINTING T0 FOREIGN OBJECT
`
`DELETE FOREIGN OBJECT
`FROM MEMORY
`
`210
`
`192
`
`194
`
`202
`
`204
`
`206
`
`208
`
`60
`
`
`
`FOREIGN POINTER
`SIGN ON TO
`
`
`FOREIGN OBJECT
`
`FOREIGN POINTER SIGNS ON
`
`
`
`
`
`52
`
`64
`
`AS ACTIVE. PASSIVE. OR
`RESTRICTING POINTER
`TO A FOREIGN OBJECT
`
`
`
`
`
`FOREIGN OBJECT ADDS
`FOREIGN POINTER T0
`
`
`ONE OF THREE LISTS
`
`66
`
`FIG. 4
`
`FOREIGN OBJECT
`
`ENCLOSING OBJECT
`
`138
`150
`14o
`/
`196
`
`
`
`FOREIGN
`
`OBJECT
`156
`
`
`INHERITANGE
`
`
`
`FOREIGN
`POINTER .
`
`
`
`INVALIDATE
`METHOD
`
`
`
`
`— 152
`
`
`
`
`CALL WILL
`
`
`I NVALI DATE
`
`
`\ E k WILL INVALIDATE , , ,
`
`STRATEGY
`
`
`’\
`144
`
`191
`
`METHOD
`
`I FOREIGN 154
`POINTER
`
`/
`
`
`
`3
`
`

`

`US. Patent
`
`Jul. 13,1999
`
`Sheet 3 0f7
`
`5,923,877
`
`272
`
`
`
`
`BROADCAST
`
`
`FIG. 6B
`
`TAPES IN USE
`
` 280
`
`PASSIVE
`
`El U D El El
`
`(VCR)
`
`FIG. 60
`
`292
`
`4
`
`

`

`US. Patent
`
`Jul. 13,1999
`
`Sheet 4 0f7
`
`5,923,877
`
`FIG. 8
`
`DELETE
`FOREIGN OBJECT
`
`330
`
`
`
`RESTRICTIVE
`POINTER IN
`LIST?
`
` 332
` 334
`
`
`
`
`RETURN
`"FALSE"
`
`FIG. 7
`
`
`
`REMOVE FOREIGN
`POINTER FROM
`
`
`FOREIGN OBJECT
`
`
`300
`
`NOTIFY FOREIGN OBJECT
`
`302
`
`LOCATE FOREIGN
`POINTER IN LISTS
`
`
`
`
`304
`
`
`
`REMOVE FOREIGN
`POINTER FROM LIST
`
`306
`
`
`
`ANY ACTIVE
`0R RESTRICTIVE
`
`POINTER ON
`LIST?
`
`
`308
`
`AUTO SELF—DESTRUCT
`IF DESIRED
`
`.310
`
`
`
`FOREIGN
`POINTER
`CLASS
`
`
`
`312
`
`
`FOREIGN-
`
`
`POI NTER_T0
`FOREIGN
`TEMPLATE
`LIST
`
`
`
`TEMPLATE
`
`
`
`
`
`
`400
`
`402
`
`404
`
`415
`
`406
`
`
`
`
`
`NOTIFIER
`POINTER-
`NOTIFIER_
`FOREIGN LIST
`T0. IMMORTAL
`POINTER_T0
`
`
`
`
`TEMPLATE
`TEMPLATE
`TEMPLATE
`
`
`
`
`
`FIG. 9
`
`
`
`LOCKED_
`POINTER_T0
`
`
`TEMPLATE
`
`
`412
`
`5
`
`

`

`US. Patent
`
`Jul. 13,1999
`
`Sheet 5 0f7
`
`5,923,877
`
`FIG. 10
`
`CHANGE FOREIGN
`OBJECT
`
`540
`
`
`
`424
`ENCLOSING
`OBJECT
`
`
`
`420
`426
`
`FOREIGN POINTER
` BUSINESS
`FOREIGN
`
`
`CLASS
`POINTER TO
`
`
`
`<BUSINESS
`(FOREIGN
`
`
`CLASS)
`OBJECT)
`
`
`
`
`
`
`
`
`
`
`
`1 1
`FIG.
`FORE]GN_,POINTER_T0
`[NVALIDATE STRATEGY
`
`
`
`
`
`520
`
`522
`
`526
`
`
`
`
`
`RECEIVE INVALIOATE
`MESSAGE FROM
`FOREIGN OBJECT
`
`
`
`SET ITSELF To NULL
`
`
`
`REMOVE FOR
`N POINTER
`FROM pEIIEVIous
`FOREIGN OBJECT
`
`544
`
`
`
`OWNED
`POINTER
`9
`
`
`
`542
`
`546
`
`548
`
`550
`
`FIG. 12
`
`ASSIGN OWNERSHIP
`OF POINTER
`
`
`
`
`FIG.
`
`1 3
`
`
`624
` ENCLOSING
`
`
`620
`OBJECT
`
` NOTIFIER
`
`
`FOREIGN POINTER
`POINTER T0
`
`
`BUSINESS
`
`(BUSINESS CLASS>
`
`
`CLASS
`
`(FOREIGN
`
`OBJECT)
`
`
`626
`
`6
`
`

`

`US. Patent
`
`Jul. 13,1999
`
`Sheet 6 0f 7
`
`5,923,877
`
`FIG.
`
`FIG.
`
`7 5
`
`642
`
`644
`
`640
`
`NOTIFIER WILL
`INVALIDATE STRATEGY
`
`
`
`RECEIVE WILL INVALIDATE
`MESSAGE FROM FOREIGN OBJECT
`
`
`
`
`
`
`
`CALL NOTIFYING METHOD
`0N ENCLOSING OBJECT
`
`646
`
`POINTER_T0_IMMORTAL
`INVALIDATE STRATEGY
`
`660
`
`RECEIVE INVALIDATE
`FROM FOREIGN OBJECT
`
`THROW AN EXCEPTION
`
`664
`
`
`
`662
`
`
`666
`
`680
`
`
`
`LOCKED_POINTER_T0 CHANGE
`FOREIGN OBJECT STRATEGY
`
`FIG. 16
`
`
`
`POINTER
`SET TO
`NULL?
`
`RETURN
`IIFALSEII
`
`684
`
`
`
`
`
`
`686
`
`FOLLOW FOREIGN_POINTER_T0
`CHANGE FOREIGN OBJECT STRATEGY
`
`FOREIGN
`OBJECT
`
`FOREIGN
`OBJECT
`
`OBJECT
`
`FOREIGN
`
`7
`
`

`

`US. Patent
`
`Jul. 13,1999
`
`Sheet 7 0f 7
`
`5,923,877
`
`FIG.
`
`7 .9
`
`FOREIGN LIST REMOVE
`OBJECT STRATEGY
`
`860
`
`
`
` 864
`
`REMOVE FOREIGN POINTER
`(THE FOREIGN LIST)
`FROM FOREIGN OBJECT
`To BE REMOVED
`
`
`862
`
`REMOVE FOREIGN OBJECT
`FROM FOREIGN LIST
`
`FIG. 78
`FOREIGN LIST
`ADD OBJECT STRATEGY
`
`840
`
`
`
`842
`
`ADD FOREIGN OBJECT T0
`FOREIGN LIST
`
`'
`
`
` OBJECT
`SUCCESSFULLY
`
`ADDED?
`
`
`
`
`ADD FOREIGN POINTER
`(THE FOREIGN LIST) TO
`FOREIGN OBJECT
`
`
`846
`
`
`
`ND
`
`855
`
`
`
`FOREIGN LIST POINTER
`INVALIDATE STRATEGY
`
`
`880
`
`
`RECEIVE INVALIDATE
`MESSAGE FROM
`FOREIGN OBJECT
`
`
`
`
`
`
`882
`
`
`
`
`DELETE RESPECTIVE
`FIG. 20 POINTER FROM LIST
`
`
`884
`
`
`
` FOREIGN
`
`NOTIFIER
`
`FOREIGN LIST
`
`OBJECT
`
`
`
`ENCLOSING
`OBJECT
`
`
`
`934
`
`8
`
`

`

`5,923,877
`
`1
`OBJECT-ORIENTED PROGRAMMING
`MEMORY MANAGEMENT FRAMEWORK
`AND METHOD
`
`BACKGROUND OF THE INVENTION
`
`10
`
`15
`
`Memory management is one of the most difficult, most
`error-prone, but also most
`important aspects of object-
`oriented programming. An object-oriented program imple-
`mented in C++, for example, is based around a collection of
`objects which represent either a physical or abstract part of
`the world which the program addresses. When the program
`runs, memory must be allocated for those objects. The C++
`language has two operators, “new” and “delete”, related to
`memory allocation. The programmer uses operator “new” to
`allocate memory for an object and uses operator “delete” to
`free up the allocated memory when the object is no longer
`needed by the program. It may be seen that the task of
`memory management is primarily a decision of when to call
`operator “delete".
`Objects within the program may refer to each other by I’
`having pointers to the allocated memory. For example, an
`employee object may have a pointer to the memory allocated
`for the object representing that employee’s manager. Objects
`can send messages to the object they point to, so that they
`can receive information and give commands from and to the
`object. These operations may result
`in a change in the
`memory location pointed to. Several memory management
`problems related to the use of pointers require careful
`attention and consideration by the programmer. These prob-
`lems include wild pointers, limited memory, and memory
`leaks.
`
`2
`diflicult. Although C++ provides one basic way of allocating
`dynamic memory, the allocated objects are used for diverse
`reasons. The “right time” to delete the objects depends on
`the way these objects and pointers pointing to them are used.
`One use for pointers is to point to one object which may
`be a part of another object. For example, a Video tape may
`have several video segments recorded on it, so each video
`segment object is a part of a video tape object. In order to
`know which tape object a video segment object is a part of,
`the video segment object may have a back pointer to a tape
`object. It may be seen that when a video tape object is
`deleted, all video segment objects that have a back pointer
`to it should also be deleted to avoid generating wild pointers.
`Another difficulty is posed when one object may have a
`list of objects of another type. A video tape object may
`include a list of video segment objects it contains.
`Additionally, a planned broadcast object may have a list of
`video segment objects residing on one or more video tape
`objects that will be shown during the course of the broad-
`cast. Further, the same Video segments may be used for
`several broadcasts, and therefore are listed on several broad-
`cast lists at the same time. Each list that contains an object
`has a pointer to that object. When an object containing a list
`is deleted,
`the list is also deleted. The difficult memory
`management decision, however, is whether the individual
`objects on the list should also be deleted. In this example,
`when a broadcast object is deleted from memory, the video
`segment objects may not be, in general, deleted. However,
`when a video tape object is deleted, all the video segment
`objects on its list should also be deleted. The C++ language
`does not provide any explicit syntax for making the distinc-
`tion between these two types of relationships. The program-
`mer must provide explicit code to properly distinguish and
`treat these two cases differently or wild pointers may result.
`A further difficulty is posed when an object may also be
`temporarily related to another object. For example, a video
`cassette recorder (VCR) may be playing a video tape. In this
`case, the VCR object has a pointer to the Video tape object.
`Syntactically, this relationship appears the same as the back
`pointer that a video segment object has to its video tape.
`However, unlike the back pointer example, the VCR object
`should not be deleted when the video tape object is deleted.
`In fact, the VCR object may point to dilferent video tape
`objects at different points in the broadcast, or may not point
`to any video tape object at all. This difference in relationship
`requires distinction and different memory management strat-
`e gies.
`the objects pointed to are
`In all the above examples,
`sharable; that is, many objects may have pointers to the same
`object. Another common use of pointers is for an object that
`is owned by another object and should only be pointed to by
`the owning object. For example, a VCR object may have a
`strategy for what it does when it reaches the end of a tape:
`rewind the tape and play it again, rewind it and eject it, or
`just stop. In object-oriented programming, objects can rep-
`resent actions such as these end-of—tape strategies.
`Therefore, the VCR object has a pointer to a strategy object,
`which may change during the course of a broadcast. In this
`scenario, different VCR objects are not pointing to the same
`strategy objects, but a new strategy object is created for each
`VCR object. This relationship is called “remote ownership”
`and typically requires a different memory management
`strategy to avoid problems.
`One of the biggest advantages of object-oriented pro-
`gramming is the ability to reuse objects in multiple appli-
`cations without having to modify the original code. To allow
`
`The central problem with memory management is that an
`object with a pointer to another object is not notified when
`that object is deleted so that the pointer is no longer valid.
`This is known as a wild pointer problem in the computer
`programming industry. If an object then sends a message to
`the now deleted object via the Wild pointer, the results are
`often unpredictable. The program may crash immediately,
`the results may be invalid, or, as is frequently the case, the
`method on the wild pointer starts a chain reaction of invalid
`operations that
`leads to a crash at a later point
`in the
`program. It is extraordinarily difficult to debug such occur-
`rences. There is a saying in the industry: “the result of even
`one wild pointer is pain, misery, and death.” (C++ FAQs by
`Cline and Lomow, pg 324).
`One way to avoid wild pointers is never to call operator
`“delete”. This may be a valid solution only if the program
`has an unlimited amount of memory for its use. Typically, a
`program will deal with many more objects during the entire g
`run of the program than it needs at any one time. Therefore,
`it
`is impractical and unrealistic to continue to maintain
`memory space for unused objects.
`Even if there is enough memory to allocate all objects an
`application needs,
`if some objects allocated by operator
`“new” during program execution are not deleted at some
`point during program execution,
`the allocated memory
`remains unavailable for other programs or additional runs of
`the same program until
`the computer is restarted. This
`problem is commonly called a memory leak. When a pro-
`gram with a memory leak is run repeatedly, eventually the
`leak is so severe that other programs will crash or new
`programs cannot be started even if no other program is
`running.
`To avoid the problems of wild pointers, limited memory,
`and memory leaks, the programmer must delete each object
`at the right time. Determining when is the right time is very
`
`40
`
`45
`
`60
`
`65
`
`9
`
`

`

`5,923,877
`
`3
`to
`for code reuse, new objects must be able to point
`previously coded objects without change to the previously
`written code. Such pointers are called anonymous pointers,
`such that
`the class pointed to has no code specifically
`referring to the class with the pointer. Deletion of objects
`pointed to by anonymous pointers is another primary cause
`of wild pointers.
`In conventional programming, memory management
`must be explicitly and carefully coded for each and every
`object. Often explicit coding is used to manage anonymous
`pointers. l-‘or example, when a broadcast object is deleted,
`the video segments it uses should not be deleted since one
`or more of them may be scheduled to be shown in other
`broadcasts. However, a video segment object should be
`deleted if is not needed by other broadcasts. The program-
`mer may manage this by writing explicit code to maintain a
`list of all open broadcasts and their video segments, which
`is referred to when a broadcast is deleted. There may be
`other business reasons to delete an object. For example, if a
`video segment object is deleted because of censorship,
`it
`should be deleted from all broadcasts. The programmer is
`required to write specific code to check all broadcasts and
`delete the video segment from all broadcasts scheduled to
`use it. Such explicit coding goes directly against the basic
`object-oriented design principles of encapsulation and reuse.
`In addition to being time consuming and error-prone to
`implement, the explicit code has to be modified everywhere
`it is in place when the application is expanded or the objects
`are reused in another context.
`
`10
`
`'.
`
`30
`
`Garbage collection is a known technique for automati-
`cally managing memory based on the concept of scope of a
`variable. A garbage collection product is Great Circle made
`by Geodesic Systems of Chicago, Ill. When memory is
`allocated for an object, but no currently active variable
`points to that object, the object can be automatically deleted
`without specific code written by the programmer. The dis-
`advantage with automatic garbage collection is that it is
`based on the syntax of pointers in memory. For example,
`garbage collection schemes cannot distinguish between
`removing a video segment from one broadcast because it is
`not scheduled to be shown next time, and removing a video
`segment from its video tape because it is censored and
`should not be shown on any broadcast ever again. Explicit
`coding is still required to fill in this gap.
`Some other techniques have been developed to solve
`some memory management problems but are not complete
`solutions. The smart pointer from the C++ compiler from
`Borland International Inc., Scotts Valley, Calif, for example,
`handles only the problem of remote ownership. Reference
`counting wrappers are also available to enable programmers ~
`to keep track of how many objects point to a particular
`object with simplified code. However, these techniques do
`not address all memory management problems encountered.
`Currently, conventional memory management is done in
`a haphazard and tedious manner, which may require many
`sleepless hours to code and debug. Most often, software
`products are made available to the consumers before prob-
`lems of improper memory management are completely
`resolved. The result is the sometimes frequent appearance of
`dialog windows informing users some non-specified error
`has occurred popping up on computer terminals and locked-
`up computer applications.
`SUMMARY OF TIIE INVENTION
`
`35
`
`40
`
`45
`
`60
`
`Accordingly, there is a need for a framework and method
`for providing memory management in object-oriented pro-
`gramming to avoid wild pointer and other problems.
`
`10
`
`4
`invention, a memory
`In accordance with the present
`management framework and method are provided which
`eliminates or substantially reduces the disadvantages asso-
`ciated with prior programming practices.
`In one aspect of the invention, an object-oriented memory
`management framework includes a foreign pointer class
`having a plurality of encapsulated methods and variables for
`memory management. The foreign pointer class provides
`one or more instances of active, passive, and restrictive
`foreign pointers. The framework further includes a foreign
`object class for providing one or more instances of foreign
`objects, where each foreign object encapsulated an active list
`variable, a passive list variable, and a restrictive list variable
`for recording therein any foreign pointer pointing thereto.
`In another aspect of the invention, a method for memory
`management in object-oriented programming includes the
`steps of encapsulating memory management methods and
`variables in a foreign pointer class, and a foreign object
`class. The foreign pointer class provides one or more
`instances of active, passive, and restrictive foreign pointers
`for conveying diverse relationships. Each foreign object has
`encapsulated an active list variable, a passive list variable,
`and a restrictive list variable for recording any foreign
`pointer pointing thereto.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`For a better understanding of the present invention, ref—
`erence may be made to the accompanying drawings,
`in
`which:
`
`FIG. 1 is a simplified block diagram of a foreign object
`and a foreign pointer;
`FIG. 2 is a simplified block diagram of a foreign object
`and its lists of active, restrictive, and passive foreign point-
`ers;
`
`FIG. 3 is a simplified flowchart of an exemplary foreign
`pointer sign-on process;
`FIG. 4 is a simplified block diagram showing an exem-
`plary destroy foreign object process by the transmission of
`a “Will invalidate” message and an “Invalidate” message;
`FIG. 5 is a simplified flowchart of an exemplary destroy
`foreign object process;
`FIGS. 6A76C are simplified diagrams illustrating the
`exemplary scenarios in which active, passive, and restrictive
`foreign pointers are used;
`FIG. 7 is a simplified flowchart of an exemplary remove
`foreign pointer from foreign object process;
`FIG. 8 is a simplified flowchart of an exemplary delete
`foreign object process;
`FIG. 9 is a simplified class inheritance diagram;
`FIG. 10 is a simplified block diagram of a foreign
`pointerito foreign pointer;
`FIG. 11 is a simplified flowchart of an exemplary foreign
`pointer invalidate process;
`FIG. 12 is a simplified flowchart of an exemplary change
`foreign object process;
`FIG. 13 is a simplified block diagram of a notifier_
`pointer
`to foreign pointer;
`FIG. 14 is a simplified flowchart of an exemplary
`notifier_pointer_to will invalidate process;
`FIG. 15 is a simplified flowchart of an exemplary
`pointer_to_immortal invalidate strategy;
`FIG. 16 is a simplified flowchart of an exemplary lockedi
`pointerito change foreign object strategy;
`
`10
`
`

`

`5,923,877
`
`5
`FIG. 17 is a simplified block diagram of a foreign list;
`FIG. 18 is a simplified flowchart of an exemplary foreign
`list add foreign object strategy;
`FIG. 19 is a simplified flowchart of an exemplary foreign
`list remove foreign object strategy;
`FIG. 20 is a simplified flowchart of an exemplary foreign
`list pointer invalidate strategy; and
`FIG. 21 is a simplified block diagram of a notifier foreign
`list.
`
`10
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`6
`operator or destructor in C++, for example. FIG. 4 shows an
`exemplary process flow and FIG. 5 is a simplified block
`diagram. Referring first to FIG. 4, a foreign object 138, like
`any object-oriented object, has a layered structure with
`multiple layers 140—144. Topmost layer I40 contains the
`behavior inherited from the foreign object class. Subsequent
`layers 142 describe other behavior, with the bottom-most
`layer 144 containing a destructor of the business class. The
`programmer may optionally insert a call to a “will invali-
`date” strategy into the destructor. The function of the will
`invalidate strategy is described below. As it is true with all
`objects, when an object is being destroyed, it is deleted in
`layers, beginning with the bottom-most layer. An enclosing
`object 150 includes a foreign pointer 152 pointing to foreign
`object 138 that has encapsulated an invalidate method 154
`and a will invalidate method 156.
`
`Referring also to FIG. 5 for the destroy foreign object
`process flow beginning in block 190, foreign object 138 may
`optionally send a “Will invalidate" message 191 to each
`foreign pointer pointing to it, as shown in block 192, by
`inserting a call therefor in the destructor or bottom-most
`layer 144 of foreign object 138. Each foreign pointer,
`including foreign pointer 152, upon receiving “Will invali-
`date” message 191, uses its own will invalidate strategy 154
`and operates accordingly, as shown in block 194.
`Subsequently upon completion of the foreign pointer’s
`will invalidate strategy 154, foreign object 138 sends an
`“Invalidate” message 196 from its topmost layer 140 (which
`has the foreign object inheritance) to each foreign pointer
`152 pointing to it, as shown in block 202. Each foreign
`pointer 152 then proceeds to executes its own invalidate
`strategy 156, a shown in block 204, with the end result that
`each foreign pointer no longer points to the foreign object,
`as shown in block 206. Foreign object 138 is then com-
`pletely deleted, as shown in block 208. The process ends in
`block 210.
`
`if enclosing object 250
`Constructed in this manner,
`desires to perform certain operations, such as obtaining
`some information from foreign object 138 immediately prior
`to foreign objects deletion from memory, it has the oppor-
`tunity to do so upon the receipt of“Will invalidate” message
`191. Without this special mechanism, by the time foreign
`object 138 issues “Invalidate” message 196 from its topmost
`layer 140, all layers below topmost layer 140 has already
`been deleted. Therefore, it would be too late for enclosing
`object 150 to perform the desired operations by the time it
`receives “lnvalidate” message 196.
`As set forth above in FIG. 2, a foreign pointer may be one
`of three types. For example, a video tape object may be
`pointed to by multiple objects using different
`types of
`foreign pointers: active, passive, and restrictive. FIGS.
`6A—6C provide exemplary applications for the three types of
`foreign pointers. For example, a planned broadcast business
`application 272, which is a schedule of a television
`broadcast, may point to a Video tape object 270 with an
`active pointer 274. This indicates that broadcast 272 plans to
`show tape 270. On the other hand, a window list box 280
`displayed on a terminal listing all the tapes currently in use
`may point to video tape 282 with a passive pointer 284.
`Further, a video cassette recorder (VCR) object 290 may use
`a restrictive pointer 292 to point to a video tape object 294
`when the tape is inserted into the VCR.
`The active, passive, and restrictive distinction may be
`illustrated with the scenario that something has occurred so
`that the last object pointing to the video tape is broadcast
`272, list box 280, or VCR 290. If planned broadcast 272
`
`15
`
`.
`
`30
`
`The preferred emhodiment(s) of the present invention is
`(are) illustrated in FIGS. 1—20,
`like reference numerals
`being used to refer to like and corresponding parts of the
`various drawings.
`Referring to FIG. 1, a framework 10 defining two classes
`that encapsulate methods and variables are foreign object
`class 12 and foreign pointer class 14, according the teach-
`ings of the present invention. Foreign object and pointer
`classes 12 and 14 are used as base classes or super classes
`for application-specific classes coded by the programmer.
`Foreign object and pointer classes 12 and 14 function
`together to encapsulate the basic methods of memory man-
`agement according to the teachings of the present invention.
`Foreign object class 12 may be used as a base class for any
`class of objects requiring memory management. The pro-
`grammer may do so by deriving a business class as “public
`virtual foreign object”. Foreign pointer class 14 is a pure
`virtual class that encapsulates communication methods with
`foreign objects 16 that inherit from foreign object class 12.
`As shown, foreign object 16 is an instance of foreign object
`class 12 and includes lists 18 which keep track of foreign
`pointers 20 that are pointed thereto. Foreign pointer 20 is
`enclosed by an enclosing object 22 and is an instance of a
`type of foreign pointer 24 as defined in framework 10. The
`specific type of foreign pointer 24 has inherited specific
`behaviors from foreign pointer class 14. Foreign pointer 20,
`constructed in this manner, is used instead of the conven-
`tional pointers to point to foreign objects 16. As shown in
`FIG. 2, each foreign object 30 maintains three lists: active,
`restrictive, and passive foreign pointer lists 32—36. Each list
`records the foreign pointers 40—45 of each type that point to
`foreign object 30. This structure supports the use of anony-
`mous pointers since neither the foreign object nor the actual
`business classes derived from it need to contain explicit code
`about particular types of pointers or the business classes that
`contain those pointers. The particular kind of foreign pointer
`used by an object to point to a foreign object determines the .,
`memory management behavior and strategy. When a foreign
`object is deleted, it sends a special message, “invalidate”, to
`each of the foreign pointers that point to it, regardless of
`type. The foreign pointers then executes their respective
`memory management strategy. This behavior is encapsu-
`lated in foreign pointers without programmer’s explicit
`coding.
`Referring to FIG. 3, an exemplary flowchart 60 illustrates
`how foreign pointers may be initiated. In block 62, each
`foreign pointer, when initiated, signs on as active, passive,
`or restrictive pointer. In response, the foreign object being
`pointed to by the pointer adds the new pointer to one of its
`active, restrictive, and passive pointer lists 32—36 (FIG. 2),
`as shown in block 64. The initiation then terminates in block
`66.
`
`35
`
`40
`
`45
`
`60
`
`65
`
`FIGS. 4 and 5 illustrate a process for destroying a foreign
`object to remove it from memory by calling the “delete”
`
`11
`
`11
`
`

`

`5,923,877
`
`7
`becomes the last object to point to video tape 50 with an
`active foreign pointer 274, video tape object 270 should not
`be deleted from memory because an active foreign pointer is
`involved. However, there may exist overriding reasons, such
`as censorship, to insist that video tape 270 be delete from
`memory. Video tape 270 may be deleted as long as planned
`broadcast 272 is notified.
`
`In contrast, if list box 280 listing all the tapes currently in
`use becomes the last object to point to Video tape 282, this
`is insullicient reason to keep video tape object 282 in
`memory, because a passive foreign pointer 284 is involved.
`Conceptually, if a tape object is not pointed to by anything
`else but passive pointers, it has outlived its usefulness. Thus,
`if an object is pointed to by only passive pointers, it may be
`deleted.
`
`10
`
`8
`subclass 402 is a template class of singular foreign pointers,
`i.e., pointers that only point to one foreign object. Foreign
`list 404, on the other hand, is a template class of foreign
`pointers that point to more than one foreign object. More
`specialized template classes inherit from foreign pointer
`to class 402: notifieripointerito 406, pointeritom
`immortal 410, and pointeritoiimmortal 410. A further
`template class,
`locked_pointer_to 412,
`inherits from
`pointeritoiimmortal 410. A notifier foreign list template
`416 further inherits from foreign list template 404.
`The subclasses of foreign pointers contain additional
`specialized behavior to aid in memory management. An
`enclosing object having a notifieripointerito pointer point-
`ing to a foreign object may perform operations immediately
`prior to the deletion of the foreign object. A lockedi
`pointerito pointer, once it is set to point to an object, cannot
`be changed. Further, a locked pointer
`to pointer provides
`exception handling when the object it points to is deleted. A
`pointeritoiimmortal pointer also throws an exception
`when the object it points to is being deleted. Notifier foreign
`list behaves much like a notifieripointerito pointer and
`also provides advanced notification that a foreign object is
`about to be deleted.
`
`In the case of restrictive pointer 292, video tape object
`294 should not be deleted at all because it is currently being
`used by VCR 290. Thus, an object being pointed to by one
`or more restrictive pointers are not to be deleted.
`FIG. 7 is a flowchart representing an exemplary process 1’
`300 to remove a foreign pointer from a foreign object. Re fer
`also to FIGS. 1 and 2 for block diagrams showing the
`structures of the objects involved. In block 302, foreign
`object 16 that was pointed to by foreign pointer 20 is first
`notified. Foreign object 30 searches its three lists of active,
`passive and restrictive pointers 32—36 and locates the
`present pointer in one of the lists, as shown in block 304.
`Foreign pointer 20 is then removed from the appropriate list,
`as shown in block 306. If the removed foreign pointer was
`the last active or restrictive pointer in that foreign object’s
`lists and no other active or restrictive pointers remain in the
`lists, as determined in block 308, then the foreign object may
`automatically self-destruct to delete itself from memory, as
`shown in block 310. The automatic self-deletion may be
`performed since the only remaining foreign pointers point-
`ing to the foreign object,
`if any, are passive pointers.
`Execution then ends in block 312.
`
`30
`
`35
`
`Referring to FIG. 10, a block diagram of a foreigni
`pointer
`to pointer 420, which acts like an anonymous
`pointer, is enclosed by an enclosing object 424 and pointing
`to a foreign object 426. Instead of declaring a pointer to a
`business class derived from the foreign object class, the
`programmer declares a foreign_pointer_t0 <business
`class> to use foreignipointerito pointers. Foreigni
`pointer_to is a template containing an actual pointer 422 to
`the business class, initialized to NULL if the programmer
`did not initialize it. This eliminates a common source of
`error resulting from uninitialized pointers.
`Operators included in the foreignipointerito template
`allow the programmer to use the foreign pointer as if it were
`a regular C++ pointer. However, as shown in the flowchart
`beginning in block 520 in FIG. 11, when foreignipointeri
`to receives an “Invalidate” message indicating that foreign
`object 426 is deleted (block 522), foreign pointer 422 is reset
`to NULL to eliminate the wild pointer that would otherwise
`result (block 526) before terminating in block 528.
`For foreign_pointer_to pointers, an ownership variable
`is further provided to implement whether remote ownership
`is implemented. If ownership is set to true, the foreign object
`pointed to is automatically deleted when the pointer no
`longer points to it. Implemented in this unique manner,
`remote ownership status may be turned on or off.
`FIG. 12 is a flowchart of an exemplary change foreign
`object process flow, beginning in block 540. Change foreign
`object is used to take a foreign pointer off a first foreign
`object and then point it to a second foreign object. In block
`542, the foreign pointer is removed from the first foreign
`_, object by executing the exemplary process flow shown in
`FIG. 7. If the ownership variable of the foreign pointer is
`true, as determined in block 544, then the first foreign object
`is deleted automatically, as shown in block 546. The foreign
`pointer then signs on to the second foreign object by
`following the process flow shown in FIG. 3, as shown in
`block 548. In block 550, the ownership of the foreign pointer
`is then determined. The process ends in block 552.
`Referring to FIG. 13, a diagram of a notifieripointerito
`pointer derived from the foreignipointerito template is
`shown. Frequently an object 624 may need to perform other
`actions when the pointer 620 it contains is reset, as in the
`case when the foreign object 626 it points to is being deleted.
`
`Referring to FIG. 8, an exemplary delete foreign object
`process flow is shown, beginning in block 330. Delete
`foreign object 330 may be called when a programmer
`desires to remove a foreign object from memory. Delete
`foreign object 330 first examines restrictive foreign pointer
`list 34 (FIG. 2) of foreign object 30 to determined whether
`any restrictive pointer is currently pointing to foreign object
`30, as shown in block 332. If list 34 shows that one or more
`restrictive pointers are currently pointing to foreign object
`30, then a predetermined value, such as boolean false, is
`returned in block 334 before the process ends in block 336.
`The return value is indicative of whether the foreign object
`was successfully deleted.
`If restrictive pointer list 34 shows no restrictive pointer
`currently points to foreign object 30, then the destroy foreign
`object method shown in FIG. 5 is called, as shown i