بافر حلقه‌ای

دستورالعمل‌ها

«بافر حلقوی»، «بافر چرخه‌ای» یا «بافر حلقه‌ای» یک ساختار داده است که از یک بافر واحد با اندازه‌ی ثابت استفاده می‌کند، آن‌هم طوری که گویی دو سر آن به هم وصل شده است.

بافر حلقوی در ابتدا خالی است و طولی از پیش تعیین‌شده دارد. برای مثال، این یک بافر ۷ عنصری است:

[ ][ ][ ][ ][ ][ ][ ]

فرض کنید عدد ۱ در وسط بافر نوشته می‌شود (این‌که دقیقاً از کجا شروع شود در بافر حلقوی اهمیتی ندارد):

[ ][ ][ ][1][ ][ ][ ]

سپس فرض کنید دو عنصر دیگر، یعنی ۲ و ۳، اضافه می‌شوند و بعد از ۱ قرار می‌گیرند:

[ ][ ][ ][1][2][3][ ]

اگر بعد از آن دو عنصر از بافر حذف شوند، قدیمی‌ترین مقادیر داخل بافر حذف می‌شوند. در این حالت دو عنصر حذف‌شده ۱ و ۲ هستند و فقط ۳ در بافر می‌ماند:

[ ][ ][ ][ ][ ][3][ ]

اگر بافر ۷ عنصر داشته باشد، کاملاً پر است:

[5][6][7][8][9][3][4]

وقتی بافر پر شود، خطایی ایجاد می‌شود که به کلاینت هشدار می‌دهد نوشتن‌های بعدی تا آزاد شدن یک جایگاه مسدود است.

وقتی بافر پر است، کلاینت می‌تواند با یک نوشتن اجباری، قدیمی‌ترین داده را بازنویسی کند. در این حالت دو عنصر دیگر، یعنی A و B، اضافه می‌شوند و ۳ و ۴ را بازنویسی می‌کنند:

[5][6][7][8][9][A][B]

۳ و ۴ با A و B جایگزین شده‌اند و اکنون ۵ قدیمی‌ترین داده‌ی بافر است. در پایان، اگر دو عنصر حذف شوند، آنچه برگردانده می‌شود ۵ و ۶ است و بافر به این شکل درمی‌آید:

[ ][ ][7][8][9][A][B]

چون فضا موجود است، اگر کلاینت باز هم از بازنویسی برای ذخیره‌ی C و D استفاده کند، فضایی که قبلاً ۵ و ۶ در آن ذخیره شده بودند استفاده می‌شود، نه محل ۷ و ۸. ۷ همچنان قدیمی‌ترین عنصر است و بافر بار دیگر پر می‌شود.

[C][D][7][8][9][A][B]

---

منبع

Wikipedia