mirror of
https://github.com/hanzoai/redis.git
synced 2026-10-30 18:25:12 +00:00
1ac3bc07d6
# Redis Array For years, Redis has been missing a real indexed data structure for the use cases where the index and the spatial relationship of elements are semantic. Hashes give you random lookups, but you have to store an index as a key, and have no range visibility. Lists give you appending and trimming, but what is in the middle remains hard to access. Streams give you append-only events, which is another (useful, indeed) beast. None of these is what you want when the *position itself* has business meaning — slot 37, step 4, row 18552, day from 2934 to 2949, file line 11, 12, 15 and so forth. And, all those types, for different reasons, are all suboptimal when you want a **ring buffer** able to store the latest N observed samples of something. Up to now, users found ways (they always do \o/) using the fact that the data structures that are obvious in this universe are also extremely powerful, if well implemented. But this forces compromises. Arrays handle these index-first requirements natively, and usually with much better memory and CPU usage than the workarounds. If the use case is the right one, Arrays often provide much better space, time and usability at the same time. ## Internal encoding 1. When dense, an Array is essentially a more fancy C array. You don't pay anything for storing the index. 2. Yet, instead of going really flat, arrays are sliced into 4096-element slices, and each slice, when it contains just a few elements, uses a special sparse encoding. When a slice is empty it's just a `NULL` stored in the directory. 3. Small ints, floats, and short strings are pointer-tagged, so they cost zero additional memory beyond the pointer slot itself. 4. When very sparse, a super-directory of windowed directories is used. This allows the data type to be safe, instead of exhibiting pathological space or time behavior. This representation is only triggered when there are more than 8 million elements or very high indexes set. ## Use cases Arrays are mostly stateless if not for the fact that each array remembers the index of the latest added item, allowing `ARINSERT` and `ARRING` to work properly. Otherwise it is a set/get at this index game, with solid support for both setting / getting ranges, server-side scanning, returning only populated elements in a time which is proportional not to the range size, but to the population size. A few concrete examples, that may work as mental models for the set of problems that are similar to them (from the POV of the data modeling). **Thermometer.** A sensor reporting once per minute, with gaps: ``` ARSET temp:room12:day7 123 22.3 ARGETRANGE temp:room12:day7 600 660 # the 10:00–11:00 window, with NULLs ARSCAN temp:room12:day7 600 660 # only populated elements AROP temp:room12:day7 0 1439 MAX # peak of the day, server-side ``` Missing minutes cost little to nothing. Numeric aggregation runs inside Redis. Telemetry, IoT, meter readings, KPI rollups. **Calendar.** A clinic with 96 fifteen-minute slots per day: ``` ARSET sched:room12:day 32 booking:991 ARSCAN sched:room12:day 0 95 # only occupied slots ARGETRANGE sched:room12:day 48 63 # the afternoon full view to render ``` The slot number is the business key in this case. Room booking, parking spaces, warehouse bins, lockers, ... **Ring buffer.** ARRING replaces the classic LPUSH+LTRIM pattern. Imagine remote `dmesg`. ``` ARRING machine:123 200 "[141087.430123]: arm_cpu_init(): cpu 14 online" # Capped to 200 entries ARLASTITEMS machine:123 50 REV # 50 newest first ``` Faster than LPUSH+LTRIM, keep indexed access to past elements. Last-N alarms, recent fraud scores, access history, remote logs, device events. Ok here the use cases are mainly the ones of the old pattern: it is just a better fit and allows to access random items in the middle, aggregate server-side, and so forth. **Workflow.** Step number is the index, value is the status. Gaps are meaningful: ``` ARSET claim:99172 0 received ARSET claim:99172 3 waiting:reviewer42 ARSET claim:99172 5 approved ARGETRANGE claim:99172 0 5 # full workflow view, with NULLs for missing steps ARSCAN claim:99172 0 5 # only steps that have a state ARCOUNT claim:99172 # number of recorded steps ARLEN claim:99172 # highest reached step + 1 ``` **Skills knowledge base for agents.** Arrays are good at representing / grepping into Markdown files: ``` ARSET skill:metal_gpu 0 "...." ARSET skill:metal_gpu 1 "...." ARSET skill:metal_gpu 2 "...." ARGREP skill:metal_gpu - + RE "M3|M4" WITHVALUES ``` ARGREP has EXACT, MATCH, GLOB, RE, you can have multiple predicates, can select AND or OR behavior. **Bulk import results.** Sparse row annotations over millions of rows / CSV / ...: ``` ARSET import:job551 18552 ERR:bad_email ARSCAN import:job551 0 1000000 # Provides only rows that have something ``` ## TLDR If the position is part of the meaning, use an Array. If you want to aggregate or grep remotely, use an Array. Feedback welcome :) --------- Co-authored-by: debing.sun <[email protected]> Co-authored-by: Shubham S Taple <[email protected]> Co-authored-by: Yuan Wang <[email protected]> Co-authored-by: Marc Gravell <[email protected]>
345 lines
10 KiB
C
345 lines
10 KiB
C
/*
|
|
tre.h - TRE public API definitions
|
|
|
|
This software is released under a BSD-style license.
|
|
See the file LICENSE for details and copyright.
|
|
|
|
*/
|
|
|
|
#ifndef TRE_H
|
|
#define TRE_H 1
|
|
|
|
#ifdef USE_LOCAL_TRE_H
|
|
/* Make certain to use the header(s) from the TRE package that this
|
|
file is part of by giving the full path to the header from this directory. */
|
|
#include "../local_includes/tre-config.h"
|
|
#else
|
|
/* Use the header in the same directory as this file if there is one. */
|
|
#include "tre-config.h"
|
|
#endif
|
|
|
|
#ifdef HAVE_SYS_TYPES_H
|
|
#include <sys/types.h>
|
|
#endif /* HAVE_SYS_TYPES_H */
|
|
|
|
#ifdef HAVE_LIBUTF8_H
|
|
#include <libutf8.h>
|
|
#endif /* HAVE_LIBUTF8_H */
|
|
|
|
#ifdef TRE_USE_SYSTEM_REGEX_H
|
|
/* Include the system regex.h to make TRE ABI compatible with the
|
|
system regex. */
|
|
#include TRE_SYSTEM_REGEX_H_PATH
|
|
#define tre_regcomp regcomp
|
|
#define tre_regexec regexec
|
|
#define tre_regerror regerror
|
|
#define tre_regfree regfree
|
|
/* The GNU C regex has a number of refinements to the POSIX standard for the
|
|
formal parameter list of the regexec() function, and some of those fail to
|
|
compile when using LLVM. The refinements seem to be opt-out rather than
|
|
opt-in when using a recent gcc, and they produce a warning when TRE tries
|
|
to mimic the API without the refinements. The TRE code still works but
|
|
the warnings are distracting, so try to #define a flag to indicate when to
|
|
add the refinements to TRE's parameter list too. */
|
|
#ifdef __GNUC__
|
|
/* Try to test something that looks pretty REGEX specific and hope we don't
|
|
need a zillion different platform+compiler specific tests to deal with this. */
|
|
#ifdef _REGEX_NELTS
|
|
/* Define a TRE specific flag here so that:
|
|
1) there is only one place where code has to be changed if the test above is not adequate, and
|
|
2) the flag can be used in any other parts of the TRE source that might be affected by the
|
|
GNUC refinements.
|
|
Note that this flag is only defined when all of TRE_USE_SYSTEM_REGEX_H, __GNUC__, and _REGEX_NELTS are defined. */
|
|
#define TRE_USE_GNUC_REGEXEC_FPL 1
|
|
#endif
|
|
#endif
|
|
#endif /* TRE_USE_SYSTEM_REGEX_H */
|
|
|
|
#ifdef __cplusplus
|
|
extern "C" {
|
|
#endif
|
|
|
|
#ifdef TRE_USE_SYSTEM_REGEX_H
|
|
|
|
#ifndef REG_OK
|
|
#define REG_OK 0
|
|
#endif /* !REG_OK */
|
|
|
|
#ifndef HAVE_REG_ERRCODE_T
|
|
typedef int reg_errcode_t;
|
|
#endif /* !HAVE_REG_ERRCODE_T */
|
|
|
|
#if !defined(REG_NOSPEC) && !defined(REG_LITERAL)
|
|
#define REG_LITERAL 0x1000
|
|
#endif
|
|
|
|
/* Extra tre_regcomp() return error codes. */
|
|
#define REG_BADMAX REG_BADBR
|
|
|
|
/* Extra tre_regcomp() flags. */
|
|
#ifndef REG_BASIC
|
|
#define REG_BASIC 0
|
|
#endif /* !REG_BASIC */
|
|
#define REG_RIGHT_ASSOC (REG_LITERAL << 1)
|
|
#ifdef REG_UNGREEDY
|
|
/* We're going to use TRE code, so we need the TRE define (dodge problem in MacOS). */
|
|
#undef REG_UNGREEDY
|
|
#endif
|
|
#define REG_UNGREEDY (REG_RIGHT_ASSOC << 1)
|
|
|
|
#define REG_USEBYTES (REG_UNGREEDY << 1)
|
|
|
|
/* Extra tre_regexec() flags. */
|
|
#define REG_APPROX_MATCHER 0x1000
|
|
#ifdef REG_BACKTRACKING_MATCHER
|
|
/* We're going to use TRE code, so we need the TRE define (dodge problem in MacOS). */
|
|
#undef REG_BACKTRACKING_MATCHER
|
|
#endif
|
|
#define REG_BACKTRACKING_MATCHER (REG_APPROX_MATCHER << 1)
|
|
|
|
#else /* !TRE_USE_SYSTEM_REGEX_H */
|
|
|
|
/* If the we're not using system regex.h, we need to define the
|
|
structs and enums ourselves. */
|
|
|
|
typedef int regoff_t;
|
|
typedef struct {
|
|
size_t re_nsub; /* Number of parenthesized subexpressions. */
|
|
void *value; /* For internal use only. */
|
|
} regex_t;
|
|
|
|
typedef struct {
|
|
regoff_t rm_so;
|
|
regoff_t rm_eo;
|
|
} regmatch_t;
|
|
|
|
|
|
typedef enum {
|
|
REG_OK = 0, /* No error. */
|
|
/* POSIX tre_regcomp() return error codes. (In the order listed in the
|
|
standard.) */
|
|
REG_NOMATCH, /* No match. */
|
|
REG_BADPAT, /* Invalid regexp. */
|
|
REG_ECOLLATE, /* Unknown collating element. */
|
|
REG_ECTYPE, /* Unknown character class name. */
|
|
REG_EESCAPE, /* Trailing backslash. */
|
|
REG_ESUBREG, /* Invalid back reference. */
|
|
REG_EBRACK, /* "[]" imbalance */
|
|
REG_EPAREN, /* "\(\)" or "()" imbalance */
|
|
REG_EBRACE, /* "\{\}" or "{}" imbalance */
|
|
REG_BADBR, /* Invalid content of {} */
|
|
REG_ERANGE, /* Invalid use of range operator */
|
|
REG_ESPACE, /* Out of memory. */
|
|
REG_BADRPT, /* Invalid use of repetition operators. */
|
|
REG_BADMAX, /* Maximum repetition in {} too large */
|
|
} reg_errcode_t;
|
|
|
|
/* POSIX tre_regcomp() flags. */
|
|
#define REG_EXTENDED 1
|
|
#define REG_ICASE (REG_EXTENDED << 1)
|
|
#define REG_NEWLINE (REG_ICASE << 1)
|
|
#define REG_NOSUB (REG_NEWLINE << 1)
|
|
|
|
/* Extra tre_regcomp() flags. */
|
|
#define REG_BASIC 0
|
|
#define REG_LITERAL (REG_NOSUB << 1)
|
|
#define REG_RIGHT_ASSOC (REG_LITERAL << 1)
|
|
#define REG_UNGREEDY (REG_RIGHT_ASSOC << 1)
|
|
#define REG_USEBYTES (REG_UNGREEDY << 1)
|
|
|
|
/* POSIX tre_regexec() flags. */
|
|
#define REG_NOTBOL 1
|
|
#define REG_NOTEOL (REG_NOTBOL << 1)
|
|
|
|
/* Extra tre_regexec() flags. */
|
|
#define REG_APPROX_MATCHER (REG_NOTEOL << 1)
|
|
#define REG_BACKTRACKING_MATCHER (REG_APPROX_MATCHER << 1)
|
|
|
|
#endif /* !TRE_USE_SYSTEM_REGEX_H */
|
|
|
|
/* REG_NOSPEC and REG_LITERAL mean the same thing. */
|
|
#if defined(REG_LITERAL) && !defined(REG_NOSPEC)
|
|
#define REG_NOSPEC REG_LITERAL
|
|
#elif defined(REG_NOSPEC) && !defined(REG_LITERAL)
|
|
#define REG_LITERAL REG_NOSPEC
|
|
#endif /* defined(REG_NOSPEC) */
|
|
|
|
/* The maximum number of iterations in a bound expression. */
|
|
#undef RE_DUP_MAX
|
|
#define RE_DUP_MAX 255
|
|
|
|
/* The POSIX.2 regexp functions */
|
|
extern int
|
|
tre_regcomp(regex_t *preg, const char *regex, int cflags);
|
|
|
|
#ifdef TRE_USE_GNUC_REGEXEC_FPL
|
|
extern int
|
|
tre_regexec(const regex_t *preg, const char *string,
|
|
size_t nmatch, regmatch_t pmatch[_Restrict_arr_ _REGEX_NELTS (nmatch)],
|
|
int eflags);
|
|
#else
|
|
extern int
|
|
tre_regexec(const regex_t *preg, const char *string, size_t nmatch,
|
|
regmatch_t pmatch[], int eflags);
|
|
#endif
|
|
|
|
extern int
|
|
tre_regcompb(regex_t *preg, const char *regex, int cflags);
|
|
|
|
extern int
|
|
tre_regexecb(const regex_t *preg, const char *string, size_t nmatch,
|
|
regmatch_t pmatch[], int eflags);
|
|
|
|
extern size_t
|
|
tre_regerror(int errcode, const regex_t *preg, char *errbuf,
|
|
size_t errbuf_size);
|
|
|
|
extern void
|
|
tre_regfree(regex_t *preg);
|
|
|
|
#ifdef TRE_WCHAR
|
|
#ifdef HAVE_WCHAR_H
|
|
#include <wchar.h>
|
|
#endif /* HAVE_WCHAR_H */
|
|
|
|
/* Wide character versions (not in POSIX.2). */
|
|
extern int
|
|
tre_regwcomp(regex_t *preg, const wchar_t *regex, int cflags);
|
|
|
|
extern int
|
|
tre_regwexec(const regex_t *preg, const wchar_t *string,
|
|
size_t nmatch, regmatch_t pmatch[], int eflags);
|
|
#endif /* TRE_WCHAR */
|
|
|
|
/* Versions with a maximum length argument and therefore the capability to
|
|
handle null characters in the middle of the strings (not in POSIX.2). */
|
|
extern int
|
|
tre_regncomp(regex_t *preg, const char *regex, size_t len, int cflags);
|
|
|
|
extern int
|
|
tre_regnexec(const regex_t *preg, const char *string, size_t len,
|
|
size_t nmatch, regmatch_t pmatch[], int eflags);
|
|
|
|
/* regn*b versions take byte literally as 8-bit values */
|
|
extern int
|
|
tre_regncompb(regex_t *preg, const char *regex, size_t n, int cflags);
|
|
|
|
extern int
|
|
tre_regnexecb(const regex_t *preg, const char *str, size_t len,
|
|
size_t nmatch, regmatch_t pmatch[], int eflags);
|
|
|
|
#ifdef TRE_WCHAR
|
|
extern int
|
|
tre_regwncomp(regex_t *preg, const wchar_t *regex, size_t len, int cflags);
|
|
|
|
extern int
|
|
tre_regwnexec(const regex_t *preg, const wchar_t *string, size_t len,
|
|
size_t nmatch, regmatch_t pmatch[], int eflags);
|
|
#endif /* TRE_WCHAR */
|
|
|
|
#ifdef TRE_APPROX
|
|
|
|
/* Approximate matching parameter struct. */
|
|
typedef struct {
|
|
int cost_ins; /* Default cost of an inserted character. */
|
|
int cost_del; /* Default cost of a deleted character. */
|
|
int cost_subst; /* Default cost of a substituted character. */
|
|
int max_cost; /* Maximum allowed cost of a match. */
|
|
|
|
int max_ins; /* Maximum allowed number of inserts. */
|
|
int max_del; /* Maximum allowed number of deletes. */
|
|
int max_subst; /* Maximum allowed number of substitutes. */
|
|
int max_err; /* Maximum allowed number of errors total. */
|
|
} regaparams_t;
|
|
|
|
/* Approximate matching result struct. */
|
|
typedef struct {
|
|
size_t nmatch; /* Length of pmatch[] array. */
|
|
regmatch_t *pmatch; /* Submatch data. */
|
|
int cost; /* Cost of the match. */
|
|
int num_ins; /* Number of inserts in the match. */
|
|
int num_del; /* Number of deletes in the match. */
|
|
int num_subst; /* Number of substitutes in the match. */
|
|
} regamatch_t;
|
|
|
|
|
|
/* Approximate matching functions. */
|
|
extern int
|
|
tre_regaexec(const regex_t *preg, const char *string,
|
|
regamatch_t *match, regaparams_t params, int eflags);
|
|
|
|
extern int
|
|
tre_reganexec(const regex_t *preg, const char *string, size_t len,
|
|
regamatch_t *match, regaparams_t params, int eflags);
|
|
|
|
extern int
|
|
tre_regaexecb(const regex_t *preg, const char *string,
|
|
regamatch_t *match, regaparams_t params, int eflags);
|
|
|
|
#ifdef TRE_WCHAR
|
|
/* Wide character approximate matching. */
|
|
extern int
|
|
tre_regawexec(const regex_t *preg, const wchar_t *string,
|
|
regamatch_t *match, regaparams_t params, int eflags);
|
|
|
|
extern int
|
|
tre_regawnexec(const regex_t *preg, const wchar_t *string, size_t len,
|
|
regamatch_t *match, regaparams_t params, int eflags);
|
|
#endif /* TRE_WCHAR */
|
|
|
|
/* Sets the parameters to default values. */
|
|
extern void
|
|
tre_regaparams_default(regaparams_t *params);
|
|
#endif /* TRE_APPROX */
|
|
|
|
#ifdef TRE_WCHAR
|
|
typedef wchar_t tre_char_t;
|
|
#else /* !TRE_WCHAR */
|
|
typedef unsigned char tre_char_t;
|
|
#endif /* !TRE_WCHAR */
|
|
|
|
typedef struct {
|
|
int (*get_next_char)(tre_char_t *c, unsigned int *pos_add, void *context);
|
|
void (*rewind)(size_t pos, void *context);
|
|
int (*compare)(size_t pos1, size_t pos2, size_t len, void *context);
|
|
void *context;
|
|
} tre_str_source;
|
|
|
|
extern int
|
|
tre_reguexec(const regex_t *preg, const tre_str_source *string,
|
|
size_t nmatch, regmatch_t pmatch[], int eflags);
|
|
|
|
/* Returns the version string. The returned string is static. */
|
|
extern char *
|
|
tre_version(void);
|
|
|
|
/* Returns the value for a config parameter. The type to which `result'
|
|
must point to depends of the value of `query', see documentation for
|
|
more details. */
|
|
extern int
|
|
tre_config(int query, void *result);
|
|
|
|
enum {
|
|
TRE_CONFIG_APPROX,
|
|
TRE_CONFIG_WCHAR,
|
|
TRE_CONFIG_MULTIBYTE,
|
|
TRE_CONFIG_SYSTEM_ABI,
|
|
TRE_CONFIG_VERSION
|
|
};
|
|
|
|
/* Returns 1 if the compiled pattern has back references, 0 if not. */
|
|
extern int
|
|
tre_have_backrefs(const regex_t *preg);
|
|
|
|
/* Returns 1 if the compiled pattern uses approximate matching features,
|
|
0 if not. */
|
|
extern int
|
|
tre_have_approx(const regex_t *preg);
|
|
|
|
#ifdef __cplusplus
|
|
}
|
|
#endif
|
|
#endif /* TRE_H */
|
|
|
|
/* EOF */
|