Destructive Reordering of CDR-Coded Lists
Linked list structures can be compactly represented by encoding the CDR ("next") pointer in a two-bit field and linearizing list structures as much as possible. This "CDR-coding" technique can save up to 50% on storage for linked lists. The RPLACD (alter CDR pointer) operati...
| Հիմնական հեղինակ: | |
|---|---|
| Լեզու: | en_US |
| Հրապարակվել է: |
2004
|
| Առցանց հասանելիություն: | http://hdl.handle.net/1721.1/5703 |
| _version_ | 1826217492013383680 |
|---|---|
| author | Steele, Guy L., Jr. |
| author_facet | Steele, Guy L., Jr. |
| author_sort | Steele, Guy L., Jr. |
| collection | MIT |
| description | Linked list structures can be compactly represented by encoding the CDR ("next") pointer in a two-bit field and linearizing list structures as much as possible. This "CDR-coding" technique can save up to 50% on storage for linked lists. The RPLACD (alter CDR pointer) operation can be accommodated under such a scheme by using indirect pointers. Standard destructive reordering algorithms, such as REVERSE and SORT, use RPLACD quite heavily. If these algorithms are used on CDR-coded lists, the result is a proliferation of indirect pointers. We present here algorithms for destructive reversal and sorting of CDR-coded lists which avoid creation of indirect pointers. The essential idea is to note that a general list can be viewed as a linked list of array-like "chunks". The algorithm applied to such "chunky lists" is a fusion of separate array- and list-specific algorithms; intuitively, the array-specific algorithm is applied to each chunk, and the list algorithm to the list with each chunk considered as a single element. |
| first_indexed | 2024-09-23T17:04:30Z |
| id | mit-1721.1/5703 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:04:30Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/57032019-04-12T08:27:11Z Destructive Reordering of CDR-Coded Lists Steele, Guy L., Jr. Linked list structures can be compactly represented by encoding the CDR ("next") pointer in a two-bit field and linearizing list structures as much as possible. This "CDR-coding" technique can save up to 50% on storage for linked lists. The RPLACD (alter CDR pointer) operation can be accommodated under such a scheme by using indirect pointers. Standard destructive reordering algorithms, such as REVERSE and SORT, use RPLACD quite heavily. If these algorithms are used on CDR-coded lists, the result is a proliferation of indirect pointers. We present here algorithms for destructive reversal and sorting of CDR-coded lists which avoid creation of indirect pointers. The essential idea is to note that a general list can be viewed as a linked list of array-like "chunks". The algorithm applied to such "chunky lists" is a fusion of separate array- and list-specific algorithms; intuitively, the array-specific algorithm is applied to each chunk, and the list algorithm to the list with each chunk considered as a single element. 2004-10-01T20:31:53Z 2004-10-01T20:31:53Z 1980-08-01 AIM-587 http://hdl.handle.net/1721.1/5703 en_US AIM-587 15 p. 5323679 bytes 3774242 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Steele, Guy L., Jr. Destructive Reordering of CDR-Coded Lists |
| title | Destructive Reordering of CDR-Coded Lists |
| title_full | Destructive Reordering of CDR-Coded Lists |
| title_fullStr | Destructive Reordering of CDR-Coded Lists |
| title_full_unstemmed | Destructive Reordering of CDR-Coded Lists |
| title_short | Destructive Reordering of CDR-Coded Lists |
| title_sort | destructive reordering of cdr coded lists |
| url | http://hdl.handle.net/1721.1/5703 |
| work_keys_str_mv | AT steeleguyljr destructivereorderingofcdrcodedlists |