core-attr.c

   1 /*
   2  * Copyright Neil Brown ©2015-2021 <neil@brown.name>
   3  * May be distributed under terms of GPLv2 - see file:COPYING
   4  *
   5  * Attributes.
   6  *
   7  * Attributes are attached to text in buffers and to marks and probably
   8  * other things.
   9  * They are simply name=value pairs, stored as strings though direct
  10  * conversion to numbers and Bools is provided.
  11  * Values must be "small".  The name and value together must be less than
  12  * 512 bytes, and there is probably some padding in there.  If you get
  13  * even close to this limit you are doing something wrong.
  14  * Larger strings need to be stored elsewhere with some sort of indirect.
  15  * (Hmmm.. this excludes file names - is that a good idea?)
  16  *
  17  * Attributes are stored in a list sorted by attribute name.  Strings
  18  * of digits in the name sort like the number they represent, so "6hello"
  19  * comes before "10world".  When such a number compares against a single
  20  * non-digit character the char comes first.
  21  *
  22  * Attributes for text are stored in one list for a section of text.
  23  * Each attribute is prefixed by the offset where the attribute applies.
  24  *
  25  * The offsets are really byte offsets - the text is utf-8.
  26  *
  27  * When attributes are stored on non-text objects they don't have
  28  * a number prefix.
  29  *
  30  */
  31
  32 #include <stdlib.h>
  33 #include <malloc.h>
  34 #include <string.h>
  35 #include <ctype.h>
  36 #include "core.h"
  37
  38 struct attrset {
  39         unsigned short  size, /* space allocated */
  40                         len;  /* space used */
  41         struct attrset *next;
  42         char            attrs[0];
  43 };
  44
  45 /* NOTE: this MAX is the largest sized allocation which
  46  * can be shared by multiple attrs.  The size is the sum
  47  * of keys and values including nul terminator.
  48  * If an attr is larger, it gets an attrset all of its own.
  49  */
  50 #if defined(TEST_ATTR_ADD_DEL)
  51 #define MAX_ATTR_SIZE (64 - sizeof(struct attrset))
  52 #else
  53 #define MAX_ATTR_SIZE (512 - sizeof(struct attrset))
  54 #endif
  55
  56 static struct attrset *safe newattr(struct attrset *old, int size)
  57 {
  58         struct attrset *set = realloc(old, sizeof(struct attrset) + size);
  59         set->size = size;
  60         if (old == NULL) {
  61                 set->len = 0;
  62                 set->next = NULL;
  63         }
  64         return set;
  65 }
  66
  67 /* attr_cmp just deals with bytes and ASCII digits, so it is
  68  * not aware for wchars
  69  */
  70 static int getcmptok(const char **ap safe)
  71 {
  72         const char *a safe;
  73         char c;
  74         int i;
  75
  76         if (!*ap)
  77                 /* FIXME smatch should handle "char * safe *ap safe" */
  78                 return 0;
  79         a = *ap;
  80         c = *a++;
  81         if (!isdigit(c)) {
  82                 *ap = a;
  83                 return c;
  84         }
  85         i = c - '0';
  86         while (isdigit(*a)) {
  87                 c = *a++;
  88                 i = i*10 + (c - '0');
  89         }
  90         *ap = a;
  91         return i+256;
  92 }
  93
  94 /* Compare 'a' and 'b' treating strings of digits as numbers.
  95  * If bnum >= 0, it is used as a leading number on 'b'.
  96  */
  97 static int attr_cmp(const char *a safe, const char *b safe, int bnum)
  98 {
  99         while (*a && (*b || bnum >= 0)) {
 100                 int ai, bi;
 101                 ai = getcmptok(&a);
 102                 if (bnum >= 0) {
 103                         bi = bnum + 256;
 104                         bnum = -1;
 105                         if (*a == ' ')
 106                                 a++;
 107                 } else
 108                         bi = getcmptok(&b);
 109                 if (ai < bi)
 110                         return -1;
 111                 if (ai > bi)
 112                         return 1;
 113         }
 114         if (*a)
 115                 return 1;
 116         if (*b)
 117                 return -1;
 118         return 0;
 119 }
 120
 121 #ifdef TEST_ATTR_CMP
 122 #include <stdlib.h>
 123 #include <stdio.h>
 124 struct {const char *a, *b; int result;} test[] = {
 125         { "hello", "there", -1},
 126         { "6hello", "10world", -1},
 127         { "0005six", "5six", 0},
 128         { "ab56", "abc", 1},
 129 };
 130 int main(int argc, char *argv[])
 131 {
 132         int i;
 133         int rv = 0;
 134         for (i = 0; i < sizeof(test)/sizeof(test[0]); i++) {
 135                 if (attr_cmp(test[i].a, test[i].b, -1) == test[i].result)
 136                         printf("%s <-> %s = %d OK\n",
 137                                test[i].a, test[i].b, test[i].result);
 138                 else {
 139                         printf("%s <-> %s = %d, not %d\n",
 140                                test[i].a, test[i].b, attr_cmp(test[i].a,
 141                                                               test[i].b, -1),
 142                                test[i].result);
 143                         rv = 1;
 144                 }
 145         }
 146         exit(rv);
 147 }
 148
 149 #endif
 150
 151 static int _attr_find(struct attrset ***setpp safe, const char *key safe,
 152                        int *offsetp safe, int keynum)
 153 {
 154         struct attrset **setp safe;
 155         struct attrset *set;
 156         int i;
 157
 158         if (!*setpp)
 159                 /* FIXME smatch should check this */
 160                 return -1;
 161         setp = *setpp;
 162         set = *setp;
 163         if (!set)
 164                 return -1;
 165         *offsetp = 0;
 166         while (set->next &&
 167                attr_cmp(set->next->attrs, key, keynum) <= 0) {
 168                 setp = &set->next;
 169                 set = *setp;
 170         }
 171         *setpp = setp;
 172
 173         for (i = 0; i < set->len; ) {
 174                 int cmp = attr_cmp(set->attrs + i, key, keynum);
 175                 if (cmp >= 0) {
 176                         *offsetp = i;
 177                         *setpp = setp;
 178                         return cmp;
 179                 }
 180                 i += strlen(set->attrs + i) + 1;
 181                 i += strlen(set->attrs + i) + 1;
 182         }
 183         *offsetp = i;
 184         return 1;
 185 }
 186
 187 static void do_del(struct attrset * *setp safe, int offset)
 188 {
 189         int len;
 190         struct attrset *set;
 191
 192         set = safe_cast *setp;
 193         len = strlen(set->attrs + offset) + 1;
 194         len += strlen(set->attrs + offset + len) + 1;
 195         memmove(set->attrs + offset,
 196                 set->attrs + offset + len,
 197                 set->len - (offset + len));
 198         set->len -= len;
 199         if (set->len == 0) {
 200                 *setp = set->next;
 201                 free(set);
 202         }
 203 }
 204
 205 bool attr_del(struct attrset * *setp safe, const char *key safe)
 206 {
 207         int offset = 0;
 208         int cmp;
 209
 210         cmp = _attr_find(&setp, key, &offset, -1);
 211
 212         if (cmp)
 213                 /* Not found */
 214                 return False;
 215         do_del(setp, offset);
 216         return True;
 217 }
 218
 219 void attr_del_all(struct attrset * *setp safe, const char *key safe,
 220                   int low, int high)
 221 {
 222         int offset = 0;
 223         /* Delete all attrs 'key' with keynum from 'low' to 'high' */
 224         while (low <= high) {
 225                 struct attrset *set;
 226                 int n;
 227                 int cmp = _attr_find(&setp, key, &offset, low);
 228
 229                 if (cmp < 0)
 230                         /* Nothing more to find */
 231                         return;
 232                 low += 1;
 233                 if (cmp == 0) {
 234                         /* Found, better delete */
 235                         do_del(setp, offset);
 236                         continue;
 237                 }
 238                 /* found something higher, possibly update 'low'
 239                  * to skip over gaps.
 240                  */
 241                 set = *setp;
 242                 if (!set || offset >= set->len)
 243                         continue;
 244                 n = atoi(set->attrs + offset);
 245                 if (n > low)
 246                         low = n;
 247         }
 248 }
 249
 250 char *attr_get_str(struct attrset *set, const char *key safe, int keynum)
 251 {
 252         struct attrset **setp = &set;
 253         int offset = 0;
 254         int cmp = _attr_find(&setp, key, &offset, keynum);
 255
 256         if (cmp != 0 || !*setp)
 257                 return NULL;
 258         set = *setp;
 259         offset += strlen(set->attrs + offset) + 1;
 260         return set->attrs + offset;
 261 }
 262
 263 char *attr_find(struct attrset *set, const char *key safe)
 264 {
 265         return attr_get_str(set, key, -1);
 266 }
 267
 268 const char *attr_get_next_key(struct attrset *set, const char *key safe,
 269                               int keynum, const char **valp safe)
 270 {
 271         struct attrset **setp = &set;
 272         int offset = 0;
 273         int cmp = _attr_find(&setp, key, &offset, keynum);
 274         const char *val;
 275
 276         if (cmp < 0)
 277                 return NULL;
 278         set = safe_cast *setp;
 279         if (cmp == 0) {
 280                 /* Skip the matching key, then value */
 281                 offset += strlen(set->attrs + offset) + 1;
 282                 offset += strlen(set->attrs + offset) + 1;
 283         }
 284         if (offset >= set->len) {
 285                 set = set->next;
 286                 offset = 0;
 287         }
 288         if (!set)
 289                 return NULL;
 290         key = set->attrs + offset;
 291         val = key + strlen(key) + 1;
 292         if (keynum >= 0) {
 293                 int kn = getcmptok(&key);
 294                 if (kn != keynum + 256)
 295                         return NULL;
 296                 if (*key == ' ')
 297                         key += 1;
 298         }
 299         *valp = val;
 300         return key;
 301 }
 302
 303 int attr_set_str_key(struct attrset **setp safe,
 304                      const char *key safe, const char *val,
 305                      int keynum)
 306 {
 307         int offset = 0;
 308         int cmp;
 309         struct attrset *set;
 310         unsigned int len, keylen, vallen;
 311         char nkey[22];
 312         int nkeylen = 0;
 313
 314         cmp = _attr_find(&setp, key, &offset, keynum);
 315
 316         if (cmp == 0)
 317                 /* Remove old value */
 318                 do_del(setp, offset);
 319
 320         if (!val)
 321                 return cmp;
 322
 323         set = *setp;
 324         if (keynum >= 0) {
 325                 snprintf(nkey, sizeof(nkey), "%d ", keynum);
 326                 nkeylen = strlen(nkey);
 327         } else
 328                 nkey[0] = 0;
 329         keylen = strlen(key);
 330         vallen = strlen(val);
 331         len = nkeylen + keylen + 1 + vallen + 1;
 332         while (set == NULL || set->len + len > set->size) {
 333                 /* Need to re-alloc or alloc new */
 334                 if (!set || (offset == 0 && len + set->len > MAX_ATTR_SIZE)) {
 335                         /* Create a new set - which may exceed MAX_ATTR_SIZE */
 336                         struct attrset *new = newattr(NULL, len);
 337                         new->next = set;
 338                         *setp = new;
 339                         set = new;
 340                 } else if (set->len + len <= MAX_ATTR_SIZE) {
 341                         /* Just make this block bigger */
 342                         set = newattr(set, set->len + len);
 343                         *setp = set;
 344                 } else if (offset + len <= MAX_ATTR_SIZE) {
 345                         /* split following entries in separate block */
 346                         struct attrset *new = newattr(NULL, set->len - offset);
 347                         new->next = set->next;
 348                         set->next = new;
 349                         new->len = set->len - offset;
 350                         set->len = offset;
 351                         memcpy(new->attrs, set->attrs + offset,
 352                                new->len);
 353                 } else if (offset == set->len) {
 354                         /* Need to add after here */
 355                         setp = &set->next;
 356                         set = *setp;
 357                         offset = 0;
 358                 } else {
 359                         /* offset must be > 0.
 360                          * Split off following entries and try again there.
 361                          */
 362                         struct attrset *new = newattr(NULL,
 363                                                       set->len - offset);
 364
 365                         new->next = set->next;
 366                         set->next = new;
 367                         new->len = set->len - offset;
 368                         set->len = offset;
 369                         memcpy(new->attrs, set->attrs + offset,
 370                                new->len);
 371                         setp = &set->next;
 372                         set = new;
 373                         offset = 0;
 374                 }
 375         }
 376         memmove(set->attrs + offset + len, set->attrs + offset,
 377                 set->len - offset);
 378         memcpy(set->attrs + offset, nkey, nkeylen);
 379         memcpy(set->attrs + offset + nkeylen, key, keylen + 1);
 380         memcpy(set->attrs + offset + nkeylen + keylen + 1, val, vallen + 1);
 381         set->len += len;
 382         return cmp;
 383 }
 384
 385 int attr_set_str(struct attrset **setp safe,
 386                  const char *key safe, const char *val)
 387 {
 388         return attr_set_str_key(setp, key, val, -1);
 389 }
 390
 391 #if defined(TEST_ATTR_ADD_DEL) || defined(TEST_ATTR_TRIM)
 392 void attr_dump(struct attrset *set)
 393 {
 394         printf("DUMP ATTRS:\n");
 395         while (set) {
 396                 int i;
 397                 printf(" %d of %d:\n", set->len, set->size);
 398                 for (i = 0; i < set->len; ) {
 399                         printf("  %3d: \"%s\"", i, set->attrs + i);
 400                         i += strlen(set->attrs+i) + 1;
 401                         printf(" -> \"%s\"\n", set->attrs + i);
 402                         i += strlen(set->attrs+i) + 1;
 403                 }
 404                 set = set->next;
 405         }
 406         printf("END DUMP\n");
 407 }
 408 #endif
 409
 410 #ifdef TEST_ATTR_ADD_DEL
 411 enum act { Add, Remove, Find };
 412 struct action {
 413         enum act act;
 414         char *key;
 415         char *val;
 416 } actions[] = {
 417         { Add, "Hello", "world"},
 418         { Add, "05 Foo", "Bar" },
 419         { Add, "1 Bold", "off" },
 420         { Add, "9 Underline", "on" },
 421         { Remove, "Hello", NULL },
 422         { Find, "5 Foo", "Bar" },
 423         { Add, "20 Thing", "Stuff" },
 424         { Add, "01 Bold", "on" },
 425         { Add, "1 StrikeThrough", "no" },
 426         { Add, "2 StrikeThrough", "no" },
 427         { Find, "1 StrikeThrough", "no" },
 428         { Find, "5 Foo", "Bar" },
 429         { Add, "1 Nextthing", "nonono" },
 430 };
 431
 432 int main(int argc, char *argv[])
 433 {
 434         int i;
 435         int rv = 0;
 436         struct attrset *set = NULL;
 437         for (i = 0; i < sizeof(actions)/sizeof(actions[0]); i++) {
 438                 struct action *a = &actions[i];
 439                 char *v;
 440                 switch(a->act) {
 441                 case Add:
 442                         attr_set_str(&set, a->key, a->val); continue;
 443                 case Remove:
 444                         if (!attr_del(&set, a->key)) {
 445                                 printf("Action %d: Remove %s: failed\n",
 446                                        i, a->key);
 447                                 rv = 1;
 448                                 break;
 449                         }
 450                         continue;
 451                 case Find:
 452                         v = attr_find(set, a->key);
 453                         if (!v || strcmp(v, a->val) != 0) {
 454                                 printf("Action %d: Find %s: Found %s\n",
 455                                        i, a->key, v);
 456                                 rv = 1;
 457                                 break;
 458                         }
 459                         continue;
 460                 }
 461                 break;
 462         }
 463         attr_dump(set);
 464         exit(rv);
 465 }
 466 #endif
 467
 468 /* Have versions that take and return numbers, '-1' for 'not found' */
 469 int attr_find_int(struct attrset *set, const char *key safe)
 470 {
 471         const char *val = attr_find(set, key);
 472         unsigned long rv;
 473         char *end;
 474
 475         if (!val)
 476                 return -1;
 477         rv = strtoul(val, &end, 10);
 478         if (!end || end == val || *end)
 479                 return -1;
 480         return rv;
 481 }
 482
 483 int attr_set_int(struct attrset **setp safe, const char *key safe, int val)
 484 {
 485         /* 3 digits per bytes, +1 for sign and +1 for trailing nul */
 486         char sval[sizeof(int)*3+2];
 487
 488         snprintf(sval, sizeof(sval), "%d", val);
 489         return attr_set_str(setp, key, sval);
 490 }
 491
 492 #ifdef TEST_ATTR_INT
 493 int main(int argc, char *argv[])
 494 {
 495         struct attrset *set = NULL;
 496
 497         attr_set_int(&set, "One", 1);
 498         attr_set_int(&set, "Twelve", 12);
 499         attr_set_int(&set, "Four", 4);
 500         if (attr_find_int(set, "One") +
 501             attr_find_int(set, "Twelve") +
 502             attr_find_int(set, "Four")
 503             != 17) {
 504                 printf("Didn't find One, Twelve, Four\n");
 505                 exit(2);
 506         }
 507         if (attr_find_int(set, "Three") != -1) {
 508                 printf("Surprisingly found Three\n");
 509                 exit(2);
 510         }
 511         exit(0);
 512 }
 513 #endif
 514
 515 void attr_free(struct attrset **setp safe)
 516 {
 517         struct attrset *set = *setp;
 518         *setp = NULL;
 519         while (set) {
 520                 struct attrset *next = set->next;
 521                 free(set);
 522                 set = next;
 523         }
 524 }
 525
 526 /*
 527  * When attributes are attached to a section of text,
 528  * we might want to split the text and so split the attributes.
 529  * So:
 530  * 1- 'trim' all attributes beyond a given key
 531  * 2- copy attributes, subtracting some number from the offset.
 532  *     At offset '0', an empty value deletes the key.
 533  */
 534
 535 void attr_trim(struct attrset **setp safe, int nkey)
 536 {
 537         int offset;
 538         struct attrset *set;
 539
 540         _attr_find(&setp, "", &offset, nkey);
 541         set = *setp;
 542         if (!set)
 543                 return;
 544         set->len = offset;
 545         if (offset)
 546                 setp = &set->next;
 547         attr_free(setp);
 548 }
 549
 550 /* make a copy of 'set', keeping only attributes from 'nkey'
 551  * onwards.
 552  */
 553 struct attrset *attr_copy_tail(struct attrset *set, int nkey)
 554 {
 555         struct attrset *newset = NULL;
 556
 557         for (; set ; set = set->next) {
 558                 int i;
 559                 for (i = 0; i < set->len; ) {
 560                         char *k, *v;
 561                         int n;
 562                         k = set->attrs + i;
 563                         i += strlen(k) + 1;
 564                         v = set->attrs + i;
 565                         i += strlen(v) + 1;
 566                         n = atoi(k);
 567                         if (n < nkey)
 568                                 continue;
 569                         while (*k && *k != ' ')
 570                                 k++;
 571                         if (*k == ' ')
 572                                 k++;
 573
 574                         attr_set_str_key(&newset, k, v, n);
 575                 }
 576         }
 577
 578         return newset;
 579 }
 580
 581 /* make a copy of 'set' */
 582 struct attrset *attr_copy(struct attrset *set)
 583 {
 584         struct attrset *newset, **ep = &newset;
 585
 586         for (; set ; set = set->next) {
 587                 struct attrset *n = newattr(NULL, set->size);
 588                 memcpy(n->attrs, set->attrs, set->len);
 589                 n->len = set->len;
 590                 *ep = n;
 591                 ep = &n->next;
 592         }
 593         *ep = NULL;
 594
 595         return newset;
 596 }
 597
 598 /* Collect the attributes in effect at a given pos and return
 599  * a new set with the new alternate numeric prefix, or nothing if '-1'
 600  */
 601 struct attrset *attr_collect(struct attrset *set, unsigned int pos,
 602                              int prefix)
 603 {
 604         struct attrset *newset = NULL;
 605         char kbuf[512];
 606
 607         for (; set ; set = set->next) {
 608                 int i;
 609                 for (i = 0; i < set->len; ) {
 610                         char *k, *v, *e;
 611                         unsigned long n;
 612                         k = set->attrs + i;
 613                         i += strlen(k) + 1;
 614                         v = set->attrs + i;
 615                         i += strlen(v) + 1;
 616                         n = strtoul(k, &e, 10);
 617
 618                         if (n > pos)
 619                                 goto done;
 620                         /* FIXME shouldn't need to test 'e' */
 621                         while (e && *e == ' ')
 622                                 e++;
 623                         if (prefix >= 0) {
 624                                 snprintf(kbuf, 512, "%d %s", prefix, e);
 625                                 e = kbuf;
 626                         }
 627                         if (*v == '\0')
 628                                 v = NULL;
 629                         if (!e) e = "FIXME";
 630                         attr_set_str(&newset, e, v);
 631                 }
 632         }
 633 done:
 634         return newset;
 635 }
 636
 637 #ifdef TEST_ATTR_TRIM
 638
 639 char *keys[] = {
 640         "1 Bold", "2 Bold", "5 Bold", "10 Bold",
 641         "0 Colour", "3 Colour", "08 Colour", "12 Colour",
 642         "2 Invis", "4 Invis", "6 Invis", "9 Invis",
 643 };
 644
 645 int main(int argc, char *argv[])
 646 {
 647         int i;
 648         struct attrset *set = NULL;
 649         struct attrset *newset, *new2;
 650
 651         for (i = 0; i < sizeof(keys)/sizeof(keys[0]); i++)
 652                 attr_set_str(&set, keys[i], keys[i], -1);
 653
 654         newset = attr_copy_tail(set, 5);
 655         attr_trim(&set, 5);
 656         new2 = attr_collect(newset, 9, 4);
 657         attr_dump(set);
 658         attr_dump(newset);
 659         attr_dump(new2);
 660         exit(0);
 661 }
 662 #endif
 663
 664 /*
 665  * Iterator for set.
 666  */