Memory Allocator

Question

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>

• Doorknob: I doubt Python lists take up exactly one byte per element. Does the "allocated memory" have to be in bytes, or can it just be "your language's generic array/list type"?
• helloworld922: No actual allocation is required (except for whatever you want for internal state tracking, which is on its own virtual address space); you're only returning integers to some abstract finite virtual address space.
• The Coder: 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
• Xwtek: Huh, language-design?
• Martin Ender: While this challenge is motivated with a language design background, designing a language is not actually part of the task (rather implementing parts of one), so I've removed the tag.

Answer 1

Ruby, 80

i,a,d=->n{$m=?o*n},->n{$m.sub!(/\B#{?o*n}/,?f*n);"#$`".size},->n,s{$m[n,s]=?o*s}

Like MegaTom's answer, but uses a string instead of an array to store state. The "o" character denotes an open cell, while an "f" denotes a filled one. This lets us use Ruby's relatively terse string manipulation functions:

?o*n initializes a string of n "o"s.

/\B#{?o*n}/ is a regular expression matching n consecutive "o"s that doesn't include the first character. sub! replaces the first match with n "f"s.

"#$`" gives the string to the left of the match, or an empty string if there was no match, so the size is either the allocated index or 0.

Deallocate just sets the designated section of the string back to "o"s.

Answer 2

JavaScript (ES6), 88

Using a global variable _ (a very sparse array) to keep track.

Now how could I test it?

I=n=>(_=[1],_[n]=0)
A=n=>_.some((x,i)=>i-p<n?(p=i+x,0):_[p]=n,p=1)?p:0
D=p=>delete _[p]

Answer 3

Ruby, 135

Has a global array keep track of whether each cell is allocated or not.

i=->n{$a=[!0]*n;$a[0]=0}
a=->n{s=$a.each_cons(n).to_a.index{|a|a.none?};n.times{|i|$a[s+i]=0}if s;s||0}
d=->s,n{n.times{|i|$a[s+i]=!0}}

Answer 4

Mathematica, 152

i=(n=#;l={{0,1},{#,#}};)&
a=If[#=={},0,l=l~Join~#;#[[1,1]]]&@Cases[l,{Except@n,e_}:>{e,e+#}/;Count[l,{a_,_}/;e<=a<e+#]<1,1,1]&
d=(l=l~DeleteCases~{#,_};)&

n store the total size, l stores the internal state. The allocator will try to allocate right behind another section of allocated memory.