1 //  $Id$
2 // Copyright (c) 2001,2002                        RIPE NCC
3 //
4 // All Rights Reserved
5 //
6 // Permission to use, copy, modify, and distribute this software and its
7 // documentation for any purpose and without fee is hereby granted,
8 // provided that the above copyright notice appear in all copies and that
9 // both that copyright notice and this permission notice appear in
10 // supporting documentation, and that the name of the author not be
11 // used in advertising or publicity pertaining to distribution of the
12 // software without specific, written prior permission.
13 //
14 // THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
15 // ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS; IN NO EVENT SHALL
16 // AUTHOR BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY
17 // DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
18 // AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
19 // OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 //
21 //
22 //  Copyright (c) 1994 by the University of Southern California
23 //  All rights reserved.
24 //
25 //    Permission is hereby granted, free of charge, to any person obtaining a copy
26 //    of this software and associated documentation files (the "Software"), to deal
27 //    in the Software without restriction, including without limitation the rights
28 //    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
29 //    copies of the Software, and to permit persons to whom the Software is
30 //    furnished to do so, subject to the following conditions:
31 //
32 //    The above copyright notice and this permission notice shall be included in
33 //    all copies or substantial portions of the Software.
34 //
35 //    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
36 //    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
37 //    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
38 //    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
39 //    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
40 //    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
41 //    THE SOFTWARE.
42 //
43 //  Questions concerning this software should be directed to
44 //  irrtoolset@cs.usc.edu.
45 //
46 //  Author(s): Cengiz Alaettinoglu <cengiz@ISI.EDU>
47 
48 #ifndef Allocator_H
49 #define Allocator_H
50 
51 #include "config.h"
52 #include <cstdio>
53 #include <cstdlib>
54 #ifdef HAVE_MALLOC_H
55 extern "C" {
56 #include <malloc.h>
57 }
58 #endif // HAVE_MALLOC_H
59 
60 // we allocate memory of chunks AllocatorChunkSize
61 // AllocatorLargeRequestSize is the largest possible fragmentation we can have
62 #define AllocatorChunkSize (1024 * 1024 - sizeof(void *))
63 #define AllocatorLargeRequestSize (16 * 1024)
64 
65 class Allocator {
66 private:
67    void *root;
68    void *free_ptr;
69    int  size;
70    int  large_request;
71    int  remaining;
72 
get_more_memory(int request)73    void *get_more_memory(int request) {
74       void *p = malloc(request + sizeof(void *));
75 
76       * (void **) p = root;
77       root = p;
78       p = (char *) p + sizeof(void *);
79       return p;
80    }
81 
82 public:
Allocator(int _size=AllocatorChunkSize,int _large_request=AllocatorLargeRequestSize)83    Allocator(int _size = AllocatorChunkSize,
84 	     int _large_request = AllocatorLargeRequestSize) {
85       size = _size;
86       large_request = _large_request;
87       remaining = 0;
88       free_ptr = NULL;
89       root = NULL;
90    }
91 
~Allocator()92    ~Allocator() {
93       deallocate_all();
94    }
95 
allocate(size_t request)96    void *allocate(size_t request) {
97       void *result;
98 
99       if (request > large_request)
100 	 return get_more_memory(request);
101 
102       if (request > remaining) {
103 	 free_ptr = get_more_memory(size);
104 	 remaining = size;
105       }
106 
107       result = free_ptr;
108       free_ptr = (char *) free_ptr + request;
109       remaining -= request;
110       return result;
111    }
112 
deallocate(char *)113    void deallocate(char *) { // intentionally blank
114    }
115 
deallocate_all()116    void deallocate_all() {
117       for (void *p = root; p; p = root) {
118 	 root = * (void **) root;
119 	 free(p);
120       }
121       remaining = 0;
122       free_ptr = NULL;
123       root = NULL;
124   }
125 };
126 
127 #endif   // Allocator_H
128