חוצץ מעגלי

ממוזער|200x200 פיקסלים|טבעת הממחישה, באופן רעיוני, חוצץ מעגלי. המחשה זו מראה שלחוצץ אין סוף אמיתי ושאפשר לעבור עליו שוב ושוב. עם זאת, מכיוון שהזיכרון אינו מוקצה פיזית בצורת טבעת, בדרך כלל משתמשים בייצוג ליניארי, כפי שיוצג להלן.
במדעי המחשב, **חוצץ מעגלי**, **תור מעגלי**, **חוצץ מחזורי** או **חוצץ טבעתי** () הוא מבנה נתונים המשתמש בחוצץ יחיד בגודל קבוע הפועל כאילו קצותיו מחוברים זה לזה. מבנה זה מתאים במיוחד לטיפול בזרמי נתונים רציפים. גרסאות מוקדמות של חוצצים מעגליים יושמו אף ישירות בחומרה.

## סקירה כללית
ממוזער|400x400 פיקסלים|חוצץ מעגלי של מקלדת המכיל 24 בתים. כאשר מצביע הכתיבה מתקרב למצביע הקריאה &#x2014; מכיוון שהמיקרו-מעבד אינו מגיב &#x2014; החוצץ מפסיק לרשום הקשות מקלדת. במחשבים מסוימים יושמע צפצוף כדי להתריע על מצב זה.
חוצץ מעגלי מתחיל במצב ריק והקיבולת שלו קבועה. בתרשים להלן מוצג חוצץ המסוגל להכיל 7 איברים:

: 250x250 פיקסלים

נניח שהערך 1 נכתב למרכז החוצץ המעגלי (מיקום ההתחלה המדויק אינו חשוב בחוצץ מעגלי):

: 250x250 פיקסלים

לאחר מכן נניח ששני איברים נוספים מתווספים לחוצץ המעגלי – 2 ו-3 – אשר ממוקמים אחרי 1:

: 250x250 פיקסלים

אם מוסרים שני איברים, שני הערכים הוותיקים ביותר בחוצץ המעגלי ימחקו. חוצצים מעגליים פועלים לפי עיקרון FIFO (נכנס ראשון, יוצא ראשון). בדוגמה זו, הערכים 1 ו-2 נכנסו ראשונים לחוצץ, ולכן הם יוסרו ראשונים, וכך יישאר הערך 3 בחוצץ.

: 250x250 פיקסלים

אם לחוצץ יש 7 איברים, אז הוא מלא לחלוטין:

: 250x250 פיקסלים

מאפיין מרכזי של חוצץ מעגלי הוא שכאשר הוא מתמלא ומתבצעת כתיבה נוספת, הנתונים הוותיקים ביותר נדרסים. בדוגמה הנוכחית מתווספים שני איברים נוספים – A ו־B – אשר מחליפים את הערכים 3 ו־4:

: 250x250 פיקסלים

לחלופין, השגרות המנהלות את החוצץ יכולות למנוע דריסה של נתונים, ובמקום זאת להחזיר שגיאה או לזרוק חריגה. ההחלטה אם נתונים יידרסו או לא תלויה בסמנטיקה של שגרות ניהול החוצץ או ביישום המשתמש בחוצץ המעגלי.

לבסוף, אם בשלב זה מוסרים שני איברים, **לא** A ו-B הם שיוסרו, אלא 5 ו-6, משום שהם כעת האיברים הוותיקים ביותר. כתוצאה מכך, החוצץ יכיל:

: 250x250 פיקסלים

## שימושים
היתרון המרכזי של חוצץ מעגלי הוא שאין צורך להזיז או לסדר מחדש את האיברים שבו כאשר אחד מהם נצרך. לעומת זאת, בחוצץ שאינו מעגלי יש להזיז את כל האיברים הנותרים לאחר הסרת איבר. לכן, חוצץ מעגלי מתאים במיוחד למימוש FIFO (נכנס ראשון, יוצא ראשון), בעוד שחוצץ רגיל שאינו מעגלי מתאים יותר להתנהגות LIFO (נכנס אחרון, יוצא ראשון).

שימוש בחוצץ מעגלי (Circular buffering) הוא אסטרטגיית מימוש יעילה לתור בעל גודל מרבי קבוע. כאשר לתור יש קיבולת מוגדרת מראש, חוצץ מעגלי הוא פתרון אידיאלי, משום שכל פעולות התור מתבצעות בזמן קבוע. עם זאת, הרחבת חוצץ מעגלי דורשת הקצאה מחדש של זיכרון והזזת נתונים, פעולה יקרה יחסית. עבור תורים שצריכים לגדול באופן דינמי ללא מגבלה קבועה, ייתכן שמימוש באמצעות רשימה מקושרת יהיה עדיף.

במצבים מסוימים, דריסה של נתונים בחוצץ מעגלי היא תכונה רצויה, למשל ביישומי מולטימדיה. כאשר החוצץ משמש כחוצץ חסום בבעיית היצרן–צרכן, ייתכן שעדיף שהיצרן (כגון מחולל שמע) ידרוס נתונים ישנים אם הצרכן (כגון כרטיס הקול) אינו מצליח לעמוד בקצב באופן זמני. בנוסף, משפחת אלגוריתמי הדחיסה הלא־מאבדת מידע LZ77 פועלת בהנחה שמחרוזות שנראו לאחרונה בזרם הנתונים צפויות להופיע שוב בקרוב. לכן, מימושים של אלגוריתמים אלה שומרים את הנתונים העדכניים ביותר בתוך חוצץ מעגלי.

## מבנה ותפקוד של חוצץ מעגלי
: ממוזער|250x250 פיקסלים| יישום חוצץ מעגלי בחומרה, פטנט אמריקאי 3979733

ניתן לממש חוצץ מעגלי באמצעות מצביע וארבעה משתנים שלמים (integers):
* כתובת תחילת החוצץ בזיכרון
* קיבולת חוצץ (האורך שלו)
* האינדקס לכתיבה לחוצץ (סוף)
* האינדקס לקריאה מהחוצץ (התחלה)

תמונה זו מציגה חוצץ מלא חלקית שאורכו הוא 7:

: 250x250 פיקסלים

תמונה זו מציגה חוצץ מעגלי מלא, שבו ארבעה איברים (מספרים 1 עד 4) נדרסו:

: 250x250 פיקסלים

בהתחלה, האינדקסים `start` ו-`end` מוגדרים ל-0. פעולת **כתיבה** בחוצץ המעגלי שומרת איבר במיקום האינדקס `end`, ולאחר מכן מגדילה את `end` למיקום הבא בחוצץ. פעולת **קריאה** מחזירה איבר ממיקום האינדקס `start` ולאחר מכן מגדילה את `start` למיקום הבא.

שימוש רק באינדקסים `start` ו-`end` אינו מספיק כדי להבחין בין מצב של חוצץ מלא לבין חוצץ ריק תוך שימוש בכל איברי החוצץ. פתרון אחד הוא להגביל את הגודל המרבי של החוצץ לשימוש של `Length - 1` בלבד. במקרה כזה, החוצץ נחשב ריק כאשר `start` שווה ל-`end`, ומלא כאשר מספר האיברים בשימוש מגיע ל־`Length - 1`. פתרון נוסף הוא להשתמש במשתנה שלם נוסף `count`, שמוגדל בעת כתיבה ומוקטן בעת קריאה. בדיקה האם החוצץ ריק מתבצעת על ידי בדיקה האם `count == 0`, ובדיקה האם החוצץ מלא מתבצעת על ידי בדיקה האם `count == Length`.

קטע הקוד הבא בשפת C מציג מימוש יחד עם בדיקה מינימלית. הפונקציה  מוסיפה איבר לחוצץ, והפונקציה  מחזירה איבר מהחוצץ. שתי הפונקציות מטפלות נכון בקיבולת החוצץ:


```c
#include <stdio.h>

enum { N = 10 };  // size of circular buffer

int buffer [N]; // note: only (N - 1) elements can be stored at a given time
int writeIndx = 0;
int readIndx  = 0;

int put (int item)
{
  if ((writeIndx + 1) % N == readIndx)
  {
     // buffer is full, avoid overflow
     return 0;
  }
  buffer[writeIndx] = item;
  writeIndx = (writeIndx + 1) % N;
  return 1;
}

int get (int * value)
{
  if (readIndx == writeIndx)
  {
     // buffer is empty
     return 0;
  }

  *value = buffer[readIndx];
  readIndx = (readIndx + 1) % N;
  return 1;
}

int main ()
{
  // test circular buffer
  int value = 1001;
  while (put (value ++));
  while (get (& value))
     printf ("read %d\n", value);
  return 0;
}
```


## אופטימיזציה
ניתן לבצע אופטימיזציה למימוש חוצץ מעגלי על ידי מיפוי  הזיכרון הבסיסי של החוצץ לשני אזורים רציפים בזיכרון הווירטואלי (אורך החוצץ חייב להיות כפולה של גודל הדף במערכת). גישה כזו מאפשרת קריאה וכתיבה בחוצץ ביעילות רבה יותר באמצעות גישה ישירה לזיכרון. כל גישה החורגת מסוף האזור הראשון בזיכרון הווירטואלי תמשיך אוטומטית מכתובת ההתחלה של החוצץ בזיכרון. כאשר הזזת הקריאה נכנסת לאזור השני בזיכרון הווירטואלי, גם הזזות הקריאה וגם הכתיבה מוקטנות באורך של הזיכרון הבסיסי של החוצץ.

## קישורים חיצוניים

* CircularBuffer במאגר התבניות של פורטלנד
* CB בליבת לינוקס
* CB ב-DSP
* תור מעגלי ב-C 

## הערות שוליים

קטגוריה:זיכרון מחשב
קטגוריה:מבני נתונים