Laden...

Ringspeicher bzw. Circular Buffer

Erstellt von der-schlingel vor 14 Jahren Letzter Beitrag vor 14 Jahren 8.450 Views
der-schlingel Themenstarter:in
799 Beiträge seit 2007
vor 14 Jahren
Ringspeicher bzw. Circular Buffer

Beschreibung:

Eine kleine Implementation eines Ringspeichers. Hier gibt es nicht viel zu sagen, ich glaube der Code erklärt sich soweit von selbst. Falls nicht, meldet euch dann schreib ich was darüber.


    /// <summary>
    /// A simple implementation of a circular buffer.
    /// </summary>
    /// <typeparam name="T">The type of the items.</typeparam>
    public class CircularBuffer<T> : IEnumerable<T>, ICollection<T>, IEnumerator<T>
    {
        protected static readonly int _MaxLength = 5000;
        /// <summary>
        /// Gets or sets the max length of the buffer.
        /// </summary>
        public int MaxLength { get; set; }

        /// <summary>
        /// Gets or sets the read pointer to the current element.
        /// </summary>
        protected int CurrentReadPointer { get; set; }

        /// <summary>
        /// Gets or sets the write pointer to the current element.
        /// </summary>
        protected int CurrentWritePointer { get; set; }

        /// <summary>
        /// Contains the elements of the buffer.
        /// </summary>
        private IList<T> Elements { get; set; }

        #region ctor
        /// <summary>
        /// Initialize the Elements array with the given array.
        /// </summary>
        /// <param name="elements"></param>
        public CircularBuffer(T[] elements) : this()
        {
            if (elements.Length > MaxLength) { MaxLength = elements.Length; }
            Elements = new List<T>(elements);
        }

        /// <summary>
        /// Initialize the Elements array with the given length.
        /// </summary>
        /// <param name="length"></param>
        public CircularBuffer(int length) : this()
        {
            MaxLength = length;
            Elements = new List<T>(length);
            MaxLength = length;
        }

        /// <summary>
        /// Initialize the circular buffer.
        /// </summary>
        public CircularBuffer()
        {
            MaxLength = _MaxLength;
            Elements = new List<T>(MaxLength);
            CurrentReadPointer = 0;
            CurrentWritePointer = 0;
        }
        #endregion

        #region IEnumerable<T> Members
        /// <summary>
        /// Gets the enumerator for this object.
        /// </summary>
        /// <returns></returns>
        public IEnumerator<T> GetEnumerator()
        {
            return this;
        }

        #endregion

        #region IEnumerable Members
        /// <summary>
        /// Gets the object enumerator for this object.
        /// </summary>
        /// <returns></returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this;
        }

        #endregion

        #region ICollection<T> Members
        /// <summary>
        /// Adds a Item in the circular buffer.
        /// </summary>
        /// <param name="item">The new item.</param>
        public void Add(T item)
        {
            if (CurrentWritePointer >= MaxLength || CurrentReadPointer >= Elements.Count)
            {
                CurrentWritePointer = 0;
            }

            if (Elements.Count > 0 && Elements.Count < CurrentWritePointer)
            {
                Elements[CurrentWritePointer] = item;
            }
            else { Elements.Add(item); }

            CurrentWritePointer++;
        }

        /// <summary>
        /// Clears the collection and resets the read and write pointers.
        /// </summary>
        public void Clear()
        {
            Elements.Clear();
            CurrentWritePointer = 0;
            CurrentReadPointer = 0;
        }

        /// <summary>
        /// Checks if the item is allready in the collection.
        /// </summary>
        /// <param name="item">The item.</param>
        /// <returns>True if the item is there, False if it isn't.</returns>
        public bool Contains(T item)
        {
            return Elements.Contains(item);
        }

        /// <summary>
        /// Copies the elements of this collection to the given array at the given index.
        /// </summary>
        /// <param name="array">The given array.</param>
        /// <param name="arrayIndex">The given index.</param>
        public void CopyTo(T[] array, int arrayIndex)
        {
            Elements.CopyTo(array, arrayIndex);
        }

        /// <summary>
        /// Returns the element count.
        /// </summary>
        public int Count
        {
            get { return Elements.Count; }
        }

        /// <summary>
        /// Returns wether the Elements are read only or not.
        /// </summary>
        public bool IsReadOnly
        {
            get { return Elements.IsReadOnly; }
        }

        /// <summary>
        /// Removes the element from the collection.
        /// </summary>
        /// <param name="item">The element for removing.</param>
        /// <returns>True if it could be removed, false if wasn't there in first place.</returns>
        public bool Remove(T item)
        {
            return Elements.Remove(item);
        }

        #endregion

        /// <summary>
        /// Gets or sets elements at the specific position in the circular buffer.
        /// </summary>
        /// <param name="index">The index of the element.</param>
        /// <returns>The value</returns>
        public T this[int index]
        {
            get { return Elements[index]; }
            set { Elements[index] = value; }
        }

        #region IEnumerator<T> Members
        /// <summary>
        /// Gets the current element.
        /// </summary>
        public T Current
        {
            get { return Elements[CurrentReadPointer]; }
        }
        #endregion

        #region IEnumerator Members
        /// <summary>
        /// Gets the current element as object.
        /// </summary>
        object System.Collections.IEnumerator.Current
        {
            get { return Elements[CurrentReadPointer]; }
        }

        /// <summary>
        /// Moves to the next element.
        /// </summary>
        /// <returns>A value wether it reached the end of the collection.</returns>
        public bool MoveNext()
        {
            if (CurrentReadPointer >= (MaxLength - 1) || CurrentReadPointer >= (Elements.Count - 1))
            {
                CurrentReadPointer = 0;
                return false;
            }

            CurrentReadPointer++;
            return true;
        }

        public bool MoveBack()
        {
            if (CurrentReadPointer <= 0)
            {
                // The latest element
                CurrentReadPointer = Elements.Count - 1;
                return false;
            }

            CurrentReadPointer--;
            return true;
        }

        /// <summary>
        /// Resets the read pointer.
        /// </summary>
        public void Reset()
        {
            CurrentReadPointer = 0;
        }
        #endregion

        /// <summary>
        /// Gets the next element and calculates calculates the next index.
        /// </summary>
        /// <returns>The current element.</returns>
        public T GetNext()
        {
            CalculateCurrendReadIndex();
            int index = CurrentReadPointer;
            CurrentReadPointer++;

            return Elements[index];
        }

        /// <summary>
        /// Checks if the CurrentReadPointer is in the bounds of the elements range.
        /// If it's not this method sets it to start when CurrendReadPointer was greater or
        /// to the end if it was lesser then the elements count.
        /// </summary>
        protected void CalculateCurrendReadIndex()
        {
            if (CurrentReadPointer >= MaxLength || CurrentReadPointer >= Elements.Count)
            {
                CurrentReadPointer = 0;
            }
            else if (CurrentReadPointer < 0)
            {
                CurrentReadPointer = Elements.Count - 1;
            }

        }

        #region IDisposable Members
        /// <summary>
        /// Dispose this element - There isn't anything to do.
        /// </summary>
        public void Dispose() { }

        #endregion
    }
    #endregion

Schlagwörter: Ring Speicher Ringspeicher Circular Buffer

Edit: v2 - Flostes Anmerkungen sind eingeflossen.

As a man thinketh in his heart, so he is.

  • Jun Fan
    Es gibt nichts Gutes, außer man tut es.
  • Erich Kästner
    Krawutzi-Kaputzi
  • Kasperl
1.130 Beiträge seit 2007
vor 14 Jahren
  1. Eine Collection sollte mehrere ienumeratoren gleichzeuitig zulassen, da unter andem verschachtelte Schleifen sonst nicht funktionieren.
public bool Remove(T item)
        {
            return Elements.Remove(item);
        }

Gibt natürlich ein Problem, wenn der Leseindex größer wie der index des zu entfernenden items ist.
3.


public bool MoveNext()
        {
            if (CurrentReadPointer >= MaxLength)
            {
                CurrentReadPointer = 0;
                return false;
            }

            CurrentReadPointer++;
            return true;
        }

Ist es gewollt, dass hinterher CurrentReadPointer gleich MaxLength sein kann, wobei true zurückgegeben wird?
4.

public T Current
        {
            get
            {
                if (CurrentReadPointer >= MaxLength || CurrentReadPointer >= Elements.Count)
                {
                    CurrentReadPointer = 0;
                }

                int index = CurrentReadPointer;
                CurrentReadPointer++;
                return Elements[index];
            }
        }

Getter von Properties sollten normalerweise nichts verändern. Mach ne Methode draus.

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

der-schlingel Themenstarter:in
799 Beiträge seit 2007
vor 14 Jahren

Hallo Floste,

danke fürs Durchsehen und die Anmerkungen. Ich hab mir die Punkte zu Herzen genommen und es bereits ausgebessert. Nun liefert die Methode GetNext() das Element und zählt weiter. Es sind weitere Checks eingebaut und es wird nun immer ein neues Enumerator-Objekt zurückgegeben.

As a man thinketh in his heart, so he is.

  • Jun Fan
    Es gibt nichts Gutes, außer man tut es.
  • Erich Kästner
    Krawutzi-Kaputzi
  • Kasperl
2.760 Beiträge seit 2006
vor 14 Jahren

und es wird nun immer ein neues Enumerator-Objekt zurückgegeben.


        #region IEnumerable<T> Members
        /// <summary>
        /// Gets the enumerator for this object.
        /// </summary>
        /// <returns></returns>
        public IEnumerator<T> GetEnumerator()
        {
            return this;
        }

        #endregion

        #region IEnumerable Members
        /// <summary>
        /// Gets the object enumerator for this object.
        /// </summary>
        /// <returns></returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this;
        }

        #endregion

Ähm wo?

1.564 Beiträge seit 2007
vor 14 Jahren

Hallo der-schlingel

Ein paar Fragen.

Warum verwendest du denn die List<> statt einem normalen Array?

Ist CurrentWritePointer und CurrentReadPointer als protected get/set Properties nicht gefährlich?

MaxLength ist public get/set, hier wird beim aber nicht geprüft wie viele Datensätze derzeit gehalten werden, ob der neue Wert negativ ist oder die Größe des internen Buffers angepasst.

ctor(length) setzt zweimal MaxLength. Ist zwar kein Problem, aber unschön

Wie bereits angesprochen, unterstützt der Buffer derzeit nur sich selbst als Enumerator.

Remove(item) passt den CurrentWritePointer nicht an.

IsReadOnly return Elements.IsReadOnly? Ist doch immer false, oder? Wenn man den Buffer wirklich locken können soll würde ich das implementieren oder einfach "false" zurückliefern. Die Klasse ist ja kein Wrapper.

Der Enumerator ist ein bisschen gefährlich. foreach ruft, wenn ich mich nicht täusche 😉, nicht automatisch Reset() auf. Laufe ich nun zweimal über die Collection dürfte der CurrentReadPointer nicht mehr passen, wenn ich beim ersten Durchlauf mit "break" die Schleife verlasse.

Allgemein sollten die Übergabeparameter der public/protected Properties sowie des Constructors auf Gültigkeitsbereiche sowie NULL validiert werden.

Grüße
Flo

Blog: Things about Software Architecture, .NET development and SQL Server
Twitter
Google+

Je mehr ich weiß, desto mehr weiß ich was ich noch nicht weiß.