.\" cdb.5: cdb file format manpage
.\"
.\" This file is a part of tinycdb package.
.\" Copyright (C) 2001-2023 Michael Tokarev <mjt+cdb@corpit.ru>
.\" Tinycdb is licensed under MIT license.
.\"
.TH cdb 5 "Apr, 2005"

.SH "نام (NAME)"
cdb \- قالب فایل پایگاه‌داده ثابت (Constant DataBase)

.SH "توضیحات (DESCRIPTION)"

یک پایگاه\zwnjداده \fBcdb\fR یک تک\zwnjفایل است که برای نگاشت «کلیدها» به «مقادیر» به\zwnjکار می\zwnjرود و شامل رکوردهایی از جفت\zwnjهای (key, value) است. فایل از ۳ بخش تشکیل شده است: toc (فهرست مطالب)، داده (data) و نمایه (index یا جدول\zwnjهای درهم\zwnjسازی).

بخش Toc دارای طول ثابت ۲۰۴۸ بایت است که شامل ۲۵۶ اشاره\zwnjگر به جدول\zwnjهای درهم\zwnjسازی درون بخش\zwnjهای نمایه است. هر اشاره\zwnjگر از موقعیت یک جدول درهم\zwnjسازی به بایت از ابتدای فایل و اندازه جدول درهم\zwnjسازی بر حسب مدخل\zwnjها تشکیل شده است؛ هر دو اعداد صحیح بدون علامت ۴ بایتی (۳۲ بیتی) به فرم little-endian هستند. طول جدول درهم\zwnjسازی می\zwnjتواند صفر باشد، به این معنی که جدول درهم\zwnjسازی مربوطه خالی است.

دقیقاً پس از بخش toc، بخش داده بدون هیچ\zwnjگونه ترازسازی (alignment) قرار می\zwnjگیرد. این بخش شامل مجموعه\zwnjای از رکوردهاست که هرکدام شامل طول کلید، طول مقدار (داده)، خود کلید و خود مقدار هستند. مجدداً، طول کلید و مقدار اعداد صحیح بدون علامت ۴ بایتی هستند. هر رکورد بعدی بدون ترازسازی خاصی به دنبال رکورد قبلی می\zwnjآید.

پس از بخش داده، بخش نمایه (جدول\zwnjهای درهم\zwnjسازی) می\zwnjآید. این بخش باید همراه با بخش toc بررسی شود، جایی که هر یک از حداکثر ۲۵۶ جدول درهم\zwnjسازی تعریف شده\zwnjاند. بخش نمایه شامل مجموعه\zwnjای از جدول\zwnjهای درهم\zwnjسازی است که موقعیت شروع و طول آن\zwnjها در بخش toc مشخص شده است. هر جدول درهم\zwnjسازی دنباله\zwnjای از رکوردهاست که هرکدام دو عدد را نگه می\zwnjدارند: مقدار درهم\zwnjسازی (hash value) کلید و موقعیت رکورد در بخش داده (بایت\zwnjها از ابتدای فایل تا اولین بایت از طول کلید که رکورد داده را آغاز می\zwnjکند). اگر موقعیت رکورد صفر باشد، این یک خانه خالی در جدول درهم\zwnjسازی است که به جایی اشاره نمی\zwnjکند.

تابع درهم\zwnjسازی CDB عبارت است از:
.nf
  hv = ((hv << 5) + hv) ^ \fIc\fR
.fi
برای تک\zwnjتک بایت\zwnjهای \fIc\fR کلید، با شروع از
hv = \fI5381\fR.

بخش Toc بر اساس (hv % 256) نمایه\zwnjگذاری می\zwnjشود، یعنی مقدار هش به پیمانه ۲۵۶ (تعداد مدخل\zwnjها در بخش toc).

برای یافتن یک رکورد، باید: نخست، مقدار درهم\zwnjسازی (hv) کلید را محاسبه کنید. دوم، به شماره جدول درهم\zwnjسازی یعنی hv به پیمانه ۲۵۶ نگاه کنید. اگر خالی باشد، چنین کلیدی وجود ندارد. اگر خالی نباشد، سوم، در میان خانه\zwnjهای درون آن جدول درهم\zwnjسازی حلقه بزنید، با شروع از خانه شماره hv تقسیم بر ۲۵۶ به پیمانه طول آن جدول، یا ((hv / 256) % htlen)، و این hv را در جدول درهم\zwnjسازی جستجو کنید. جستجو را با رسیدن به خانه خالی (اگر موقعیت رکورد صفر باشد) یا زمانی که همه خانه\zwnjها پیمایش شدند متوقف کنید (به جستجوی چرخشی توجه کنید که از انتهای جدول به ابتدای آن می\zwnjپرد). هنگامی که مقدار درهم\zwnjسازی مورد نظر در جدول درهم\zwnjسازی یافت شد، به کلید رکورد مربوطه نگاه کرده و آن را با کلید مورد نظر مقایسه کنید. اگر هم\zwnjطول و با یکدیگر برابر باشند، رکورد پیدا شده است؛ در غیر این صورت، این کار را با خانه بعدی جدول درهم\zwnjسازی تکرار کنید. توجه داشته باشید که ممکن است چندین رکورد با یک کلید یکسان وجود داشته باشد.

.SH "همچنین ببینید (SEE ALSO)"
cdb(1), cdb(3).

.SH "نویسنده (AUTHOR)"
بسته \fBtinycdb\fR توسط Michael Tokarev <mjt+cdb@corpit.ru> بر پایه ایده\zwnjها و قالب فایل مشترک با کتابخانه اصلی cdb اثر Dan Bernstein نوشته شده است.

.SH "مجوز (LICENSE)"
نرم\zwnjافزار Tinycdb تحت مجوز MIT منتشر شده است.