core-attr.c

   1 /*
   2  * Copyright Neil Brown ©2015 <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 #if defined(TEST_ATTR_ADD_DEL)
  46 #define MAX_ATTR_SIZE (64 - sizeof(struct attrset))
  47 #else
  48 #define MAX_ATTR_SIZE (512 - sizeof(struct attrset))
  49 #endif
  50
  51 static struct attrset *safe newattr(struct attrset *old, int size)
  52 {
  53         struct attrset *set = realloc(old, sizeof(struct attrset) + size);
  54         set->size = size;
  55         if (old == NULL) {
  56                 set->len = 0;
  57                 set->next = NULL;
  58         }
  59         return set;
  60 }
  61
  62 /* attr_cmp just deals with bytes and ASCII digits, so it is
  63  * not aware for wchars
  64  */
  65 static int getcmptok(char **ap safe)
  66 {
  67         char *a safe;
  68         char c;
  69         int i;
  70
  71         if (!*ap)
  72                 /* FIXME smatch should handle "char * safe *ap safe" */
  73                 return 0;
  74         a = *ap;
  75         c = *a++;
  76         if (!isdigit(c)) {
  77                 *ap = a;
  78                 return c;
  79         }
  80         i = c - '0';
  81         while (isdigit(*a)) {
  82                 c = *a++;
  83                 i = i*10 + (c - '0');
  84         }
  85         *ap = a;
  86         return i+256;
  87 }
  88
  89 /* Compare 'a' and 'b' treating strings of digits as numbers.
  90  * If bnum >= 0, it is used as a leading number on 'b'.
  91  */
  92 static int attr_cmp(char *a safe, char *b safe, int bnum)
  93 {
  94         while (*a && *b) {
  95                 int ai, bi;
  96                 ai = getcmptok(&a);
  97                 if (bnum >= 0) {
  98                         bi = bnum + 256;
  99                         bnum = -1;
 100                         if (*a == ' ')
 101                                 a++;
 102                 } else
 103                         bi = getcmptok(&b);
 104                 if (ai < bi)
 105                         return -1;
 106                 if (ai > bi)
 107                         return 1;
 108         }
 109         if (*a)
 110                 return 1;
 111         if (*b)
 112                 return -1;
 113         return 0;
 114 }
 115
 116 #ifdef TEST_ATTR_CMP
 117 #include <stdlib.h>
 118 #include <stdio.h>
 119 struct {char *a, *b; int result;} test[] = {
 120         { "hello", "there", -1},
 121         { "6hello", "10world", -1},
 122         { "0005six", "5six", 0},
 123         { "ab56", "abc", 1},
 124 };
 125 int main(int argc, char *argv[])
 126 {
 127         int i;
 128         int rv = 0;
 129         for (i = 0; i < sizeof(test)/sizeof(test[0]); i++) {
 130                 if (attr_cmp(test[i].a, test[i].b, -1) == test[i].result)
 131                         printf("%s <-> %s = %d OK\n",
 132                                test[i].a, test[i].b, test[i].result);
 133                 else {
 134                         printf("%s <-> %s = %d, not %d\n",
 135                                test[i].a, test[i].b, attr_cmp(test[i].a,
 136                                                               test[i].b, -1),
 137                                test[i].result);
 138                         rv = 1;
 139                 }
 140         }
 141         exit(rv);
 142 }
 143
 144 #endif
 145
 146 static int __attr_find(struct attrset ***setpp safe, char *key safe,
 147                        int *offsetp safe, int keynum)
 148 {
 149         struct attrset **setp safe;
 150         struct attrset *set;
 151         int i;
 152
 153         if (!*setpp)
 154                 /* FIXME smatch should check this */
 155                 return -1;
 156         setp = *setpp;
 157         set = *setp;
 158         if (!set)
 159                 return -1;
 160         *offsetp = 0;
 161         while (set->next &&
 162                attr_cmp(set->next->attrs, key, keynum) <= 0) {
 163                 setp = &set->next;
 164                 set = *setp;
 165         }
 166         *setpp = setp;
 167
 168         for (i = 0; i < set->len; ) {
 169                 int cmp = attr_cmp(set->attrs + i, key, keynum);
 170                 if (cmp >= 0) {
 171                         *offsetp = i;
 172                         *setpp = setp;
 173                         return cmp;
 174                 }
 175                 i += strlen(set->attrs + i) + 1;
 176                 i += strlen(set->attrs + i) + 1;
 177         }
 178         *offsetp = i;
 179         return 1;
 180 }
 181
 182 int attr_del(struct attrset * *setp safe, char *key safe)
 183 {
 184         int offset = 0;
 185         int cmp;
 186         int len;
 187         struct attrset *set;
 188
 189         cmp = __attr_find(&setp, key, &offset, -1);
 190
 191         if (cmp)
 192                 /* Not found */
 193                 return 0;
 194         set = safe_cast *setp;
 195         len = strlen(set->attrs + offset) + 1;
 196         len += strlen(set->attrs + offset + len) + 1;
 197         memmove(set->attrs + offset,
 198                 set->attrs + offset + len,
 199                 set->len - (offset + len));
 200         set->len -= len;
 201         if (set->len == 0) {
 202                 *setp = set->next;
 203                 free(set);
 204         }
 205         return 1;
 206 }
 207
 208 char *attr_get_str(struct attrset *set, char *key safe, int keynum)
 209 {
 210         struct attrset **setp = &set;
 211         int offset = 0;
 212         int cmp = __attr_find(&setp, key, &offset, keynum);
 213
 214         if (cmp != 0 || !*setp)
 215                 return NULL;
 216         set = *setp;
 217         offset += strlen(set->attrs + offset) + 1;
 218         return set->attrs + offset;
 219 }
 220
 221 char *attr_find(struct attrset *set, char *key safe)
 222 {
 223         return attr_get_str(set, key, -1);
 224 }
 225
 226 char *attr_get_next_key(struct attrset *set, char *key safe, int keynum,
 227                         char **valp safe)
 228 {
 229         struct attrset **setp = &set;
 230         int offset = 0;
 231         int cmp = __attr_find(&setp, key, &offset, keynum);
 232         char *val;
 233
 234         if (cmp < 0)
 235                 return NULL;
 236         set = safe_cast *setp;
 237         if (cmp == 0) {
 238                 /* Skip the matching key, then value */
 239                 offset += strlen(set->attrs + offset) + 1;
 240                 offset += strlen(set->attrs + offset) + 1;
 241         }
 242         if (offset >= set->len) {
 243                 set = set->next;
 244                 offset = 0;
 245         }
 246         if (!set)
 247                 return NULL;
 248         key = set->attrs + offset;
 249         val = key + strlen(key) + 1;
 250         if (keynum >= 0) {
 251                 int kn = getcmptok(&key);
 252                 if (kn != keynum + 256)
 253                         return NULL;
 254                 if (*key == ' ')
 255                         key += 1;
 256         }
 257         *valp = val;
 258         return key;
 259 }
 260
 261 int attr_set_str_key(struct attrset **setp safe, char *key safe, char *val, int keynum)
 262 {
 263         int offset = 0;
 264         int cmp;
 265         struct attrset *set;
 266         unsigned int len;
 267         char nkey[22];
 268         int nkeylen = 0;
 269
 270         cmp = __attr_find(&setp, key, &offset, keynum);
 271
 272         if (cmp == 0) {
 273                 /* Remove old value */
 274                 set = safe_cast *setp;
 275                 len = strlen(set->attrs + offset) + 1;
 276                 len += strlen(set->attrs + offset + len) + 1;
 277                 memmove(set->attrs + offset,
 278                         set->attrs + offset + len,
 279                         set->len - (offset + len));
 280                 set->len -= len;
 281         }
 282         if (!val)
 283                 return cmp;
 284         set = *setp;
 285         if (keynum >= 0) {
 286                 snprintf(nkey, sizeof(nkey), "%d ", keynum);
 287                 nkeylen = strlen(nkey);
 288         }
 289         len = nkeylen + strlen(key) + 1 + strlen(val) + 1;
 290         if (set == NULL || set->len + len > set->size) {
 291                 /* Need to re-alloc or alloc new */
 292                 if (!set) {
 293                         set = newattr(NULL, len);
 294                         *setp = set;
 295                 } else if (set->len + len <= MAX_ATTR_SIZE) {
 296                         /* Just make this block bigger */
 297                         set = newattr(set, set->len + len);
 298                         *setp = set;
 299                 } else if (offset + len <= MAX_ATTR_SIZE) {
 300                         /* split following entries in separate block */
 301                         struct attrset *new = newattr(NULL, set->len - offset);
 302
 303                         new->next = set->next;
 304                         set->next = new;
 305                         new->len = set->len - offset;
 306                         set->len = offset;
 307                         memcpy(new->attrs, set->attrs + offset,
 308                                new->len);
 309                 } else {
 310                         /* Split follow in entries and store new entry there */
 311                         struct attrset *new = newattr(NULL, set->len - offset + len);
 312
 313                         new->next = set->next;
 314                         set->next = new;
 315                         new->len = set->len - offset;
 316                         set->len = offset;
 317                         memcpy(new->attrs, set->attrs + offset,
 318                                new->len);
 319                         set = new;
 320                         offset = 0;
 321                 }
 322         }
 323         memmove(set->attrs + offset + len, set->attrs + offset, set->len - offset);
 324         strncpy(set->attrs + offset, nkey, nkeylen);
 325         strcpy(set->attrs + offset + nkeylen, key);
 326         strcpy(set->attrs + offset + nkeylen + strlen(key) + 1, val);
 327         set->len += len;
 328         return cmp;
 329 }
 330
 331 int attr_set_str(struct attrset **setp safe, char *key safe, char *val)
 332 {
 333         return attr_set_str_key(setp, key, val, -1);
 334 }
 335
 336 #if defined(TEST_ATTR_ADD_DEL) || defined(TEST_ATTR_TRIM)
 337 void attr_dump(struct attrset *set)
 338 {
 339         printf("DUMP ATTRS:\n");
 340         while (set) {
 341                 int i;
 342                 printf(" %d of %d:\n", set->len, set->size);
 343                 for (i = 0; i < set->len; ) {
 344                         printf("  %3d: \"%s\"", i, set->attrs + i);
 345                         i += strlen(set->attrs+i) + 1;
 346                         printf(" -> \"%s\"\n", set->attrs + i);
 347                         i += strlen(set->attrs+i) + 1;
 348                 }
 349                 set = set->next;
 350         }
 351         printf("END DUMP\n");
 352 }
 353 #endif
 354
 355 #ifdef TEST_ATTR_ADD_DEL
 356 enum act { Add, Remove, Find };
 357 struct action {
 358         enum act act;
 359         char *key;
 360         char *val;
 361 } actions[] = {
 362         { Add, "Hello", "world"},
 363         { Add, "05 Foo", "Bar" },
 364         { Add, "1 Bold", "off" },
 365         { Add, "9 Underline", "on" },
 366         { Remove, "Hello", NULL },
 367         { Find, "5 Foo", "Bar" },
 368         { Add, "20 Thing", "Stuff" },
 369         { Add, "01 Bold", "on" },
 370         { Add, "1 StrikeThrough", "no" },
 371         { Add, "2 StrikeThrough", "no" },
 372         { Find, "1 StrikeThrough", "no" },
 373         { Find, "5 Foo", "Bar" },
 374         { Add, "1 Nextthing", "nonono" },
 375 };
 376
 377 int main(int argc, char *argv[])
 378 {
 379         int i;
 380         int rv = 0;
 381         struct attrset *set = NULL;
 382         for (i = 0; i < sizeof(actions)/sizeof(actions[0]); i++) {
 383                 struct action *a = &actions[i];
 384                 char *v;
 385                 switch(a->act) {
 386                 case Add:
 387                         attr_set_str(&set, a->key, a->val); continue;
 388                 case Remove:
 389                         if (attr_del(&set, a->key) == 0) {
 390                                 printf("Action %d: Remove %s: failed\n",
 391                                        i, a->key);
 392                                 rv = 1;
 393                                 break;
 394                         }
 395                         continue;
 396                 case Find:
 397                         v = attr_find(set, a->key);
 398                         if (!v || strcmp(v, a->val) != 0) {
 399                                 printf("Action %d: Find %s: Found %s\n",
 400                                        i, a->key, v);
 401                                 rv = 1;
 402                                 break;
 403                         }
 404                         continue;
 405                 }
 406                 break;
 407         }
 408         attr_dump(set);
 409         exit(rv);
 410 }
 411 #endif
 412
 413 /* Have versions that take and return numbers, '-1' for 'not found' */
 414 int attr_find_int(struct attrset *set, char *key safe)
 415 {
 416         char *val = attr_find(set, key);
 417         unsigned long rv;
 418         char *end;
 419
 420         if (!val)
 421                 return -1;
 422         rv = strtoul(val, &end, 10);
 423         if (!end || end == val || *end)
 424                 return -1;
 425         return rv;
 426 }
 427
 428 int attr_set_int(struct attrset **setp safe, char *key safe, int val)
 429 {
 430         /* 3 digits per bytes, +1 for sign and +1 for trailing nul */
 431         char sval[sizeof(int)*3+2];
 432
 433         snprintf(sval, sizeof(sval), "%d", val);
 434         return attr_set_str(setp, key, sval);
 435 }
 436
 437 #ifdef TEST_ATTR_INT
 438 int main(int argc, char *argv[])
 439 {
 440         struct attrset *set = NULL;
 441
 442         attr_set_int(&set, "One", 1);
 443         attr_set_int(&set, "Twelve", 12);
 444         attr_set_int(&set, "Four", 4);
 445         if (attr_find_int(set, "One") +
 446             attr_find_int(set, "Twelve") +
 447             attr_find_int(set, "Four")
 448             != 17) {
 449                 printf("Didn't find One, Twelve, Four\n");
 450                 exit(2);
 451         }
 452         if (attr_find_int(set, "Three") != -1) {
 453                 printf("Surprisingly found Three\n");
 454                 exit(2);
 455         }
 456         exit(0);
 457 }
 458 #endif
 459
 460 void attr_free(struct attrset **setp safe)
 461 {
 462         struct attrset *set = *setp;
 463         *setp = NULL;
 464         while (set) {
 465                 struct attrset *next = set->next;
 466                 free(set);
 467                 set = next;
 468         }
 469 }
 470
 471 /*
 472  * When attributes are attached to a section of text,
 473  * we might want to split the text and so split the attributes.
 474  * So:
 475  * 1- 'trim' all attributes beyond a given key
 476  * 2- copy attributes, subtracting some number from the offset.
 477  *     At offset '0', an empty value deletes the key.
 478  */
 479
 480 void attr_trim(struct attrset **setp safe, int nkey)
 481 {
 482         char key[22];
 483         int offset;
 484         struct attrset *set;
 485
 486         sprintf(key, "%d", nkey);
 487         __attr_find(&setp, key, &offset, 0);
 488         set = *setp;
 489         if (!set)
 490                 return;
 491         set->len = offset;
 492         if (offset)
 493                 setp = &set->next;
 494         attr_free(setp);
 495 }
 496
 497 struct attrset *attr_copy_tail(struct attrset *set, int nkey)
 498 {
 499         struct attrset *newset = NULL;
 500
 501         for (; set ; set = set->next) {
 502                 int i;
 503                 for (i = 0; i < set->len; ) {
 504                         char *k, *v;
 505                         int n;
 506                         k = set->attrs + i;
 507                         i += strlen(k) + 1;
 508                         v = set->attrs + i;
 509                         i += strlen(v) + 1;
 510                         n = atoi(k);
 511
 512                         if (n <= nkey && *v == '\0')
 513                                 v = NULL;
 514                         attr_set_str_key(&newset, k, v, nkey);
 515                 }
 516         }
 517
 518         return newset;
 519 }
 520
 521 /* Collect the attributes in effect at a given pos and return
 522  * a new set with the new alternate numeric prefix, or nothing if '-1'
 523  */
 524 struct attrset *attr_collect(struct attrset *set, unsigned int pos,
 525                              int prefix)
 526 {
 527         struct attrset *newset = NULL;
 528         char kbuf[512];
 529
 530         for (; set ; set = set->next) {
 531                 int i;
 532                 for (i = 0; i < set->len; ) {
 533                         char *k, *v, *e;
 534                         unsigned long n;
 535                         k = set->attrs + i;
 536                         i += strlen(k) + 1;
 537                         v = set->attrs + i;
 538                         i += strlen(v) + 1;
 539                         n = strtoul(k, &e, 10);
 540
 541                         if (n > pos)
 542                                 goto done;
 543                         /* FIXME shouldn't need to test 'e' */
 544                         while (e && *e == ' ')
 545                                 e++;
 546                         if (prefix >= 0) {
 547                                 snprintf(kbuf, 512, "%d %s", prefix, e);
 548                                 e = kbuf;
 549                         }
 550                         if (*v == '\0')
 551                                 v = NULL;
 552                         if (!e) e = "FIXME";
 553                         attr_set_str(&newset, e, v);
 554                 }
 555         }
 556 done:
 557         return newset;
 558 }
 559
 560 #ifdef TEST_ATTR_TRIM
 561
 562 char *keys[] = {
 563         "1 Bold", "2 Bold", "5 Bold", "10 Bold",
 564         "0 Colour", "3 Colour", "08 Colour", "12 Colour",
 565         "2 Invis", "4 Invis", "6 Invis", "9 Invis",
 566 };
 567
 568 int main(int argc, char *argv[])
 569 {
 570         int i;
 571         struct attrset *set = NULL;
 572         struct attrset *newset, *new2;
 573
 574         for (i = 0; i < sizeof(keys)/sizeof(keys[0]); i++)
 575                 attr_set_str(&set, keys[i], keys[i], -1);
 576
 577         newset = attr_copy_tail(set, 5);
 578         attr_trim(&set, 5);
 579         new2 = attr_collect(newset, 9, 4);
 580         attr_dump(set);
 581         attr_dump(newset);
 582         attr_dump(new2);
 583         exit(0);
 584 }
 585 #endif
 586
 587 /*
 588 Iterator for set.
 589 */