Bedrock Computer Technologies, LLC v. Softlayer Technologies, Inc. et al

Filing 284

Response to CLAIM CONSTRUCTION BRIEF filed by AOL Inc, Inc., Google Inc., Match.Com LLC, MySpace Inc., Softlayer Technologies, Inc., Yahoo! Inc.. (Attachments: #1 Affidavit, #2 Exhibit 1, #3 Exhibit 2, #4 Exhibit 3, #5 Exhibit 4, #6 Exhibit 5-1, #7 Exhibit 5-2, #8 Exhibit 5-3, #9 Exhibit 5-4, #10 Exhibit 5-5, #11 Exhibit 5-6, #12 Exhibit 6)(Chaikovsky, Yar)

Download PDF
Bedrock Computer Technologies, LLC v. Softlayer Technologies, Inc. et al Doc. 284 Att. 2 EXHIBIT 1 BTEX0000I 59 11111 11111111 III 11111 11111 11111 11111 11111 11111 11111 11111 111111 III 11111 liii USOOS 893 120A United States Patent Nemes Patent Number Patent 5893120 Apt Program Design Cliffs Date of 1999 METHODS AN1 APPARATUS FOR INFORMATION STORAGE AND RETRIEVAL HASHING TECHNIQUE WiTH USING EXTERNAL CHAINING ANI ON-THE-FLY REMOVAL OF EXPIRED DATA Inventor Richard Michael R.L Krusc Data Structures Jail and Second Edition Section Prentice-WI Englewood and New Jersey 1987 of Uash ing UI 6.5 Hashing pp 198215 Stubbs Typcs and Section 6.6 Analysis NW Webre Data Structure with Abstract Data and Pascal Brooks/Cole Section Nemes 1432 F. 35th Monterey tations Primary California 1985 Company 7.4 Hased Implemen Publishing St Brooklyn N.Y 11234-2604 pp 310336 ExaminerThomas ExaminerIlosain Black App Filed No 775864 Asvistant Alam Jan 1997 ABSTRACT CO6F 707/206 707/1 17/30 in mt Cl U.S method an and apparatus storage for performing is storage and that retrieval Cl of Search 707/100 707/202 information technique resolution system the disclosed uses the for 707/JO Field hashing collision noration with In external to chaining method 707/1 707/2 200206 100103 order prevent performance expiring that dete data due to the presence of automatically technique is items References Cited all garbage records collection stored into used removes chain expired in the the system data in the external targeted by probe each storage system of More record U.S 5121495 5202981 5287499 PATENT Nemea DOCUMENTS 707/3 707/1 707I206 particularly is insertion an retrieval entire or deletion an occasion to search linked-list chain of records an expired if 6/1992 4/1993 2/1994 Sliaekelford for expired data items and then not remain probed are remove in it them Because system Nemes item will is the is long term the system frequently that useful for large require the information fast access for Ot11ER D.E Sorting PUBLICATIONS Programming Reading vol storage systems by heavily used Knuth and The An provided of Computer removal hashing and cannot be taken off-line of expired data Searching MdisonWesley Massa Claims DrawIng Sheets ehusetLs 1973 pp 506549 BTEX0000I 60 U.S Patent Apr 1999 Sheet of 5893120 15 FIG USER ACCESS SOFTWARE 20 ____ GENERAL UTILITY OPERATING SYSTEM SOFTWARE _________ Ir SOFTWARE 22 21 r25 APPLICATION APPLICATION APPLICATION SOFTWARE SOFTWARE SOFTWARE FIG BTEX0000I 61 U.S Patent Apr 1999 Sheet of 5893120 FIG BTEX0000I 62 U.S Patent Apr 1999 Sheet of 5893120 ADVANCE PTR TO ELEMENT FOLLOWING ONE TO REMOVE DE-ALLOCATE LIST ELEMENT TO BE REMOVED FIG BTEX0000I 63 US Patent Apr 1999 Sheet of 5893120 FIG BTEX0000I 64 U.S Patent Apr 1999 Sheet of 5893120 -Td FOR AND RECORD CLEAN TARGET LIST SEARCH FIG BTEX0000I 65 U.S Patent Apr 1999 Sheet of 5893120 START10 SEARCH-TABLE FOR RECORD AND CLEAN TARGET SEARCH LIST 102 104 YES REMOVE DELETE ELEMENT FIG.4 RECORD FOUND NO 103 RETURN FAILURE RETURN SUCCESS STOP --106 FIG BTEX0000I 66 5893120 METHODS AND APPARATUS FOR INFORMATION STORAGE AND RETRIEVAL hAShING TECHNIQUE WITH USING EXTERNAL CHAINING AND ON-THE-FIN REMOVAL OF EXPIRED DATA CROSS-REFERENCE TO RELATED Hall 6.5 Incorporated Englewood Cliffs N.J 1987 Section hashing and Section 6.6 198215 and in Data Structures by FL Analysis with of Hashing pp 4pav Abstract Data and Pascal Publishing Stubbs and Webre Calif Brooks/Cole Section 7.4 Company Monterey 1985 Hashed APPLICATIONS Not Applicable 10 Implementations pp 310336 are Some forms of information items their after limited in the such that individual data period of time storage activities the become is obsolete needed data and or that presence system for no longer involve desired Scheduling example FEDERAlLY STATEMENT REGARDING OR DEVELOPMENT SPONSOREI RESEARCh Not Applicable become obsolete once scheduled item event has occurred it An automatically-expiring data once expires could needlessly occupies pitt 15 computer memory an storage that otherwise be expired items to use storing eventually data unexpired removed In to item Thus the REVERENCE Not Applicable TO MICROFICHE APPENDIX must be reclaim the storage for subsequent expired the insertions in addition presence of many items results lists needlessly long search external times since will linked than expired to associated BACKGROUND This invention systems techniques relates to OF THE information INVENTION longer storage to the with chaining is be they otherwise would the be The goal storage to remove and of retrieval 20 these access items to reclaim data is and maintain fast and in more such particularly use hashing the systems stored in The problem then computer-controlled stor 25 to provide the heavily data speed of access of stor Information or data hashing age techniques for large used information at can be retrieved by searching for age mechanism record key value in the stored records The stored matching searching the storage the search particular systems the having expiring and the same time from the with key Such into large prevent performance of many dealing degradation resulting key require to value is then access retrieved to records In if accumulation technique disclosed that 30 inapplicable there traverses for in expired records Although with expiring data issued is hashing techniques mechanism retrieval efficient requires repeated known Jun and perform key comparisons such searching such even as the U.S is Pat No 5121495 to linear 1992 entirely storage and by often systems search aug technique to confined external probing The and is mented search large procedures amount binary chaining order table procedure shown of an excessive of time due to the in reverse in the records consecutive sequence number of key comparisons well-known information of additional also In called required faster records residing hash to array continually left relocat of Another retrieving and much way of so-called storing albeit at and the ing unexpired ones fill gaps by the removal from computer storage is storage expired expense technique the or hashing it Unlike arrays linked are lists leave no gaps it when items from possible to effi are scatter-storage key-transformation operated on by removed traverse and furthermore linked list is not method hashing such to system produce hash of record directly the key is ciently singly in reverse order lhere function called storage address is in the large storage significant 40 ing that advantages sometimes to external it chaining over linear method the prob as space is the array table which oneaddress make the in of choice dis dimensional then locations for the This storage record by cussed in considerable techniques detail aforementioned with expiring wholly if texts data that for arc accessed are desired text Hashing Knuth and so hashing do not for dealing techniques entitled described in the classic use external applications considerable chaining For prove inadequate records The and Art of Computer Prograintning Volume certain example can the data Sorting Searching Addison-Wesley Reading Mass universe the large memory of linear hashing be saved using external there is 1973 pp 506549 functions addresses are chaining instead designed to translate the probing techniques Accordingly for external Hashing of keys hash into need with patent lists to develop chaining uniformly hashing and distributed throughout expiring are data to The methods arrays of the cannot above-mentioned with linked table lpical functions include truncation disadvan limited to the and be used folding tage transposition modulo than arithmetic due significant difference in the organization of of hashing in is that more one key will the inevitably in computers memory translate the same storage address causing collisions must therefore called storage Some form of collision provided For example which consists to the of the BRIEF In resolution be SUMMARY with the OF THE INVENTION illustrative simple strategy linear from the is accordance these embodiment overcome of the probing initial searching first forward storage invention garbage types and other problems are by using other In storage address empty location collection access to procedure the storage data on-the-fly space are or while often used method In for resolving this of taking retrieval place Another nal eoffisions is called exter is particular into 60 fled the during normal data insertion obsolete external records are probes identi list list chaining to the translate technique of the linked each list hash table all location store the expired the records arc linked pointer head under The of records to of whose very hash and removed expired the record from or to chain in the keys table hashing list is function itself that Specifically including the obsolete linked as part address retrieving are linked searched sequentially be accessed removed of when deletion inserting or deleting pointers record Insertion in and list normal search procedure garbage of collection done by is adjusting discussed the linked detail lhis 65 incremental advantage without taken technique has the unneeded External chaining in considerable in the decided records automatically that the eliminating information aforementioned text by Knuth Edition in Data Structures and requiring fur storage sys is Program Design Second by II Kruse Prentice- tem be off-line sueb garbagc collection This BTEX0000I 67 5893120 for particularly requiring important rapid access information storage to systems the user Central Processing controller input Unit and continuous availability Output plurality IO of CPU such as 10 also controls an Input to 14 that in turn provides access cathode devices for ray population devices as CRT of tube as More specifically records method using at for storing list and retrieving terminal printer puter information access cally list linked to the storc records and provide 15 as well 16 lerminal to introduce of plurality output such 15 provides instructions mechanism com to thc records is least some of method at It automati the linked user expiring of records disclosed The identifies accesses computer other located 10 system FIG such as and and commands into the with may be supplemented tape and of the expired least some automatically at least input devices magnetic readers remotely types expired ones automatically records ones is also removes some list terminals Similarly the of optical printer readers and 16 the other of input for of the records from the linked the devices displaying provides operation of mechanism the Printer when the linked list accessed Furthermore method results for of the computer 16 ray provides for dynamically expired ones list is determining to maximum when number of the linked system similarly FIG computer user may tube of the records be removed be supplemented phototypesetters types by line printers laser printers cathode graphical accessed is displays and other plotters of output of the operation devices computer are BRIEF DESCRIPTION VIEWS Aeompletc gained OF THE SEVERAL oi DIE DRAWING of the present following invention The their constituents system of FIG art and asperative of to all well-known in the and arc typical understanding the may be in 20 puters operation further computer systems from small personal com and not by considering with the detailed large mainframe systems here graphical for systems are The architecture description in conjunction accompanying general drawing diagram which of the which computer of such described well-known and will be HG system storage shows hardware and block in arrangement system information might 25 FIG software shows architecture representation of such typical as that user retrieval of the present invention shown in be HG computer system The software of FIG the comprises implemented FIG system access mechanism that for simple personal computers consist may larger shows software general block in diagram the of computer stor of nothing more providing than turning to system on In arrangement which information systems service many be users login implemented mechanism is and in pass user age and retrieval system of the present invention might find word procedures access mechanism 30 would typically user use 20 Once login access the user 20 in has the llG operation shows that general flow in chart for table storage searching system in completed operating coordinates the procedure placed might be used the present hashed system the environment of all 21 in Operating system components 21 accordance with invention for linked-list the table activities of the hardware HG remove operation shows procedure of general that flow chart forms part clement of the computer utility system shown for FIG use and to the provides computer basic file of searching number of user programs 22 of general FIG general Utilities 22 might example comprise system HG operation shows that flow chart in for record insertion storage access facilities and and manipulation programming programs language of as maintenance might be used the present hashed system in compilers accordance with invention flow chart storage for The computer record retrieval in includes 40 application software system programs such FIG typically also HG operation shows for general application software 25 use in hashed system accordance 2324 for 25 Application software 23 through editor might with the present invention general and flow in chart for record storage deletion example comprise spreadsheet text document database formatting HG operation shows that software hashed system in program and is management might he the used system The storage game program present invention It so forth concerned with software accordance with present invention identical reference to the information packages as and retrieval or lo facilitate reader can be application parts operating retrieval understanding designate numerals figures arc used to elements common 23-25 access used by 20 other or of the system 21 such user software system technique software provided in The information DETAII..ED storage are and by the II3SCRIPIlON OF ThE so present invention herein as disclosed as flowcharts FIGS in the INVENTION FiG of the drawings shows general block Central through and shown to this PASCAL-like pseudocode APPENDIX diagram of Before the ss present specification to it proceeding invention in data description is first of one embodiment to discuss of computer ing unit Unit hardware 10 system comprising Access in Process useful CPU and Random Memory the 11 Computer programs stored RAM at RAM are hashing and techniques retrieving storage general are is Many known in fast techniques for storing the prior art In situations where accessed by by CPU 10 and CPU 10 Data stored executed in other one instruction portions time of RAM space considered called in cheap compared is with retrieval used storage to for In classic 11 are time hashing 60 includes called technique each hashing the often operated from on by the program instructions accessed by CPU 10 data record information unique as the in value basis as array system tAIvl 11 all in accordance with well-known distinguished the field is each record storing processing Central accesses digital disk data techniques Processing disk stored unit Unit key the which associated used and hash CPU unit 10 that also in controls accesses and retrieving table is record Taken whole of controller 12 turn large one-dimensional logically storage on one or more 13 until required are in disk storage units such as 65 contiguous units Such of consecutively table numbered is is fixed-size stored in storage by CPU 10 from disk At this time storage unit of records each record typically RAM function Ill such programs and data and stored retrieved FIG where in an identifiable and addres 13 in blocks RAM 11 for rapid access sable location physical memory hashing BTEX0000I 68 5893120 translates the into key hash the table array subscript which for the is successful and returns success in box 35 followed by box and the is used record the tiled as an index into begin that array where can searches data procedures entered terminates If termination failure is in terminal returned 37 the If not box 36 The hashing function be any operation on where in procedure again key results the in subscripts mostly uniformly hashing modulo functions distrib include box of the 37 list across table Known the end has not been reached is as determined determine by to for truncation combinations functions folding of transposition arithmetic and by decision if box thcsc 33 decision to has box 38 expired the entered is to operations not Unfortunately unique keys locations to hashing in the the record generally in that do pointed This determined the record produce distinct hash table many what is map the same 10 In comparing some portion of contents of in location collision producing resolution are called in collisions all Some form of systems location some external condition he by compared all timestamp with the the record time-of-day the example could value current required hashing an maintained of an event event in every for location the occurrence collided of collision is computers compared In is Alternatively occur finding alternate the rence record can he with if to field necessary reachable Moreover during future identifying alternate that the record box 39 the in must be readily record collision is searches for any case the record if has not the expired in decision entered determine If it key displaced this record matches is search common present invention external resolution is strategy called table with external entry which the key does is the address If of the record record saved box 40 the and box 41 search directly to entered the concerned each at chaining stores all does not match Under the chaining collided hash of the bypasses box 44 the and proceeds key the procedure to box 41 In box 41 next record in the records that that location pointer by storing to the not records linked themselves list hut instead head lists of are procedure list advances the forward the to that 20 linked If and of those the same records Such procedure 38 returns box the 33 record to linked in decision box formed allocated to the determines box 42 is under the list by storing storage location records individually dynamically question pointer on-the-fly and maintaining with each record of the search there not is has expired entered record perform next record key is in the to the chain hash first of collided table removal of the expired it from the linked to the records the When found does to hashed to locate entry If the and the return of the storage 25 occupies system storage pointer used the record pool as will be described in connection of box linked that first with HG In search there key is match the key found record there the In this general the pointer to remove procedure from the to 42 HG operates its if used locate is second way remove an element pointer to list the by adjusting chain record of records is traversed the sequentially until the is desired predecessors the 30 there is bypass is element element table However array entry found or until involves record end of the chain the reached to element no he removed the of the list then is Deletion of records bypass the deleted predecessor and the hash of table merely adjusting and returning the pointers it storage occu adjusted instead from box On 42 that completion the search procedure procedure remove returns to pied to the available llashing fast access table techniques to static storage pool maintained been term such used data storage invoked box It by the system for have short in 33 can be to classically very seen the search table 35 operates the such as compiler deletions procedure of records to of 11G expired examine the entire is symbol are Typically systems linked list of which infrequent In and the need for the storage types is system disappears storage searched-for returning If the record storage part to is and remove quickly some common of data long lived passage systems can the 40 records removal records then the the storage pool with and each however the storage system become obsolete merely by occurrence lete records and records storage despite pool such depleted many expired the of time or by lapsed or remain insertion automatic is garbage collection of some event arc not If such from expired the obso in of new records is inhibited the boxes 76 and procedure chance garbage removed the system they will of the 77 of FIG until the deletion search time system seriously degrade performance up in retrieval First the since 45 HG to made by delete or until the table procedure its has had on-the-fly Degradation of expired the shows records two ways replenish storage pool through collection presence they lengthens to search longer times than cause external chains be they Though the search in table procedure as shown in HG otherwise dynamically returned to would be Second memory memory into the expired storage records that occupy be implemented pseudoeode the APPENDIX above and retrieval as PASCAL-like in allocated the the could and described storage appears connection using the on-the-fly system pool for useful pool is allocation with an information so system its list Thus when be system memory depleted system new only if data the hashing removal anywhere technique technique linked with external chaining linked item can inserted storage is while traversing list can be used appears in the applied memory search ratory occupied then by an to expired one there is reclaimed flowchart table in of records to with expiring person can data Referring table to FIG for shown the of even art in contexts appreciate unrelated that hashing skilled procedure searching hash prepa accor will this technique not be readily inserting retrieving or deleting record the to manipulate linked table in entire for lists necessarily used with hashing dance with the present invention in and involving targeted linked dynamic as The search procedure the shown in FIG all implemented above removal in of expired records of the search being table list Starting the in search pseudocode the APPENDIX list and described box 30 procedure for is of HG In traverses as 60 it linked removing expired records can be readily records key of the record scarched hashed box box the 31 to searches to key match The procedure all provide the subseript table array is of an array indicated to element the 32 hash in adapted thereby remove some but not list of the expired location by subscript to the generated target to linked shortening the linked at traversal time and speeding box 31 list accessed box the provide the pointer examines the up the search records in the expense For of perhaps leaving some expired Decision 33 pointer list value deter If to 65 the list mine whether the end of the linked reached match decision has been is reached entered in decision modified to terminate like example the when key match alternate procedure occurs can be PASCALtahl has the even end has been if box pseudocode for this version of search determine box 39 key will was previously found If appears in the is APPENDIX The implementor strategies as he described below so the search prerogative of choosing among these dynamically BTEX0000I 69 5893120 at the time search table all is invoked by the at at caller other other thus sometimes removing choosing decision removing expired records and yet times times begins at staring bps 70 from which box box 71 the search table procedure of FIG the search 71 is is entered In invoked with in the some to but not all of them key with of the record the to he inserted As noted finds remove be none based is of them Such on factors in dynamic runtime connection linked therein list FIG whose the search table procedure ceeord might such as for example pool records other element key value key of the contained time list how much memory system residing available the the matches expired box the search system storage and where at the same that it general currently factors load in time of day the information numher of system and removes Decision whether records is on-the-fly entered from linked 72 then table If is determined record the both internal and external itself to the information in the expired to search procedure is found where with record in In the storage art and retrieval system the person skilled all will matching to key value is so box 73 into the entered list be inserted appreciate that technique linked not the of removing list records position include are replaced terminal put linked element value of the insert old record with matching reports that the the key old box while searching techniques the can be all expanded 74 the procedure record has been in whereby that necessarily expired records if removed and records In to decision regarding and how many by the box new record and procedure terminates 75 to delete there can is he dynamic one Returning of remove system as decision box is 72 if matching to record if is not is FIG shown record flowchart proce either will found decision storage list box 76 entered determine there dure that removes an unexpired noted through with in from the the retrieval sufficient in the system storage If is pool to accommodate is record through with table delete procedure or an noted be new that 20 inserted nal If linked element system that not fall box and the entered record to report connection the search In FIG is expired in record the storage cannot in be procedure as connection Following the procedure terminates termi FIG table general this the accomplished procedure passing list by the invoking box 75 box 76 determines system is procedure search being either procedure pointer that to delete HG the to array or the decision that sufficient storage can FIG linked predecessor to remove be list allocated from the then is storage pool for the new linked procedure pointer linked to list element element table the In elements in the remove same location list element box 78 In entered where actual memory is is 25 allocation made the box 79 the record to he box inserted and the subscript the pointer is to of the the hash of copied entered record to 30 into In storage allocated linked in list 78 into and box 80 containing head linked the case from the list box 80 it the in element containing the linked the list which element the the the to element to is be the removed first that copied the that into box 79 record is inserted be removed pointer element of the linked procedure which contained the record bashed inserted in The procedure into the then predecessor invoking or passed to the has the procedure value to ML remove by reports storage terminates was information sometimes the called and retrieval in system box 81 and the procedure NULL the EMP1Y element indicating to remove proce in box 75 detailed record Starting flowchart dure that list the he removed has no predecessor expects advanced now-removed in that final the the FIG used to retrieval shows retrieve of retrieve The on invoking completion procedure to remove passed element from in the information storage procedure and procedure pointer that it if have to the originally to the pointed successor dure record it of HG to system is box invoked as in box 90 the search table proce 91 using the key of the key not In decision so that or ML points the element linked list be retrieved if the search box 92 found to removed procedure element of FIG was the element The in is determined the record with procedure retrieve If matching box key was 93 is search the table in particular this makes use of the by 40 search failure in table entered remove procedures advancing use passed pointer described entered way directly it is made of in that box 33 of of box FIG as report is of the terminal is procedure and the procedure record terminates box to 96 copy If the following in completion with 42 was matching matching was into descrihed The ahove connection FIG actual found box 94 record store to is entered record for processing remove procedure by element has the causes the removal of the entered return by the calling program box 95 and an indication of successful retrieval in terminal designated that the array it element the adjusting to predecessor In pointer so 45 the procedure terminates detailed box of 96 delete bypasses be removed the ease that table role HG.7 useful storage shows actively flowchart records Starting search procedure information predecessor entry pointer the NIL value is the hash the for removing system the from the at indicated by passed subscript adjusted the the plays and retrieval box 100 the of the its predecessor Following the pointer pointer and same storage stead by adjustments is way in occu system cedure of in FIG invokes table procedure to of HG the pro box 101 using the key box able of the record be deleted if as pied storage removed element allocation starting returned to the seareh key In decision table 102 to it is determined the search pool for future then at procedure box 103 and was is to find record with matching of the in as key box by Beginning to it box 50 is of FIG in the pointer If not entered report failure deletion the list element its to remove in the advanced list box 51 so that box procedure the procedure record remove in terminates terminal points to successor if linked to Next is decision first 106 in If matehing box 102 the was found with determined is 52 in determines the the element list remove by the the element decision procedure of containing for the to linked pointer is ML testing predecessor If box 104 A_s noted connection of FIG FIG linked is invoked remove element to the the list value the as described list ahove pointer so box 54 in the procedure from report its causes removal containing linked designated entered array adjust to linked the to head hash the list to Box 105 then entered table bypass on first element If after which is successful deletion the calling program and procedure where element again the to the to continues box 55 is not box to entered the 60 procedure terminates in terminal box 106 PASCAL-like predecessor pointer adjusted bypass The attached APPENDIX for all contains remove after which in the procedure proceeds once by pseudocede necessary system to listings box 55 of the programmed components storage the will present Finally is box 55 the to the storage occupied storage implement in an information with art and retrieval invention no difficulty bypassed the element returned and procedure shows for terminates detailed in the system in terminal box of an pool operating accordance skill 56 procedure retrieval 65 HG suitable My person implementing the of ordinary the in the have flowchart information insert disclosed including system and procedures for all use storage insert and system of the present inveotion The procedure of HG APPENDIX and system programs shown in common hard basis ware software arrangements on the of this BTEX0000I 70 5893120 tO description the It including flowcharts and information shown in present that the invention It is also clear to those in skilled in the art APPENDIX should also invention and is can it be is used diverse to the computcr of be clear to those skilled in the art that other those applications tables lists that not limited techniques use hash linked embodiments skilled in the of the present art invention may be wade by from the teachings but applicable to other requiring without departing of the with expiring records Appendix Functions Provided The rolling insert Returns functions are made available to the application program record record_type if replaced record associated with record.key was round and subsequently Returns passed Returns record retrieve Returns recorrt Returns delete replaced inserted it record subseqnently associated inserted with recorstkey was not frund and the record full if was record associated with no recorrtkey was is not round arid the passed could not be inserted because memory available record success record if type record associated with reeord.key was found and assigned to failure if search was unsuccessful record success deleted key record_key_type if Returns quently Returns record associated with record_key was found sad subse failure if not found Definitions tire following formal definitions global to all are required for specifying functions the insertion retrieval and deletion procedures connt rype type They are procedures and shown below Size of of hash linked linked table list list table .aize list_element Pointer list_element_pointer list...elenrent to elements rI element of record record contenrs record_type /5 Singly-linked lint next end var table lrnt_etement_poutter array table_size lJ of list_element_pointer I-lash table of lint Each Initial array entry is pointer to bead state of table tablefi nil table_size Insert Procedure tnitially empty function var insert position record record type replaced inserted full Pointer or into list list.element_pointe of found if record found new element positions to not dummy_pointer index begin if list_element table aize pointer fhble Dont index need predecessor hash function mapped by search_table then begin recordirey position dummy_pointer index Record already passed exist record 5/ Yea .reeord_contenla update it with positiont return record replaced end else if No available then return insert /s if new record at bead to fur of list so sI no memory else full memory is available available allocate do begin Memory record node node it newposition positiont .record .next contents Dynamically new hook in position tablerindex position tablr return inserted else /5 Retrieve insert 5/ begin 5/ end end Procedure function var retrieve position var record rordtype success failure Pointer into list list_element_pointer list_element_pointer table size ot round record durrtmy_poisrer drrmmy._indrx begin if Dont Dont need table index need positions to predecessor function mapped by hash search_table then begin record.key position dummy_pointer dununy index Record exist caller Yes position success .record return it to record return contents end else return failure retrieve /5 No report failure end BTEX0000I 71 5893120 11 -continued 12 Appendix Delete Procedure function var delete position record key record_key_type elencnt_potnter succcssinilure /e /C Table Pointer Points into to list Iist_eleinent._potnter ...position list.. of found record Cl 5/ previous positions to predecessor function index begin if table_size index mapped by hash search_table then begin record_key position previous_position index /5 te Record Yes exist it si remove remove return position success previous_position index end else return failure delete No Search Ibble Procedure report failure end function search table var vat var record position key record_key_type list_element_pointer list_element previous_position inder record_key _pointer boolean table_size Search point to table located is for and delete expired records to its in target list if found is position is made otherwise to record index and is prevtous_position set to table predecessor and is TRUE returned in FALSE ease vsr 5/ returned- subscript thst mapped to by hash function either list_element pointer je Used Points for to traversing chain previous_p begin index list element_pointer ps predecessor table_size before Cl hash record_keg hash returns value in the range /s tsbl4indcxj previous_p position previous_position while nil nil nil tnitialization loop lilto /a Ditto Ditto 5/ 5/ 5/ ps nil HttAR1 OP TI-lIt TECHNIQUE Traverse expired entire records lint as deleting 5/ we sesrch begin if pt then else .record_cnntenls is expired remove begin position previous_p index /5 ON-THE-FLY REMOVAL OF EXPIRED RECOI1Dt if nil then if p1 .record_contents.key record_key /5 If this is record wantedf then begin position pi previous_position previous_p end save its position to WI previous_p .scxt /s Advance next record begin 5/ end /5 else end return position nil Return /s Alternate Version TRUE table if record located otherwise FAISF. SI end search thble of Search Procedure function search_table var var var record_key position previous reeord_ key_type list_element_pointer ..position list_element_pointer boolean index table_size SAME AS VERSION SHOWN ABOVE EXCEPT THAT ITR3 RECORI IS FOUND INSTEAD OP ALWAYS TRAVERSING var SEARCH TERMNAEES 1TIE ENTIRE CHAIN Used Points for to IF lint_element previous_p pointer txaverning chain list_element_pointer ps predecessor table_size before /5 /n 5/ begin index hash record_key hash returns value in the range trrble previous_p position previous_position while nil Initialization loop Ditto Ditto Ditto 5/ 5/ 5/ 5/ nil nil nil /5 hEART OF TIlE TECHNIQUE /5 expired Traverse records list as deleting we search begin if p1 then else if record_contents is expired remove begin previous_ index fS ON fIB-PLY REMOVAl OF EXPIRED If thin /5 in RItCORDI 5/ .record_contents.key then begin record_key record its wanted5/ position 5/ save positiott previous return position previous /5 true We found the record so terminate search 5/ end previous_p next /s Advance next to 5/ 5/ record BTEX0000I 72 5893120 13 eontinued 14 Appendix end /5 else begin 5/ end return false /5 aearch.tnble /5 Record not found end Remove Procedure procedure remove var elem to dcl list_element.pointer previous_elem index /5 Delete list_element_pointer table_size dent_to_del from list advancing nil if elem_to_del is to next element in previous_clem points to elem_to_dels var begin predecessor or etem_to_delt element Save lisL/ to list_element_pointer pointer elem_to_del ror disposal elem_to_del cleat_to_del ir /5 Save so we can dispose wben tmnisbcd adjusting pointers dent nil to deif next /a Deleting previous_elem then else element head /5 ja requires as changing opposed pointer to 5/ 5/ tahl4index previous_elemf dent next to del pointer elem_to_del predecessors next dispose Dynamically dc-allocate node end rcmove/ claim technique storage to store the the records with same hash automatically search the address An information and retrieval system the system 25 at least some of records expiring key to access comprising linked in list record linked search means list utilizing to store and provide access at to records the stored records the of records memory of the system expiring means utilizing least some of having including same hash means address record search and removing at automatically record linkcd the record search list search means least list for identifying of the records list is search key to access the 311 some expired ones when the from the linked of records linked means at including means the for identifying acce.ssed and the and removing from and least some of list expired ones the linked of the list is meals utilizing record search records at means for inserting records the linked when retrieving the and deleting from the system and at accessed same time removing records in the least linked some expired ones of list means the utilizing linked list the record at and the search means for accessing same time removing at least the accessed of records according deter to The information to storage and retrieval system some of list the expired ones of the records in the linked claim further including means for the list for record dynamically search mining storage maximum in the number means The information to and retrieval system according dynamically search deter to 40 remove accessed for storing linked of records information to the the records records records auto- claim further including means for the list for record method using hashing and retrieving to mining remove maximum in the numher means technique provide access accessed for storing list to linked of records information to the records and using an external with same hash matieally chaining technique at least to store the the method using at and retrieving address the some of records steps linked store and provide access automatically records the least some expiring method list comprising records of hash of the the records steps list expiring method comprising the of records automatically expired accessing address linked of having same accessing identifying linked of at least some and of the ones so identifying at least some of the automatically expired ones of the removing records of the removing records records at records at least the least the some linked of the list automatically expired list is some linked of the list automatically expired list is from when the linked from and when the linked accessed The step accessed according to method claim further including the inserting the retrieving or deleting the to step one of the records from of dynamically of the determining to maximum when the number of linked list system following according of removing further including the expired ones is records remove The method step claim accessed of dynamically ones of the determining records to maximum when the number linked of list An information storage and retrieval system the system expired is remove comprising hashing accessed means of the to provide access to records stored in 60 memory system and using an external chaining BTEX0000I 73

Disclaimer: Justia Dockets & Filings provides public litigation records from the federal appellate and district courts. These filings and docket sheets should not be considered findings of fact or liability, nor do they necessarily reflect the view of Justia.

Why Is My Information Online?