Re: [Caml-list] How could I implement an efficient ring buffer?

[Gabriel Scherer <gabriel.scherer@gmail.com>]

A small implementation of a FIFO queue implemented as a circular
buffer of fixed length:

type 'a circular_buffer = {
  mutable pos : int;
  mutable count : int;
  data : 'a array;
  size : int;
}

let create size dummy = {
  pos = 0;
  count = 0;
  data = Array.make size dummy;
  size;
}

let push buffer elem =
  let k = buffer.pos + buffer.count in
  buffer.data.(if k < buffer.size then k else 0) <- elem;
  if buffer.count < buffer.size then
    buffer.count <- buffer.count + 1
  else
    buffer.pos <- buffer.pos + 1;
  ()

let pop buffer =
  if buffer.count = 0 then raise Not_found;
  let result = buffer.data.(buffer.pos) in
  (* if you want to free the buffer content, buffer.data.(pos) <- dummy *)
  let pos' = buffer.pos + 1 in
  buffer.pos <- (if pos' < buffer.size then pos' else 0);
  buffer.count <- buffer.count - 1;
  result

(* test *)
let () =
  let buf = create 2 '0' in
  (* *)
  push buf '1';
  (* 1 *)
  push buf '2';
  (* 1 2 *)
  push buf '3';
  (*   2 3 *)
  assert (pop buf = '2');
  (*     3 *)
  push buf '4';
  (*     3 4 *)
  assert (pop buf = '3');
  (*       4 *)
  assert (pop buf = '4');
  (*         *)
  assert (try ignore (pop buf); false with Not_found -> true);
  assert (try ignore (pop buf); false with Not_found -> true);


On Mon, Apr 2, 2012 at 5:04 PM, David Allsopp <dra-news@metastack.com> wrote:
> Hongbo Zhang wrote:
>> Hi List,
>>     I want to implement sliding window algorithm (in place, no memory
>> copy), I wonder whether I need to write c code.
>>
>>     To make it clear and simple,
>>        In c, you can record the head pointer of the array, and do the
>> modulo operations when get and set
>>        In ocaml, it seems you have an array a of type int array,  you can
>> not do things like this *(&a+5).
>
> Perhaps I'm missing something, but if you're planning on using arrays, what's wrong with retrieving the item using the array index modulo the length of the array?
>
> i.e.
>
> let a = [| ... or whatever ... |] in
> a.(5 mod Array.length a)
>
> If accessing an array by index instead of by pointer worries you, then you're looking at the wrong language ;o)
>
>
> David
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>