You're designing a new esoteric programming language and one feature you've decided to add is a dynamic memory allocator. Your language specifies a special dedicated virtual address space for the user's program space. This is separate from the address space used by the memory allocator for any internal state.
To help reduce the cost of distributing your implementation the size of the code must be as small as possible.
Interface
You must provide three functions: initialization, allocate, and deallocate.
Initialization
This function takes a single positive integer parameter N
. This means a user's program has N
bytes in its address space from which there are N-1
bytes to allocate memory from. The address 0
is reserved for "null".
It is guaranteed that this function will be called exactly once before any allocate/deallocate calls.
Note that this function does not need to allocate any physical memory for the user program's virtual address space; you're basically creating the "look and feel" of a hollow memory allocator.
Allocate
The allocate function must take a request of the number of bytes of memory to allocate. The input is guaranteed to be positive.
Your function must return an integer address to the start of the allocated block, or 0
to denote that there is no contiguous block of the requested size available. If a contiguous block of the available size is available anywhere in the address space you must allocate!
You must ensure that no two allocated blocks overlap.
Deallocate
The deallocate function must take an address of the start of an allocated block, and optionally may also take the size of the given block.
Memory that has been deallocated is available again for allocation. It is assumed that the input address is a valid address.
Example Python implementation
Note that you may choose any method for keeping track of internal state; in this example the class instance keeps track of it.
class myallocator:
def __init__(self, N):
# address 0 is special, it's always reserved for null
# address N is technically outside the address space, so use that as a
# marker
self.addrs = [0, N]
self.sizes = [1, 0]
def allocate(self, size):
for i,a1,s1,a2 in zip(range(len(self.addrs)),
self.addrs[:-1], self.sizes[:-1],
self.addrs[1:]):
if(a2 - (a1+s1) >= size):
# enough available space, take it
self.addrs.insert(i+1, a1+s1)
self.sizes.insert(i+1, size)
return a1+s1
# no contiguous spaces large enough to take our block
return 0
def deallocate(self, addr, size=0):
# your implementation has the option of taking in a size parameter
# in this implementation it's not used
i = self.addrs.index(addr)
del self.addrs[i]
del self.sizes[i]
Scoring
This is code golf; shortest code in bytes wins. You need not worry about running out of memory for any internal state required by your allocator.
Standard loop holes apply.
Leaderboard
var QUESTION_ID=67895,OVERRIDE_USER=31729;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
To help reduce the cost of distributing your implementation the size of the code must be as small as possible
or could it be efficient (small and efficient are not same) as possible? :D \$\endgroup\$