File: gen_list.ads

package info (click to toggle)
libtexttools 2.0.3-4
  • links: PTS
  • area: main
  • in suites: etch, etch-m68k
  • size: 1,188 kB
  • ctags: 635
  • sloc: ada: 13,120; cpp: 1,679; ansic: 777; makefile: 156; sh: 2
file content (183 lines) | stat: -rw-r--r-- 8,012 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
------------------------------------------------------------------------------
-- GEN LIST                                                                 --
--                                                                          --
-- Part of TextTools                                                        --
-- Designed and Programmed by Ken O. Burtch                                 --
--                                                                          --
------------------------------------------------------------------------------
--                                                                          --
--                 Copyright (C) 1999-2003 Ken O. Burtch                    --
--                                                                          --
-- This is free software;  you can  redistribute it  and/or modify it under --
-- terms of the  GNU General Public License as published  by the Free Soft- --
-- ware  Foundation;  either version 2,  or (at your option) any later ver- --
-- sion.  This is distributed in the hope that it will be useful, but WITH- --
-- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License --
-- for  more details.  You should have  received  a copy of the GNU General --
-- Public License  distributed with this;  see file COPYING.  If not, write --
-- to  the Free Software Foundation,  59 Temple Place - Suite 330,  Boston, --
-- MA 02111-1307, USA.                                                      --
--                                                                          --
-- As a special exception,  if other files  instantiate  generics from this --
-- unit, or you link  this unit with other files  to produce an executable, --
-- this  unit  does not  by itself cause  the resulting  executable  to  be --
-- covered  by the  GNU  General  Public  License.  This exception does not --
-- however invalidate  any other reasons why  the executable file  might be --
-- covered by the  GNU Public License.                                      --
--                                                                          --
-- This is maintained at http://www.vaxxine.com/pegasoft                    --
--                                                                          --
------------------------------------------------------------------------------
--
-- A generic package for handling general purpose linked lists.
-- eg. package AnIntegerList is new list_manager(integer, "=", ">=");
--     MyIntegerList : AnIntegerList.List;

with Ada; use Ada;
with Unchecked_Deallocation;

generic

  -- There are three generic parameters:
  --   AListElement -- what the list is made of
  --   >=           -- used by find to match an item
  --   >=           -- used by insert to maintain a sorted list

  type AListElement is private;
  with function "=" (x, y : AListElement ) return boolean is <>;
  with function ">=" (x, y : AListElement ) return boolean is <>;

package gen_list is

---> List Structure
--
-- A List is composed of a list header (List) with a single-linked
-- list chain of records (AListRecord).
--
-- The header contains convenient pointers to the first and last
-- records, as well as a count of the number of records.
--
-- As a quick way to increase speed on small lists that undergo constant
-- change (eg. the event queue), the "FreeCache" field points to a single
-- record (if not null).
--
-- Note: Should be a controlled type (so memory can be discarded
--       during finalization), but no controlled types in gnat 2.0.
--       Make sure all lists are cleared before discarding them!

type AListRecord;
type AListRecordPtr is access AListRecord;
--pragma Controlled( AListRecord ); -- no garbage collection, Ada!
subtype AListIndex is long_integer range 0..long_integer'last;
-- yeah, AListIndex should be it's own type, but then you have to "use"
-- the list to make operations like "+" visible, because it's a generic.
-- That's too inconvenient.

type AListRecord is record
     Data : AListElement;       -- the user data
     Next : AListRecordPtr;     -- pointer to next item
end record;

type List is private;

type ListPtr is access all List;
-- and, yeah, List should be (and was) limited private, but then it can't
-- be used in objects!  Where do these stupid rules come from?!

---> Package Level Operations
--
-- GetAllocation - get number of bytes allocated (for memory leak testing)
-- MemoryLeak    - checks if current number of records is same as allocation

procedure GetAllocation( allocation : out AListIndex );
function  MemoryLeak( allocation : in AListIndex ) return boolean;

---> List Level Operations
--
-- Compact - remove records waiting for deallocation & general tidying
--         - (this procedure's use is optional)
-- Clear   - removes all items, disposes of all allocated memory
-- Copy    - makes one (or two) copies of a list
-- Move    - move list from one list variable to another
-- Swap    - swap lists in two variables

procedure Compact( TheList : in out List );
procedure Clear( TheList : in out List );
procedure Copy( FromList, ToList : in out List );
procedure Copy( FromList, ToList1, ToList2 : in out List );
procedure Move( FromList, ToList : in out List );
procedure Swap( List1, List2 : in out List );

---> Adding Items
--
-- Push = add to front of list
-- Queue = add to end of list
-- Insert = add to a priority queue

procedure Push( TheList : in out List; NewData : AListElement );
procedure Queue( TheList : in out List ; Data : AListElement );
procedure Insert( TheList : in out List ; Data : AListElement );
procedure Insert( TheList : in out List ; atIndex : AListIndex;
                  Data : AListElement );

---> Removing Items
--
-- Free should be declared in the body (oh, well..)
-- Pull - remove an object from the front of a list
-- Clear - remove the nth object from a list; returns Constraint_Error
--         if index is out of range

procedure Free is new Unchecked_Deallocation(
       Object => AListRecord,
       Name   => AListRecordPtr );
procedure Pull( TheList : in out List ; data : in out AListElement );
procedure Pull( TheList : in out List );
procedure Cut( TheLIst : in out List; atIndex : AListIndex;
   data : in out AListElement );
procedure Clear( TheList : in out List ; atIndex : AListIndex );

---> Find and replace
--
-- Find - return nth element of the list
--      - or find next occurance of data
-- Replace - rewrites the data in element n

procedure Replace( TheList : in out List; atIndex : AListIndex;
          data : AListElement );
procedure Find( TheList : in out List ; atIndex : AListIndex ;
          data : in out AListElement );
procedure Find( TheList : in out List ; data : AListElement;
          start : AListIndex := 1; FoundAt : in out AListIndex );

---> List attributes
--
-- Length  = number of items in the list
-- IsEmpty = true of no items in list (what else?!)

function Length( TheList : in List ) return AListIndex;
function IsEmpty( TheList : in List ) return boolean;

---> Sublists and List Arithmetic
--
-- SubList - extract a portion of a list, mainly for list controls
-- Concat  - add two lists together

procedure SubList( TheList : in out List; index, len : AListIndex;
   Result : in out List );
procedure Concat( List1, List2 : List; Result : in out List );

private ----------------------------------------------------------

---> List Definition

type List is record
     First     : AListRecordPtr := null; -- the first record in list (or null)
     Last      : AListRecordPtr := null; -- the last record in list
     Count     : AListIndex     :=    0; -- number of records in the list
     FreeCache : AListRecordPtr := null; -- pointer to a recyclable record
     LastRec   : AListIndex     :=    0; -- last record accessed (or undefined)
     LastPtr   : AListRecordptr := null; -- last record accessed (or nil)
end record;

end gen_list;