From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,ddba2f4eebde1467 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2003-07-31 09:50:08 PST Path: archiver1.google.com!postnews1.google.com!not-for-mail From: mheaney@on2.com (Matthew Heaney) Newsgroups: comp.lang.ada Subject: Re: Elegant 'realloc'? Date: 31 Jul 2003 09:50:07 -0700 Organization: http://groups.google.com/ Message-ID: <1ec946d1.0307310850.3b9842ea@posting.google.com> References: <1ec946d1.0307310642.74d93921@posting.google.com> NNTP-Posting-Host: 66.162.65.162 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1059670208 28832 127.0.0.1 (31 Jul 2003 16:50:08 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 31 Jul 2003 16:50:08 GMT Xref: archiver1.google.com comp.lang.ada:41085 Date: 2003-07-31T16:50:08+00:00 List-Id: Lutz Donnerhacke wrote in message news:... > * Matthew Heaney wrote: > > Lutz Donnerhacke wrote in message news:... > >> When dealing with dynamically allocated variable length arrays, the > >> allocated space might change. Is there a common idiom to simulate an > >> 'realloc' (especially shrinking) other than, allocate, copy, free? > > > > I don't know how to implement a realloc in Ada, unless you write your own > > storage pool. > > Any hint? A storage pool is typically implemented using a Storage_Array. When you allocate, you're really allocating an array that is at least as big as the size of the allocation request. The internal array might be longer, so in theory you could give the caller the rest of the array. I haven't tried this, so I don't know whether it's even possible. One issue that comes to mind immediately is initialization of array components, which is controlled by the Ada run-time. But it's not clear whether any of this is necessary. This does exactly what a vector constainer does already, so why not just use a vector? > > You can try using the vector container in Charles, which hides all the > > allocate, copy, and free calls. > > Performance does matter in this case. So hiding necessary parts does not help. The cost of insertion into a vector container (at least, insertion at the back end of the vector) is amortized constant time. You can't do better than that, so it's not clear what your performance issue is. > > The length of the vector refers to the number of active elements in the > > vector. The size of the vector refers to the length of the underlying > > array, which is at least the number of elements. > > Exactly this is the way I implement it: Trading allocated space for running > time. Internal reallocation during insertion into a vector container occurs under precisely specified conditions. Also, the size of the newly-allocated internal array is always a function of the current size of the internal array. It does not depend on the number of active elements (if it did then insertion wouldn't be amortized constant time). In Charles the size of the newly-allocated internal array is two times the current size. So internal reallocation in a vector container does exactly what realloc would do. Most of the time reallocation won't be necessary, and inserting an element into the vector will simply update the length. If you know apriori the number of elements you intend to put in the vector container, then you can always call Resize, which preallocates an internal array having at least the specified size. Charles is available at my home page. http://home.earthlink.net/~matthewjheaney/charles/