חוצץ מעגלי

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

 סקירה כללית 
ממוזער|400x400 פיקסלים|חוצץ מעגלי של מקלדת המכיל 24 בתים. כאשר מצביע הכתיבה מתקרב למצביע הקריאה — מכיוון שהמיקרו-מעבד אינו מגיב — החוצץ מפסיק לרשום הקשות מקלדת. במחשבים מסוימים יושמע צפצוף כדי להתריע על מצב זה.
חוצץ מעגלי מתחיל במצב ריק והקיבולת שלו קבועה. בתרשים להלן מוצג חוצץ המסוגל להכיל 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 מציג מימוש יחד עם בדיקה מינימלית. הפונקציה  מוסיפה איבר לחוצץ, והפונקציה  מחזירה איבר מהחוצץ. שתי הפונקציות מטפלות נכון בקיבולת החוצץ:

#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 

 הערות שוליים 

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